视频封面

视频元信息

  • 视频标题：【MIT本科一年级必修】6.001 计算机程序的构造与解释（SICP）1986传奇原版·全20讲·中英双语字幕 p20 19-编译
  • 课程：MIT 6.001 Structure and Interpretation of Computer Programs（1986 版）
  • 本讲主题：编译器（Compiler）——从显式控制求值器到寄存器机器代码生成

本视频转录文本存在大段语音识别失败（大量乱码与「酷」字重复），以下笔记基于可辨识的英文技术讲解部分（约占视频主体后半段）整理，乱码段落不作内容还原，避免编造。技术要点集中在：零阶编译器、寄存器优化、代码序列的 need/modify 数据结构、append 与 preserving 机制。

内容摘要（TL;DR）

本讲从上一讲的「显式控制求值器」出发，说明编译器与求值器的本质区别：求值器边分析边执行、必须极度悲观地保存寄存器；编译器把分析做一次、只生成必要的寄存器操作。课程先给出「零阶编译器」（逐条复刻求值器动作），再通过消除 X、UNEV、CONTINUE 等无关寄存器以及冗余的 save/restore，把 19 条指令压缩到 3 条。随后讲解编译器的实现骨架：用 append + preserving 组合代码序列，用「需要/修改寄存器集合」的数据结构推导保存策略，并以递归 factorial 为例展示生成代码，最后讨论内联优化与 Lisp 编译器历史。

一、回顾：显式控制求值器与编译器的分界 [00:19]

上一讲讨论了 Lisp 求值器的显式控制（explicit control），它把 Lisp、查询语言等高层语言，与传统的寄存器机器（register machine）汇编语言之间的鸿沟桥接起来。

理解：所谓「显式控制」，就是把求值器内部原本隐含的递归过程，展开成一串明确的寄存器操作与跳转——本质上就是一台「Lisp 解释器的汇编代码」。

要点：

  • 求值器的显式控制可以看作Lisp 解释器在传统寄存器/传输机汇编语言上的实现代码。
  • 编译器的行为与求值器「很像」：它也是遍历表达式，但不执行这些操作，而是把它们存起来（stash away）。
  • 关键区别：求值器是「分析 + 执行」同时进行；编译器只分析一次，把结果作为代码输出。

考点：求值器 vs 编译器的本质差异

  • 求值器：每次运行都要重新分析「这是什么表达式、该走哪个分支」，分析开销随运行次数线性增长（运行一百万次就分析一百万次）。
  • 编译器：分析只做一次，之后只剩纯粹的寄存器操作。

这就是为什么即使是最笨的零阶编译器，也已经比求值器更高效。

二、零阶编译器：逐条复刻求值器的动作 [05:00]

以表达式 (f x) 为例，追踪求值器启动后的动作：

  1. 求值器查看表达式，发现是一个应用（application），跳转到 EV-APPLICATION 位置。
  2. 保存操作数（operands）到 UNEV，把 operator 放入 X 寄存器。
  3. 递归地去求值 operator。
  4. 生成一系列寄存器赋值：assign unev (operands exp)、assign x (operator exp)、保存环境等。

把这些操作「写下来」而不是「执行掉」，就得到了约 19 条操作的代码片段，直到求值器分支到 apply-dispatch 为止。

关于 apply-dispatch 的设计决策：

  • 在本编译器中，完全不为 apply-dispatch 做特殊处理。
  • 无论是解释代码还是编译代码，调用过程（apply procedure）一律走 apply-dispatch。
  • 理解：这样做的好处是让「解释代码」与「编译代码」可以互相调用，便于混合执行与逐步替换。

零阶编译器如何处理条件分支（if / 谓词）：

易错点：编译时无法预知条件走哪一支 求值器可以在运行时根据谓词结果决定跳转；但编译器在编译期不知道结果，不能只编译一支。

处理办法（非常直接）：

  1. 编译谓词 P，保证结果放入 val 寄存器。
  2. 生成指令：branch (if val is true) to label1。
  3. 编译分支 B 的代码，末尾加 goto next。
  4. 放置 label1 标签。
  5. 编译分支 A 的代码，末尾加 goto next。

即：两支都编译，用标签与跳转指令在运行时选择。

思考：这与现代编译器生成「基本块 + 跳转」的 CFG（控制流图）思路完全一致，只是这里用最原始的方式手工拼接。

三、零阶编译器的三大浪费 [09:30]

零阶编译器虽然正确，但「很糟糕、很笨（wretched compiler）」。审视它生成的指令，可以发现三类明显冗余：

1. 表达式寄存器 X 与 UNEV 是多余的

  • 求值器：assign x (operator (fetch exp))，然后 assign val (lookup (fetch x) env)。
  • 但编译器已经知道 operator 就是符号 F，操作数就是列表 X。
  • 因此可以直接写成：assign val (lookup F env)，根本不需要 X 寄存器。

考点：X 和 UNEV 不是「目标机器」的寄存器 它们是求值器自身的数据结构寄存器，用于安排「如何构造目标机器」。从编译器视角看，它们持有的永远是常量表达式，可以直接内联进代码。

2. 大量对 CONTINUE 的赋值是无关的

  • 例如 assign continue (eval-args)，这是求值器用来记录「下一步该回哪里」的。
  • 但编译器已经把分析完成了，这些「分析流程的续点」对生成代码毫无意义，可以全部删除。

理解：CONTINUE 记录的是「求值器分析该继续到哪里」，而非「运行中的机器该继续到哪里」——这是两类完全不同的续点，容易混淆。

3. 过度的 save / restore（悲观策略）

  • 例如 save env ... restore env：因为求值器递归调用 eval-dispatch 前不知道会不会破坏环境，所以必须先存。
  • 例如 save argl ... restore argl：同理。
  • 但实际上，被调用的那段代码（如求值符号 F、查表）根本没有破坏这些寄存器。

考点：求值器必须「最大程度悲观」（maximally pessimistic） 求值器的视角是「我要跳出去求值某个东西，不知道它会干什么，所以先把以后要用的都存起来」。 编译器在分析完成后，确切知道哪些寄存器真的被破坏了，因此只需保存真正需要的。

优化效果对比：

阶段 操作数
求值器原始动作 约 19 条
去掉 X / UNEV / 无关 CONTINUE 约减半
再去掉冗余 save/restore 仅 3 条

四、栈操作图解：哪些 save/restore 真的必要 [15:00]

课程用一张图展示 (f x) 求值过程中所有 save/restore 的配对关系：横轴是求值器经过的各个位置，向下箭头表示「保存寄存器」，向上箭头表示「恢复」。

分析结论：

  • UNEV 是完全无用的寄存器，使用代码的常量结构后，根本不需要保存 UNEV。
  • CONTINUE 是否需要保存，取决于调用约定（calling discipline）的设计。
  • 求值 F 时不会破坏 env，所以不必保存 env。
  • 求值 X 时，求值器出于保守保存了 fun 寄存器和 argl，但编译器知道实际上不需要。

推导：编译器能省掉 save/restore 的两条根本理由——

  1. 被保护的对象实际上没被破坏（例如只是变量查表）；
  2. 保存它的目的后来根本不需要它了。

五、更复杂的例子：(f (g x) 1) 的优化 [19:00]

用更复杂的表达式 (f (g x) 1) 展示优化空间：

  • 求值器走完整个表达式，会产生大约 16 对寄存器 save/restore。
  • 逐条分析哪些属于「求值器的业务」、哪些属于「编译器的业务」：
    • UNEV 相关的保存：完全无用。
    • CONTINUE 被反复搬动：多数无用。
    • fun 寄存器跨第一个操作数被保存：可能不必要。
  • 进一步推理：
    • 求值 F 不破坏 env 寄存器 → 不必保护。
    • 查表符号 X 不破坏 fun 寄存器 → 不必保护。
    • 第二个参数是常量 1，查常量不需要 env 寄存器 → 这一处对 env 的保存也可以删掉。
  • 最终从「一大堆」压缩到大约 2 对 save/restore。

易错点：对 G 的保守假设 编译器对 G 一无所知（G 可能是任意代码），所以求值 G 之前必须保存 env——这一处无法消除。 思考：这正说明「编译器的优化上限取决于它对被调用过程的了解程度」。若知道 G 是纯函数/不碰 env，还能再省。

六、课堂提问：能否只用六寄存器机器？ [24:00]

学生提问：你一直说 UNEV 寄存器完全不需要用，那是否意味着可以只做一台六寄存器（six-register）机器？还是只是这些例子不需要？

回答要点：

  • 对编译器而言，完全可以只生成使用五个寄存器的代码（X 与 UNEV 都可去掉）。
  • 原因：它们是求值器的数据结构，从编译器视角看都是常量。
  • 但注意：本编译器的设计目标是让解释代码与编译代码共存。
  • 因此更准确的类比是：把求值器做成一枚芯片，编译器为这枚芯片生成代码，只是不使用其中两个寄存器。

七、编译器实现骨架：递归编译 + append + preserving [26:00]

以「一个 operator + 两个参数」的表达式为例，说明编译器应生成什么代码：

  1. 递归编译 operator，让结果最终落在 fun 寄存器。
  2. 递归编译第一个参数，结果放到某处。
  3. 生成字面指令：assign argl (cons <结果> '())，开始构造参数表。
  4. 编译第二个参数，目标为 val。
  5. 生成字面指令：assign argl (cons val argl)，把新值接到旧参数表上。
  6. 生成 apply 指令（此处走 apply-dispatch）。

关键：preserving 注释

编译器在拼接代码时，会给某些片段打上「必须在保护某寄存器的前提下完成」的标记：

  • 编译第一个参数时，需要保护 env（因为后面还要用环境）。
  • 编译第二个参数时，需要保护 argl（因为要往旧参数表上 cons）。
  • 最后那段代码，需要保护 fun（因为 operator 已在里面）。

核心对比：编译器 vs 解释器的唯一本质差别

  • 编译器有 preserving 注释：它可能生成 save/restore，也可能不生成。
  • 解释器最大程度悲观：这里永远有 save/restore。

这就是全部的本质区别。

八、append 与 preserving 的具体算法 [31:00]

编译器组合代码序列的基本手段是 append 两个代码序列，但要「在保护某寄存器的前提下」进行。

规则（伪代码）：

append sequence1 to sequence2 preserving reg:
  若 sequence2 需要 reg，且 sequence1 修改 reg：
      输出: save reg
      输出: sequence1 的编译结果
      输出: restore reg
      输出: sequence2 的编译结果
  否则：
      输出: sequence1 的编译结果
      输出: sequence2 的编译结果

理解：只有当「后一段需要」且「前一段会破坏」时，才必须插入 save/restore；否则直接顺序拼接即可。

九、代码序列的数据结构：need / modify [34:00]

为了做上述判断，编译器必须知道每个代码片段需要哪些寄存器、修改哪些寄存器。

代码序列（code sequence）的组成：

  1. 实际的指令序列（instructions）；
  2. 修改的寄存器集合（modified registers）；
  3. 需要的寄存器集合（needed registers）。

原始片段（primitive fragments）：手工标注。

  • 例：assign R1 (fetch R2)
    • modifies: {R1}
    • needs: {R2}

组合规则（sequence1 接 sequence2）：

  • 新的 modifies = M1 ∪ M2（两者修改的并集）。
  • 新的 needs = N1 ∪ (N2 − M1)
    • 即：sequence1 需要的全部，加上 sequence2 需要、但不是由 sequence1 建立起来的那些。

考点：N2 − M1 的含义 sequence1 修改过的寄存器，等于「由 sequence1 负责设置好了」，所以 sequence2 对它们的「需要」不再算作整个复合序列的对外需求。 推导：这就是最朴素的「活跃变量分析 / 寄存器分配」思想的雏形。

十、示例：递归 factorial 的编译结果 [38:00]

以递归版 factorial 为例展示编译器输出（幻灯片较小，仅快速展示代码量）：

  • 第一块：编译过程入口（procedure entry），做一系列赋值，直到设置好谓词并测试其真假。
  • 第二块：递归调用 factorial(n-1) 所产生的代码。
  • 第三块：从递归调用返回后，处理常量情形（base case）的代码。

理解：这就是「把高阶语言程序翻译成寄存器机器指令」的完整落地——三块代码对应 if 的两支加递归调用。

十一、如何让编译器更好 + 课堂问答：内联加法 [41:00]

本编译器的最大改进空间：

  • 它不对被调用过程做任何假设。
  • 例如它甚至不知道「乘法可以在线内联（in line）」，而是老老实实构造参数表、走 apply-dispatch。
  • 每次走 apply-dispatch 都要cons 参数表，开销巨大。
  • 真正的编译器会：用寄存器直接传参数，并用类似本讲的 preserving 策略来管理这些寄存器。

其他可优化方向：

  • 变量查表（variable lookup）的优化；
  • 更高效的原始操作（primitive operations）；
  • 思考：好的 Lisp 编译器可以「吸收任意多的优化努力」——这是一个开放式的工程。

关于 Lisp 比 Fortran 慢的历史原因：

从历史看，投入 Lisp 编译器的工程努力，远远不及投入 Fortran 编译器的努力。这或许正是 Lisp 相对较慢的原因之一，也许未来几年会改变。

课堂提问：为什么加法有 %plus 这样的原语？

  • 一般化的 plus 接受任意多个参数，因此必须把参数 cons 成表、再数个数，效率极差。
  • 而绝大多数情况只是两个数相加。
  • 所以实现上会为 plus 提供多个入口：大部分逻辑相同，但有一个特殊入口，当已知只有两个参数时直接使用，参数放在寄存器里、不 cons 参数表。
  • 理解：这就是「多入口 + 特化快速路径」的经典优化手法，现代 JIT 与运行时库中依然常见。

关键标签 / 关键词

SICP 6.001 编译器 compiler 求值器 evaluator 显式控制 explicit control 寄存器机器 register machine 零阶编译器 zero-order compiler 寄存器优化 save/restore preserving need/modify 代码序列 append apply-dispatch 内联优化 Lisp Scheme factorial 参数表 argl env val fun unev continue

生成时间：2026-10-11 14:46:58 生成平台：VideoNote www.xygy.top