SICP 第 2 讲：过程与代换模型

视频封面

视频元信息

主题：过程（Procedures）与代换模型（Substitution Model）
讲师：Hal Abelson（SICP 作者之一）
时长：约 20 分钟（本讲为第 2 讲，对应课程总第 3 个视频）

内容摘要（TL;DR）

本讲建立"程序文本"到"过程行为"之间的机械映射——代换模型。通过 sum-of-squares、皮亚诺加法、斐波那契、汉诺塔等例子，演示如何用代换规则一步步推演过程演化，并揭示迭代过程与递归过程在时间/空间复杂度上的本质差异，以及"递归定义 ≠ 递归过程"这一关键洞见。

一、引言：程序员的"咒语"与过程的映射 [00:41]

核心问题：程序员写下的"符号咒语"（spells）如何转化为实际的过程行为？要有效控制过程，必须理解所写代码与过程行为之间的对应关系。

程序员的代码本质上是一些"咒语"（spells），它们指向某个过程以完成预期目标。
本讲目标：建立"特定过程与表达式模式"→"特定执行模式与过程行为"的连接。
理解：这是 SICP 全课的方法论主线——用模型理解机器，而不是死记语法。

二、代换模型：一个工程近似模型 [01:23]

代换模型（Substitution Model） 是理解"过程如何工作、过程如何产生进程"的最简单模型。
类比：电阻的欧姆定律 V = IR 只是近似模型（大电流下电阻会烧毁，电压不再正比于电流），但在一定范围内足够有效。
思考：模型不是真理，而是工程上有用的简化。代换模型在前几讲够用，后续会失效，需要更精细的模型（环境模型）。

易错点：代换模型不是计算机真实的工作方式，它只是一个便于推理的"半形式化机械模型"。不要把它当成硬件的真实描述。

三、表达式的种类与组合式的求值规则 [03:53]

3.1 表达式的种类

基本表达式：数字（求值为自身）、符号
特殊形式（Special Forms）：lambda、define、if（条件式）等，各有独立规则
组合式（Combinations）：本讲重点

理解：符号在代换模型中会"消失"，所以真正需要详细解释的只有组合式如何求值。

3.2 组合式的求值规则（Applicative Order）

考点：组合式求值三步法

求值运算符（operator），得到一个过程（procedure）
求值运算对象（operands），得到实参（arguments）
将过程应用于实参：复制过程体，用实参代换形参，然后求值得到的新过程体
形参（formal parameters）：过程声明中定义的名字
实参（arguments）：实际传入的值

关键术语要记牢：operator / operands / procedure / arguments / formal parameters / body。讲师强调："如果你知道一个东西的名字，你就对它有了掌控力"——必须学会这些术语才能参与讨论。

四、代换模型实战：sum-of-squares 的逐步推演 [07:28]

以 (sum-of-squares 3 4) 为例，演示代换过程：

(sum-of-squares 3 4)
→ (sum (square 3) (square 4))        ; 代换 x=3, y=4
→ (sum (* 4 4) ...)                  ; 先算右边的 (square 4)
→ (sum (square 3) 16)
→ (sum (* 3 3) 16)
→ (sum 9 16)
→ 25

求值顺序：讲师选择从右到左，但顺序其实是任意的（只要最终结果一致）。
+、* 被视为原语（primitive），不打开看内部实现。

核心思想：忽略细节的能力 "理解复杂事物的关键，是知道什么不该看、什么不该算、什么不该想。" 这是抽象的核心——把 * 当作黑盒，才不会陷入无穷的细节。

4.1 正规序 vs 应用序

应用序（Applicative Order）：先求值运算符和运算对象，再做代换（本课默认，也是真实机器的方式）。
正规序（Normal Order）：先把表达式代换进过程体，最后才求值，结果相同。
拓展：正规序求值在某些情况下更"懒"，这与后来的惰性求值（lazy evaluation）、λ 演算的规约策略密切相关。SICP 第 3 章会再次讨论。

五、条件式的求值规则 [12:20]

条件式 if 的三部分命名（考点）：

谓词（predicate）：求值为真或假的表达式
推论（consequence）：谓词为真时求值的表达式
替代（alternative）：谓词为假时求值的表达式

求值规则：先求值谓词；若为真，求值推论；否则求值替代。

易错点：if 是特殊形式，不是普通过程——它的两个分支不会都被求值（否则递归就无法终止）。这与普通组合式"先求所有运算对象"的规则根本不同。

六、皮亚诺算术：加法的两种写法 [14:00]

用"增量/减量"（increment/decrement）实现加法，即皮亚诺算术（只用 +1 和 -1）：

(define (+ x y)
  (if (= x 0)
      y
      (+ (dec x) (inc y))))

推演 (+ 3 4)：

(+ 3 4) → (+ 2 5) → (+ 1 6) → (+ 0 7) → 7

思路：把 x 不断减到 0，同时把减掉的部分加到 y 上。
理解：这就是"两堆弹珠"的比喻——从一堆搬到另一堆，搬空时另一堆就是总和。

原语说明：inc（+1）和 dec（-1）是原语操作，本课会不断引入新的原语，只要说明其功能即可，无需关心底层实现。

七、迭代 vs 递归：两个几乎相同的程序 [17:30]

7.1 两个程序对比

程序 A（迭代）：

(define (+ x y)
  (if (= x 0)
      y
      (+ (dec x) (inc y))))

程序 B（递归）：

(define (+ x y)
  (if (= x 0)
      y
      (inc (+ (dec x) y))))    ; 注意 inc 在外面

关键差异：inc 的位置不同（一个在参数里，一个在返回值上）。

7.2 过程形状对比

程序 A 的推演（线性迭代）：

(+ 3 4) → (+ 2 5) → (+ 1 6) → (+ 0 7) → 7

过程形状：一条直线，宽度（空间）不变。

程序 B 的推演（线性递归）：

(+ 3 4)
→ (inc (+ 2 4))
→ (inc (inc (+ 1 4)))
→ (inc (inc (inc (+ 0 4))))
→ (inc (inc (inc 4)))
→ (inc (inc 5))
→ (inc 6)
→ 7

过程形状：先膨胀后收缩（展开再回缩），宽度随输入增长。

7.3 复杂度分析（考点）

程序	时间	空间	过程类型
程序 A	O(x)	O(1)	迭代（iteration）
程序 B	O(x)	O(x)	线性递归（linear recursion）

时间：两者都正比于输入 x（多一个输入就多一行）。
空间：A 是常数（只需记住当前变量），B 正比于 x（有 x 个"延迟的 inc"待处理）。

核心结论（易错点）： 递归定义 ≠ 递归过程！ 两个程序都是递归定义（定义中引用自身），但程序 A 产生的是迭代过程，程序 B 产生的是递归过程。决定过程类型的是过程的形状，而非定义的形式。

八、官僚模型：理解迭代与递归的直觉 [21:00]

8.1 迭代 = 懒惰的官僚

GGS 要算 3+4，把问题写纸条交给下属，不关心过程，只要最终结果。
下属再交给更下属，层层转包，最后有人直接给出答案 7，逐层回传。
特点：任何时候只有一个"活跃"的问题，没有待办事项堆积。

8.2 递归 = 更官僚的体系

GGS 交给 Joe，Joe 说"我要记住稍后还要加 1"，把 (2+4) 交给 Harry。
Harry 返回 6 后，Joe 才做 inc 得到 7，再返回给 GGS。
特点：有更多"悬而未决的纸条"（deferred operations）堆在桌上。

8.3 "桌下的东西"（关键直觉）

迭代过程：所有状态都在显式变量中。如果机器突然停止，可以从变量恢复计算。 递归过程：除了变量，还有"桌子底下"的隐藏信息（被延迟的操作）。若丢失这些信息（如只剩 (+ 1 4)），无法重建原始计算。

思考：这解释了为什么递归过程需要更多空间——它在"隐藏状态"里存了待办事项。

8.4 微分方程类比：画圆

用微分方程画圆：状态 (x, y)，导数为 (dy = x·dt, dx = -y·dt)。
程序：(circle x y) → (circle (- x (* y dt)) (+ y (* x dt)))
这是迭代（两个状态变量，无延迟操作）。
拓展：这是欧拉法数值积分，会因误差逐渐螺旋发散（"spiral out"），但在短时间内近似成圆。

九、斐波那契：树形递归的代价 [28:00]

9.1 斐波那契数列

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...（每项为前两项之和）

9.2 最直接的递归程序

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

这是对斐波那契递推关系最直接的翻译。

9.3 树形递归的推演

计算 (fib 4) 会展开成一棵树：

(fib 4) → (fib 3) + (fib 2)
(fib 3) → (fib 2) + (fib 1)
(fib 2) 被重复计算多次

性能灾难（易错点）：

时间复杂度：O(fib(n))，即指数级！每增加一个 n，计算量按比例爆炸。

空间复杂度：O(n)，等于树的最长路径（需要记住回溯路径）。

这是最糟糕的斐波那契算法之一，但它的程序极其简洁，直接反映了数学定义。

9.4 程序与过程的关系

程序只有两条规则：
1. n < 2 时，答案是 n（叶子节点）
2. n ≥ 2 时，分解为两个子问题之和（分支节点）
过程的树形结构，就是这两条规则不断实例化的结果。

思考：编程的难点在于——你写的是通用规则，但要预想它在所有可能的输入下产生的过程形状。

十、汉诺塔：递归思维与"许愿式"编程 [36:00]

10.1 问题描述

三根柱子（from、to、spare），n 个大小不同的盘子。
目标：把所有盘子从 from 移到 to，规则是大盘不能压小盘。
传说：64 层汉诺塔需 2⁶⁴ 次移动，完成后宇宙终结。

10.2 递归解法（"许愿式思维" Wishful Thinking）

核心思路：

假设我神奇地能把上面 n-1 个盘子从 from 移到 spare（不管怎么做到）
把最大的盘子从 from 移到 to
再神奇地把 n-1 个盘子从 spare 移到 to

为什么可行：因为 n 不断减小，最终降到 0（0 层塔无需移动），递归终止。

10.3 程序

(define (move-tower n from to spare)
  (if (= n 0)
      'done
      (begin
        (move-tower (- n 1) from spare to)
        (print-move from to)
        (move-tower (- n 1) spare to from))))

10.4 过程形状

汉诺塔产生指数级的树形递归过程（类似斐波那契）。
移动次数：2ⁿ - 1。

与斐波那契的联系：两者结构相似——都是树形递归，都把问题分解为两个子问题，都导致指数级爆炸。区别只是汉诺塔的每个节点还包含一次实际移动操作。

十一、学生提问与拓展 [46:00]

11.1 提问：能否用记忆化加速斐波那契？

讲师回答（记忆化 Memoization）：

每次计算出一个斐波那契数，就存入表格。
下次需要时直接查表，O(1) 时间。
这样可以把指数级时间降为线性时间。
拓展：这是动态规划的雏形，SICP 后续会详细讨论。

11.2 提问：能否写迭代版汉诺塔？

讲师鼓励学生课后思考：能否不用"分解为子问题"的方式，而是用局部规则一步步推进？
拓展：这涉及"迭代式汉诺塔解法"，需要发现盘子的移动规律（如最小盘总是按固定方向循环移动）。

11.3 讲师布置的练习

课后必做：

用迭代方式（线性时间、常数空间或线性空间）计算斐波那契数。

思考汉诺塔的迭代算法。

这两个练习对理解"递归定义 vs 迭代过程"至关重要。

关键标签 / 关键词

SICP MIT 6.001 代换模型 Substitution Model 应用序求值 正规序求值 组合式 特殊形式 条件式 谓词 皮亚诺算术 迭代过程 线性递归 树形递归 空间复杂度 时间复杂度 斐波那契 汉诺塔 许愿式思维 记忆化 Memoization 抽象 忽略细节