视频封面

视频元信息

  • 课程：MIT 6.001 Structure and Interpretation of Computer Programs（1986 原版）
  • 本讲主题：流（Streams）下半部分——延迟求值、无穷流、流处理范式与函数式编程的边界

内容摘要（TL;DR）

本讲延续"流"的主题，核心解决三个问题：流元素何时被求值（force 的时机）、如何用流表示无穷序列（整数流、素数流、斐波那契流）、流的信号处理视角（add-streams、scale-stream、积分器）。最后深入探讨延迟求值带来的根本矛盾：normal order 语言虽优雅，但与赋值/副作用不兼容，无法表达迭代，也带来"拖尾问题"和交互式调试困难。老师指出这是计算机科学中一个根本性的难题。

一、流的按需求值：force 的时机 [00:20]

要点

流的本质是"惰性"：只有当我们真正需要某个元素时，它才会被计算。这是流能够表示超长甚至无穷序列的关键。

详细说明

两种"请求"流元素的方式：

  1. 取第 n 个元素：写一个递归过程 stream-ref（视频中称为 nth element），沿流向下走：
    • 若 n = 0，计算并返回流的 head（即 car）
    • 否则递归访问流的 tail（即 cdr），n 减 1

理解：这与列表的 nth 过程几乎一样，唯一区别是——列表的元素在构造时已经全部算好了，而流的元素只有在向下走、真正访问到时才会被计算。

  1. 打印整个流：print-stream 过程
    • 打印 head（这一步会强制（force） head 被计算）
    • 递归打印 tail
    • 结束时返回一个 "done" 消息

易错点：流的元素不是一开始就全部计算好的。print-stream 会随着打印过程逐个触发元素的计算。如果流非常长（甚至无穷），打印会一直进行下去，需要人为中断。

核心结论：流可以非常长——甚至可以是无穷长的。

二、无穷流实例：整数流与"无 7 整数流" [02:35]

要点

用 cons-stream 可以定义无穷流，因为 cons-stream 内部隐藏了 delay，使得递归定义成为可能。

详细说明

定义整数流（从 n 开始）：

(define (integers-from n)
  (cons-stream n (integers-from (+ n 1))))

理解：这个定义表面上是"无穷递归"，但它能工作，是因为 cons-stream 不会立即求值第二个参数——它只留下一个"承诺"（promise），等到访问 tail 时才真正递归展开。

定义所有整数：

(define integers (integers-from 1))

查询第 20 个整数：得到 21（因为计数从 0 开始）。

更复杂的例子——过滤出不能被 7 整除的整数：

(define (divisible? x y) (= (remainder x y) 0))
(define no-sevens
  (stream-filter (lambda (x) (not (divisible? x 7)))
                 integers))
  • 查询 no-sevens 的第 100 个元素 → 得到 117
  • 用 print-stream 打印全部 → 会一直打印下去，需要等待很长时间

Henderson 图（Henderson Diagrams）

老师画出整数流的程序结构图，并介绍这种图叫 Henderson 图，由 Peter Henderson 首创（他也是 S1 语言的作者）。

图约定：

  • 实线：流（stream）的输出
  • 虚线：初始值（initial value）的输入

理解：integers-from 盒子接收一个整数 n，先把它 +1，再递归送入另一个 integers-from 盒子；同时把原始的 n 和递归结果用 cons-stream 组合成一个流输出。

哲学性提问

"如果每当你去看的时候它都在那里，它是否真的存在？" —— 就像你银行储蓄账户里的钱一样。

思考：这是"流"作为数据结构的核心哲学——它不是预先存在的全部数据，而是"按需生成"的构造。这与现实世界中"潜在存在"的概念相呼应。

三、埃拉托斯特尼筛法：无穷素数流 [08:30]

要点

用流优雅地实现埃拉托斯特尼筛法（Sieve of Eratosthenes），生成无穷素数流。

算法原理（原始版本）

  1. 从 2 开始列出所有整数
  2. 第一个数（2）是素数
  3. 划掉所有能被 2 整除的数
  4. 剩下的第一个数（3）是素数，划掉所有能被 3 整除的数
  5. 依次类推，永远进行下去
  6. 最终剩下的就是所有素数

流版本实现

(define (sieve stream)
  (cons-stream
    (stream-car stream)
    (sieve (stream-filter
             (lambda (x) (not (divisible? x (stream-car stream))))
             (stream-cdr stream)))))

(define primes (sieve (integers-from 2)))

执行过程：

  • 取流的 head 作为素数输出
  • 用 head 去过滤 tail（扔掉所有能被 head 整除的数）
  • 对过滤结果递归调用 sieve

结果验证：

  • 第 20 个素数 → 73
  • 老师强调：只有在开始请求第 20 个素数时，计算才真正开始

【拓展】埃拉托斯特尼筛法的复杂度

理解：经典筛法需要预先知道上界 N，复杂度 O(N log log N)。而流版本是"增量式"的，可以无限生成素数，但每个素数都需要维护一个过滤器链，空间开销随已生成素数数量增长。这是"惰性"换来的优雅，也带来一定代价。

无穷递归过滤器

老师强调：sieve 是一个无穷递归的过滤器——sieve 盒子里面还有 sieve 盒子，再里面还有……这体现了信号处理视角与递归计算视角的融合。

四、流处理的另一种视角：整体操作 [12:30]

要点

前面所有例子都是"生成器"视角——逐个生成流元素。现在切换到"整体操作"视角——把整个流当作一个对象来操作。

两个基础工具

1. add-streams（逐元素相加）

(define (add-streams s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (cons-stream
           (+ (stream-car s1) (stream-car s2))
           (add-streams (stream-cdr s1) (stream-cdr s2))))))

理解：如果任一为空，返回另一个；否则新流的 head 是两个 head 之和，tail 是递归相加。

2. scale-stream（按常数缩放）

(define (scale-stream s k)
  (stream-map (lambda (x) (* x k)) s))

理解：本质就是 map 一个"乘以常数"的函数到流上。

五、无穷流 ones 与整数流的另一种定义 [14:30]

要点

利用 add-streams 和 scale-stream，可以写出自引用（self-referential）的流定义。

ones 流

(define ones (cons-stream 1 ones))

理解：这是一个无穷的 1 流。第一个元素是 1，tail 又是 ones 本身。因为 cons-stream 隐藏了 delay，所以定义 ones 时不需要 ones 已经存在——定义完成后，ones 就有了。

展开来看：

ones = (cons 1 (delay ones))

推导：定义时，系统先构造 cons 的第一个部分（1），第二个部分是一个 promise（承诺稍后计算）。所以定义能成功完成。之后访问 tail 时，才会去 force 那个 promise，此时 ones 已经有定义了。

整数流的循环定义

(define integers
  (cons-stream 1 (add-streams ones integers)))

理解：integers 的第一个元素是 1；其余部分 = ones + integers（逐元素相加）。这样 integers 的第二个元素 = ones[1] + integers[1] = 1 + 1 = 2，第三个 = 1 + 2 = 3……

整数流的 Henderson 图（反馈回路）

  • ones 流进入 add-streams（加法器）
  • 加法器输出 integers
  • integers 又反馈回加法器的另一个输入
  • 需要一个初始值 1 来"启动"

思考：这个图非常像有限状态累加器或数字信号处理中的积分器——本质上就是一个反馈系统。

六、积分器：从整数流到信号处理 [17:30]

要点

把上述反馈结构推广，就得到流的积分器（integral），它与模拟计算机中的积分器块图完全对应。

积分器实现

(define (integral s initial-value dt)
  (define int
    (cons-stream initial-value
                 (add-streams (scale-stream s dt)
                              int)))
  int)

说明：

  • 输入流 s 先乘以 dt（时间步长）
  • 与 int 自身相加（反馈）
  • 初始值是 initial-value
  • 使用内部定义 int 实现自引用

理解：这个程序几乎就是模拟计算机解微分方程的块图程序。初始值就是积分器的初值。

七、斐波那契流 [19:30]

要点

用流可以非常优雅地定义斐波那契数列。

定义

(define fibs
  (cons-stream 0
    (cons-stream 1
      (add-streams (stream-cdr fibs) fibs))))

展开过程：

  • fibs 开头是 0, 1
  • 其余部分 = fibs 的 tail + fibs 本身（逐元素相加）
  • 已知 fibs 开头 0, 1，tail 开头 1
  • 所以下一个 = 0 + 1 = 1
  • 再下一个 = 1 + 1 = 2
  • 再下一个 = 1 + 2 = 3
  • 再下一个 = 2 + 3 = 5
  • ……

重点：斐波那契流的定义体现了流的核心思想——用"自身"和"自身的 tail"来定义自身，因为 delay 让这种自引用成为可能。

八、程序与数据的统一 [21:00]

要点

老师做了一段哲学性总结：程序与数据之间最终没有本质区别。

说明

  • 在某种意义上，底层空间里存放的就是过程，只是我们不那样看待它们
  • 既然有递归过程，那么自然也应该有递归数据
  • 流正是"递归数据"的典型体现——数据本身可以自引用

思考：这与 Lisp 的"代码即数据"（homoiconicity）哲学一脉相承。SICP 反复强调这一主题。

九、流解决不了的问题：解微分方程时显式 delay 的困境 [22:00]

要点

流并非万能。当系统存在复杂的自引用时，必须显式插入 delay，否则无法工作。

例子：解微分方程 dy/dt = y²，y(0) = 1

模拟计算机块图：

  • y 是积分器输出，初值 1
  • dy 是 y 经过平方器（square）的输出
  • 积分器输入是 dy

流程序（错误版本）：

(define y (integral dy 1 0.001))
(define dy (stream-map square y))

问题所在：

  • 定义 y 时，需要 dy，但 dy 还没定义 → 报错
  • 反过来先定义 dy，又需要 y → 也报错
  • 两个定义互相依赖，谁先谁后都不行

为什么 ones 可以，这个不行？

理解：ones 能自引用，是因为 cons-stream 内部隐藏了 delay——构造 ones 时不需要 tail 的值。

关键洞察：

  • cons-stream 可以延迟，因为不看 tail 也能知道流的第一个元素
  • integral 也应该可以延迟，因为不看被积分的流也能知道积分的第一个元素（就是初值）

改进版 integral（显式 delay 版本）

(define (integral delayed-s initial-value dt)
  (define int
    (cons-stream initial-value
                 (let ((s (force delayed-s)))
                   (add-streams (scale-stream s dt)
                                int))))
  int)

关键改动：被积分的流是延迟对象（delayed object），只有访问 tail 时才 force 它。

正确写法

(define y (integral (delay dy) 1 0.001))
(define dy (stream-map square y))

推导：定义 y 时，integral 不需要 dy 的值，只需要知道初值 1，所以 y 定义成功。此时 y 和 dy 都有了第一个元素。之后向下走时，才 force dy，dy 又 force y，两者都已定义，可以正常展开。

十、延迟求值的代价：拖尾问题与调试困难 [26:30]

要点

老师指出：为了获得流的强大能力，有时不得不显式插入 delay，这让程序变得复杂。

问题描述

  • 简单例子（如微分方程）还能看清哪里需要 delay
  • 复杂系统中，各种自引用交织，很难看出哪里需要 delay
  • 如果遗漏 delay，很难诊断为什么程序不工作

出路：把 delay 内建到语言中

方案：让所有过程都像 cons-stream 一样，对参数自动加隐式 delay。

  • 调用过程时，参数不立即求值
  • 参数以 promise 形式传递
  • 只有真正需要值时（传给原始操作符时）才 force

这样的语言叫做 normal order（正则序）求值语言，与我们现在用的 applicative order（应用序） 相对。

两种求值模型的对比

模型 求值时机 替换模型
应用序（applicative order） 先求值所有参数，再代入过程体 先算参数值再代入
正则序（normal order） 参数不求值，以 promise 代入过程体 代入表达式本身，直到遇到原始操作符才化简

理解：正则序就是"惰性求值"的极端形式——所有东西都是 promise，直到最后才 force。

正则序语言的优点

如果 cons 本身就是延迟过程，那么 cons 就等同于 cons-stream，列表自动变成流，所有数据结构都自动具有惰性——不需要显式的 delay。

十一、正则序语言的代价 [31:00]

要点

正则序虽优雅，但代价不小。

代价 1：无法表达迭代

以迭代版阶乘为例：

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

在应用序中：product 每次都被求值成具体数字，状态不增长 → 是真正的迭代。

在正则序中：(* counter product) 不会被求值，而是作为 promise 传给下一次调用。下一轮又包一层 promise……状态不断增长，不再是迭代，而是递归展开。

推导：写替换模型可以看出，所有 promise 被记住，最后才一起 force，导致状态膨胀。

易错点：正则序语言无法真正表达迭代过程，因为参数总是以 promise 形式传递，导致状态不断累积。

代价 2：拖尾问题（Dragging Tail Problem）

  • 用正则序语言写文本编辑器等真实系统
  • 运行一段时间后，内存里堆积了大量未 force 的 promise
  • 这就是所谓的"拖尾问题"（dragging tail）
  • 需要研究编译器技术来消除这些拖尾

代价 3：正则序与副作用不兼容

核心矛盾：normal order 求值 与 side effects（副作用）根本无法共存。

十二、正则序与副作用冲突的经典例子 [36:30]

要点

用一个极简例子说明 normal order 与赋值（set!）的深层冲突。

例子

(define x 0)
(define (identity n) (set! x n) n)
(define (increment n) (+ n 1))
(define y (increment (identity 3)))

在正则序语言中：

  • 定义 y 时，(identity 3) 不被求值，而是作为 promise 传入
  • 此时查看 x → 仍然是 0（identity 还没被调用）
  • 查看 y → y 是 4，这一步触发 identity 被调用，x 才变成 3

结果：

  • 定义后立即看 x → 0
  • 看 y 之后再查 x → 3

思考：这种"什么时候求值"的不确定性，让交互式程序的调试变得极其混乱。这是延迟求值的根本代价。

深层原因

  • 延迟求值的本质是抛弃时间（throw away time）
  • 而状态、赋值、变化恰恰是关于时间的
  • 因此二者存在根本性的矛盾

十三、函数式编程：纯粹函数式语言的利与弊 [39:30]

要点

介绍纯函数式语言（purely functional language）——没有副作用、没有赋值操作符的语言。

优点

  • 没有时间概念 → 没有同步问题
  • 并行算法可以任意切分，各部分独立运行
  • 是非常友好的并行计算环境
  • 可以用替换模型和数学推理来理解程序

代价

  • 必须放弃赋值（assignment）
  • 支持者认为这是"很小的代价"——大多数时候本来就不该用赋值

函数式视角的模块化

随机数生成器的例子（Cesaro 求 π）：

  • 传统视角：随机数生成器是一个有局部状态的对象，用 set! 隐藏状态
  • 函数式视角：直接生成一个无穷随机数流，通过某个处理器（测试过程）得到π 的逼近值流

理解：模块化的本质不是"对象封装状态"，而是"把无穷流当作整体来思考"。

银行账户的例子

消息传递视角：

  • 银行账户是一个对象，有局部状态 balance
  • 用户发送交易请求（deposit）
  • 账户返回当前余额

流视角（无副作用）：

  • 银行账户处理交易请求流
  • 输入：1, 2, 2, 4……（存款金额）
  • 输出：1, 3, 5, 9……（余额流）
  • 实现：
(define (make-deposit-account balance deposit-stream)
  (cons-stream balance
    (make-deposit-account
      (+ balance (stream-car deposit-stream))
      (stream-cdr deposit-stream))))

理解：这是一个"消息传递对象"用无副作用方式实现的典型例子。用户完全看不出这个系统没有状态。

十四、纯函数式的边界：合并（merge）难题 [46:30]

要点

纯函数式编程在某些场景下会崩溃——尤其是涉及 两个独立主体共享资源 时。

联合银行账户的例子

  • Bill 和 Dave 共享一个银行账户
  • 两人各自产生一个交易请求流
  • 需要一个 merge（合并） 过程把两个流合并成一个

merge 的困境

朴素想法：交替取 Bill 和 Dave 的请求。

问题：如果 Dave 去度假两年，Bill 就被卡住了——系统在等 Dave 的下一个请求。

理想方案：fair merge（公平合并）

  • 应该交替取
  • 但如果一边没有请求，应该允许另一边连续取两次
  • 老师坦言："我甚至没法在不谈时间的前提下描述 fair merge"

根本问题

merge 的输出不是输入流的函数——它依赖于输入流和某种时间信息。

  • 如果 Bill 输入 1,1,1,1……，Dave 输入 2,2,2……
  • 输出应该是什么？"1,2,1,2" 不够描述——因为什么时候取谁，取决于实时情况
  • 而正则序语言没有时间概念

现实约束

  • 用户"不幸地存在于时间中"
  • 用户坐在银行窗口等待应答
  • 在分时系统上，用户敲一个字符希望立即得到响应
  • 不能等整个系统的所有人敲完一个字符才轮到自己

思考：这就是"抛弃时间"与"真实世界"之间的根本张力。

可能的出路

  • 给输入显式加时间戳，然后按时间戳排序
  • 或者把时间离散化（每微秒读一次，没有就是空的）
  • 老师评价："这些都是 hack（权宜之计）"

更深层的问题

  • 即使有 fair merge，也无法处理动态加入新参与者的情况（比如突然加入 John）
  • 需要更一般的机制（老师提到有叫 "managers" 之类的东西）
  • 这是一个活跃的研究领域：如何把副作用的需求局限在定义良好的模块中，不让它泄漏到整个系统

十五、总结：一个根本性的难题 [55:30]

要点

老师总结本讲的核心洞察：如何设计既支持延迟求值、又能反映"世界中对象"视角的语言，是计算机科学的一个基本难题。

说明

  • 延迟求值带来优雅（无穷流、无同步问题）
  • 对象视角带来表达力（局部状态、真实世界建模）
  • 二者存在根本性的不兼容
  • 老师甚至怀疑：这可能不只是计算机科学的问题，而是关于两种不兼容的世界观的问题

关于赋值的讨论

有学生问：是否有技术或准则来局部化赋值的影响，让"非常小心"变得可定义？

老师回答：

  • 在 memo-proc 里确实有赋值，但它被隐藏起来，且只赋值一次（结果一旦算出就不再改变）
  • 一次性赋值（one-time assignment） 是可以接受的
  • 但研究显示：只要有 fair merge 或类似机制，就足以在语言其余部分模拟赋值
  • 所以任何"一点点"引入，都可能像赋值一样糟糕

思考：这暗示了一个深刻的结论——纯函数式的边界可能非常脆弱，任何为实用而开的口子都可能瓦解整个纯函数式的优势。

关键标签 / 关键词

SICP 流 Streams 延迟求值 Lazy Evaluation cons-stream delay force 无穷流 埃拉托斯特尼筛法 Sieve of Eratosthenes 素数流 斐波那契流 add-streams scale-stream 积分器 Integral Henderson 图 信号处理 正则序 Normal Order 应用序 Applicative Order 副作用 Side Effects 赋值 set! 纯函数式编程 Purely Functional 拖尾问题 Dragging Tail fair merge 公平合并 消息传递 面向对象 Miranda David Turner 迭代 vs 递归

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