视频封面

视频元信息

  • 课程：MIT 6.001 Structure and Interpretation of Computer Programs（SICP）1986 原版
  • 本讲主题：流（Streams）——上篇
  • 主讲：Hal Abelson（本讲），Jerry Sussman（上节课引入赋值与状态）

内容摘要（TL;DR）

本讲引入「流处理」范式，作为对「对象/状态/赋值」范式的替代。核心思想：把程序拆解为枚举器（enumerate）→ 过滤器（filter）→ 映射（map）→ 累加器（accumulate） 的流水线，用统一的数据结构「流（stream）」连接各部件。流通过 delay（延迟求值）与 force（强制求值）实现按需计算，从而兼顾优雅与效率。

一、回顾：赋值与状态带来的麻烦 [00:18]

上节课 Jerry 引入了赋值（assignment）与状态（state），后果「absolutely frightening（极其可怕）」。

核心影响：

  • 替换模型（substitution model）彻底失效：不是「这个替换模型不太好用，换一个」，而是任何类似替换模型的东西都不可能再工作。
  • 变量不再只是「代表一个值」，而是必须指定一个「存放值的位置」，且该位置上的值可以改变。
  • 像 f(x) 这样的表达式可能带有副作用（side effect）：先调用 f(x) 得到一个值，稍后再调用 f(x) 可能得到不同的值，取决于求值顺序。
  • 于是我们必须同时思考值和时间。
  • 序对（pair）不再等同于它的 car 和 cdr，而在于它的身份（identity）。两个 car、cdr 相同的序对，可能是同一个对象，也可能是不同对象——必须关心共享（sharing）。

易错点：引入赋值后，语言的含义不再能用数学方式（替换模型）解释，必须用更「机械」的环境模型（environment model）和图示来定义程序语句的含义。这是概念上的根本转变，不是单纯的技术细节。

为什么我们会陷入这个麻烦？

  • 因为我们想构建模块化系统，希望程序能自然地拆分成块。
  • 例：把随机数生成器的状态封装在内部，从而将「选随机数」与「蒙特卡洛估计策略」分离，也与 Cesaro 求 π 的具体随机数用法分离。
  • 例：建模数字电路时，希望程序拆成的块能映照现实系统的部件——每个部件有身份、有状态，状态存在于导线上；系统变化被看作信号流入、改变这里的状态、再传到那里。

理解：赋值和状态让我们能「像现实世界一样」写程序，但代价是引入了顺序、别名、共享等复杂性。

二、换个视角：也许「时间」才是问题 [05:29]

Hal 提出一个大胆的反思：也许为「映照现实」付出如此技术代价，是因为我们对现实的看法错了——也许时间只是幻觉，没有什么会改变。

两个例子：

  1. 粉笔：我们说粉笔是对象、有状态（每一刻有位置和速度），状态会变化。但学过相对论的人不会把粉笔的轨迹看作「一刻接一刻」，而更愿意把粉笔的整个存在看作时空中的一条路径——没有单独的位置和速度，只有它在时空中不变的存在。
  2. 电子系统 / 信号处理：设计信号处理系统的工程师不会想「每一刻有电压进来，转化成什么，影响这里的状态，再改变那里的状态」。他们会说：有一个信号，它随时间整体展开；这个盒子作为一个滤波器，把整个输入变换成整个输出。你把它看成一个整体，而不是小部件在特定时刻互发状态消息。

结论：今天要看的另一种系统分解方式，更接近信号处理工程师的世界观，而不是「对象互相发消息」的世界观。它叫 流处理（stream processing）。起点是：扔掉程序中对时间的过度关注，让程序更统一、看到更多共性。

三、两个看似不同、实则相同的程序 [08:16]

3.1 程序一：求树中奇数叶子的平方和

  • 给定一棵整数二叉树，每个节点有整数。
  • 目标：找出所有奇数，求它们的平方，再求和。
  • 递归策略：对每个叶子，若是奇数则贡献其平方，偶数则贡献 0；整棵树的求和 = 左子树之和 + 右子树之和。

3.2 程序二：求前 n 个斐波那契数中的奇数

  • 给定整数 n 和函数 f，对 1 到 n 的每个整数 k 计算 f(k)。
  • 目标：把满足某性质的函数值收集成列表。
  • 具体：计算第 k 个斐波那契数，看哪些是奇数，组装成列表。
  • 写法是标准的迭代循环（对 k 递归）：k > n 则空列表；否则计算第 k 个斐波那契数 f，若为奇数则 cons 到后续结果，否则直接取下一个。

3.3 用信号处理的语言描述两者

程序一：枚举树的叶子 → 过滤出奇数 → 映射求平方 → 用加法从 0 开始累加。

程序二：枚举区间 1..n → 映射求斐波那契数 → 过滤出奇数 → 用 cons 从空列表开始累加。

理解：这两个程序的结构在代码里看起来完全不同，但用「枚举-过滤-映射-累加」的语言描述后，几乎一模一样。

3.4 问题所在：共性被代码结构掩盖了

回到「求奇数平方和」的代码，问：

  • 枚举器在哪里？ 不在一个地方——一部分在「叶子节点测试」里（判断何时停止），一部分在递归结构本身里。
  • 累加器在哪里？ 也不在一个地方——一部分在这个 0，一部分在这个 +。

「求奇数斐波那契数」也一样：枚举器一部分在 > 测试里，一部分在循环的递归结构和调用方式里；累加器也散落各处。

核心原则：计算机科学的一条基本原理是——要控制某样东西，你需要它的名字。这些非常自然的「盒子」（枚举器、过滤器、累加器）在程序里没有名字、没有显式出现，因为我们没有合适的语言去谈论它们，所以无法真正掌控这种思维方式。

解决方向：发明一种合适的语言，能构建这些部件。关键问题是——在这些盒子之间流动的「信号」是什么？ 答案：一种叫流（stream）的数据结构。

四、什么是流（Stream）？[14:43]

流是一种数据抽象（data abstraction），需要给出它的构造器和选择器。

构造器：

  • cons-stream：把两个东西组合成一个流。

选择器：

  • head（流头）
  • tail（流尾）

公理（axioms）：

  • 对任意 x 和 y：head(cons-stream(x, y)) = x
  • 对任意 x 和 y：tail(cons-stream(x, y)) = y

另外：还有一个 the-empty-stream（空流），类似空列表。

思考：这些公理和 cons/car/cdr 的公理完全一样。如果把 cons-stream 写成 cons，head 写成 car，tail 写成 cdr，就是序对的公理。

为什么引入新术语，而不直接用序对和列表？

提醒：暂时可以「假装」流就是列表的另一种叫法。但很快会看到，为什么要保留这层额外的抽象——流不是列表，这是本讲后面「鱼与熊掌兼得」的关键。

五、流的操作部件 [17:35]

有了流，就可以构建操作流的「语言部件」：

5.1 map（映射）

  • 输入：一个流 S 和一个过程。
  • 输出：新流，元素是过程依次作用于 S 的每个元素。
  • 实现：若流为空则返回空流；否则构造新流，首元素是 proc(head(S))，其余是 map(proc, tail(S))。
  • 这和列表的 map 完全一样，只是把判空换成 empty-stream?。

5.2 filter（过滤）

  • 输入：一个谓词和一个流。
  • 输出：新流，包含原流中所有满足谓词的元素。
  • 实现：若流为空则返回空流；测试 pred(head(S))，若真则把 head 加到 filter(pred, tail(S)) 上，否则直接 filter(pred, tail(S))。

5.3 accumulate（累加）

  • 输入：一个组合方式（如 +）、一个初始值、一个流。
  • 实现：若流为空则返回初始值；否则把 head(S) 与「从初始值开始累加 tail(S)」的结果组合起来。
  • 例：用 + 累加即可求流中所有元素之和。

5.4 其他部件

  • 枚举树叶子：若树本身是叶子，则生成只含该节点的流；否则把左子树、右子树的枚举结果用 append 拼接。
  • 枚举区间：enumerate-interval(low, high) 生成从 low 到 high 的整数流。
  • append：类似列表的 append。

六、用流重写两个程序 [20:41]

求树中奇数平方和：

accumulate(+, 0, map(square, filter(odd?, enumerate-leaves(tree))))

求奇数斐波那契数：

accumulate(cons, empty, filter(odd?, map(fib, enumerate-interval(1, n))))

理解：现在代码恰好长得像信号处理的框图了——枚举、过滤、映射、累加各司其职。

6.1 流处理的好处

  • 可混搭（mix and match）：想改成「先求整数平方再过滤」，只需换一个标准部件 map square；想对树的叶子做斐波那契计算，只需把枚举器换掉。
  • 建立约定接口（conventional interfaces）：这是本课程的一大主题。map、filter 等成为标准组件，可以各种方式拼装程序。
  • 揭示程序的共性：这是「生成-测试（generate and test）」范式。

重要事实（考点）：MIT 研究生 Richard Waters 在其论文研究中分析了 IBM 科学子程序库的一大块，发现其中约 60% 的程序都可以只用 map、filter、accumulate 表达出来。

6.2 课堂问答

  • 问：本质是不是就是「有一个非常统一、简单的数据结构——流」？
  • 答：本质是约定接口，让你能把很多东西拼起来；流是支撑这一切的统一数据结构。这很像 APL——APL 也是同样的思想，只不过用数组和向量代替流，APL 的强大正源于此。

七、两个更复杂的例子 [25:03]

7.1 flatten（展平流之流）

  • 场景：有一个流，其每个元素本身也是流（如第一个元素是 1,2,3...）。想把所有子流中的元素收集成一个流。
  • 实现：flatten(stream-of-streams) = accumulate(append-streams, the-empty-stream, stream-of-streams)。
  • 这是用高阶操作做有趣运算的例子。

7.2 flatmap（扁平映射）

  • flatmap(f, S)：f 是一个函数，对 S 中每个元素产生一个流；把所有流合并。
  • 实现：flatten(map(f, S))——对 S 每个元素应用 f 得到流，映射后得到「流之流」，再展平。

7.3 案例：求所有满足 i+j 为素数的数对

  • 问题：给定整数 n，找出所有数对 (i, j)，0 < j < i ≤ n，使得 i + j 为素数。输出 (i, j, i+j) 三元组的流。
  • 例：n = 6 时，i=2,j=1 得 3；i=3,j=2 得 5；i=4,j=1 得 5；等等。

构建步骤：

  1. 对区间 1..n 中的每个 i，生成一个流；
  2. 对每个 i，对区间 1..i-1 中的每个 j 生成数对 (i, j)；
  3. 对每个 i 用 flatmap 展开——现在有了所有数对 (i, j)；
  4. 用谓词「car + cadr 为素数」filter 这些数对；
  5. 对过滤结果 map，生成 (i, j, i+j)。

理解：嵌套循环在此表现为 flatmap 的嵌套组合——flatmap 的 flatmap 的 map……

易错点：一直手写「flatmap 套 flatmap 套 flatmap」非常糟糕，prime-sum-pairs 即使每块都简单，整体也难读。

7.4 语法糖：collect

  • collect 是这种「flatmap/filter 嵌套」的缩写（syntactic sugar）。
  • 用 collect 重写 prime-sum-pairs：收集结果 (i, j, i+j)，其中 i 遍历 1..n，j 遍历 1..i-1，且 i+j 为素数。
  • 可以看到 collect 的各部分正好对应原程序的各部件。

八、八皇后问题与回溯搜索 [33:20]

8.1 问题描述

  • 在棋盘上放 8 个皇后，使任意两个都不互相攻击（不同行、不同列、不同对角线）。
  • 需要先有表示棋盘、位置的方法（暂不关心），假设有谓词 safe：给定已放好的皇后位置，判断在某个位置再放一个是否安全。

8.2 传统做法：回溯搜索（backtracking）

  • 在第 1 列尝试 8 种放法；在每种前提下尝试下一列……每个分支代表该层的可能性；
  • 走到某处发现不行就回退到上一层，换一种可能，再往下走；
  • 若某处下面无解，一直回退；最终若能走到底就找到解。
  • 这是编程中常用的回溯搜索，但很复杂。

为什么复杂？ 因为它过度关注时间——「我试了这个，我又试了那个，我回到上一个可能性」。一旦这么在意时间，描述就变复杂。

8.3 流的做法：扔掉时间，看整体

新思路：假设我手上已经有「在前 k-1 列放好皇后的所有可能方式」（不关心怎么得到的）。如何扩展到第 k 列？

  • 对每种已有位置，尝试在每一行放一个新皇后，得到下一层；
  • 用 safe 过滤，只保留安全的；
  • 就得到了「到第 k 列的所有解」。

递归策略：fill-columns(k) 表示在前 k 列安全放皇后。

  • 若 k = 0，解就是空棋盘；
  • 否则用 collect：枚举「前 k-1 列的所有解」，枚举「尝试的新行（size 行）」，收集「新行 + 新列 + 已有皇后」，条件是安全。

关键点：这个程序不仅解决八皇后，还给出所有解——结果是流，流中每个元素是一种解法。

为什么更简单？ 因为我们扔掉了「这是一个随时间发生、有状态的过程」的想法，只说它是「一整个集合」。这正是本讲开头的主题——改变我们对「要建模什么」的看法：不再建模随时间演化、有步骤、有状态的东西，而是建模整体（像粉笔的整条时空轨迹，而非每一刻的状态）。

8.4 课堂提问与悬念

  • 问：回溯法似乎只找第一个解，而这个递归搜索找所有解；如果搜索空间很大，第二种会不会变得不可能？
  • 答：这正是本讲余下部分要回答的——「它很美，但难道不是极其低效吗？」Hal 让大家在此刻保持怀疑。

九、怀疑与「陷阱」：效率问题 [43:03]

Hal 提醒：现在应该开始怀疑了。

  • 我们展示了这种简单优雅的拼装方式，与那些「丑」的传统程序（求奇数平方和、求奇数斐波那契数）形成对比——后者把枚举器、过滤器、累加器混在一起，失去了流处理的概念优势和混搭能力。
  • 但大多数程序看起来都像那些丑的。难道计算机科学家都那么迟钝，没发现这样写更优雅？一定有陷阱。

9.1 陷阱：效率

例子：求 10,000 到 1,000,000（或更大范围）之间的第二个素数。

  • 用流：枚举 10,000 到 1,000,000 的所有整数 → 过滤出素数（测试每一个）→ 取第二个元素（head(tail(...))）。
  • 这显然荒谬：机器里根本放不下这么多整数，更别说测试它们，而我们只要第二个。

核心矛盾：传统编程风格的力量恰恰就是它的弱点——它把枚举、测试、累加混在一起，所以不会全部做完。让程序概念上丑陋的东西，正是让它高效的东西。

9.2 转折：鱼与熊掌可以兼得

Hal 说：我们可以既优雅又高效——写出和上面一样的流程序，同时让机器运行时像传统风格一样高效。

关键：流不是列表（streams are not lists）。

十、流如何实现按需计算 [47:07]

10.1 两种图像对比

如果流就是列表：先对整条流做第一个 filter，处理完所有元素得到新流；再把这个结果整个送进第二个处理单元……每一步都处理全部数据。

真正的流：各部件通过数据连接。想要结果时，从末端「拽（tug）」一下：

  • 末端部件说「我需要更多数据」，去拽它的上游；
  • 上游再去拽更上游（如 filter、枚举器）；
  • 只有被拽到的部分才被生成，只有需要的元素才流过处理单元。

理解：这就是「按需计算（on-demand computation）」——流是一种会增量地计算自己的数据结构。

10.2 实现的关键：程序与数据没有严格界限

这是贯穿全课程的基本思想之一。流同时是：

  • 你想象中的数据结构（如「树叶子组成的流」）；
  • 一个知道如何计算自己的过程。

不需要额外机制——只需要「过程作为一等对象（first-class procedures）」这一点。

10.3 cons-stream、head、tail 的真实定义

  • cons-stream(x, y) 是 (cons x (delay y)) 的缩写——把 x 和一个 delay y 组成序对。
  • head(S) 就是 car(S)。
  • tail(S) 是 force(cdr(S))。

delay 是什么？ 取一个表达式，产生一个承诺（promise）：当你需要时才计算该表达式。它不做任何计算，只给你一张「欠条」。

force 是什么？ 调用那个承诺，真正计算它。

十一、逐步追踪：求第二个素数 [52:20]

以「求 10,000 到 1,000,000 之间的第二个素数」为例，用替换模型逐步追踪（因为流没有副作用，替换模型可用）。

  1. 表达式：head(tail(filter(prime?, enumerate-interval(10000, 1000000))))
  2. enumerate-interval 构造出 cons-stream(10000, <承诺计算 10001 到 1000000>)，即 cons(10000, delay(...))。目前只生成了一个整数。
  3. filter 先测试 head，即 10000——不是素数，于是递归 filter 其 tail。
  4. tail 触发 force，计算那个承诺，得到下一个：cons(10001, delay(...))。
  5. filter 测试 10001——不是素数，再次 force……
  6. 一直 force 到第一个素数是 10009，此时停止，这就是第一个素数。
  7. 需要第二个素数时再继续。

结论：枚举器不会生成超过 filter 需要的整数；filter 也不会生成超过你需要的元素。我们把「生成与测试的混合」放进了机器实际运行的过程中，尽管从程序表面看不出来。

十二、delay 与 force 没有魔法 [55:03]

  • delay 某表达式 = (lambda () <表达式>)，即无参数的过程。过程本身就是「承诺计算一个表达式」。
  • force 一个承诺 = 调用那个过程，即 (promise)。

核心洞察：delay 做的事，是解耦（decouple）程序表面的事件顺序与机器实际的事件顺序。我们放弃了「程序运行顺序映照某种清晰时间观」的想法，从而给 delay 自由去安排计算顺序。这就是全部要点。

十三、memoization：避免重复计算 [56:34]

13.1 问题

在这些递归流程序中，会出现大量 tail(tail(tail(...)))。如果每次计算 tail 都要重新求值一个过程、再重算它的 tail、再重算……会非常低效。就像列表元素都在那儿，不必每次取下一个 tail 都重算。

13.2 解决方案：memo-proc

把 delay 的缩写改成 (memo-proc (lambda () <表达式>))。

memo-proc 把一个无参过程转换成只计算一次的过程：

  • 第一次调用时运行原过程，记住结果；
  • 以后调用直接返回缓存结果。

实现思路：内部有两个「标志」——「是否已经运行过」（初始为否）和「上次的结果」。

  • 若未运行过：计算 proc，把结果存入变量 result，标记「已运行」，返回 result；
  • 若已运行过：直接返回 result。

这就是所谓的 memoization（记忆化），它短路了「重算 tail 的 tail 的 tail……」。有了它，流的运行效率与传统程序几乎相同。

13.3 总结性洞察

  • 我们利用了「过程与数据没有明确分界线」这一事实，写出了「像过程一样的数据结构」。
  • 我们把一种常见控制结构——迭代——嵌入到数据结构中：因为流的 tail 是一个过程，它「自带」迭代控制结构。这就是流的本质。

十四、课堂问答要点 [59:38]

  • 问：tail 的 tail……如果不用 memo-proc，force 会真的执行过程；memo-proc 只是绕过了「tail 的 tail 的 tail 总是执行同一个」的问题吗？

  • 答：是的。要点是——为了得到答案必须做一次计算；但一旦找到了流的 tail，要得到 tail 的 tail，不应该重算第一个 tail。若不用 memo-proc，这种重算就会发生。

  • 问：你说因为无副作用所以能用替换模型。如果某个过程有副作用、有状态，还能用流模型吗？

  • 答：也许可以，但这是个难题。一般来说，除非非常小心，任何输入输出的副作用都会把一切搞乱。后面会专门讲「替换与副作用不能很好混合」的地方。

  • 问：memo-proc 操作中，lambda 何时执行？执行 memo-proc 时只是生成 lambda 表达式，并不求值。

  • 答：正确。进入 memo-proc 的 proc 是无参过程，将来某天你会调用它。memo-proc 把它转换成另一个无参过程（那个 lambda），将来某天你会调用。lambda 在你调用 memo-proc 的结果时被调用——也就是你本来会调用原过程的时刻。

  • 问：是不是实际上必须把列表建起来，但元素不求值？每个阶段实际在建列表？

  • 答：不完全对。以「枚举 1 到十亿」为例：它就是一个 cons(1, <承诺>) 的序对，什么都没建起来。当你 force 它，这个承诺递归地又是一个 cons-stream：2 和一个承诺……直到你沿着流走下去，才逐步构建。因为这里放的不是列表，而是生成列表的承诺（技术上就是过程）。流不会提前建起来。

关键标签 / 关键词

SICP 6.001 流处理 stream processing delay force memo-proc memoization 按需计算 惰性求值 约定接口 conventional interfaces map filter accumulate flatmap flatten collect 生成-测试范式 八皇后 回溯搜索 替换模型 赋值与状态 副作用 过程与数据 迭代控制结构 Richard Waters APL

生成时间：2026-10-11 14:24:22 生成平台：VideoNote www.xygy.top