SICP 第 10 讲：计算对象

视频封面

视频元信息

课程：MIT 6.001 Structure and Interpretation of Computer Programs（1986 原版）
主题：计算对象（Computational Objects）——面向对象编程、事件驱动仿真、赋值与可变数据
讲师：Hal Abelson（本讲由 Abelson 主讲）

内容摘要（TL;DR）

本讲从"世界中的对象"出发，引出面向对象编程思想，并以数字电路仿真器为例，讲解如何用 LISP 构建嵌入式语言。核心内容包括：原始对象与组合手段、抽象屏障与层次化设计、事件驱动仿真中的信号传播、议程（agenda）与队列（queue）的数据结构实现，以及引入赋值后 cons 的身份（identity）与共享（sharing）问题，最后用纯 lambda 演算实现可变 cons。

一、从世界对象到计算对象 [00:00]

1.1 对象的核心概念

考点：对象 = 独立局部状态 + 身份

视频开篇指出：世界中的每个事物都有独立的局部状态（independent local state），这正是它成为一个"事物"（thing）的根本原因。
我们希望在世界中的对象与计算机中的对象之间建立一一对应关系：
- 世界中的每个对象 → 计算机中的对象
- 世界中对象之间的关系 → 计算机中对象之间的关系

理解：这就是面向对象编程（Object-Oriented Programming）的思想源头。对象不仅仅是数据的封装，更重要的是它拥有"自己的状态"，且状态可以随时间变化。

正是这种对应关系的需求，催生了面向对象编程的发明。

1.2 为什么选择电路作为对象模型

讲师认为电路系统是物理学家能找到的最好的对象模型。
电路的关键优势：连接是清晰明确的
- 一段电线连接机器的两个部分，原则上没有任何"未描述"的连接。
- 例如：灯泡与电源插座相连，连接关系完全清楚。
- 即使把电线打个结，灯泡依然亮——物理排列方式不影响连接语义（至少在低频情况下）。

思考：这种"连接清晰性"正是模块化设计的基础。对象之间的交互应当像电路中的导线一样明确、可追踪，而不是隐式的全局耦合。

1.3 数字电路——最抽象的电路对象

数字电路是电路系统中最抽象的类型：
- 原始对象：反相器（inverter）、与门（AND gate）、或门（OR gate）
- 组合手段：用导线（wire）连接，导线代表抽象信号
- 我们甚至不关心信号是电压、电流还是水压——它们是抽象变量

理解：抽象层次越高，越能忽略底层物理细节。数字电路把"电压/电流"抽象为"信号 0/1"，这正是层次化抽象的典范。

二、在 LISP 中构建嵌入式语言 [04:13]

2.1 两种"嵌入"的区别

易错点：区分两种语言嵌入方式

方式	说明	例子
解释器方式	用 LISP 程序解释另一种语言	模式匹配替换语言（上一讲）
过程封装方式	构建越来越多的过程来封装结构	Henderson 的图片语言、本讲的电路语言

本讲采用第二种方式：用过程（procedure）封装电路结构，而非写一个解释器。

2.2 电路语言的原始对象与组合

原始对象：反相器、与门、或门
组合手段：导线（wire）
示例声明：
- 定义导线 A、B、C、D、S
- 或门：输入 A、B，输出 D
- 与门：输入 A、B，输出 C
通过一系列声明，可以连接出任意电路。

2.3 抽象：半加器（Half Adder）

考点：抽象 = 盒子（box）

半加器：输入 A、B，输出和（Sum）与进位（Carry）
抽象的关键是边界（boundary），即盒子：
- 盒子外部可见的变量：A、B、S、C（即 lambda 表达式的声明变量）
- 盒子内部隐藏的互连线：D、E（不穿透盒壁）
内部连线逻辑：
- E 是或门输出线，D 是与门输出线
- 按与门、或门、反相器的组合方式连接

理解：抽象屏障（abstraction barrier）让使用者只需关心盒子的接口，无需了解内部实现。这正是模块化编程的核心。

2.4 层次化设计的正确性

考点：语言必须"正确层次化"

一个好的语言，复合对象应当看起来像原始对象。
如果复合对象不像原始对象，说明语言设计有问题。
本讲电路语言的层次：
- 起点：电学对象（而非数学函数）
- 构建：更多电学对象
- 胶水：list 结构（cons），"cons 是终极胶水"

2.5 全加器（Full Adder）与更大抽象

全加器由两个半加器 + 额外导线（SC-1、C-2）+ 一个或门组成
输入：两个数 + 进位输入（carry-in）
输出：和（sum）+ 进位输出（carry-out）
用全加器可以构建行波进位加法器链（ripple-adder chains）和更大的加法器

拓展：半加器只能处理两个 1 位二进制数相加，无法处理来自低位的进位；全加器通过引入 carry-in 解决了这个问题，是构建多位加法器的基础单元。

三、实现原始对象：反相器与与门 [08:24]

3.1 实现策略

只需要实现原始对象，组合与抽象手段从 LISP 继承。
以反相器（inverter）为例：
- 有两个导线：输入（in）、输出（out）
- 需要知道信号到来时该做什么

3.2 对象间的通信机制

考点：对象通过"注册动作"实现通信

反相器必须告诉它的输入导线："当你变化时，告诉我。"
类比："我叫 George，我的工作是在你变化时处理结果。"
实现方式：在输入导线上添加一个动作（action），称为 invert-in
- invert-in 是一个无参数过程
- 功能：获取输入导线上信号的逻辑非
- 经过反相器延迟（inverter delay）后，将输出导线上的信号设为新值

理解：这是事件驱动（event-driven）模型的核心。对象不主动轮询，而是被动响应——当依赖的信号变化时，被"唤醒"并执行动作。

3.3 输出导线的敏感性

输出导线必须"敏感"：当它的信号变化时，要通知其他对象"嘿，醒醒，我的值变了！"
当反相器与与门连接时，会有大量通信发生
必须确保信号正确传播

3.4 与门（AND Gate）实现

与门有两个输入 A1、A2，一个输出
结构与反相器完全相同：
- 定义 and-action 过程：当输入变化时被调用
- 功能：计算输入信号的逻辑与
- 经过与门延迟（AND gate delay）后，设置输出信号为新值
实现细节：
- 使用赋值操作 set!（派生赋值操作，按惯例用感叹号标记）
- and-action 通过 add-action! 告知 A1 和 A2 导线：当变化时调用 and-action

四、信号传播的计算模型 [12:07]

4.1 物理世界与计算模型的对应

考点：为世界中的每个对象和关系，在计算机中建立对应对象和关系

示例电路：与门（输入 A、A）→ 导线 C → 反相器 → 输出导线 D
物理世界：可以在 Radio Shack 花几美分买到，型号如 LS04
目标：在计算机中为每个对象和每个关系建立对应

4.2 导线的内部状态

每个导线必须知道：
- signal：当前信号值（0 或 1）
- action-procedures：信号变化时需要通知的动作过程列表
每个导线关联一个环境（environment），绑定 signal 变量

理解：这就是对象的"局部状态"。每个导线拥有自己的私有变量，外部无法直接访问，只能通过消息（message）交互。

4.3 对象间的连接关系

与门动作过程需要知道：
- A1：指向第一条输入导线
- A2：指向第二条输入导线
- output：指向输出导线
当与门动作过程被唤醒时：
1. 询问 A1："你的信号是什么？"
2. 询问 A2："你的信号是什么？"
3. 计算逻辑与
4. 通知输出导线："你的信号变了"

4.4 与门的环境结构

调用与门时创建一帧（frame），绑定 A1、A2、output 到传入的导线
在该环境中构造 and-action 过程（lambda 表达式求值的结果）
and-action 过程捕获（hang onto）定义它的帧
因此 and-action 可以访问 A1、A2、output——这是它的局部状态

考点：闭包 = 过程 + 环境

理解：这正是闭包（closure）的本质。and-action 过程"记住"了它被创建时的环境，因此能访问 A1、A2、output。这是面向对象中"对象拥有状态"的实现机制。

五、导线的实现细节 [15:00]

5.1 导线的构造

调用 make-wire 创建导线时：
1. 创建变量 signal 和 action-procedures
2. 在该上下文中定义多个过程

5.2 导线内部的过程

（1）set-my-signal!（设置信号）

接受新值
如果新值等于当前信号值，直接返回（不做任何事）
否则：
1. 将 signal 设为新值
2. 调用 action-procedures 列表中的每个过程

易错点：信号值未变化时不应触发动作

思考：这个"值不变则不通知"的优化避免了无限循环和不必要的计算。在事件驱动系统中，这种判断至关重要。

（2）accept-action-procedure!（接受动作过程）

将新过程 cons 到 action-procedures 列表
立即调用该过程一次
- 讲师提到这与"事件房间和仿真启动"有关，需要仔细思考

理解：立即调用一次是为了初始化。例如，与门刚连接时，需要根据当前输入值立即计算输出，而不是等待输入变化。

（3）dispatcher（调度器）

接受消息，提取信息：
- get-signal：获取当前信号值
- set-signal!：获取设置信号的方法
- add-action!：获取添加动作过程的方法
返回 dispatch 过程作为值

5.3 导线的消息传递接口

考点：导线是"消息接受对象"

导线是一个接受消息的对象：
- 问："你的添加动作过程的方法是什么？" → 返回一个过程
- 用该过程作用于一个动作过程 → 在导线中创建新的动作过程
获取信号：(wire 'get-signal) → 返回信号值

设置信号：

(define (set-signal! wire new-value)
  ((wire 'set-signal!) new-value))

添加动作：

(define (add-action! wire action)
  ((wire 'add-action!) action))

理解：这是消息传递风格（message-passing style）的经典实现。对象通过 dispatch 过程接受消息，根据消息类型返回不同的方法。这是早期面向对象编程的雏形。

六、时间控制：议程（Agenda）与延迟 [22:36]

6.1 延迟机制

反相器和与门都有延迟（delay）
信号变化后，经过延迟才执行动作
需要一种机制：延迟一段时间后执行动作

6.2 议程（Agenda）

考点：议程 = 组织时间和动作的结构

议程是一种特殊结构，用于组织时间和动作
延迟是一个数字，动作是一个过程
设置方式：
- 时间 = 延迟时间 + 当前时间
- 将动作添加到议程中该时间点

6.3 传播循环（Propagate）

仿真运行机制：
1. 如果议程为空，结束
2. 否则，取出议程的第一项（一个无参数过程）
3. 调用该过程（执行动作）
4. 从议程中移除第一项
5. 回到步骤 1（循环）

理解：这就是事件循环（event loop）的原型。议程按照时间顺序组织待执行的动作，propagate 不断取出并执行，直到没有待处理事件。

七、仿真器演示 [24:00]

7.1 仿真器的实际应用

重点：这个仿真器被用于制造一台真实的计算机

讲师强调：这个仿真器看起来简单，但已被用于制造一台相当大型的计算机
实际使用的仿真器与演示的差异：
- 有更多种类的原始对象（不只是反相器和与门）
- 包括：边沿触发触发器（edge-triggered flip-flops）、锁存器（latches）、透明锁存器（transparent latches）、错误器件等
- 有大量原始对象定义（型号如 LS04），以及更多参数（建立时间、保持时间等）
但除这些复杂性外，仿真器的结构与演示的完全相同

拓展：这说明一个好的抽象设计具有强大的可扩展性。核心机制（事件驱动、议程、信号传播）不变，只需扩展原始对象库即可支持更复杂的电路。

7.2 演示过程

设置延迟，创建议程
创建输入：input-1、input-2、sum、carry
在 sum 和 carry 导线上放置探针（probe）
- 探针特性：当所连导线变化时，打印消息
初始状态：
- sum 在时间 0 的值为 0
- carry 在时间 0 的值为 0
构建半加器结构，连接 input-1、input-2、sum、carry
设置 input-1 信号为 1，传播：
- 时间 8：sum 新值变为 1
设置 input-2 信号为 1，传播：
- 时间 11：carry 变为 1
- 时间 16：sum 新值变为 0

理解：这个演示展示了事件驱动仿真的完整流程——设置信号、传播、观察结果。时间戳反映了信号经过各级门电路的累积延迟。

八、议程与队列的数据结构 [29:00]

8.1 仿真器的本质

仿真是一种"世界的仿真"：
- 世界中的对象 → 计算机中的对象
- 世界中随时间变化的状态 → 计算机中的时间
- 世界中事件的先后顺序 → 计算机中事件的相同顺序
这种对齐需要赋值（assignment）

8.2 议程的原始操作

考点：议程的原始操作

操作	功能
`make-agenda`	创建新议程
`current-time`	获取议程当前时间
`empty-agenda?`	判断议程是否为空
`add-to-agenda!`	添加动作到议程（需指定时间）
`first-agenda-item`	获取议程第一项（返回动作）
`remove-first-agenda-item!`	移除议程第一项

8.3 议程的数据结构

议程是一个可修改的列表，按时间组织
结构：
- header（头部）：有一个头部单元，便于在开头插入
- segments（段）：列表的列表
  - 每个段有一个时间（如 10、30）
  - 每个段有一个队列（queue）：该时间要做的动作列表

理解：为什么需要 header？因为要在列表开头插入元素时，需要有一个"位置"来修改。这是链表操作中的常见技巧。

8.4 议程的修改操作

（1）添加动作到已有时间段（如时间 10）

遍历找到时间 10 的段
增加该段的队列

（2）添加动作到不存在的时间段（如时间 20）

需要创建新段
修改前一段的 cdr，指向新的 cons（新段 + 后续段）
涉及数据结构的修改（mutation）

（3）添加动作到开头（如时间 5）

需要修改头部单元
这正是需要 header 的原因

（4）移除动作

从开头移除较简单：
1. 找到第一个段
2. 如果队列非空，删除队列中一个元素
3. 如果队列变空，删除整个段，修改指针

8.5 队列（Queue）的数据结构

考点：队列的原始操作

操作	功能
`make-queue`	创建新队列
`insert-queue!`	插入新项
`delete-queue!`	删除第一项
`front-queue`	获取第一项
`empty-queue?`	判断是否为空

队列结构：

有队列头（queue header），包含两个指针：
- front pointer：指向队首
- rear pointer：指向队尾
两个指针的作用：可以在队尾添加而无需从头遍历

操作：

插入（insert）：创建新 cons，修改 rear 指针指向新项，更新 rear 指针
取队首（front）：沿 front 指针找到第一项
删除（delete）：移动 front 指针到下一项

理解：队列的 front/rear 双指针设计是经典的数据结构优化。如果用单指针，在队尾插入需要 O(n) 遍历；双指针使其变为 O(1)。

8.6 命名约定

易错点：注意操作命名约定

修改操作（有副作用）：名字后加 !，如 set-car!、insert-queue!
测试操作（无副作用）：名字后加 ?，如 empty-queue?
这种约定帮助程序员区分操作是否有副作用

九、赋值与可变数据：cons 的身份问题 [37:00]

9.1 引入赋值后的 cons

原始 cons 的公理：
- 对所有 x、y：(car (cons x y)) = x
- 对所有 x、y：(cdr (cons x y)) = y
这些公理没有说明 cons 是否有身份（identity）
引入赋值（set-car!、set-cdr!）后，公理不再讲述完整故事：
- 如果设置某个 cons 的 car，是设置所有相同部分的 cons，还是只设置这一个？

9.2 数字 vs 物理对象

数字：改变分母没有意义。可以创建一个不同分母的新数，但"改变一个数的分母"在数学上很奇怪。
物理对象：改变 cons 的 car 就像剪掉指甲的一部分——对象有身份
cons 用于表示物理世界的事物时，具有身份

9.3 身份与共享示例

(define a (cons 1 2))
(define b (cons a a))

a 是一个指向 (1 . 2) 的指针
b 是一个指向 (a . a) 的指针
此时对象 a 有三个名字：a、(car b)、(cdr b)——这些称为别名（aliases）

(set-car! (car b) 3)

找到 (car b)，即 a
设置 a 的 car 为 3
现在 (car a) 也是 3——a 被改变了

考点：共享（sharing）是强大但危险的

共享的好处：队列等数据结构正是为了促进共享而设计
共享的代价：意外的共享和非预期的对象交互，是复杂程序大多数 bug 的来源

思考：引入身份和共享带来了巨大能力，但也带来了复杂性。这就是为什么函数式编程（无副作用）在某些场景下更受青睐——它避免了共享带来的 bug。

9.4 非局部交互

(car (cdr b))

取 (cdr b)，即 a
取 a 的 car
结果也是 3
即使这个表达式与 (car a) 看似无关，也受到共享的影响

易错点：共享导致非局部交互

理解：修改一个对象可能影响到看似无关的另一处代码。这是可变状态编程中最难调试的问题之一。

9.5 一种赋值操作就够了

表面上有多种赋值操作：set!、set-car!、set-cdr!
实际上，只要有一个 set!，就能实现所有"坏事"
可以用纯 lambda 实现 cons，并用 set! 实现 set-car! 和 set-cdr!

十、用纯 lambda 实现 cons [42:00]

10.1 Church 的 cons 定义

考点：Alonzo Church 的 lambda 演算 cons

Alonzo Church：20 世纪最伟大的程序员（虽然从未见过计算机），1930 年代在普林斯顿定义

定义：

(define (cons x y)
  (lambda (m) (m x y)))

(define (car x)
  (x (lambda (a d) a)))

(define (cdr x)
  (x (lambda (a d) d)))

10.2 验证 Church 定义

计算 (car (cons 35 47))：

(cons 35 47) = (lambda (m) (m 35 47))
(car ...) = ((lambda (m) (m 35 47)) (lambda (a d) a))
将 (lambda (a d) a) 代入 m：((lambda (a d) a) 35 47)
将 35 代入 a，47 代入 d：结果为 35
验证成功！不需要任何数据结构，甚至不需要数字

拓展：这就是 lambda 演算的威力——可以用纯函数表示数据结构。Church 编码（Church encoding）是函数式编程的理论基础之一。

10.3 可变 cons 的 lambda 实现

考点：用 set! 实现可变 cons

(define (cons x y)
  (lambda (m)
    (m x
       y
       (lambda (n) (set! x n))
       (lambda (n) (set! y n)))))

(define (car x)
  (x (lambda (a d sa sd) a)))

(define (cdr x)
  (x (lambda (a d sa sd) d)))

(define (set-car! x y)
  (x (lambda (a d sa sd) (sa y))))

(define (set-cdr! x y)
  (x (lambda (a d sa sd) (sd y))))

关键点：

cons 返回的过程接受 4 个参数：
- x 的值、y 的值
- 设置 x 的权限（permission）、设置 y 的权限
这些权限是闭包，捕获了 cons 参数所在的环境
set-car! 使用设置 x 的权限

10.4 环境分析

推导：当调用 (cons x y) 时，lambda 表达式在 x、y 定义的环境中求值。该环境成为返回过程的父环境。因此：

x 和 y 在父帧中有位置
权限过程可以修改这些位置
set-car! 通过传入的权限过程，将 x 设置为新值

考点：一旦引入一个赋值操作，就引入了所有赋值操作

逻辑上，只需一个 set! 就能实现所有可变数据操作
实际实现中不会这样做（出于工程考虑），但原理上等价

理解：这是计算理论中的一个深刻结论——赋值的本质能力是相同的，不同的赋值操作只是语法糖。

十一、常见问题与易错点总结

11.1 对象与状态

易错点：对象必须有独立局部状态

没有独立局部状态的事物不能称为"对象"
状态通过闭包捕获环境实现

11.2 信号传播

易错点：信号未变化时不应通知

set-my-signal! 中必须先判断新值是否等于旧值
否则会导致无限循环和不必要的计算

11.3 共享与别名