SICP 第 7 讲：模式匹配与规则代换

视频元信息

• 课程：MIT 6.001 Structure and Interpretation of Computer Programs（1986 原版）
• 讲次：第 8 讲（p08）——模式匹配与规则代换（Pattern Matching and Rule-based Substitution）
• 主题：用规则驱动的方式实现符号微分与代数化简，构建"模式匹配器 + 实例化器 + 控制结构"三件套

内容摘要（TL;DR）

本讲从"符号微分规则"出发，提出一个核心思想：不要把规则翻译成程序，而要让计算机理解规则本身。为此设计了一套规则语言（模式变量、骨架、字典），并实现三个组件：匹配器（matcher）、实例化器（instantiator）、控制结构（simplifier）。匹配器把模式与表达式比对生成"字典"，实例化器用字典填充骨架生成新表达式，控制结构则递归遍历表达式、反复套用规则直到不再变化——即一个"垃圾进垃圾出"的递归化简器。

一、从"写程序实现规则"到"让计算机理解规则" [00:06]

1.1 上一讲的局限

上一讲实现了符号微分：把微积分课本上的求导规则（常数、变量、和、积、幂等）逐一翻译成计算机语言，写成一组高度风格化的程序（根据表达式是常数、变量、乘积……分别处理）。

这种写法的根本问题：

• 程序本身就是那些规则，规则与实现纠缠在一起；
• 如果想换一套数学（比如三角函数的化简），就得重写一个全新程序；
• 匹配、实例化、控制结构这些共性部分无法复用。

1.2 本讲的核心转向

不是把规则降到计算机的层次（写程序表达规则），而是把计算机提升到我们的层次——写一个能理解这类规则的解释器。

理解：这是 SICP 反复强调的"元语言抽象"思想：与其为每个问题写程序，不如造一门语言。

需要被封装、与规则本身分离的共性部分：

• 匹配（matching）：把规则左部与表达式比对；
• 实例化（instantiation）：用匹配结果填充规则右部；
• 控制结构（control structure）：决定何时、在哪些子表达式上、以什么顺序套用规则。这个控制结构"非常复杂"。

二、规则语言的设计 [05:17]

2.1 规则的结构：左部模式 + 右部骨架

一条规则形如：

(derivative (constant c) v)  →  0
(derivative v v)             →  1
(derivative u v)             →  0      ; u 与 v 不同
(derivative (+ x1 x2) v)     →  (+ (derivative x1 v) (derivative x2 v))
(derivative (* x1 x2) v)     →  (+ (* x1 (derivative x2 v)) (* (derivative x1 v) x2))

• 左部（left-hand side）= 模式（pattern）：要拿去和"求导表达式"匹配的东西；
• 右部（right-hand side）= 骨架（skeleton）：匹配成功后用来生成新表达式的模板；
• 以 ? 开头的符号（如 ?x、?x1、?v）叫 模式变量（pattern variable）。

易错点：同一个模式变量在同一条规则里出现两次（如 (derivative ?v ?v) 中的 ?v），意味着两次匹配到的对象必须一致，否则匹配失败。这是模式匹配中"一致性约束"的关键。

2.2 模式匹配语法

匹配是逐元素比较：模式中不含模式变量的部分必须与表达式对应元素完全相同；含模式变量的部分则把匹配到的对象作为值记录下来。

推导：?c 和 ?v 相当于给 ?x 加了"类型谓词"约束——只有通过常量/变量检测的对象才允许绑定。

2.3 实例化语法（骨架）

理解：骨架的 : 前缀与模式的 ? 前缀对称——一个负责"取出"，一个负责"填入"。

三、匹配器（Matcher）的内部结构 [12:40]

3.1 匹配器的接口

matcher:  (pattern, expression, dictionary) → dictionary

输入一个模式、一个表达式、一个已有字典；输出扩充后的字典（把本次匹配新绑定的模式变量加进去）。若匹配失败，返回符号 failed。

关键设计：字典是贯穿整个匹配过程的"线程"。匹配 car 得到的字典要传给匹配 cdr 使用，因此失败必须能向上传播。

3.2 案例分析法（case analysis）

匹配器是一大段 case 分析，主要分支：

1. 失败传播：若传入字典已是 failed，直接返回 failed，不做任何进一步处理。
2. 模式是原子符号：
   • 表达式也是原子且相同 → 返回原字典（无变化）；
   • 表达式是不同原子 → 失败；
   • 表达式是复合 → 失败。
3. 模式是模式变量：分三种——
   • ?x（任意表达式）：不检查表达式语法，直接扩充字典；
   • ?c x（任意常量）：先检查表达式是否为常量，是则扩充字典，否则失败；
   • ?v x（任意变量）：先检查表达式是否为变量，是则扩充字典，否则失败。
4. 一般情况（两个都是复合）：同时遍历"模式树"和"表达式树"，先匹配 car，用得到的字典再匹配 cdr。

3.3 双树同步遍历的实例

模式（要找的东西）：

(+ (* ?x ?y) ?y)

表达式（实际输入）：

(+ (* 3 x) x)

遍历过程：

• 比较 car：都是 +，✓；
• 进入子表 (* ?x ?y) vs (* 3 x)：car 都是 *，✓；
• ?x 匹配 3 → 字典 {x=3}；
• ?y 匹配 x → 字典 {x=3, y=x}；
• 回到外层，?y 再次匹配 x：字典中 y 已绑定为 x，本次匹配值也是 x，一致 ✓；
• 匹配成功，得到字典 {x=3, y=x}。

思考：如果把表达式改成 (+ (* 3 x) 4)，则 ?y 第二次要匹配 4，但字典里 y=x，两者不同 → 匹配失败。这就是"一致性约束"的实际作用。

3.4 extend-dictionary 的语义

扩充字典时：

• 取出模式变量的名字；
• 在字典中查找是否已有值：
  • 没有 → 新增绑定；
  • 已有 → 必须与已存值相等，否则失败。

易错点：字典不是简单的"覆盖式赋值"，而是"一致性合并"。这一点直接决定了模式匹配能否表达"同一对象出现两次"这类约束。

3.5 关于字典的抽象

学生反复追问"字典到底是不是有序对表"，讲师坚持抽象：

• 字典是一个函数（从模式变量名到值的映射）；
• 抽象意义上函数就是一组有序对；
• 具体可以用表对、哈希表、甚至函数本身来实现——这留给"George 以后去建"。

理解：这是数据抽象（data abstraction）的经典示范——先约定接口语义，实现细节推迟。

四、实例化器（Instantiator）[约 28:00]

4.1 接口与实现

instantiate: (skeleton, dictionary) → expression

实现是对骨架的递归遍历：

• 骨架是原子符号 → 原样返回；
• 骨架是复合 → 递归实例化 car 与 cdr，cons 成新表；
• 骨架是 :x 形式（skeleton evaluation）→ 在字典中查出 x 的值并返回。

易错点：匹配阶段不做任何替换，只构建字典；替换发生在实例化阶段。学生常疑惑"为什么匹配到就立刻替换"——因为匹配器是独立单元，它不知道骨架长什么样。

4.2 关于 evaluate 的"魔法"

实例化中 :x 的求值涉及 evaluate，讲师明确表示："你现在看到的是魔法，很快就会揭晓，但不是今天。" 这部分与后续讲次中的求值器（evaluator）相关。

理解：这是课程刻意埋下的伏笔——evaluate 相对字典求值，本质上是把字典当作环境（environment）。

五、控制结构：化简器（Simplifier）[约 33:00]

5.1 化简器的接口

simplify = simplifier(rules)

simplifier 接受一组规则，返回一个"针对这组规则的化简过程"。例如：

(define dsimp (simplifier derivative-rules))
(dsimp '(derivative (+ x y) x))
→ (+ 1 0)

理解：这是"过程作为返回值"的又一实例——规则集被闭包捕获，产出一个专用化简器。

5.2 控制结构的核心循环

化简的过程可类比为"一锅酶汤"：

把表达式丢进一锅充满酶的汤里，酶（规则）附着到表达式的任意部分，能匹配就改变它，然后离开；过程持续到表达式不再变化为止。

正式描述：

1. 对表达式的每一个子表达式；
2. 依次尝试每一条规则；
3. 若某条规则匹配成功 → 用实例化器生成新表达式，替换该子表达式；
4. 对生成的新表达式递归化简（它未必已是最简）；
5. 把结果嵌回原表达式；
6. 重复上述过程，直到不再有任何变化。

易错点 / 风险：这种"反复套用直到不动点"的机制，可能陷入无限递归（规则写错时）。讲师明确指出：任何足够强大的语言都允许写出死循环程序，代数化简规则写错就会产生这种后果。

5.3 递归遍历的两种写法

写法一（两个互相递归的过程）：

• simplify-exp：若表达式复合，先 simplify-parts 简化所有部分，再对结果试规则；若表达式原子，直接试规则（因为规则可能想把 pi 展开成 3.14159…）。
• simplify-parts：空表返回空表；否则 cons（化简 car）与（化简 cdr）。

写法二（用 map 的惯用法）：

(define (simplify x)
  (try-rules
    (if (compound? x)
        (cons (operator x) (map simplify (operands x)))
        x)))

理解：写法二用高阶过程 map 消除显式的 simplify-parts 辅助过程，是"高阶过程捕获常见递归模式"的典型示范。两种写法语义等价，选哪种取决于可读性偏好。

5.4 try-rules 与 scan

try-rules(exp):
    scan(rules, exp)

scan(rules, exp):
    若 rules 为空 → 返回 exp（已无法化简）
    否则：
        用空字典匹配第一条规则的左部与 exp
        若失败 → scan(剩余规则, exp)
        否则   → instantiate(该规则骨架, 字典) 的结果再 simplify

要点：scan 找到第一条匹配的规则就立即使用并返回，不再尝试后面的规则。这意味着规则的顺序会影响化简结果——先匹配的规则优先。

六、代数化简规则示例 [约 40:00]

讲师展示了一组代数操作规则（不关心具体内容，重点在于"规则可任意编写"）：

• 常量折叠：(op e1 e2)（e1、e2 均为常量）→ 直接算出结果；
• 常量前移：(op e1 e2)（e2 为常量）→ (op e2 e1)；

  • [!IMPORTANT] 易错点：讲师亲口说这条规则"有 bug"——对除法不成立（a/2 ≠ 2/a）。规则必须考虑运算的代数性质（交换律）。

• 单位元：(+ 0 e) → e；(* 1 e) → e；(* 0 e) → 0；
• 常量合并：(* e1 (* e2 e3))（e1、e2 为常量）→ 先算 e1*e2 再乘 e3；
• 分配律：(* c (+ d e)) → (+ (* c d) (* c e))。

思考：这些规则大多是"等价变换"（equational rules），因此可以对表达式的任意子表达式套用，而不必担心改变语义。

七、工程与设计哲学 [约 50:00]

7.1 "知道什么不用去想"

讲师反复强调：不要试图在脑中模拟整个递归控制流，否则一定会晕。

正确做法：

• 为每个过程建立规格（specification）；
• simplify-exp 的规格：输入任意表达式，输出按规则化简后的表达式；
• 只要相信规格，就可以把它当作黑盒使用，不必关心内部如何递归。

核心方法论：好的编程与设计，关键是"知道什么不用去想"（know what not to think about）。这是"愿望式编程"（wishful thinking）的体现。

7.2 关于"AI 专家系统"的调侃

讲师半开玩笑地说：如今有人花大价钱请人做"AI 专家系统"，其内核不过就是一个匹配器加一个实例化器；20 年前这类程序很了不起，现在对大一新生来说已经很容易——"你可以开个创业公司赚几百万"。

理解：这段话点出规则驱动系统（rule-based system）正是早期专家系统的技术基础，也呼应了本讲"造语言"这一强大设计手段。

7.3 关于"模式匹配是否该内建进语言"

有学生问：模式匹配这么重要，是否应该成为语言的基本特性（如某些语言所做）？

讲师回答：我更愿意教你自己做，这样你就不必依赖语言设计者的施舍——你可以自己造（roll your own）。

八、学生问答要点 [约 30:00 与 45:00]

• 匹配器与实例化器是分开的程序吗？ 是。匹配器负责比对并产出字典，实例化器负责用字典生成新表达式，二者拼装进更大的结构。
• 会不会死循环？ 会。规则写错就可能无限递归，这是任何足够强大的语言都固有的问题。
• 字典是不是有序对表？ 讲师拒绝回答具体表示，坚持抽象——它是一个函数，实现方式多样。
• 匹配到之后为什么不立刻替换？ 因为匹配器是独立单元，它不知道骨架；替换必须等实例化阶段。
• 失败如何传播？ 匹配器接受字典作为输入，因此第一个条件分支专门负责把 failed 继续向上传，避免对已失败的结果继续操作。

九、本讲知识地图（小结）

规则语言
 ├── 模式（LHS）：符号 / 表 / ?x / ?c x / ?v x
 └── 骨架（RHS）：符号 / 表 / :x

三大组件
 ├── matcher(pattern, expr, dict) → dict | failed
 │     └── 案例：失败传播 / 原子 / 模式变量 / 一般（双树同步遍历）
 ├── instantiate(skeleton, dict) → expr
 │     └── 递归遍历骨架，:x 查字典
 └── simplifier(rules) → 化简过程
       ├── 递归遍历表达式（simplify-exp / simplify-parts 或 map）
       └── try-rules → scan（逐条规则匹配，命中即用）

关键机制
 ├── 字典 = 模式变量名 → 值的映射（抽象为函数）
 ├── extend-dictionary：一致性检查（同名变量必须匹配同一对象）
 └── 不动点迭代：反复套用规则直到表达式不再变化

关键标签 / 关键词

SICP MIT 6.001 符号微分 模式匹配 pattern matching 模式变量 pattern variable 骨架 skeleton 实例化 instantiation 字典 dictionary A-list 关联表 规则驱动 rule-based system 化简器 simplifier 控制结构 control structure 不动点迭代 元语言抽象 数据抽象 高阶过程 map 专家系统 AI 愿望式编程 wishful thinking Abelson Sussman

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