SICP 第 13 讲：元循环求值器（上）

视频封面

视频元信息

课程：MIT 6.001 Structure and Interpretation of Computer Programs（1986 原版）
本讲主题：元循环求值器（上）——用 Lisp 写一个 Lisp 求值器
主讲：Hal Abelson

内容摘要（TL;DR）

本讲在黑板（blackboard）上完整写出一个 Lisp 求值器——即"元循环求值器"（metacircular evaluator）。核心是两个过程：eval（对表达式做分派：数字、符号、quote、lambda、cond、一般应用）与 apply（区分原始过程与复合过程）。随后用环境模型手工"代入"求值一个嵌套 lambda 表达式，并讨论不动点语义：递归定义（如 expt）可以理解为函数的不动点，引出 Y 组合子（Curry 悖论组合子）。

一、从"通用机器"谈起：EVAL 的意义 [02:00]

1.1 电路图式程序与通用机

课程先回顾了"用电路图（wiring diagram）表示程序"的视角：一个 factorial 机器，其内部又包含 factorial 机器，因此可能有无限多个部件，深度不可预知。
这种"递归包含"正是程序记号的本质——它是一张可以自我复制/自我嵌套的接线图的文字描述。
有人提议把编程语言做成图形化的，Abelson 本人对此持怀疑态度：图形化占用页面空间大、难以打包成 listing、难以编辑。

1.2 通用机（Universal Machine）

计算世界中最惊人的事实之一：存在通用机（universal machine）。
EVAL 就是这样一台机器：它以"另一台机器的描述"作为输入。例如把 factorial 机器的接线图作为输入，EVAL 就变成 factorial 机器的模拟器——输入 6，输出 720。
最令人惊叹的是：这台通用机可以画在黑板（blackboard）上。
对比：在模拟电子世界，理论上也可以造一台"通用模拟机"——给它一个低通滤波器（one-pole low-pass filter）的电路图，它应能把自己配置成具有相应频率响应的滤波器。但这样的机器极难制造，绝无可能画在黑板上。

考点：通用机 vs 专用机 通用机的本质是"接受程序描述作为数据，并模拟该程序"。这正是解释器（interpreter）与编译器（compiler）的理论基础，也是"程序即数据"（homoiconicity）思想的体现。

1.3 讲者的"仪式感"

Abelson 特意穿上西装外套、戴上合适的帽子，以示对"通用机"这一伟大概念的敬意。
他开玩笑警告：本讲会出现一定程度的"神秘主义"（mysticism），可能让听众心智受到困扰，心理脆弱者建议离场。

思考：这种"仪式感"并非纯粹的幽默，它暗示接下来要讲的内容——用 Lisp 写 Lisp 求值器——在理论上具有循环自指的性质，容易让人产生"这难道不是循环论证吗"的困惑。

二、黑板上的求值器：eval 的主体结构 [05:15]

2.1 关于代码风格的声明

Abelson 明确声明：黑板上写的程序是"丑陋、肮脏、恶心"的，不是他作为专业人士会写的方式。原因：

使用具体语法（concrete syntax），即大量使用 car、cdr——这正是他之前告诫学生不要做的。
目的是让程序足够小、紧凑，能塞进黑板，让听众看到全貌。
因此刻意使用短名字，而非平时用的长名字。这是一个权衡（trade-off）。
重要提醒：不要模仿这种写法，这纯粹是为了演示效果。

2.2 省略的部分

这是一个相当完整的解释器，但省略了 define 和 assignment（赋值）。
省略原因：一是它们不是数学上必需的（后面会证明），二是它们占空间。

2.3 eval 的骨架

(define (eval exp env)
  (cond ((number? exp) exp)
        ((symbol? exp) (lookup exp env))
        ((eq? (car exp) 'quote) (cadr exp))
        ((eq? (car exp) 'lambda) (list 'closure (cdr exp) env))
        ((eq? (car exp) 'cond) (evcon (cdr exp) env))
        (else (apply (eval (car exp) env)
                     (evlis (cdr exp) env)))))

eval 接受两个参数：一个表达式（expression）和一个环境（environment）。像所有有趣的程序一样，它是一个分情况分析（case analysis）。

分派（dispatch）的各分支

表达式类型	处理方式	说明
数字（如 3）	返回自身	数字求值为它自己
符号（如 x、car）	在环境中查找（lookup）	符号是变量，代表其他东西
quote 表达式	返回 `(cadr exp)`	引号对象求值为它本身
lambda 表达式	构造 closure 对象	捕获当前环境
cond 表达式	交给 evcon 处理	条件表达式
其他（一般应用）	求值 operator 和 operands，再 apply	组合式（combination）

2.4 各类表达式的详细说明

（1）数字

如果表达式是数字，直接返回该数字本身。

（2）符号

符号如 x、n、car 等，是变量，代表其他东西。
求值符号 = 在环境中查找它的值。例如 x 可能变换为 3；car 可能变换为某个过程对象（内部可能是机器语言代码）。
环境本质上是一个字典（dictionary），把符号名映射到它们的值。它只是一张表，lookup 就是这张表的访问例程。

易错点：环境是什么 环境 = 从符号名到值的映射表。视频中强调"that's all it is"，但具体实现（如何组织表结构）留到后面讲。理解这一点对掌握环境模型至关重要。

（3）quote 表达式

像 'who 这样的非数字常量，会被语法糖转换为列表结构 (quote who)。
这个转换不在求值器内部完成，而是在更早的阶段（reader 或类似环节）完成。
这样 eval 就可以通过检查表达式的 car 是否为 quote 来识别引用表达式。
若 car 是 quote，则返回 (cadr exp)——即列表的第二个元素，也就是被引用的对象本身。

（4）lambda 表达式

lambda 表达式的值是一个过程对象（procedure object）。
关键区分：过程不是 (lambda (x) ...) 这个表达式本身——那只是它的文本描述。
过程对象应包含一个环境作为其组成部分（针对词法作用域语言）。
需要一个类型标志（type tag）来区分 lambda 产生的过程与原始过程（primitive）。这里随意地命名为 closure（历史原因）。

closure 对象的组成部分：

类型标签：closure
绑定变量表（bound variable list）：如 (x)
过程体（body）：如 (+ x y)
环境：创建 lambda 时的当前环境
这个表示用户永远不应看到，纯粹是过程对象的内部表示。

考点：闭包（closure）的核心 闭包 = 代码 + 捕获的环境。lambda 表达式被求值时，求值器把当时的环境捕获进过程对象。这正是环境模型中"过程构造规则"的实现：lambda 表达式产生的过程，其自由变量在该 lambda 被求值时的环境中解释。

（5）cond 表达式

形如 (cond (p1 e1) (p2 e2) ...)，每个子句包含一个谓词和一个待求值表达式。
若 car 是 cond，则把 (cdr exp)（所有子句）和当前环境交给 evcon 处理。

（6）一般应用（组合式）

形如 (+ x 3)，是运算符作用于运算对象。
这是"默认情况"（else 分支），不属于任何特殊形式。
处理方式：
1. 求值 (car exp)（运算符）得到过程；
2. 求值 (cdr exp)（所有运算对象）得到参数列表——这一步交给 evlis；
3. 把过程应用到参数上——这一步交给 apply。

2.5 关于特殊形式的讨论

如果写专业程序，应该用数据导向（data directed）的方式组织分派，而不是一串 cond。这样可以方便地添加新特殊形式、运行更快。
但本讲不关心这些，目的是看整体。
重要观点：语言中的特殊形式/保留字数量不应超过一个人手指加脚趾能记住的数量。Abelson 对拥有数百个保留字的语言非常不满。

思考：这体现了 SICP 的核心哲学——语言的核心应当极小，其余一切都可以用这些核心构造出来。

三、apply 的结构 [15:35]

3.1 apply 的职责

apply 接受一个过程和一组参数（两者都已求值完毕），把过程应用到参数上。

(define (apply proc args)
  (cond ((primitive? proc) (apply-primop proc args))
        ((eq? (car proc) 'closure)
         (eval (caddr proc)
               (bind (cadr proc) args (cadddr proc))))
        (else (error "Unknown procedure type"))))

3.2 两种情况

（1）原始过程（primitive）

具体实现方式不重要，可能是通过类型信息判断。
执行一些"魔法"——直接跳到机器语言，执行 add 指令等。
有趣的事实：其实不需要任何原始过程也能工作（通过 lambda 演算的技巧），但有它们更方便。

（2）复合过程（compound，由 lambda 产生）

检查类型标签是否为 closure。
处理方式：在"扩展后的环境"中求值过程体。
扩展方式：把过程的环境与"形式参数绑定到实参"的新绑定结合。

用自然语言表述这个长句：

求值一个过程对参数的应用 = 在"该过程的环境 + 形式参数到参数的绑定"所产生的新环境中，求值该过程体。

3.3 访问 closure 各部分的 car/cdr 链

过程体（body）：(caddr proc)，即 (car (cdr (cdr proc)))
形式参数（formal parameters）：(cadr proc)，即 (car (cdr proc))
环境：(cadddr proc)，即 (car (cdr (cdr (cdr proc))))

Abelson 边写边说"horrible, isn't it?"——这正是具体语法风格丑陋的体现。

3.4 错误检查与扩展性

可以加一个 else 分支检查"未定义的过程类型"。
在真实系统中，这里会做分派，可能还有其他情况，如：
- 这是不是编译代码？区分解释器产生的代码和编译器产生的代码很重要。
- 这是不是其他语言的程序？

考点：eval 与 apply 的相互递归 eval 处理组合式时调用 apply，apply 处理复合过程时又调用 eval。这个"大循环"正是解释器的核心。视频后半段会专门用图示强调这一点。

3.5 抽象语法 vs 具体语法

当前写的是具体语法求值器，内建假设"表达式是列表"（用 car 取运算符、cdr 取运算对象）。
存在抽象语法求值器，其中这些部分有抽象名字如 operator、operand。这种版本可以重新编程为支持 Algol 等语言。

四、辅助过程：evlis、evcon、bind、lookup [24:30]

4.1 evlis

(define (evlis l env)
  (if (null? l)
      '()
      (cons (eval (car l) env)
            (evlis (cdr l) env))))

把一串运算对象（operands）映射为参数（arguments）。
之所以完全展开写而不使用 map，是出于"神秘的原因"：要让这个求值器简单到能理解它自己。
这个求值器不使用函数式参数、不产生函数值。因此即使求值的是 Algol（不允许过程值），也能用这个求值器。
它是"所有可能语言求值器的内核"（the kernel of all possible language evaluators）。

4.2 evcon

(define (evcon clauses env)
  (cond ((null? clauses) '())
        ((eq? (caar clauses) 'else)
         (eval (cadar clauses) env))
        ((eval (caar clauses) env)
         (eval (cadar clauses) env))
        (else (evcon (cdr clauses) env))))

处理条件表达式。
递归出口：若没有更多子句，返回空列表（也可以选择报错，这是程序员的任意选择）。
else 子句：若第一个子句的谓词是 else，返回求值该子句表达式的结果。
谓词为真：若求值第一个谓词得到真值，返回求值该子句表达式的结果。
谓词为假：丢弃第一个子句，递归处理剩余子句。

4.3 bind

用于构造新的环境结构（environment structure）。
环境结构表示为帧的列表（list of frames）。
bind 通过"把一个新帧 cons 到现有环境结构上"来创建新环境。
新帧 = 把过程的形式参数与传入的实参配对（pair up）的结果。

4.4 pairup

把变量列表与值列表配对。
若变量和值同时用完，正常结束。
若值先用完（变量还有），说明参数太少。
若变量先用完（值还有），说明参数太多。
一般情况：把第一对（第一个变量，第一个值）cons 到"剩余变量与剩余值配对"的结果上。

4.5 lookup

(define (lookup sym env)
  (if (null? env)
      (error "Unbound variable")
      (let ((val (assq sym (car env))))
        (if (null? val)
            (lookup sym (cdr env))
            (cdr val)))))

在环境中查找符号。
若环境为空，报"未绑定变量"错误。
否则，在环境的第一个帧中用 assq 查找。
若找到，返回该值单元（value cell）的 cdr（即值部分）。
若未找到，继续在剩余帧中查找。

4.6 assq

(define (assq sym alist)
  (cond ((null? alist) '())
        ((eq? sym (caar alist)) (car alist))
        (else (assq sym (cdr alist)))))

接受一个符号和一个配对列表（alist）。
若列表为空，返回空。
若符号是列表第一项的 car，返回该配对。
否则在剩余列表中查找。

易错点：视频中的 bug Abelson 在写 assq 时一度写成 (eq? sym (caar alist)) 后又口误说成"cr, c-a-a-r"，并说"sorry for producing a bug"。这提醒我们：即便是大师也会在黑板上一时写错，代码审查和测试很重要。

五、手工代入求值：嵌套 lambda 的例子 [30:45]

5.1 待求值的表达式

(((lambda (x)
    (lambda (y) (+ x y)))
  3)
 4)

这是一个接受一个参数 x 的过程，其返回值是接受一个参数 y 的过程，后者把 x 和 y 相加。
先应用 x 过程于 3，x 绑定为 3。
再把结果（一个 y 过程）应用于 4。
最终应得到 3 + 4 = 7。

5.2 初始环境 E0

全局环境 E0 包含 +、*、-、/、car、cdr、cons、eq? 等原始过程的定义。
这些是"机器与生俱来"的东西。

5.3 求值步骤（代入法）

由于这个解释器没有赋值和定义，所以没有副作用，可以放心使用代入（substitution）。

步骤 1：识别为组合式（application），不是特殊形式。

运算符：((lambda (x) (lambda (y) (+ x y))) 3)
运算对象：(4)

步骤 2：先求值运算对象。

(evlis '(4) E0) → (cons 4 '()) → (4)

步骤 3：求值运算符（本身又是一个组合式）。

运算符：(lambda (x) (lambda (y) (+ x y)))
运算对象：(3)

步骤 4：求值 lambda 表达式，产生 closure 对象。

closure 包含：类型标签、绑定变量表 (x)、过程体 (lambda (y) (+ x y))、捕获的环境 E0。

步骤 5：apply 这个 closure 于参数 (3)。

创建新环境 E1：父环境是 E0，新增绑定 x = 3。

步骤 6：在 E1 中求值过程体 (lambda (y) (+ x y))。

这又是一个 lambda，产生新 closure，捕获 E1。
closure 包含：绑定变量表 (y)、过程体 (+ x y)、环境 E1。

步骤 7：apply 这个新 closure 于参数 (4)。

创建新环境 E2：父环境是 E1，新增绑定 y = 4。

步骤 8：在 E2 中求值过程体 (+ x y)。

求值 +：在 E2 中找不到，沿父链 E1 → E0 找到原始加法过程。
求值 x：在 E2 中找不到，在 E1 中找到，值为 3。
求值 y：在 E2 中找到，值为 4。
应用原始加法过程于 (3 4)，得到 7。

5.4 环境链图示

E0: {+, *, -, /, car, cdr, cons, eq?, ...}
     ↑
E1: {x = 3}   (父环境 E0)
     ↑
E2: {y = 4}   (父环境 E1)

理解：这个例子完美展示了词法作用域（lexical scoping）——内层 lambda 中的 x 之所以能找到值为 3，是因为它捕获了定义时的环境 E1，而非调用时的环境。

考点：为什么 x 绑定到 3 而不是 4 视频中有学生提问此问题。关键在于读对表达式：((lambda (x) ...) 3) 是一个组合式，3 是它的运算对象，所以 x 绑定为 3。这个组合式的结果（一个 y 过程）再被应用于 4。所以 x=3、y=4。

六、eval 与 apply 的大循环 [39:15]

Abelson 用一个图示总结：

        eval
   表达式 + 环境  ←→  过程 + 参数
        apply

eval 处理表达式和环境，产生过程和参数（给 apply）。
apply 处理过程和参数，对复合过程产生表达式和环境（给 eval）。
这个大循环就是解释器的核心状态：要么是"表达式 + 环境"，要么是"过程 + 参数"。
存在小的子循环：
- eval 直接处理数字、符号、quote、lambda、cond（"琐碎"的事）。
- eval 依次求值所有参数（不有趣）。
- apply 处理原始过程如 +（不有趣）。
但本质的大循环是 eval ↔ apply 的相互递归。

思考：这个循环也解释了为什么求值器能"理解自己"——因为 eval 和 apply 本身就是用同样的机制定义的过程，可以互相调用。

七、元循环求值器的哲学困惑 [41:30]

7.1 循环论证的质疑

Abelson 提出一个尖锐的问题：

"我在黑板上写了一个 Lisp 程序，本意是作为 Lisp 的解释器。但你需要一个 Lisp 解释器才能理解这个程序。那么这个程序怎么能告诉我关于 Lisp 的任何知识呢？这难道不是完全空洞（vacuous）的吗？"

7.2 类比：埃舍尔（Escher）的画

视频展示了埃舍尔风格的画：两只手互相绘制对方。
埃舍尔是极聪明的艺术家，他只是不知道这些"精灵"的名字。

八、递归定义的意义：不动点语义 [43:00]

8.1 递归定义的问题

考虑指数函数定义：

(define (expt x n)
  (if (= n 0)
      1
      (* x (expt x (- n 1)))))

这是递归定义：用 expt 自身定义 expt。
高中数学老师会警告你这种自指定义有问题。这种警告有道理吗？

8.2 类比：联立方程

考虑三组联立线性方程：

方程组	解的情况
x + y = 3, x - y = 1	唯一解
2x + 2y = 6, x + y = 3	无穷多解
x + y = 3, x - y = 2	无解

三组方程形式相同，但解的个数不同。
结论：不能仅凭形式判断定义是否有意义，必须看具体内容（如系数）。

考点：形式 vs 内容 递归定义是否有意义，不能光看形式（"它自己定义自己"），必须看内容。这是理解不动点语义的关键前提。

8.3 不动点（Fixed Point）视角

把方程 x = 3 - y、y = x - 1 看作一个线性变换 T：

(x, y) = T(x, y)

我们要找的是 T 的不动点——即满足 (x, y) = T(x, y) 的点。
对于 expt 定义，可以构造一个函数 F：

(define (F g)
  (lambda (x n)
    (if (= n 0)
        1
        (* x (g x (- n 1))))))

expt 是 F 的不动点：F(expt) = expt。
即：如果把一个好的 expt 过程代入 F，得到的结果仍是好的 expt 过程。

8.4 通过迭代寻找不动点

类比：在计算器上按 cos 键反复迭代，会收敛到约 0.73–0.74 的不动点。

对 expt 的 F，构造近似序列：

E0：对任何参数都报错的过程（最差的近似）。
E1 = F(E0)：能正确处理 n=0 的情况（任何数的 0 次方 = 1），其他情况报错。
E2 = F(E1)：能正确处理 n=0 和 n=1 的情况。
E3 = F(E2)：能正确处理 n=0、1、2 的情况。
...
En：能正确处理 n 从 0 到 n-1 的所有情况。

断言（无证明，证明极难）：

expt = lim(n→∞) En
     = F(F(F(F(...F(...)))))

即 expt 是 F 的无限次嵌套。这个"无限嵌套"可以用 Y 组合子构造。

考点：不动点语义 由 Scott 和 Strachey 发明的指称语义（denotational semantics）用拓扑学证明了：在我们关心的情形下，这样的不动点存在。这是递归定义合法性的数学基础。

九、Y 组合子：构造无限嵌套 [51:30]

9.1 最简单的无限循环

((lambda (x) (x x))
 (lambda (x) (x x)))

这是最简单的无限循环。
原因：把参数代入形式参数时，每个 x 都被替换成整个表达式本身，产生自我复制。

9.2 Curry 悖论组合子 Y

(define Y
  (lambda (f)
    ((lambda (x) (f (x x)))
     (lambda (x) (f (x x))))))

由逻辑学家 Curry（1930 年代）提出，称为 Curry 悖论组合子（Curry's paradoxical combinator）。
关键性质：Y(F) = F(Y(F))。
即：Y 应用于某函数，产生该函数的不动点（如果存在）。

9.3 推导 Y(F) = F(Y(F))

Y(F)
= ((lambda (x) (F (x x))) (lambda (x) (F (x x))))
→ 代入 x = (lambda (x) (F (x x)))
= F((lambda (x) (F (x x))) (lambda (x) (F (x x))))
= F(Y(F))

把 Y(F) 代入 F，得到 Y(F) 自身——这正是不动点的定义。

9.4 回到求值器

黑板上写的那些求值器递归方程是联立的（simultaneous），涉及多个变量（eval、apply、evlis、evcon 等）。
list 的意义就是这套递归方程的不动点：如果我知道 list 是什么，代入到 eval、apply 等右边，那么左边也应该得到 list。
但不动点是否存在并不显然，需要用 Scott-Strachey 的方法论证。

十、危险论证：极限的陷阱 [56:30]

Abelson 特意用一个"反面教材"警告学生：

10.1 收敛的例子（正确）

U = 1/2 + 1/4 + 1/8 + ...
U - 1 = 1/2 + 1/4 + 1/8 + ...
2(U - 1) = 1 + 1/2 + 1/4 + ... = U
∴ 2U - 2 = U
∴ U = 2  ✓

10.2 发散的例子（错误）

V = 1 + 2 + 4 + 8 + ...
V - 1 = 2 + 4 + 8 + ...
(V - 1)/2 = 1 + 2 + 4 + ... = V
∴ V - 1 = 2V
∴ V = -1  ✗（明显错误）

易错点：极限论证的危险 同样的代数操作，在收敛级数上给出正确答案，在发散级数上给出荒谬答案。在玩极限论证时必须非常小心，论证必须良构（well-formed）。这类论证在不动点理论中尤其危险。

10.3 关于收敛条件的讨论

有学生问：收敛性与函数性质（线性/非线性）的关系？

Abelson 回答：

他不知道一般情形下如何判断收敛。
存在一类技术性的 F（单调、连续等条件）具有收敛性质，但从 F 的定义判断它是否具有这些性质非常困难。
推荐阅读：Joseph Stoy 的 Denotational Semantics: The Scott-Strachey Approach（MIT Press）。这本书详细推导了这些内容，"足以让你恐惧"，但确实可读。

十一、关于 define 的补充讨论 [60:30]

有学生问：既然可以不用 define，那 define 是不是只是"记住一个值以便以后应用"的副作用？