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

1. 背景

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

现代程序设计语言通常都会提供交互式的模式，方便日常使用，包非解释型的程序设计语言也提供类似的设施，例如 Scala REPL、go-eval 等——当然也包括我们的 UNIX Shell！另一个有趣的 “REPL” Jupyter Notebook，虽然不是严格意义上的 REPL，但代码和 Markdown 的融合、支持实时计算的特性也给了我们许多启发。

在这个实验里，我们试图为 C 语言实现 “交互式” 的 shell，借助编译器实现 C 语言表达式的 “实时计算”。

2. 实验描述

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

• 如果输入的一行定义了一个函数，则把函数编译并加载到进程的地址空间中；
• 如果输入是一个表达式，则把它的值输出。(在读取到表达式后立即输出结果，并 fflush(stdout) 确保结果立即可见。)

总览

crepl

描述

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

• 函数总是以 int 开头，接收若干 int 类型的参数，返回一个 int 数值，例如：

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

• 否则，如果一行不是以 int 开头，我们认为这一行是一个 C 语言的表达式，其类型为 int，例如：

1 + 2 || (fib(3) * fib(4))

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

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

当然，大家的实验只有功能性的要求：我们对大家只有最简的实验要求：你只要你为每一个函数或表达式输出一行即可 (实际中，你可以让 AI 帮助你完成这些 “额外” 的 features)，例如你可以把你的 crepl 实现成这样：

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

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

3. 正确性标准

你只要能正确解析单行的函数 (以 int 开头)，并且默认其他输入都是表达式即可。我们可能会输入不合法的 C 代码 (例如不合法的表达式)；你的程序应该给出错误提示而不应该 crash。Online Judge 不会刁难大家，但依然注意：

• 注意我们允许函数和表达式调用之前 (在 crepl 中) 定义过的函数；
• 你可以假设我们输入的命令/表达式数量不超过 100 个；
• 注意你处在的运行目录可能没有写入的权限。建议你将创建的临时文件都放在 /tmp/ 目录下。建议使用 mkstemp family API 创建临时文件；
• 主进程确实求出了所有表达式的值。

4. 实验指南

4.1 解析读入的命令

我们当然可以直接用

printf("crepl> ");
fflush(stdout);
fgets(line, sizeof(line), stdin);

读取一行——不过细心的你会发现，fgets 的行为和 Shell 里我们可以做的 “行编辑” 还有不少的差距。虽然我们还是可以用 Ctrl-U 来删除整行、Ctrl-A 来移动光标到行首，但没法像 Shell 里那样用上下键 (或者 Ctrl-P/Ctrl-N) 来浏览历史命令。这个时候，AI Copilot 就能派上用场了，我们提了一个好问题！AI 会把我们引向正确的方向。

4.2 把函数编译成共享库

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

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

我们只需要把这个文件保存到临时文件里，例如 a.c 中，然后使用正确的选项调用 gcc 即可。

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

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

你可以：

• 为过去定义过的函数生成它们的签名。这当然是 “正确” 的解决方法。
• 直接什么也不做，你的编译器可能产生一个 Warning，或者一个 Error 阻止你编译，但使用 -Wno-implicit-function-declaration 选项可以忽略这个错误。

4.3 把表达式编译成共享库

把库函数的实现编译到共享库中是 “常规操作”。通过动态链接的加载器使库函数可以被执行。但表达式怎么办？这里用的小技巧是使用代码生成另一份代码 (wrapper function)。在课程里我们会多次用到 wrapper function。每当我们收到一个表达式，例如 gcd(256, 144) 的时候，我们都可以 “人工生成” 一段 C 代码

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

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

4.4 共享库的加载

我们可以使用 dlopen 加载共享库。我们已经为大家提供了 -ldl 的链接选项，大家可以在大语言模型的帮助下阅读相关库函数的手册。另一个很不错的手册是 elf (5)。如果你把这个问题交给人工智能，人工智能能立即给你一份正确的代码！但要注意遵守 AIGC Policy：我们在学习、试错的过程中，形成了自己对问题独特的理解。因此阅读手册、调试代码也是《操作系统》课程训练很重要的一部分。