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

Soft Deadline: 2025 年 4 月 27 日 23:59:59

请注意遵守实验须知中的 AIGC Policy;在命令行中 git pull origin M4 下载框架代码。

⚖️M4 - crepl

请输入 Token 登录。

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 创建临时文件;
  • 主进程确实求出了所有表达式的值。
⚠️禁止使用 system() 和 popen()

调用它们将会导致编译错误。好消息是这个实验我们不禁止 exec family 的系统调用:execl, execlp, execle, execv, execvp, execvpe 都是允许的。虽然在 AI 时代,这些功能的实现都非常容易,但我们仍然希望你能对使用系统调用编程有切身的体会。

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 会把我们引向正确的方向。

💬
Prompt: C 语言里如何实现这个功能?

4.2 把函数编译成共享库

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

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

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

⚠️选取合适的路径和文件名

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

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

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 的地址,直接进行函数调用就能得到表达式的值了。

💬
Prompt: Wrapper function 和函数式编程是否有关系?

4.4 共享库的加载

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