视频封面

视频元信息

  • 课程：MIT 6.001 Structure and Interpretation of Computer Programs（1986 传奇原版）
  • 本讲主题：复合数据（Compound Data）与数据抽象（Data Abstraction）
  • 备注：备选版本（Alternative Version），内容与主线第 24 讲基本一致，讲解顺序略有差异

内容摘要（TL;DR）

本讲从程序抽象过渡到数据抽象，以有理数算术系统为例，引入构造器（constructor）与选择器（selector）的愿望思维设计法。随后引出序对（pair）作为数据的粘合剂，介绍 cons/car/cdr 与盒指针表示法。最后用纯过程（lambda）实现 cons/car/cdr，证明数据可完全由过程构建，模糊数据与过程的界限。

一、回顾：语言三要素与分层系统 [00:22]

课程开头回顾了讨论语言时使用的框架，包含三个核心要素：

  1. 基本元素（primitive things）：系统内建的东西，如数字；
  2. 组合手段（means of combination）：把基本元素组合成更复杂的东西；
  3. 抽象手段（means of abstraction）：给复杂的东西命名，使其可作为简单积木复用。

上一讲通过高阶过程展示了组合抽象手段后能获得的惊人表达力，例如用不动点法或牛顿法表达通用的计算方法。

核心思想：我们构建的是分层系统（layered system），层与层之间存在抽象屏障（abstraction barrier）。

理解：所谓"与 George 签约"，本质上是把某个子任务的行为契约（contract）与实现细节分离。只要 George 实现的行为符合契约，他内部怎么做、甚至他是否又找 Harry 写了 abs 过程，都与上层无关。

关键点：构建东西的任务与实现部件的任务被解耦（divorce）。大型系统中这种抽象屏障会在极多层出现。

二、从过程抽象到数据抽象 [02:39]

本讲把同样的思路搬到数据上：

  • 系统有基本数据（primitive data），如数字；
  • 数据也有组合手段（glue），把基本数据粘合成复合数据（compound data）；
  • 数据也有抽象方法论，用于自底向上构建数据。

思考：过程抽象解决"如何计算"，数据抽象解决"如何表示"。两者共享同一套分层哲学——上层只关心行为契约，下层细节被屏障隔离。

本节关键：从"过程的三要素"平行迁移到"数据的三要素"，这是本讲所有后续内容的骨架。

三、有理数算术：愿望思维与"云" [03:39]

3.1 问题背景

目标：让计算机能回答"1/2 + 1/4 = 3/4""3/4 × 2/3 = 1/2"这类问题。这些都是五六年级就学过的分数运算：

  • 加法公式：N1/D1 + N2/D2 = (N1·D2 + N2·D1) / (D1·D2)
  • 乘法公式：N1/D1 × N2/D2 = (N1·N2) / (D1·D2)

3.2 遇到的障碍

易错点：系统只提供单个数字（如 5、3），没有"有理数"这种数据对象——没有一种东西能同时装下一个分子和一个分母。

理解：视频里用"云（cloud）"作比喻——我们希望有一个对象，里面同时包含分子和分母，可以整体命名、整体传递。

3.3 解决方案：愿望思维（Wishful Thinking）

沿用此前写 sqrt 时"假设 fixed-point 已存在"的策略，假设有三个过程：

过程 作用 类型
make-rat 输入分子、分母，返回一个"云" 构造器（constructor）
numer 输入"云"，返回分子 选择器（selector）
denom 输入"云"，返回分母 选择器（selector）

重点：make-rat 返回的"云"到底是什么，是 George 的事，我们不想知道。这就是与 George 签的契约。

3.4 用愿望思维实现有理数加法

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

乘法同理：

(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))

关键点：只要假设有构造器和选择器，上层运算的代码就极其自然，几乎就是数学公式的直译。

四、为什么需要复合数据对象？ [10:05]

课堂上有学生提问：既然最终还是要取出分子分母，为什么不直接传四个数字？

4.1 反面例子：临时变量泛滥

若直接操作四个数字，计算 (x + y) * (s + t) 时：

  • 先算 x+y，需要两个临时变量存分子分母；
  • 再算 s+t，又需要两个临时变量；
  • 最后相乘，还要再组合。

易错点：随着表达式变复杂，这些"临时变量"（有理数的内部细节）会散落（hang out）在整个系统中，既搞乱编程，也搞乱思维。

4.2 正面理由：语言应表达头脑中的概念

关键论点：编程语言应当能表达我们头脑中的概念——"有理数"是一个可以相加、可以把结果再相乘的整体对象。

理解：就像过程体本来只是一串指令，我们却要把它打包成"过程"并命名一样。有理数也应该被打包、命名、整体传递。

重点：这是数据抽象的根本动机——让数据对象成为一等公民，而非散落的零件。

五、George 的解决方案：序对（Pairs） [16:30]

5.1 数据的粘合剂：list structure

现在解决 George 的问题——如何把分子和分母真正粘在一起。引入序对（pair）：

  • cons：构造器，接受 x 和 y，返回一个 pair，第一部分是 x，第二部分是 y；
  • car：选择器，取 pair 的第一部分；
  • cdr：选择器，取 pair 的第二部分。

5.2 盒指针表示法（Box and Pointer Notation）

用一个小盒子加两个箭头表示 (cons 2 3)：

[ * | * ]
  |   |
  2   3

易错点：很多学生误以为箭头的几何方向有含义（如朝上、朝下）。实际上只有连接关系有意义，箭头画在哪、朝哪个方向完全无所谓。

5.3 序对的行为契约（公理）

对任意 x 和 y：(car (cons x y)) = x，(cdr (cons x y)) = y。

重点：这就是 cons/car/cdr 的全部行为定义。至于它们内部怎么实现，与上层无关。

5.4 用序对实现有理数

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))

至此，有理数系统完整实现。

六、测试与 Bug：约分问题 [22:30]

6.1 测试用例

(define a (make-rat 1 2))
(define b (make-rat 1 4))
(define ans (add-rat a b))
(numer ans)  →  6
(denom ans)  →  8

易错点：期望输出 3/4，系统却输出 6/8。程序完全按公式执行，逻辑没错，但结果未约分到最简形式。

6.2 修复方案一：构造时约分

让 George 在 make-rat 时就除以最大公约数：

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))

这样 add-rat 中调用 make-rat 时会自动约分。

6.3 修复方案二：选择时约分（替代表示）

另一种做法是构造时原样存，选择时再算 GCD：

(define (make-rat n d) (cons n d))
(define (numer x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (car x) g)))
(define (denom x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (cdr x) g)))

思考：哪种更好？取决于使用模式——若频繁构造、很少读取，则选择时约分更省；若频繁读取、很少构造，则构造时约分更好。这正是数据抽象的价值：表示选择被局部化，可以随时替换。

七、数据抽象方法论 [26:10]

7.1 抽象屏障的建立

┌─────────────────────────────┐
│  有理数算术（add-rat 等）    │  ← 使用层
├─────────────────────────────┤
│  make-rat / numer / denom   │  ← 抽象屏障
├─────────────────────────────┤
│  cons / car / cdr（序对）    │  ← 表示层
└─────────────────────────────┘

7.2 数据抽象的定义

数据抽象（Data Abstraction）：通过假定构造器和选择器存在来建立数据对象，从而把数据的使用与数据的表示隔离开来。

7.3 反面教材：不抽象会怎样

若直接写 (car (car s)) 这类代码，会带来两大问题：

  1. 可读性差：代码难以理解；
  2. 脆弱：一旦表示改变（如 George 把 x 坐标放前面、或要求线段反向绘制），所有依赖细节的代码都要改。

理解：视频里用"打 George 一拳"的玩笑说明——在十层系统里，表示细节泄漏会导致复杂度爆炸。

7.4 命名的力量

编程中最重要的原则之一，和巫术一样：如果你知道精灵的名字，你就能控制它。

重点：make-rat/numer/denom 就是给"表示选择"这个精灵命名。命名后，决策被局部化，上层代码可以假装决策已经做出。

八、抽象与决策延迟 [32:00]

8.1 两种表示的权衡

  • 构造时约分：构造慢、读取快；
  • 选择时约分：构造快、读取慢。

关键点：在写系统时你可能无法预先决定哪种更好。

8.2 延迟决策 vs. 拖延

作为系统设计者，你希望保留灵活性——不到被迫时绝不做决定。但"延迟决策"与"彻底拖延"之间只有一条很窄的线。

思考：数据抽象让你"假装已经做了决定"继续前进，日后真正需要时再回来面对。这是控制复杂度的核心技巧。

8.3 关于"先设计后编码"的讨论

有学生问：抽象分层是否意味着"先完成所有设计再写代码"？

易错点：讲师明确反对这种"教条"。真正强大的地方在于：你可以假装已经做了决定，之后再回头判断哪个决定是对的——两全其美。

8.4 补充：let 与 define 的区别

  • define：在全局环境中建立名字，之后一直记得；
  • let：建立局部名字，只在该表达式内有效，外部访问会报"unbound variable"。
(let ((z 10)) (+ z z))  →  20
z                        →  未绑定变量（错误）

理解：let 提供局部上下文，不会污染全局命名空间。

九、分层构建：线段与向量 [38:00]

9.1 向量（点）的表示

  • 构造器：make-vector（或 make-point），接受两个坐标；
  • 选择器：xcor（x 坐标）、ycor（y 坐标）；
  • 可用序对实现，但对上层隐藏。

9.2 线段的表示

  • 构造器：make-segment，接受起点和终点；
  • 选择器：start-segment、end-segment；
  • 用序对实现，两个元素都是点。

9.3 线段操作

中点（midpoint）：取两端点的 x、y 坐标平均值，构造新点。

长度（length）：用勾股定理。

(define (length s)
  (let ((dx (- (xcor (start-segment s))
               (xcor (end-segment s))))
        (dy (- (ycor (start-segment s))
               (ycor (end-segment s)))))
    (sqrt (+ (* dx dx) (* dy dy)))))

9.4 分层结构

┌──────────────────────┐
│  线段操作（length 等） │
├──────────────────────┤
│  make-segment/start/end │  ← 抽象屏障 1
├──────────────────────┤
│  向量操作             │
├──────────────────────┤
│  make-vector/xcor/ycor │  ← 抽象屏障 2
├──────────────────────┤
│  cons / car / cdr     │
└──────────────────────┘

理解：若不用抽象屏障，length 会写成 (car (car s)) 这种深层嵌套，一旦表示改变（如坐标顺序调整、线段方向反转），代码会全面崩溃。

十、闭包（Closure）：组合手段的关键性质 [52:00]

10.1 什么是闭包

闭包（Closure）：组合手段的性质——用它组合出的东西，本身还能再用同样的手段继续组合。

重点：cons 是闭包的——不仅能造"数字的序对"，还能造"序对的序对"。

10.2 反例

理解：某些语言的数组不是闭包的——能造"数字的数组"，却不能造"数组的数组"。这是组合手段的质量判据。

10.3 用序对表示三元组

若要表示三维点（三个坐标），可用嵌套序对：

(cons 1 (cons 2 3))

易错点：如何嵌套是任意的（可以 (cons (cons 1 2) 3)），有多种约定，后续课程会讨论。

关键点：这依赖于"序对的序对"是合法的——即闭包性质。若只能造"数字的序对"，就做不出复杂结构。

十一、数据到底是什么？——用过程实现序对 [58:00]

11.1 回到原点

我们一直假设 make-rat/numer/denom 存在。现在追问：它们的行为契约到底是什么？

有理数的契约：对任意 n 和 d，(= (/ (numer (make-rat n d)) (denom (make-rat n d))) (/ n d))。

重点：任何满足这个契约的三个过程，都可以作为有理数的表示。这就是"抽象数据"的含义。

11.2 更震撼的问题：序对又是什么？

我们说过 cons/car/cdr 是原语，但其实我们只告诉了它们的行为公理：

(car (cons x y)) = x，(cdr (cons x y)) = y。

11.3 用纯过程实现序对

这是本讲最精彩的部分——不用任何数据结构，只用 lambda 实现 cons/car/cdr：

(define (cons x y)
  (lambda (pick)
    (if (= pick 1) x y)))

(define (car p) (p 1))
(define (cdr p) (p 2))

易错点：这里没有任何"数据"，全部是过程。cons 返回的是一个过程，它"记住"了 x 和 y。

11.4 用替换模型验证

验证 (car (cons 37 49)) 是否等于 37：

  1. (cons 37 49) 替换为 (lambda (pick) (if (= pick 1) 37 49))；
  2. (car ...) 展开为 (... 1)；
  3. 把 pick = 1 代入，(= 1 1) 为真，返回 37。

同理 (cdr (cons 37 49)) 返回 49。

重点：这证明了只用过程就能满足序对的公理，因此数据抽象根本不需要"数据"。

11.5 为什么这么做

讲师给出两个理由：

  1. 强化抽象观念：抽象到极致，数据可完全由过程构建；
  2. 模糊数据与过程的界限：这是后续课程反复出现的主题——许多重要编程技术依赖于打破"数据 vs. 过程"的传统界线。

思考：这正是 SICP 的哲学——数据即过程，过程即数据。Church 编码（用 lambda 编码数据）在理论计算机科学中有深厚根基。

十二、课堂问答：过程即对象 [01:02:00]

12.1 若打印这个"序对"会怎样？

答：会打印出 compound procedure（复合过程），因为系统不知道它是"数据"，只知道它是个过程。

12.2 多个 cons 会不会混淆？

学生问：(cons 37 49) 和 (cons 1 2) 同时存在，系统怎么知道取哪个？

答：这是本讲最重要的哲学问题。过程不只是"动作"，而是有独立存在的对象（conceptual entity）。

  • (cons 37 49) 创建了一个特定的过程对象，内部"记住"了 37 和 49；
  • (cons 1 2) 创建了另一个独立的对象；
  • 二者互不干扰，就像 (sqrt 5) 和 (sqrt 20) 互不混淆一样。

重点：这标志着从"过程是动作"到"过程是对象"的观念转变。

12.3 延伸：两个相同的 cons 是同一个对象吗？

(cons 37 49) 做两次，是同一个东西还是不同的东西？如何判断？什么时候重要？

这是一个极深的问题，讲师说这将在课程中段（约一半处）用一整讲来讨论——涉及对象同一性（identity）与引用透明性。

思考：这正是函数式编程与命令式编程的核心分歧之一。SICP 在此埋下伏笔，后续会讨论 eq?、赋值、副作用等主题。

关键标签 / 关键词

数据抽象、构造器、选择器、愿望思维、抽象屏障、分层系统、有理数算术、序对（pair）、cons/car/cdr、盒指针表示法、闭包（closure）、Church 编码、过程即对象、延迟决策、数据与过程的界限、SICP、MIT 6.001

本讲要点速查

概念 核心要点 易错点
数据抽象 用构造器+选择器隔离使用与表示 直接写 (car (car s)) 会破坏屏障
愿望思维 假设过程已存在，先写上层 契约必须明确（如有理数比值不变）
序对公理 car(cons x y)=x，cdr(cons x y)=y 箭头几何方向无意义
闭包 组合结果可再组合 数组常不满足闭包
过程实现序对 cons = λpick. if pick=1 then x else y 需用替换模型验证
过程即对象 每次 cons 创建独立对象 对象同一性是深层问题

生成时间：2026-10-11 17:09:11 生成平台：VideoNote www.xygy.top