SICP 第 20 讲：存储分配与垃圾回收

视频封面

视频元信息

主题：存储分配（Allocation）、垃圾回收（Garbage Collection）、可计算性收尾
讲师：Hal Abelson（SICP 作者之一）

内容摘要（TL;DR）

本讲揭开 SICP 最后一个"谜团"：cons、car、cdr 这些基本操作在真实机器上如何实现。先用哥德尔编码说明数据可用纯数字表示，再讲线性内存中 car/cdr 数组的实现、自由表分配法，最后深入标记-清扫（mark-sweep）与 Minsky 复制式垃圾回收算法，并以停机问题不可判定为全课收尾。

一、遗留的谜团：数据结构的"胶水"是什么 [00:18]

核心问题：此前课程中我们一直在"盲目地"使用 cons、car、cdr，假设总有下一个可用单元，却从未说明这些操作在物理机器上如何实现。

要点：

我们说过 cons 等价于"拥有过程"，但这并不能真正解决问题——过程本身又需要环境结构等复杂机制，而这些机制在模型中又建立在 cons 之上，形成循环依赖。
真正的问题是：数据结构赖以构成的"胶水"究竟是什么？
之前展示的机器模型只有控制器、寄存器、栈，从未提及更大的内存（memory）——这正是本讲要处理的对象。
关键定性：这是一个纯粹实现层面（purely implementational）的问题，与语义无关。

易混淆点：数据抽象的"胶水"问题不是语义问题，而是实现问题。抽象屏障之上的一切行为都不依赖具体实现方式，但实现必须存在。

二、用数字表示一切：哥德尔编码 [01:37]

理解：这是"存在性证明"——先说明数据可以用极简的原始材料（数字）构造出来，再讨论工程上可行的方案。

要点：

1930 年代逻辑学家哥德尔（Gödel）发明了用数字编码复杂表达式的巧妙方法。
编码思路：为每个表达式分配一个数字，通过组合各部分的数字来制造整体数字。
在本课程语境下的类比方案：
- 若对象用数字表示，则 (cons x y) 可表示为 2^x × 3^y
- 提取部分：(car n) = n 中因子 2 的个数；(cdr n) = n 中因子 3 的个数

致命缺陷：数字位数会迅速膨胀到超过宇宙中质子总数的量级，因此该方案只有理论意义，无法实际使用。

思考：这个例子说明"可实现"与"可工程化"是两回事。哥德尔编码在理论上完备，但空间复杂度指数级爆炸，这提醒我们评估方案时不能只看正确性。

三、线性内存与 car/cdr 数组 [03:38]

要点：

我们一直用"小盒子"（pigeon holes，格子）思考 cons，画成树形结构。
但半导体厂商实际提供的是线性内存：一大排格子，每个格子容量固定。
每个格子由地址（address）索引（0、1、2、3……），地址写成数字只是为了方便，关键是它们互不相同、可顺序访问。
复杂列表（如 25 个元素）装不进单个格子。

如何在树结构与线性内存之间架桥：

假设厂商允许内存格子大到足以容纳另一个格子的地址，就基本可行。
实际还需要多一点空间存放标签（tag），描述该位置存放的是什么类型。
若硬件不直接支持，也可通过巧妙的组合方式拼出来。

四、经典实现：car 数组与 cdr 数组 [05:51]

要点：

标准做法：把内存分成两部分——一个数组叫 cars，一个数组叫 cdrs。
两者是否为连续地址不重要，属于实现细节。
每个格子中存放的是带类型的对象（typed object），类型用字母前缀表示：
- P = pair（序对）
- N = number（数字）
- E = empty list（空表，列表结束标志）

示例结构：列表 ((1 2) 3 4)，即首元素是子列表 (1 2)，第二、三元素是 3 和 4。

用盒指针（box-and-pointer）记法画出后，将其映射到线性内存：

索引 1 处的格子：car 为 P5（指向索引 5 的序对），cdr 为 P2
P2：car 为 N3，cdr 为 P4
P4：car 为 N4，cdr 为 E（空表，列表结束）
P5：对应子列表 (1 2) 的结构

易错点：这里的"1、2、4、5"是内存地址索引，不是数据值本身。盒指针图中的指针，在线性内存中就是这些索引数字。

五、car/cdr 的寄存器机器实现 [09:12]

要点：

寄存器机器指令 (assign A (car B))（B 中存放序对的类型索引/指针）实际展开为对数组的索引访问。
引入抽象结构 vector（向量）：
- vector-ref：取向量名与索引，读取元素
- vector-set：设置向量中某元素
car 实现：(assign A (vector-ref cars B))，即用索引 B 去查 cars 数组
cdr 实现：类似地查 cdrs 数组
对数据结构的赋值（如 set-car!）同理，实现难度不大

理解：这里体现了抽象层次的下降——car 从"语言原语"降为"数组索引 + 类型标签"的组合操作。

六、存储分配：自由表（Free List）方案 [11:17]

问题：每次调用 cons 都需要一个新格子，必须知道哪里有未使用的内存。

要点：

分配方案很多，此处展示的只是其中一种（非本质，但方便且被广泛采用）。
自由表分配法（free list allocation）：把所有空闲内存用链表串起来，就像其他数据结构一样。
需要新格子时：取链表第一个，把 free list 更新为其 cdr，然后分配该格子。

自由表示例：free list 从位置 6 开始 → 指向 8 → 指向 3 → 指向 0 → 指向 15……

cons 的展开程序（(assign A (cons B C))）：

取 free list 当前头部（存入 A）
令 free list 变为该头部的 cdr
把 A 的 car 设为 B
把 A 的 cdr 设为 C

讲师自陈的"小作弊"：上述代码中没有设置新对象的类型标签为 pair。实际实现中需要设置若干标志位。也可以让 free list 本身由 pair 构成来回避此问题——这属于具体实现者的设计选择。

分配实例：若要在已有结构上分配表示 (1 1 2) 的新格子（其中 1 2 是之前列表的 car）：

从 free list 头部 6 取出
新 free list 从 8 开始
位置 6 存入数字 1，其 cdr 指向位置 5 的序对

七、内存有限与"无限"的幻觉 [15:14]

要点：

半导体内存是有限的，这是遗憾的现实。
快速估算：若每次 cons 耗时 1 微秒，一年约 π×10⁷ 秒，则机器寿命内约需 10¹⁴ 次 cons。
若有 10¹⁴ 字的存储，理论上永不会耗尽——这并非完全不合理（10¹⁴ 不算很大的数）。
但按当前经济状况，10¹⁴ 片内存极其昂贵，只能使用小得多的内存。

核心思想：我们需要制造无限的幻觉（illusion of infinity）。

人和计算机生命有限、观察次数有限，只需保证"每次查看时东西都在"。
即：无论实际有多少，只要保证每次访问时都有足够内容即可。

垃圾的来源：

环境帧：每次调用过程都构造环境帧，其生命周期可能只覆盖过程调用期间；若过程返回内部定义的过程，帧的生命周期等于被导出过程的生命周期。大量帧最终成为垃圾。
用户产生的垃圾：例如 append 的一种实现是先 reverse 第一个列表到空表，再 reverse 到第二个列表——中间结果（第一个列表的反转）此后永远不会再被访问。

思考：垃圾的本质是"可达性"的丧失，而非"无用性"的判定。垃圾回收器不去判断数据是否有意义，只判断它是否还能被访问到——这是可判定且高效的关键。

八、垃圾回收的核心定理：可达性 [21:48]

机器模型：

数据通路含若干寄存器（x、n、val 等）
一个 stack 寄存器指向栈结构
有限控制器（有限状态机）+ 控制信号与谓词结果
结构化内存（即前述 list memory），内含各种数据结构和栈

关键洞察：

这台机器的全部"意识"都在寄存器里。除非内存中的某个东西通过一系列数据结构与寄存器相连，否则机器不可能访问到它。

要点：

机器只能通过合法数据结构选择器（数组引用、cons 引用、car、cdr）访问内存。
不能谈论内存中的任意位置——因为无法到达它（名称是任意的，求值表达式时不允许"数数"）。
定理：从所有寄存器中的指针出发，递归地标记（mark）所有能通过选择器到达的位置；最终未标记的一切都是垃圾，可以回收，且不会影响计算的未来。

九、标记-清扫算法（Mark-Sweep）[24:33]

标记阶段步骤（以示例内存说明）：

所有标记初始为 0
从根（root，可把全部寄存器内容集中到一个根指针）开始
能访问到位置 1 → 标记
位置 1 含 P5 → 标记 5
5 的 car 是数字（不标记数字），cdr 是 7 → 标记 7
7 是空表，car 是数字，不再深入
回到位置 1，其含引用 2 → 标记 2
2 含引用 4 → 标记 4
4 引用 7（已标记，跳过）
至此所有可达结构标记完毕

清扫阶段步骤：

从头到尾扫描整个内存
遇到已标记的格子 → 取消标记（恢复为 0）
遇到未标记的格子 → 链入 free list

历史轶事：老 DEC PDP-6 计算机的标记-清扫回收器小到整个程序连同所需寄存器能装进机器的 16 个快速寄存器中，执行极快。

标记-清扫的固有缺陷：由于递归处理（先处理 car 再处理 cdr），需要辅助栈。这导致数据结构在 car 或 cdr 方向的递归深度受限。

但对 MacLisp（运行 Macsyma）等系统，处理数千项长的代数表达式也无问题，只要栈足够大就察觉不到限制。

改进算法（Deutsch-Schorr-Waite）：

由 Peter Deutsch、Herb Schorr（IBM）和 Waite 提出
无需辅助内存：向下走时反转指针记录来路，向上走时沿反转指针爬回
代价：算法非常棘手（"第一次写、前三次写都会有严重 bug"），且慢约 6 倍（内存引用次数大幅增加）

十、标记-清扫的缺点与复制式回收 [33:14]

标记-清扫的严重缺点：

地址空间越来越大时，扫描全部内存的代价极高
理想情况：只扫描有用部分，且对"确定有用"的部分少看几次

Minsky 复制式垃圾回收算法（Minsky-Fenichel-Yochelson）：

由 Minsky 于 1961 年为拥有 4096 字内存 + 磁鼓的 RLA PDP-1 发明
核心思想：只扫描"好结构"，将其复制到磁鼓并压缩，再换回内存
是已知最快的垃圾回收算法

算法机制（需约两倍于实际使用量的地址空间）：

from space：初始的"有用数据 + 垃圾"混合区
to space：复制目标区
步骤：
1. 从根指针开始，复制看到的第一个对象到 to space 起始处
2. 在原位置留下"破碎的心"（broken heart），记录对象被移到何处
3. 移动根指针
4. 扫描刚复制的对象，遇到的每个指针都当作根指针处理：
  - 若指向的对象已复制（有破碎的心）→ 用破碎的心指向的新地址替换该指针
  - 若未复制 → 复制到 to space 下一位置，移动 free pointer，留下破碎的心
5. 当扫描指针追上 free pointer，说明全部复制完成
6. 剩余空区可做成 free list（但此类系统通常不这么做，而是继续按此方式分配）

"破碎的心"名称由来：1966 年一位实现该算法的朋友是位浪漫的人，如此命名。这是术语来源的趣闻，非技术必需。

理解：复制式回收同时完成了回收与压缩（compaction），因此分配时无需 free list，只需在 to space 中连续推进指针，分配效率极高。

实时化改进（Henry Baker）：

简单修改后可实时运行：无需停机回收，而是把 cons 操作与垃圾回收步骤交错执行，使回收工作分散化。

虚拟内存场景：

在虚拟内存系统中，很多数据位于不可访问之处，复制式回收变得非常昂贵。
Moon 等人有论文描述针对虚拟内存系统更高效的改进版本（对增量式 Minsky-Fenichel-Yochelson 与 Baker 算法的修改）。

十一、垃圾回收器的特殊工程约束 [42:00]

要点（回答学生提问）：

学生观察到楼上系统的垃圾回收运行极快——因为它是复制式回收器，只遍历需要复制的有用结构，而非全部内存。
复制两三兆字节的东西不到一秒。

垃圾回收器必须小，不是因为要快，而是因为没人能调试复杂的垃圾回收器。

回收器一旦出错，会以无法追溯的方式破坏内存——它重排了一切，你无从知道发生了什么。

需要审计线索（audit trail），但回收器的本质决定了很难获得。

因此这是唯一一类"必须盯着看足够久、确信它正确"的程序。

必须小到能装进脑子，能自我证明正确性。小程序通常也快。

思考：这是一个关于"可验证性"约束的经典案例——当系统具有全局破坏性副作用时，简洁性成为正确性的前提条件。

十二、可计算性的边界：停机问题不可判定 [46:00]

背景：课程已展示通用机器（求值器）的完整实现，也展示了"有东西不可计算"。现在要具体展示你想计算但算不了的东西。

动机：写编译器时，你希望有个程序能检查待执行的程序是否会工作，比如捕获死循环——但一般而言写不出这样的程序。

形式化论证一（safe 函数）：

定义函数 S(P, A)：若 P 作用于 A 能收敛到值且不出错，则为真；若 P 作用于 A 死循环或出错，则为假。
这确实是一个函数：对每个过程和参数，答案非真即假，理论上可造一张巨大的表。
问题：能否写一个过程计算 S 的值？

假设可以，设过程 safe 计算 S。定义过程 diagonal-1：

diagonal-1 = (lambda (P)
  (if (safe P P)
      无限循环
      3))

（无限循环可用 λ 演算经典写法：((lambda (x) (x x)) (lambda (x) (x x)))）

考察 (diagonal-1 diagonal-1)：

若 (safe diagonal-1 diagonal-1) 为真 → 应进入无限循环，即不安全，矛盾
若为假 → 返回 3，即能收敛，是安全的，矛盾
故 safe 不可定义

形式化论证二（diagonal-2，避免"这是不是一个把戏"的疑虑）：

定义 other-than：(lambda (x) (if (eq? x 'a) 'c 'a))——总是产生与参数不同的东西
定义过程 diagonal-2：

diagonal-2 = (lambda (P)
  (if (safe P P)
      (other-than (P P))
      #f))

若 safe 可定义，则 diagonal-2 在任何输入上都是安全的（只在安全时才调用 P P）
于是 (diagonal-2 diagonal-2) 必等于 (other-than (diagonal-2 diagonal-2))——矛盾
故 safe 不可定义

命名来源：称为 "diagonal" 是因为这是康托尔对角线论证的实例——康托尔在 19 世纪末用它证明实数不可数（直线上的点比计数数更多）。

计数论证（为何这不奇怪）：

可能的函数数量 = 答案数 ^ 输入数（单变量情形）
函数数量总是大于程序数量（基数论证）
因此必然有大量函数无法由程序计算

回答学生追问："S(diagonal-1) 的值是什么？"

讲师答：S 是一个函数，但我不知道它的值，也无法计算它。存在这样的函数，只是没有机器能被造出来计算它。

十三、关于自顶向下设计的反思 [52:00]

学生提问：从规格说明到解决方案之间，有没有自动化的步骤？

要点：

软件工程中确实有从规格说明经多层设计到实现的实践，但讲师认为部分现实、部分不现实。

电气工程类比一（阻抗匹配滤波器）：

需求：匹配发射机功率输出到天线，同时滤除谐波辐射
传统方法（镜像阻抗法）：用基本模块 L 型节
- 若接到电阻 R，且串联阻抗为 Q×R，则产生 Q²+1 的低通滤波器并实现匹配
把两个 L 型节对接成 π 型节滤波器：一个降压、一个升压，各是一个低通滤波器
问题：这样做产生了两个线圈，而本该只需一个——严重的低效
大多数软件工程的毛病：除了人工优化和编译器，没有机制消除自顶向下设计产生的冗余部分

电气工程类比二（IF 放大器级间耦合）：

一个看似合理的耦合方案中，那个元件在层级上不是单一事物：
- 它是调谐电路的电感
- 是变压器的初级
- 还是偏置条件到达晶体管集电极的直流路径
没有简单的自顶向下设计能产生这样的结构——一个事物同时承担多重交叠用途
就像玩拼字游戏要拿三倍词分——自顶向下设计策略做不到这么"划算"

核心结论：真实工程的本质是"以最小努力获取最大效能（most oomph for effort）"。标准的自顶向下设计是一种相当浅薄（shallow）的方法，无法刻画人们在设计中真正想做的事。

思考：这一反思与 SICP 全课主题呼应——抽象屏障帮助管理复杂性，但真实系统的优化往往需要跨越抽象层次，这正是"自顶向下"与"自底向上"必须结合的原因。

全课收尾

讲师总结：

我们已展示通用机器（求值器）的完整实现，达到"可以想象造出一台"的细节层次。
展示了一个具体的 Lisp 实现（基于前日讨论的某种方案），主要是对内存的接口加少量时序处理，在 1979 年达到了 DEC PDP-10 上解释执行 Lisp 的速度。
也展示了不可计算的东西——确实存在你无法计算的事物。
最后以"停机问题不可判定"的证明和"自顶向下设计的局限"收尾。

关键标签 / 关键词

SICP MIT 6.001 存储分配 垃圾回收 GC 标记-清扫 mark-sweep 复制式回收 Minsky算法 Fenichel Yochelson Baker算法 Deutsch-Schorr-Waite 自由表 free list car/cdr数组 线性内存 哥德尔编码 停机问题 可计算性 康托尔对角线论证 破碎的心 broken heart 自顶向下设计 抽象屏障 环境帧 可达性分析