SICP 第 17 讲：寄存器机器

视频元信息

• 课程：MIT 6.001 SICP（1986 原版）
• 主题：寄存器机器（Register Machines）
• 说明：本讲承接前文对求值器的讨论，转向如何用硬件级抽象——数据通路（data paths）与控制器（controller）——来实现程序。

本讲的核心思想：程序就是机器的描述。写下一个程序，等价于描述了一台能完成该任务的机器。这是从软件到硬件的一次关键"落地"。

一、总纲：从程序到机器 [02:01]

Abelson 教授开篇即点明本讲的方法论：他不打算走"先讲某种现成计算机的机器语言、再展示这台机器如何工作"这条中间路线，因为那样不够启发人。

So what I'm really going to show you is how a piece of machinery can be built to do a job which you're written down as a program, a program is in fact a description of a machine.

• 核心命题：程序就是机器的描述。 你写下的程序，本质上描述了一台机器。
• 教学路径：从非常简单的程序出发 → 展示简单的机械装置 → 逐步增强，直到能处理递归等复杂结构。

理解：这句话是整讲的"纲"。SICP 前几讲一直在讲"过程"（process）和"数据"（data），这一讲开始把过程"物化"成硬件。程序不再只是纸上的符号，而是一台可以被"打开看内部"的机器的图纸。

二、案例一：GCD 机器（迭代过程）[03:00]

2.1 欧几里得算法回顾 [03:07]

• 求两个数 A、B 最大公约数（GCD）的算法，可追溯到公元前 350 年，是已知最古老的算法。
• 算法极其简单：
  • 若 B = 0，则结果为 A；
  • 否则，GCD(A, B) = GCD(B, A 除以 B 的余数)。

考点：递归定义 vs 迭代过程

• 这是一个递归定义的过程（recursively defined procedure），但它产生的是一个迭代过程（iterative process）。
• 判断依据：每一步都不需要上一步的"待办信息"。运行这个算法所需的全部信息都装在 A 和 B 里——它只有两个良定义的状态变量（state variables）。

易错点： "递归定义"和"递归过程"是两回事。GCD 是递归定义，但产生的是迭代过程。判断标准是：过程是否需要在每一步保留"未完成的工作"（deferred operations）。迭代过程不需要，所以状态可以用有限个变量完全描述。

2.2 计算机的通用结构：数据通路 + 控制器 [05:05]

Abelson 提出一个普遍结论：历史上每一台单处理器计算机都遵循同一个设计蓝图——分为两部分：

• 数据通路完全没有智能，纯机械。哪怕它能算出一个数的符号，也是纯机械可实现的。
• 控制器也没有复杂度：它只是按纸上写好的序列按按钮，遇到分支时看灯决定走哪条路。

思考：这个"计算器 + 按按钮的人"的模型，是理解后续所有机器（包括求值器本身）的钥匙。数据通路是"能力"，控制器是"顺序与决策"。

2.3 GCD 机器的数据通路设计 [06:40]

设计原则（Abelson 特别强调）：

研究你要解决的问题，用从研究中得到的知识，把解决问题所需的机制放进你正在造的计算机里，不多也不少。

• 这就是所谓的 "针对问题的机器"（special-purpose machine），与"通用解释器"相对。

GCD 机器需要的能力，以及对应的硬件：

1. 把 B 的值送进 A → 一条从 B 到 A 的数据通路（带一个按钮）。
2. 计算 A 除以 B 的余数 → 一个标着 remainder 的小盒子，输入 A 和 B，输出余数。
   • 注意：这个盒子的内部暂时不管，先当黑箱。
3. 测试 B 是否等于 0 → 一个灯泡，B = 0 时点亮。
4. 需要一个临时寄存器 T：
   • 易错点： 因为新 A 要等于旧 B，新 B 要等于旧 A 除以旧 B 的余数，而机器一次只能做一件事、一个寄存器一次只能装一个数，所以必须有个地方先存一个值。
   • 这就是所谓的时序问题（timing errors）——很多计算机设计中的 bug 都源于此。

数据通路的完整构成：寄存器 A、B、T + remainder 盒子 + 零测试灯 + 若干按钮。

2.4 控制器的"弹珠迷宫"模型 [10:30]

Abelson 用了一个生动的类比来描述控制器：

• 想象一个迷宫（maze），由有向箭头连接若干位置。
• 一颗弹珠（marble）代表控制器的状态，在迷宫里滚动。
• 弹珠每经过某些"缓冲器（bumpers）"，就像弹珠机一样按下一个按钮。
• 遇到岔路口（division），有一个由指示灯控制的挡板（flap）决定走哪边。

拓展：Abelson 提到，这种控制器在真实计算机里早已不用，现代用一小块 ROM + 状态寄存器实现。但历史上确实有过这样的机器——比如 DEC 的 PDP-6，用延迟线（delay line）里跑一个 bit 来触发操作。他还幽默地提到"两个 bit 一起跑"这种经典 bug。

2.5 用语言描述控制器 [13:30]

Abelson 指出：画图有缺点——占空间（求值器机器的图要占两块黑板，这间屋子都放不下）。所以需要一种语言来描述控制器。

• 好处：一旦有了语言表示，就可以操作这些表达式、模拟它们、甚至把它们变换成布局。
• 描述形式：define-machine GCD，列出寄存器 A、B、T，然后写控制器指令序列。

控制器的指令序列（GCD）：

loop:
  branch (fetch B = 0) → done
  assign T ← (remainder (fetch A) (fetch B))
  assign A ← (fetch B)
  assign B ← (fetch T)
  goto loop
done:

关键概念解释：

• 标签（labels）：图中用箭头表示跳转，文本里用给位置命名来代替箭头。这只是编码，没有任何魔法。
• assign：相当于"按下某个按钮"，把结果写进某个寄存器。
• branch：相当于岔路口的挡板，根据条件选择路径。

考点： 控制器语言看起来很像传统计算机语言，但它是机器的描述，不是被解释执行的高级语言。指令序列直接对应数据通路上的按钮操作。

2.6 手动执行 GCD(30, 42) [17:00]

Abelson 现场"跑"了一遍机器，追踪弹珠和寄存器的变化：

验证：30 = 2×3×5，42 = 2×3×7，最大公约数 = 2×3 = 6。✓

易错点： 注意第 1 步 remainder(30, 42) = 30，因为 30 小于 42。这是欧几里得算法的一个常见"反直觉"点。

2.7 扩展：加入 IO 操作 [24:00]

真实机器还需要输入输出：

• read：一个"总是有值"的源，可以门控（gate）进 A 或 B 寄存器。
• print：按按钮就打印 A 寄存器的当前值。
• Abelson 回忆：在 IBM 7090 时代，读写单个数字确实是 IO 控制器的原语操作。

2.8 扩展：把 remainder 展开成机器 [25:30]

关键洞察：remainder 盒子内部可能藏着一整台计算机。

• 最简单的 remainder 程序用重复减法：
  • 若 n < d，结果为 n；
  • 否则 remainder(n, d) = remainder(n − d, d)。
• 这个程序的结构和 GCD 一模一样。

思考：这意味着"黑箱"是递归的——你可以不断打开盒子，里面又是一台机器，直到最底层的原语操作。

优化案例： Abelson 展示了一台把 remainder 整合进 GCD 的机器：

• 数据通路仍只有 3 个寄存器，但多了一个减法器（subtractor）。
• 测试条件变成两个：B = 0 和 T < B。
• 控制器有两个循环：主 GCD 循环 + 减法循环（实现 remainder）。
• 推导：如果把 remainder 的 lambda 表达式代入 GCD 程序，再做简化，就能"展开"出这台机器。

三、案例二：阶乘机器（递归过程）[30:00]

3.1 递归过程的本质困难 [30:30]

阶乘的递归定义：

factorial(n) = 1,                          若 n = 1
             = n × factorial(n − 1),       否则

与迭代过程的关键区别：

• 计算完 factorial(n−1) 之后，还要对结果做乘法（乘以 n）。
• 这意味着：外层机器必须在内层机器运行之前和之后都存在。
• 而迭代过程（如 GCD）中，内层机器运行时，外层机器不需要存在——因为不需要回头再做任何事。

理解：递归过程需要"无限嵌套的机器"，而现实世界没有无限硬件。所以必须制造"无限"的假象。

考点： 迭代 vs 递归的根本区别在于——过程是否需要在每一步保留"待完成的工作"。递归过程需要，所以需要额外的存储机制（栈）。

3.2 用栈模拟"无限机器" [33:30]

解决方案：

• 把机器分解成两部分：
  1. 有限且简单的部分：控制器（controller）。
  2. "无限"但非常规整的部分：内存（memory）。
• 内存虽然不真的无限，但极其简单、可廉价大量复制。
• 用内存构造一个栈（stack），用来模拟"递归嵌套的无限机器"。

栈的工作方式：

• 内层机器运行前，把外层机器"续命"所需的信息存进栈。
• 内层机器运行完，从栈中恢复这些信息，继续外层机器的计算。
• 因为机器是递归嵌套的，栈的访问天然满足后进先出（LIFO）——最后存进去的最先取出来。

思考：这是"用有限资源模拟无限"的经典手法。栈的 LIFO 特性不是人为规定的，而是递归嵌套结构的必然结果。

3.3 阶乘机器的数据通路 [35:00]

需要的寄存器：

• n：存放当前要计算阶乘的数。
• val：存放答案（结果）。
• continue：存放"弹珠下一步该去哪"（即控制器的返回地址）。

需要的操作：

• 乘法器：输入 n 和 val，结果写回 val。
• 减一器（decrementer）：输入 n，结果写回 n。
• 零测试灯：测试 n 是否等于 1。
• 栈：存放 n 和 continue 的旧值。
• 常数：after-fact 和 fact-done，用于设置 continue。

3.4 阶乘机器的控制器 [38:00]

（初始化）
  assign continue ← fact-done

loop:
  branch (fetch n = 1) → base
  save continue
  save n
  assign n ← (decrement (fetch n))
  assign continue ← after-fact
  goto loop

after-fact:
  restore n
  restore continue
  assign val ← (product (fetch n) (fetch val))
  goto (fetch continue)

base:
  assign val ← (fetch n)
  goto (fetch continue)

fact-done:

指令解释：

• save：把寄存器的值压入栈。
• restore：从栈中弹出值，写回寄存器。
• goto (fetch continue)：跳转到 continue 寄存器指向的位置（相当于"返回"）。

考点：save 和 restore 必须严格配对。 谁 save 的，谁负责 restore。这是栈纪律的核心。

3.5 手动执行 factorial(3) [44:00]

追踪栈和寄存器的变化：

阶段一：向下递归

阶段二：base 返回

阶段三：第一次 after-fact

阶段四：第二次 after-fact

答案：val = 6。✓ 栈已恢复初始状态。

思考：注意每一步 save 都有对应的 restore，栈最终回到空。这就是"栈纪律"——不平衡的 save/restore 会导致栈溢出或数据错乱。

3.6 关于栈溢出的问答 [53:00]

学生提问：如果栈用完了怎么办？

Abelson 的回答：

• 真相：每台机器都是有限的。 对于阶乘这样的过程，能嵌套的子阶乘数量有上限。
• 如果违反"无限"的假象，魔法就失效了。
• 每次递归大约消耗 2 个内存块。计算 factorial(10000) 需要的内存不算太多，但结果数字极大。
• Abelson 指出：这个限制在实践中通常不是大问题，因为内存便宜、人贵。

易错点： 栈不是真的无限。递归深度过大时会发生栈溢出（stack overflow）。这是所有真实计算机的固有限制。

四、案例三：双重递归斐波那契机器 [56:00]

4.1 斐波那契程序

fib(n) = n,                          若 n < 2
       = fib(n − 1) + fib(n − 2),    否则

与阶乘的区别： 斐波那契需要调用自己两次，且两次调用的结果都要保留，最后相加。这对栈纪律提出了更高要求。

4.2 斐波那契机器的控制器

（初始化）
  assign continue ← fib-done

fib-loop:
  ; 契约：n 含参数，continue 是接收者
  branch (fetch n < 2) → immediate-answer
  save continue
  assign n ← (difference (fetch n) 1)
  assign continue ← after-fib-n-1
  goto fib-loop

after-fib-n-1:
  restore n
  ; （此处原本有 restore continue，但被优化掉了）
  assign n ← (difference (fetch n) 2)
  save continue
  assign continue ← after-fib-n-2
  save val                    ; 保存 fib(n−1) 的结果
  goto fib-loop

after-fib-n-2:
  assign n ← (fetch val)      ; 把 fib(n−2) 挪到 n（因为 n 不再需要）
  restore val                 ; 恢复 fib(n−1) 到 val
  restore continue
  assign val ← (sum (fetch n) (fetch val))
  goto (fetch continue)

immediate-answer:
  assign val ← (fetch n)
  goto (fetch continue)

fib-done:

4.3 关键优化：删除冗余的 restore/save 对

Abelson 在 after-fib-n-1 处演示了一个编译器级别的优化：

• 原本写了 restore continue，然后很快又 save continue，中间没有引用 continue。
• 既然 restore 后紧接着 save，且中间不引用，这一对操作对栈没有任何净影响。
• 所以可以直接删除，只保留 assign continue 的赋值。

考点： 这个优化只有在把指令写下来之后才能发现。Abelson 强调："我先把它们写下来，然后才能看出这是不必要的。"

4.4 栈纪律（Stack Discipline）[01:05:00]

Abelson 总结斐波那契机器体现的栈纪律：

1. 只保存你以后真正需要的东西。 不要因为"方便"就保存一堆垃圾。
2. 谁 save，谁 restore。 保存者有责任恢复，因为他需要它。
3. restore 必须匹配 save。 不平衡会导致灾难。
4. 只 restore 到曾经 save 过的寄存器。

拓展：Abelson 提到，有些人用"帧（frames）"的方式，把所有东西都保存下来再恢复，因为"感觉更容易"。但这种做法会导致各种灾难。

易错点： 在斐波那契机器中，save val 和 restore val 必须配对。因为 fib(n−1) 的结果在计算 fib(n−2) 时会被覆盖，所以必须先保存。

4.5 关于 list 语法的澄清

Abelson 特别提醒：

• 控制器代码里用了很多括号，看起来像 Lisp 的 list 语法，但这不是被解释执行的 Lisp 代码。
• 这只是另一种语言的表示，用 Lisp 的 list 结构来书写，方便用 Lisp 写一个模拟器来模拟这台机器。
• 理解：这是一种"嵌入式语言（embedded language）"的手法——用 Lisp 的语法作为载体，表达机器描述语言。

五、拓展与收尾 [01:10:00]

5.1 更复杂的原语：cons、car、cdr

Abelson 指出，真实系统还需要：

• car、cdr、cons、向量构造、向量索引等操作。
• 这些都可以当作数据通路中的原语操作（primitive operations）。
• 例如 append 机器：cons(car(x), append(cdr(x), y))，结构与阶乘机器类似。

思考：cons 可以和 car、cdr 共享硬件，就像加法器和减法器可以共享一样。打开 cons 盒子，里面又是一台机器，可能还有自己的内存部分。

5.2 本讲核心总结

考点： 本讲是从"软件"到"硬件"的桥梁。理解 GCD（迭代）和阶乘/斐波那契（递归）两种机器的设计差异，是理解后续"求值器机器"和"编译器"的基础。

关键标签/关键词

SICP 6.001 寄存器机器 数据通路 控制器 GCD 欧几里得算法 迭代过程 递归过程 阶乘 斐波那契 栈 栈纪律 save/restore continue 寄存器 时序错误 弹珠迷宫模型 黑箱展开 原语操作 LIFO 双重递归 编译器优化

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