SICP 第 7 讲（备选版本）：模式匹配与规则代换

视频封面

视频元信息

课程主题：符号操作（Symbolic Manipulation）、模式匹配（Pattern Matching）、规则代换（Rule Substitution）
核心内容：用"模式-骨架"语言表示微积分求导规则与代数化简规则，实现通用匹配器（Matcher）与实例化器（Instantiator），并搭建化简器的控制结构

内容摘要（TL;DR）

本讲把微积分求导规则与代数化简规则写成"左模式、右骨架"的统一语言，让模式变量（?x、?c、?v）负责匹配，骨架负责实例化替换。核心是三个部件：匹配器（模式+表达式→字典）、实例化器（骨架+字典→新表达式）、化简器控制结构（遍历所有子表达式、轮询所有规则、递归化简直到不再变化）。这是"用做语言的方式解决问题"的经典范例。

一、从上一讲过渡：为什么要抽象出通用框架 [00:25]

要点

上一讲实现了一个"风格化程序"（stylized program），直接把微积分书上的求导规则翻译成计算机语言。
本讲要解决上一讲方法的局限：如果换成另一套数学规则（比如三角函数的化简、代数化简），就得重写整个程序。
目标：把匹配、实例化、控制结构这些"两类程序共有的东西"抽象封装起来，与规则本身分离。

详细说明

上一讲的做法：针对求导这一特定问题写程序。如果现在想写"三角函数操作"或"代数化简"的规则，用昨天的方法就得写一个完全不同的程序。

理解：这正是软件工程中"关注点分离"的早期教学表达——把"通用的规则引擎"与"具体的规则数据"分开。规则是数据，引擎是程序，换规则不用改引擎。

考点：本讲的核心动机——从"解决一个特定问题"升级为"解决一类问题"（a class of problems rather than a particular one）。

二、规则的表示：模式（Pattern）与骨架（Skeleton） [05:20]

要点

每条规则由左部（模式，pattern）与右部（骨架，skeleton）构成。
左部是"要匹配的模板"，右部是"匹配成功后要生成的新表达式"。
用问号开头的符号称为模式变量（pattern variables），用于匹配任意对象。
本讲刻意不纠结语法细节，重点在规则的结构。

详细说明

求导规则示例（用简化语言表示）：

常数的导数：(derivative ?c ?v) → 0
变量对自身的导数：(derivative ?v ?v) → 1
变量对另一变量的导数：(derivative ?u ?v) → 0
和的导数：(derivative (+ ?x1 ?x2) ?v) → (+ (derivative ?x1 ?v) (derivative ?x2 ?v))
积的导数（乘积法则）：(derivative (* ?x1 ?x2) ?v) → (+ (* ?x1 (derivative ?x2 ?v)) (* (derivative ?x1 ?v) ?x2))

演讲者原话大意：这些规则长什么样我并不太关心，我们要写一门语言来解释这些规则，这样就能随意制定规则——这本身又是另一种编程语言。

思考：把规则写成数据（而非硬编码进程序），是"元编程"思想的雏形。规则集可以像数据一样增删改，程序只负责解释这些数据。

三、模式匹配语言的语法 [07:55]

要点

匹配（pattern matching）的语法规则：

原子符号：如 foo，只匹配它自己本身。
列表模式：如 (F A B)，匹配任何"第一个元素是 F、第二个是 A、第三个是 B"的列表。
?x：匹配任意东西，并把它记为 x。
?c x：只匹配常量，记为 x。
?v x：只匹配变量，记为 x。
同名模式变量的一致性：如果同一模式变量出现两次，两次匹配到的对象必须相同。

详细说明

实例化（instantiation）的语法规则：

符号实例化为它自己。
列表 (F A B) 实例化为一个三元素列表，各元素分别是 A、B 实例化的结果。
?x 实例化为匹配时 x 所对应的值。

易错点：同名模式变量必须匹配到相同对象。 例如规则 (derivative ?v ?v) 中，?v 出现两次，只有当求导表达式里被求导的对象与求导变量是同一个东西时才能匹配成功。这是模式匹配中"一致性检查"的关键。

理解：?c、?v、?x 三种模式变量的区分，本质上是给匹配加上"类型约束"——常量只能配常量，变量只能配变量，任意量则无约束。

演讲者感叹：造一门语言是非常有趣的事，你一直在做这件事，而最有威力的设计工作，往往就是"造一门语言来解决问题"。

四、化简器 simplifier 与规则集 [13:50]

要点

定义通用程序 simplifier，输入是一个规则集，输出是一个过程。
输出的这个过程专门用来化简"含有这些规则所涉及对象"的表达式。
例如 (define dsimp (simplifier derivative-rules)) 之后，dsimp 就是专门化简含导数表达式的过程。

详细说明

运行示例：

(dsimp '(derivative (+ x y) x))

返回结果：(+ 1 0)

推导：(+ x y) 对 x 求导 = x 对 x 求导 + y 对 x 求导 = 1 + 0。

演讲者说：我就在这个层次上做化简，这已经是很"简化"的了。

拓展：代数化简规则集

除了求导规则，还可以写代数操作规则，例如：

任何操作符作用于两个常量 E1、E2，结果就是直接算出 E1 op E2。
(+ 0 E) → E；(* 1 E) → E；(* 0 E) → 0。
常量合并：(* ?e1 (* ?e2 ?e3)) 中若 e1、e2 都是常量，先相乘再放回 e3。
分配律：(* C (+ D E)) → (+ (* C D) (* C E))。

易错点（演讲者自曝的 bug）： 有一条规则把 (op E1 E2) 交换成 (op E2 E1) 以"把常量往前挪"，但如果操作符是除法，交换会改变结果——所以这是规则集里的一条 bug。规则写得不谨慎，就会引入错误甚至死循环。

考点：规则集是数据，可以任意制定；但规则的正确性、终止性由写规则的人负责。

五、整体架构：匹配器与实例化器 [18:30]

要点

把规则集想象成"一叠牌"（a deck of rules），每张牌有模式和骨架。
核心两个部件：
- 匹配器（matcher）：接收"模式"和"表达式"，输出字典（dictionary）。
- 实例化器（instantiator）：接收"骨架"和字典，输出新表达式。
字典记录"哪个模式变量匹配到了哪个子表达式"。
匹配器→字典→实例化器→新表达式→再送回匹配器，形成循环。

详细说明

演讲者用生动的比喻：可以把这个过程想象成一种"有机过程"——一锅汤里有很多酶（enzyme），它们附着到表达式上、改变它、然后离开（像钥匙和锁的匹配），表达式就一直变化，直到不再能变化为止。

理解：这是一个"重写系统"（rewrite system）的直观图景。规则像化学反应，表达式像分子，化简就是不断施加反应直到达到"不动点"。

易错点：递归死循环风险。 学生提问："这样会不会陷入递归循环？" 演讲者回答：会。如果规则写得不好，任何足够强大的语言都可能写出死循环。做代数操作的程序尤其容易不终止。

拓展：演讲者提到，有些语言设计者认为"模式匹配 + 规则应用"重要到应该成为语言的一部分，比如 Prolog。但他坚持：与其依赖语言设计者，不如教你自己造（roll your own）。

六、匹配器的内部结构 [22:00]

要点

匹配器的基本形态：输入模式 + 表达式 + 字典，输出新字典（在原字典上扩充匹配结果）。

匹配器是一个大型 case 分析程序，主要分支：

原子模式的处理。
模式变量的处理（三种：任意常量、任意变量、任意表达式）。
一般情况（general case）：同时遍历模式树与表达式树。

详细说明

一般情况的处理（最重要）：

表达式通常可以分成"前半"和"后半"（car 与 cdr）。
先匹配两者的 car，得到一个字典；再用这个字典去匹配两者的 cdr。
字典像一条线一样贯穿整个结构（threads through the entire structure）。

推导：字典作为递归的"累积器"，car 匹配的结果传给 cdr 匹配使用，这样前面匹配到的变量绑定能约束后面的匹配。

失败传播：

匹配可能失败（返回 failed 符号）。
因为匹配器把"上一次匹配的字典"作为输入，所以必须能传播失败。
条件表达式的第一个子句就是处理失败传播的。

易错点： 若模式不是原子的、而表达式是原子的（无法再拆），必须判为失败。这是"模式比表达式结构更复杂"时的失败情况。

原子模式的处理：

若模式原子、表达式原子、且两者相同 → 字典不变，匹配成功。
若两者不同（如 + 配 *）→ 失败。
若模式原子但表达式是复合的 → 失败。

三种模式变量的处理：

?c x（任意常量）：先检查表达式是否为常量；不是则失败；是则扩充字典。
?v x（任意变量）：先检查表达式是否为变量；是则扩充字典。
?x（任意表达式）：不检查任何语法，直接扩充字典。
扩充字典内部还有失败检查：若某模式变量已有值，而新匹配到的东西与旧值不等价，则失败。

七、匹配过程实例演示（树上同步遍历） [24:30]

要点

用一个具体例子演示匹配器如何同时遍历两棵树。

详细说明

模式：(+ (* ?x ?y) ?y) 即：找一个"和"，其第一个加数是乘积，且该乘积的第二个因子与这个和的第二个加数相同。

表达式：(+ (* 3 x) x)

遍历过程：

比较两棵树的左枝：都是 +，匹配成功。
比较下一层：都是 *，匹配成功。
模式变量 ?x 对上 3 → 字典记 x = 3。
模式变量 ?y 对上 x → 字典记 y = x。
继续走，模式中的 ?y 又要求匹配 x，而字典里 y 已经是 x → 一致，成功。

反例（失败情形）：若表达式是 (+ (* 3 x) 4)，则第二个 ?y 要求匹配 4，但字典里 y = x，两者不等 → 匹配失败。

易错点： 这个例子清楚展示了"同名模式变量一致性"如何在遍历中逐步建立约束，以及不一致时如何触发失败。

思考：匹配器本质是在做"带约束的树同构检查"，模式变量是"可绑定的洞"，字典是约束集。

八、实例化器 instantiator 的内部结构 [28:40]

要点

实例化器的目的：给定骨架 + 字典，生成新表达式。

对骨架做递归前序遍历（recursive tree walk）。
遇到骨架变量（skeleton evaluation，规则中以冒号开头的形式）→ 查字典求值。
遇到普通原子 → 原样返回。
遇到复合结构 → 递归实例化 car 与 cdr 后重新组合。

详细说明

演讲者说：实例化骨架这件事一点都不难。

evaluate 的细节（部分展示）：

若表达式是原子 → 查字典。
否则 → 应用一个过程（把操作符部分查字典得到的结果作为过程），并把各参数查字典后传给它。

演讲者提醒："你们现在看到的是魔法（magic）"——evaluate 里涉及 lambda 的部分会稍后讲清，今天先不必深究细节。

拓展：这里暗示了后面要讲的"环境模型"与"求值器"内容——字典的求值其实就是一个微型解释器。

九、字典（Dictionary）的抽象与实现 [31:30]

要点

字典不暴露具体结构，是一个抽象对象（abstract）。
它可以实现为：序对集合、列表对、花哨的表格机制，甚至就是一个函数。
关键操作：extend-dict（扩充字典）、lookup（查找）。
字典本质上是"函数/映射"：模式变量名 → 匹配到的值。

详细说明

学生反复追问："字典到底长什么样？是有序对吗？" 演讲者回答：

这没告诉你，我们保持抽象。为什么要知道它是什么？它是一个函数。函数可以是一组有序对，可以是列表对，可以是表格，也可以是函数本身。这由以后实现它的人（"George"）决定。

extend-dict 需要的信息：

要绑定值的模式变量（三种模式变量情形）。
它匹配到的表达式（值）。
原字典（已积累的绑定）。
返回一个新字典。

易错点（学生困惑点）： 为什么不在匹配时就做替换？演讲者解释：匹配与实例化是独立的单元。匹配阶段只负责建立"变量→值"的字典，替换只发生在实例化阶段（那时才有骨架）。匹配时根本不知道骨架长什么样，无法替换。

理解：这是"两阶段分离"的设计——先收集绑定（match），再应用绑定（instantiate）。分离让匹配器可复用于不同骨架。

十、控制结构：化简器如何应用规则 [36:00]

要点

化简器要处理多重交错的循环：

遍历所有子表达式：对输入表达式的每个子表达式都要处理（递归树遍历）。
对每个节点轮询所有规则：每个规则都来看这个节点。
规则匹配则替换：用实例化骨架产生的新表达式替换该节点。
递归化简新表达式：替换后产生的新表达式本身需要再化简。
直到不再变化：反复进行，直到表达式不再改变。

详细说明

演讲者称之为"垃圾进垃圾出式化简器"（garbage in garbage out）——它是递归的化简器：要化简一个复合对象，就假设它的各个部分已经化简，然后自底向上组合。

理解：这就是"结构化递归"的典型模式——先递归化简子部分，再对组合结果尝试规则。

十一、化简器的代码结构 [38:00]

要点

simplifier 接收规则集，返回一个在"该规则集作用域内定义"的过程 simplify-x。

内部包含：

递归遍历：simplify（化简任意表达式）与 simplify-parts（化简表达式的各部分）。
规则尝试：try-rules 与 scan。

详细说明

递归遍历部分：

若表达式是复合的 → 先化简所有部分，得到新表达式，再对它尝试规则。
若表达式是简单的（如原子）→ 也尝试规则（因为规则可能想展开它，比如把 π 展开成 3.14159...，虽然不一定这么做，但没理由不做）。

化简各部分：

空表达式 → 直接返回。
否则 → (cons (simplify (car e)) (simplify (cdr e)))。

演讲者提示：这段代码可以改写成更紧凑的形式，用 map 代替 simplify-parts：

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

理解：map 把"对列表每个元素施加同一操作"的模式抽象出来，省掉了辅助过程。这是"高阶过程"威力的体现。

十二、try-rules 与 scan：规则尝试机制 [42:00]

要点

try-rules 定义内部过程 scan，从整个规则表开始逐个尝试。
scan 逻辑：
- 若没有更多规则 → 无法再化简，返回表达式本身。
- 否则 → 用空字典匹配第一条规则的模式与表达式。
  - 匹配失败 → 试剩下的规则。
  - 匹配成功 → 实例化该规则的骨架，递归化简结果，返回。

详细说明

演讲者强调：虽然这是个复杂程序，但每个复杂程序都由许多简单的小块组成。

关键编程心法：不要去想递归的实际展开模式。 演讲者原话大意：如果你试图在脑子里展开这个递归的执行路径，你会被绕晕。好的编程与设计的关键，是知道什么不必去想。

理解：这就是"抽象屏障"与"契约式编程"——只要你相信 simplify 的规格（输入表达式、输出化简后的表达式），就可以在 try-rules 里放心调用它，无需关心它内部怎么递归。

simplify 的规格（specification）：

输入：一个表达式。
输出：按规则集化简后的表达式。
复合表达式：先化简各部分，再对结果尝试规则。
简单表达式：直接尝试所有规则。
规则匹配成功时，try-rules 会对"实例化骨架的结果"再次调用 simplify。

十三、字典的实现细节与课程收尾 [46:00]

要点

字典用 A-list（association list，关联列表） 表示——一种用列表做表格的惯用法。
由序对（pairs）构成，有专门的查找过程（如 assq），可在手册中查到。
extend-dict 唯一有趣之处：
1. 取出模式变量的名字。
2. 在字典中查找它是否已有值。
3. 没有 → 加入新绑定。
4. 已有 → 检查新值是否与旧值相等；相等则字典不变，否则失败。

详细说明

演讲者总结：打开任何程序，你都会发现里面全是简单的小块。

本讲回顾：

介绍了要实现的"模式替换语言"。
展示了规则示例。
讲了匹配与实例化——规则运作的两半。
讲了应用规则到表达式以做代数化简的控制结构。

演讲者最后说：到这里，这个程序就基本讲完了，可以提问了。

关键标签 / 关键词

SICP 6.001 符号操作 模式匹配 pattern matching 规则代换 rule substitution 匹配器 matcher 实例化器 instantiator 字典 dictionary 模式变量 pattern variable 骨架 skeleton 化简器 simplifier 重写系统 rewrite system 递归 不动点 抽象屏障 A-list extend-dict try-rules scan 符号微分 代数化简 元编程 Prolog