视频封面

视频元信息

  • 课程：MIT 6.001 Structure and Interpretation of Computer Programs（1986 原版）
  • 本讲主题：显式控制求值器（The Explicit-Control Evaluator）
  • 语言：中英双语字幕

内容摘要（TL;DR）

本讲是 6.001 课程的收尾高潮之一：把元循环求值器手工翻译成寄存器机器，用七个寄存器和栈实现整个 LISP。核心在于揭示 eval/apply 循环如何变成显式的顺序寄存器操作，以及尾递归（tail recursion）为何能让语法上递归的过程真正迭代运行、不增长栈空间。所谓"魔法"就此消失。

一、开场：让最后的魔法消失 [00:15]

本段开头约 15–120 秒存在大量转录噪声（疑似误识别内容），实际有效内容从"all of these languages were based on LISP"开始。

  • 课程回顾：我们之前看过元循环求值器（metacircular evaluator），发现 LISP 是建立在 LISP 之上的——这是一个"不动点方程"式的自指结构，当时看来像真正的魔法。
  • 今天的任务：让所有魔法消失。方法是把求值器写成寄存器机器（register machine）上的显式程序。
  • 理解：所谓"魔法"指的是元循环求值器用 LISP 本身实现 LISP，看似循环定义、无从落地；而寄存器机器给出了一个不依赖 LISP 的、纯硬件层面的实现基础。

寄存器机器的基本概念（回顾）

  • 机器有一个固定且有限的部分：有限状态控制器（finite state controller）+ 数据通路（data paths），用固定数量的硬件完成特定操作。
  • 为了支持递归、维持"无限"的假象，机器配有一大块内存，即栈（stack）。

  • [!IMPORTANT] 关键结论：只要把 LISP 用寄存器机器实现，一切就变得完全具体，魔法全部消失。

实现思路：翻译元循环求值器

  • 上一讲（Jerry 讲授）已学会：如何把任意 LISP 过程手工翻译成寄存器机器上运行的程序。
  • 因此实现整个 LISP 只需一步：把元循环求值器这个特定程序手工翻译成寄存器机器程序。
  • 思考：这在种类上与翻译递归 factorial 没有区别，只是"更大、细节更多"，没有概念上的新东西。

本课程 LISP 模型的演进脉络

  1. 代换模型（substitution model）：类似代数，最抽象。
  2. 环境模型（environment model）：讨论实际的帧（frames）以及它们如何链接。
  3. 元循环求值器：把环境模型变得更具体。
  4. 显式控制求值器（本讲）：最终、最显式的 LISP 模型，用顺序寄存器操作实现。

元循环求值器留下的未解之谜

  • 元循环求值器没有回答：为什么 recursive factorial 会增长空间，而语法上同样递归的 fact-iter 却不占空间？
  • 之前只用代换模型"论证"了它不需要空间，但没有说明机器究竟是如何做到这一点的。
  • 这取决于参数如何传递给过程的细节，而这恰恰是元循环求值器看不到的——因为它的参数传递方式本身就依赖于 LISP 的参数传递方式（自指）。

  • [!IMPORTANT] 本讲将把这一点变得极其显式。

二、整个 LISP 系统的全景图 [06:30]

在讲求值器之前，先看一个完整 LISP 系统的组成，明确哪些讲、哪些不讲。

组件 职责 本讲是否涉及
用户（user） 输入字符、接收结果 —
Reader（读取器） 把字符转成 LISP 结构内存中的数据 不涉及
LISP 结构内存 存放 pair、指针等数据结构 下一讲涉及
Evaluator（求值器） 核心求值逻辑 本讲主题
原始操作符（primitive operators） 如浮点单元等 与 LISP 无关，可自行实现
Printer（打印器） 把 list 结构转回字符输出 不涉及
  • Reader 的工作：把用户输入的符号、括号、A、B、1、3 等字符，转换为 LISP 结构中的 pair 和指针。
  • 到求值器运行时，世界里已经没有字符了，只有指针。
  • 现代 LISP 系统中，用户与 reader 之间还有窗口系统、顶层、鼠标等大量组件，但概念上仍是"字符进来"。
  • 求值器有一堆辅助器（helpers）：所有可能的原始操作符（如浮点单元）都放在独立的盒子里，与求值器分离。
  • 求值器得到答案后交给 printer，printer 把 list 结构转回字符传给用户。

看完求值器后，唯一剩下的谜团就是：如何在常规内存上构建 LISP 结构——这是下一讲的内容。

三、求值器的七个寄存器 [09:53]

这个求值器是"一个运行 LISP 的特定寄存器机器"，共有 7 个寄存器，是一个最小化的实现（实际可加更多寄存器提升性能）。

寄存器 全称/含义 作用
X Expression 存放待求值的表达式（指向 LISP 结构内存的指针）
N（Env） Environment 存放求值所处的环境（指向数据结构的指针）
Fun Function 应用过程时存放待应用的过程
Arg（Argl） Arguments 存放已求值参数构成的列表
Continue — 实现递归与栈纪律，记录求值完成后下一步去哪
Val Value 存放求值结果
Unev — 临时寄存器，存放表达式中尚未求值的部分

求值器的基本结构

  • 一部分处理表达式 + 环境（eval 侧）。
  • 一部分处理过程 + 参数（apply 侧）。
  • 两者之间来回跳转的就是著名的 eval/apply 循环。
  • 理解：Continue 寄存器正是上一讲学到的、用来实现递归和栈纪律的关键机制。

四、数据通路与操作 [11:50]

机器有大量针对 list 的特殊操作，以下是几个典型的数据通路示例：

  • 简单赋值：assign Val, (fetch X)——把 X 的内容赋给 Val。
  • 条件分支：branch (if X is a conditional) to EV-conditional——如果 X 中是一个条件表达式，跳转到 EV-conditional 标签。
    • 理解：这个条件测试可以有很多实现方式——特殊用途子程序、硬件类型测试某几位编码等，都位于当前抽象层次之下，不必关心。
  • 取子句：assign X, (first-clause of X)——处理条件表达式时取第一个子句，同样是一个选择器，细节不需关心。
  • 变量查找：assign Val, (lookup-variable-value of X in N)——在环境结构中搜索变量并取值。
    • 理解：这涉及环境数据结构的细节，同样在当前抽象层次之下。

关键点：尽管操作很多，但数量是固定的、有限的（大约 150 个左右），因此完全可以把它们直接做进硬件。

五、元循环求值器的结构回顾 [14:16]

以书中使用抽象语法（abstract syntax）的版本为例（与 Jerry 展示的略有不同）：

  • 核心是对表达式种类做分情况分析（case analysis）：自求值（self-evaluating）、引用（quoted）、变量等。
  • 一般情况（表达式是一个应用 application）下有两种递归：
    1. 简单递归（"红递归"/eval 自身）：eval 调用自身来求值操作符和所有操作数，就像爱丽丝沿着表达式树往下走。
    2. 困难递归（"红→绿"）：eval 调用 apply——求值一个过程应用归结为把过程应用到参数列表上。
  • apply 接收过程与参数：对于复合过程，apply 又"绿色调用红色"回到 eval，在扩展环境中求值过程体；对于原始过程，则调用 primitive-apply（不属于求值器的职责）。
  • 理解：红→绿→红→绿……这就是 eval/apply 循环，是本讲要在求值器中显式看到的东西。

六、两大部件：eval-dispatch 与 apply-dispatch 的契约 [16:40]

求值器的两大部件对应 eval 与 apply。理解它们的最好方式是看它们与外部世界的"契约"。

eval-dispatch 的契约（对应 eval）

  • 调用时假设：待求值表达式在 X 寄存器，环境在 N 寄存器，Continue 指明求值完成后机器下一步去哪。
  • 承诺：执行求值，结束时到达 Continue 指定的位置，结果在 Val 寄存器。

  • [!IMPORTANT] 警告：它不承诺其他寄存器会保留——其他所有寄存器都可能被破坏。

apply-dispatch 的契约（对应 apply）

  • 调用时假设：Arg 寄存器含已求值参数列表，Fun 含过程。
  • 本求值器采用一种纪律：apply 完成后机器下一步应去的位置，在 apply-dispatch 被调用时位于栈顶。
  • 承诺：执行应用，结果在 Val，栈被弹出（stack popped），其他所有寄存器内容可能被破坏。

七、逐步执行：从 1 到 (+ x y) [21:00]

这是本讲最详细的部分，用"字面执行单元"逐条指令地走查求值过程。

例 1：求值 1（自求值）[21:30]

  • 假设存在环境 E0，其中 x = 3、y = 4（仅为后续引用，求值 1 本身不需要）。
  • 从 eval-dispatch 开始，判断表达式是否自求值 → 是 → 跳到 EV-self-eval。
  • EV-self-eval：把 X 的内容赋给 Val，然后 fetch continue。

  • [!IMPORTANT] 踩坑点：讲者现场发现一个 bug——初始化机器时忘了把 done 放进 Continue 寄存器，导致无处可去。启动机器时必须设置 Continue。

例 2：求值变量 x [25:00]

  • 从 eval-dispatch 开始：自求值？否。变量？是 → 跳到 EV-variable。
  • EV-variable：在 X 中查找变量值赋给 Val，然后 fetch continue，到达 done。

例 3：求值 (+ x y)——展开表达式树 [25:40]

前置假设：环境中 + 绑定到原始过程 plus。

执行步骤：

  1. 从 eval-dispatch 判断：非自求值、非变量、非其他特殊形式（quote/lambda/set 等）→ 是应用 → 跳到 EV-application。
  2. EV-application：
    • assign unev, (operands of X)——把操作数存入临时寄存器 unev。
    • assign X, (operator)——把操作符存入 X（此时原表达式被破坏，但需要的部分已在 unev 中）。
  3. 为递归调用做准备（保存现场到栈）：
    • 保存 Continue（此处是 done）。
    • 保存环境 N。
    • 保存 unev（操作数）。
    • assign continue, eval-args。
    • 理解：之所以保存到栈，是因为 eval-dispatch 的契约不承诺保留任何其他寄存器。
  4. 递归调用 eval-dispatch 求值操作符 +：判断为变量 → EV-variable → Val 得到原始过程 plus → 回到 eval-args。
  5. eval-args：
    • 恢复 unev、恢复 N。
    • assign Fun, (fetch Val)——把求出的操作符存入 Fun。
    • 先保存 Fun（因为求值参数时可能发生任意事情）。
    • 初始化 Arg 为空列表，进入 ev-args-loop。
  6. 循环求值参数（一次一个，从 unev 移到 Arg）：
    • 保存 Arg。
    • assign X, (first operand of unev)。
    • 判断是否最后一个操作数：不是 → 保存 N、保存 unev，assign continue, accumulate-args，递归调用 eval-dispatch。
    • 短路演示：求值 x 得 3，存入 Val，返回 accumulate-args。
  7. accumulate-args：
    • 恢复 Fun、恢复 N、恢复 Arg。
    • assign Arg, (cons (fetch Val) Arg)——把结果 cons 到参数列表。
    • assign unev, (rest operands)。
    • 回到 ev-args-loop 处理下一个参数。
  8. 处理最后一个参数 y：
    • 保存 Arg，assign X, (first operand of unev)，判断为最后一个 → 跳到 ev-args-last。
    • 理解：求值最后一个参数后不再需要环境，这是与前面步骤的关键区别。
    • assign continue, accumulate-last-arg，递归调用 eval-dispatch，短路得 4。
  9. accumulate-last-arg：
    • 恢复 Arg，assign Arg, (cons (fetch Val) Arg)。
    • 恢复 Fun（本例中未被破坏，但一般情况下会）。
    • 准备进入 apply-dispatch。
  10. apply-dispatch：判断是原始过程还是复合过程 → 是原始过程 → 跳到 primitive-apply。
  11. primitive-apply：assign Val, (apply-primitive-procedure Fun to Arg)。
    • 讲者请"原始操作符"帮忙算出 3 + 4 = 7。
    • 恢复 Continue，fetch continue，到达 done。

本例的三个重要观察

观察 1：求值器需要递归，是因为求值过程本身是递归的，而不是因为被求值的过程是递归的。

  • 很多人误以为求值器需要栈和递归，是因为可能要求值 factorial、fibonacci 这类递归过程——这是错的。
  • 本例只求值了 (+ x y)，就用了栈和递归。
  • > [!IMPORTANT] 不要把它和"递归数据结构/递归 list 操作"混淆——那完全是另一回事。这里递归仅仅因为表达式包含子表达式。

观察 2：真正"做完"意味着栈上没有任何累积的东西，机器回到初始状态，只是 Val 里有值。

  • "归约（reduce）"的精确含义：表达式 (+ x y) 归约为值 7，栈上什么都没剩，它不再是任何子问题的一部分，没有东西需要返回。

关于参数顺序反转的问答 [45:00]

  • 问题：为什么参数列表的顺序被反转了（得到 4, 3 而非 3, 4）？
  • 回答：这只是约定（convention）问题——因为我们从 unev 取参数并 cons 到 Arg 上，自然形成反转。
  • 理解：类比牛顿光学——透过晶状体看到的像是倒立的，但人并不会觉得世界颠倒，因为这只是约定。
  • 需要留意反转约定的两处：
    1. apply-primitive-operator 必须知道原始过程的参数是反序传入的。
    2. 后面绑定过程参数时，参数会以与变量相反的顺序传入。

  • [!IMPORTANT] 只要记住这两处约定，就没有问题；它完全是任意的（若改成用向量迭代赋值，顺序可能相反）。

八、走通 eval/apply 循环：复合过程 [47:30]

前面只看了原始过程，现在看复合过程——求值一个过程归结为应用一个过程，再归结为求值该过程体，即真正走通 eval/apply 循环。

场景设定

  • 定义 (define (f a b) (+ a b))。
  • 执行 define 后，E0 中 f 绑定到一个过程：参数为 a、b，体为 (+ a b)。
  • 求值 (f x y)（E0 中 x = 3、y = 4）。

执行过程

  • 前面求值操作符和参数的过程与 (+ x y) 完全相同。
  • 唯一区别：到 apply-dispatch 时，Fun 中不是原始过程 plus，而是复合过程（指向参数为 a、b、体为 (+ a b) 的过程数据结构）。
  • apply-dispatch 判断为复合过程 → 跳到 compound-apply。

compound-apply 做什么（回顾元循环求值器）

  • 在新环境中求值过程体。
  • 新环境 = 取过程打包的环境，把过程参数绑定到传入的参数，作为新帧扩展过程环境。

compound-apply 的寄存器操作

  1. assign X, (procedure body from Fun)——把过程体存入 X。
  2. assign N, (make-bindings ...)——构造新环境 E1。
    • 理解：make-bindings 利用过程自带的环境（每个过程构建时都附带定义环境）、参数列表 Arg（注意反转约定），构造出 E1：a = 3、b = 4，链接到 E0。
  3. restore continue——恢复 Continue（apply-dispatch 契约假设下一步位置在栈顶，此处即最初的 done）。
  4. 回到 eval-dispatch，在 E1 中求值 (+ a b)。

关键观察：归约（reduction）的真实含义。

  • 此时已把"在 E0 中求值 (f x y)"归约为"在 E1 中求值 (+ a b)"，栈上什么都没有。
  • 机器状态中不再含有"正在求值某个叫 f 的过程"这一事实——没有累积状态。
  • 这正是代换模型中"此表达式归约为彼表达式、无需记住任何东西"的精确机器含义。

九、尾递归与迭代过程：fact-iter 为何不占空间 [52:30]

迭代 factorial 的归约链

  • (fact-iter 5) → 在某环境 E1 中归约为 (iter 1 1 n)，栈上无累积。
  • 机器不记得"求值 iter 是 iterative-factorial 的一部分"，只是把表达式归约为另一个。
  • iter 的体求值谓词 → 假 → 归约为 (iter (* counter product) (+ counter 1))，在环境 E2 中（含 product、counter 新绑定）。
  • 再次调用 iter → 归约为类似表达式，在环境 E3 中，如此往复。

  • [!IMPORTANT] 每次都是真正的归约：栈上无累积。这就是"语法上递归、实际迭代、常量空间运行"的机制。

关于环境帧的追问

  • 问题：那么环境帧本身会不会累积？
  • 回答：确实要创建新环境帧，但用完不必保留，可以被垃圾回收或自动重用。
  • 但关键在于：求值器的控制结构真正利用了"归约"这一概念，所以这些过程是真正的迭代过程。

十、对比：递归 factorial 的空间增长 [57:30]

代换模型下的链式增长

  • (fact 5) → 5 * (fact 4) → 5 * 4 * (fact 3) → …… 链式累积。

机器中链式增长的位置

  1. 求值 (fact 5)：构造环境 E1（n = 5，链接到定义环境 E0），在其中求值过程体。
  2. 谓词判断 → 求值 alternative 分支 → 整个表达式归约为 (* n (fact (- n 1)))，在 E1 中。
  3. 这是一个应用 → 第一步就把 Continue 存入栈（栈上出现 done）。
  4. 求值操作符：把操作符放入 X，环境放入 N，Continue 设为求值参数的位置；栈上保存：原 Continue、环境、未求值参数。
  5. 返回时操作符（原始乘法）进入 Fun，求值第一个参数得 5 存入 Arg。
  6. 求值第二个参数 (fact (- n 1)) → 最终归约为又一次对 fact 的调用。

  7. [!IMPORTANT] 此时栈上累积了：操作符（乘法）、另一个参数（5）、以及"回来后要 accumulate-last-arg"的标记——这就是代换模型中那串链在机器中的真实对应物。

  8. 每次递归调用都新建环境（n = 4、3、2……），栈上不断堆叠，直到第四次调用后开始返回。

结论：代换模型并非谎言——那串 5 * 4 * 3 * ... 的链，实实在在地坐在栈上。

十一、求值器为何"聪明"：它其实很笨 [1:04:00]

核心原理

  • 求值器之所以能对某些过程迭代执行、对另一些递归执行，根本原因是它只保存真正需要的东西。
  • 例 1：当"求值表达式"归约为"应用过程"时，不再需要原环境，因为任何环境信息都打包在过程中。
  • 例 2：遍历参数列表时，求值完最后一个参数后，不再需要参数列表和环境。
  • 思考：所以它不是在"聪明地分析"过程，而是"笨"地只保存必需项。

决定尾递归的那一行代码

restore continue 就是使求值器尾递归的关键行。

  • 在 compound-apply 中，求值过程体时告诉机器：完成后回到原求值本应返回的地方。
  • 如果为了某种奇怪原因想构造非尾递归求值器：只需在此处不 restore continue，而是设一个标签 where-to-come-back，设 Continue 为该标签，去 eval-dispatch，返回后再 restore 原来的 continue。
  • 后果：答案完全相同，但所有迭代过程（如 fact-iter）都会变成递归执行、堆积栈。

处理表达式序列的真实求值器

  • 前面展示的是简化版（假设过程体只有一个表达式），真实过程中体是表达式序列。
  • 差异：compound-apply 不直接去 eval，而是把整个体交给 eval-sequence。
  • eval-sequence 是一个小循环：逐个求值，返回后继续下一个；求值最后一个表达式时直接 restore continue 后去 eval-dispatch。
  • 若想破坏尾递归：不要特殊处理最后一个表达式，求值完后回到某处再 restore continue。
  • 理解：历史上很多 LISP 求值器就是这么写的，唯一后果是迭代过程会堆积栈，原因不明。

十二、总结 [1:08:30]

  1. 把元循环求值器翻译成 LISP 寄存机器，就得到了整个 LISP——概念上与翻译任何其他程序没有区别。
  2. 魔法消失了：整个系统原则上都非常清晰，唯一剩下的谜团是如何构建 LISP 结构内存（下一讲，且不难）。
  3. 尾递归来自"只保存下一步所需"的纪律，而不是"调用子程序就保存所有寄存器再返回"的粗暴做法。

  4. [!IMPORTANT] 有时关注效率是值得的：在求值器机器内部，这类细节会产生巨大后果。

实物展示：掌心里的 LISP 求值器

  • 讲者展示了一枚芯片（比演示的求值器复杂得多），结构相同：寄存器阵列、数据通路、有限状态控制器、外部内存。
  • 该芯片为让 LISP 跑得快，含大量并行操作（如索引数组时同时检查索引是整数、不越界、访存等，全部通过后再取值）。
  • 微码规模：约 389 条指令、220 位微码，整个芯片约 89,000 个晶体管。

  • [!IMPORTANT] 讲者希望借此让你真正相信："一个 LISP 求值器具体到可以放在掌心里。"

十三、关键问答 [1:10:30]

Q1：把 restore continue 放对位置，是否就让本会递归的过程变成迭代？

  • 更准确的说法：把 restore continue 放错位置，能让任何语法上看似递归的过程实际堆积栈。
  • 但没有理由这么做——只需改动 compound-apply 返回方式的两三条指令，就能得到非尾递归求值器。

  • [!IMPORTANT] 没有魔法：不存在某个聪明的预处理程序分析 fact-iter 后决定"不必压栈"。机制笨得多——就是那一处 restore 指令的位置，是自动的。

Q2：尾递归会影响时间复杂度吗？

  • 不会。尾递归不改变任何东西的时间复杂度，因为本质上还是同一个算法。
  • 它做的是让过程作为真正的迭代运行——不会因为计数到巨大数字而耗尽内存（栈被压爆）。
  • 理解：我们写的 (define (loop) (loop)) 这类"无限循环"，与 forever-loop 的差别只是语法糖；有了尾递归，它们才是真正诚实的迭代。

关键标签 / 关键词

显式控制求值器、寄存器机器、元循环求值器、eval/apply 循环、尾递归、尾调用、栈纪律、Continue 寄存器、eval-dispatch、apply-dispatch、compound-apply、eval-sequence、归约、代换模型、环境模型、七寄存器机器、有限状态控制器、数据通路、LISP 结构内存、Reader/Printer、SICP、MIT 6.001

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