M4: C Real-Eval-Print-Loop (crepl)

⏰ 截止日期

Soft Deadline: 2022 年 5 月 8 日 23:59:59。

你需要首先阅读实验须知。

在命令行中 git pull origin M4 下载框架代码。

⚠️ 特别注意

在本实验中，我们要求你实现 REPL，即主进程能获得所有表达式的值，因此请保证你在主进程打印表达式的值 (防止你把所有表达式拼接起来成一个程序打印)。

OS2022-M4 提交结果

1. 背景

大家一定很熟悉编程语言提供的交互式 read-eval-print-loop (REPL)，更俗一点的名字就是 “交互式的shell”。例如我们在课堂上展示的 Python Shell，可以快速帮助大家解决高等数学作业、高精度计算等烦恼：

现代程序设计语言通常都会提供交互式的模式，方便日常使用，包非解释型的程序设计语言也提供类似的设施，例如 Scala REPL、go-eval 等——当然也包括我们的 UNIX Shell！

在学习过动态链接和加载之后，你会预期 C 同样也可以实现 “交互式” 的 shell，支持即时定义函数，而且能计算 C 表达式的数值。如果你输入一行代码，比如strlen("Hello World")，这段代码会经历 gcc 编译、动态加载、调用执行，最终把代码执行得到的数值 11 打印到屏幕上。这就是本实验的内容。

2. 实验描述

crepl - 逐行从 stdin 中输入，根据内容进行处理：

如果输入的一行定义了一个函数，则把函数编译并加载到进程的地址空间中；
如果输入是一个表达式，则把它的值输出。

总览

crepl

描述

解释执行每一行标准输入中的 C “单行” 代码 (假设我们只使用 int 类型，即所有输入的表达式都是整数；定义函数的返回值也永远是整数)，分如下两种情况：

函数总是以 int 开头，例如

int fib(int n) { if (n <= 1) return 1; return fib(n - 1) + fib(n - 2); }

函数接收若干 int 类型的参数，返回一个 int 数值。如果一行是一个函数，我们希望它将会经过 gcc 编译，并被加载到当前进程的地址空间中。函数可以引用之前定义过的函数。

如果一行不是以 int 开头，我们认为这一行是一个 C 语言的表达式，其类型为 int，例如
```
1 + 2 || (fib(3) * fib(4))
```

函数和表达式均可以调用之前定义过的函数，但不允许访问全局的状态 (变量) 或调用标准 C 中的函数。如果一行既不是合法的函数 (例如调用了不允许调用的函数)，也不是合法的表达式，crepl 可以不保证它们执行的结果 (不一定要报告错误，例如你的程序依然可以照常编译或执行，但你的程序要尽量不会 crash)；重复定义重名函数你也可以当做 undefined behavior 不必做出过多处理——我们的测试用例中没有这样的情况。

以下是我们的参考实现，它调用了一些外挂程序在终端里实现了语法高亮。你完全没有做这件事情的必要——我们的环境里没有你需要的运行库，因此会导致你无情的 Compile Error 或 Wrong Answer。如果你使用外挂，一个更好的习惯 (也是编写软件常见的做法) 是在运行时检查外挂是否存在。如果存在则调用；如果不存在则直接输出没有外挂非高亮的版本。

当然，和之前的实验一样，我们对大家只有最简的实验要求：你只要你为每一个函数或表达式输出一行即可，例如你可以把你的 crepl 实现成这样：

$ ./crepl-64
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
OK.
gcd(256, 144) * gcd(56, 84)
= 448.

这个实验表明，编译和解释并没有明确的边界——在 OpenJDK 的实现中，即便是 “解释器” 也是编译的 (只是没有经过优化)。动态 (just-in-time) 技术在程序运行时 (而非程序执行前) 进行编译，并将编译得到的二进制代码 (指令/数据) 动态加载。其中最成功的案例之一是 Sun (现在是 Oracle) 的 Java 虚拟机 HotSpot (现在是OpenJDK的一部分)，它使 Java 彻底摆脱了 “性能低下” 的诟病，也是引领 Web 热潮的核心后端技术。另一个最成功的案例是 JavaScript 的 V8 引擎。借助 Webkit/v8，Chrome 成功地把微软公司的 Internet Explorer 拖下神坛，并且奠定了 Google 在互联网技术领域的霸主地位。

3. 正确性标准

你只要能正确解析单行的函数 (以 int 开头)，并且默认其他输入都是表达式即可。我们可能会输入不合法的 C 代码 (例如不合法的表达式)；你的程序应该给出错误提示而不应该 crash。你可以做出比较友好的假设——不像之前的实验，会为了 “强迫” 你掌握某些知识而使你疯狂 Wrong Answer。这个实验纯属放松，Online Judge 没有刁难你的测试用例，都和 demo 中的差不多。

注意我们允许函数和表达式调用之前 (在 crepl 中) 定义过的函数；
你可以假设我们输入的命令/表达式数量不超过 100 个；
注意你处在的运行目录可能没有写入的权限。建议你将创建的临时文件都放在 /tmp/ 目录下。建议使用 mkstemp family API 创建临时文件；
主进程确实求出了所有表达式的值。
禁止使用 C 标准库 system 和 popen。这稍稍增加了实验的难度，不过并没有增加多少。请把这个限制理解成强迫大家掌握操作系统知识的训练。

禁止使用 system() 和 popen()

调用它们将会导致编译错误。好消息是这个实验我们不禁止 exec family 的系统调用：execl, execlp, execle, execv, execvp, execvpe 都是允许的。

4. 实验指南

4.1 解析读入的命令

框架代码里已经包含了读入命令的循环 (看起来像是一个小 shell)，它打印出一个提示符，然后接受输入并解析：

int main(int argc, char *argv[]) {
  static char line[4096];
  while (1) {
    printf("crepl> ");
    fflush(stdout);
    if (!fgets(line, sizeof(line), stdin)) {
      break;
    }
    printf("Got %zu chars.\n", strlen(line)); // WTF?
  }
}

当你在终端里按下 Ctrl-d，会结束 stdin 输入流，fgets 会得到 NULL。

这段代码里一个有趣的小细节是对 fflush 的调用：你会发现把它去掉对程序的运行并没有什么影响。但如果你在 fgets 之前插入一些延迟，例如 sleep(1)，你会发现 fgets 会 flush stdout 的缓冲区。但 C 标准并没有规定这个行为，glibc 只是因为大家用错得太多，为大家贴心地兜了——其实 System 领域这种 “事实行为” 并不少见，大家错得多了，我们的库函数、编译器等不得不做出防御性的行为容忍大家犯错。一个例子是某一时期本的 gcc 会非常激进地对能证明的 undefined behavior 进行优化，但却导致不少以前 “正确” 工作的代码的崩溃，到新版本里反而不再做这些激进的优化了。

回到实验，在上面的代码里，如果读入的字符串以 int 开头，你就可以假设是一个函数；否则就可以假设是一个表达式。

4.2 把函数编译成共享库

对于一个一行的函数，比如

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

如何把它编译成共享库？我们在课堂上讲解过编译成共享库 (shared object, so) 的代码，我们的 M2 (libco) 也实现了共享库。我们只需要把这个文件保存到临时文件里，例如 a.c 中，然后使用正确的选项调用 gcc 即可。

选取合适的路径和文件名

如果你的工具在当前目录下创建文件，有可能会失败——例如，你可能在一个没有访问权限的工作目录上 (例如文件系统的根 /)。在 /tmp 中创建临时文件是更安全的做法。此外，glibc 还为我们提供了 mkstemp family API 调用，能够帮助我们生成名称唯一的临时文件。

除了编译和命名的问题，大家可能会感到困惑是，如果我的函数调用了其他函数怎么办？

int foo() { return bar() + baz(); }

你不妨试着编译这个程序……它竟然可以被编译！所以忽略所有的 warnings 就好了！最后，为了巩固大家在上一个实验中学过的知识，我们限制你不能使用 libc 中的 system 和 popen——它们会让实验变得有些过于简单。

4.3 把表达式编译成共享库

把函数编译成共享库是常规操作——库函数主要就是为我们提供函数的。但表达式怎么办？又用到我们这门课里反复用的小技巧了：我们可以做一个 wrapper 呀！每当我们收到一个表达式，例如 gcd(256, 144) 的时候，我们都可以 “人工生成” 一段 C 代码

:::C
int __expr_wrapper_4() {
  return gcd(256, 144);
}

注意到函数名里的数字——我们通过加上数字为表达式生成不一样的名字。我们的表达式变成一个函数，我们就可以把它编译成共享库了。把动态库加载到地址空间并得到 __expr_wrapper_4 的地址，直接进行函数调用就能得到表达式的值了。

4.4 共享库的加载

我们可以使用 dlopen 加载共享库。我们已经为大家提供了 -ldl 的链接选项，大家可以阅读相关库函数的手册。另一个很不错的手册是 elf (5)。

4.5 试试自己用 mmap 加载？

参考 loader-static，你也可以自己实现 dlopen。在这个实验里，我们的假设很简单，函数只访问局部变量，不涉及任何全局符号，因此只需要加载程序的代码即可——也就是说，你只需要把代码 mmap 到地址空间中，再解析符号找到入口地址，就可以不调用库函数实现加载了！