第 10 课导言

前置知识与学习目标

继续之前，你应该已经掌握列表的操作。建议复习 map、filter 等关键过程。

本课我们将学习流（stream）及其部分应用。

阅读材料

本课基于 SICP 3.5。

流简介

我们已经很好地理解了赋值（assignment）作为一种建模工具的作用，也体会到赋值带来的种种复杂问题。现在该问一问：能不能换一条路走，从而避开其中一部分问题？本节我们将探索一种建模状态的替代方案，它基于一种称为流（stream）的数据结构。我们会看到，流可以缓解建模状态时的部分复杂性。

先退一步，看看这些复杂性从何而来。为了给现实世界现象建模，我们做出了一些看似合理的决定：用具有局部变量的计算对象来模拟现实世界中具有局部状态的对象；把现实世界中的时间变化对应到计算机中的时间变化；用给模型对象的局部变量赋值，在计算机中实现模型对象状态的时间变化。

有没有别的办法？能不能不把计算机中的时间与被建模世界的时间绑在一起？为了给变化的世界中的现象建模，一定要让模型跟着时间变吗？用数学函数来想想这个问题。我们可以把量 $x$ 随时间变化的行为描述为时间的函数 $x(t)$。如果我们逐瞬间地考察 $x$，会把它看成一个变化的量；但如果我们关注整个时间历程上的取值，就不再强调变化——函数本身并没有变。

如果时间是按离散的步长来度量的，我们就可以把时间函数建模成（可能无穷的）序列。本节将看到如何用表示被建模系统时间历程的序列来建模变化。为此，我们引入一种新的数据结构——流。从抽象的观点看，流就是一个序列。不过我们会发现，像 2.2.1 节那样把流直接实现成列表，并不能充分发挥流处理的威力。作为替代，我们引入延迟求值（delayed evaluation）技术，用它来表示非常大（甚至无穷）的序列。

流处理让我们无需使用赋值或可变数据，就能为带有状态的系统建模。这在理论和实践上都有重要意义，因为我们可以构造出避开赋值固有缺陷的模型。另一方面，流框架也有自己的难处，至于哪种建模技术能带来更模块化、更易维护的系统，这个问题仍然没有定论。

列表的低效之处

从第 4 课起，我们一直用列表表示序列。但列表表示有缺点：要操作这些列表序列，程序就必须在每一步构造并复制数据结构（有时规模巨大）。

看一个例子。下面这个过程用我们熟悉且喜欢的迭代风格写成：

(define (sum-primes a b)
  (define (iter count accum)
    (cond ((> count b) accum)
          ((prime? count) (iter (+ count 1) (+ count accum)))
          (else (iter (+ count 1) accum))))
  (iter a 0))

第二个过程则借助了 accumulate、filter 和 enumerate-interval：

(define (sum-primes a b)
  (accumulate +
              0
              (filter prime? (enumerate-interval a b))))

进行计算时，第一个程序只需保存正在累加的和。相比之下，第二个程序里的 filter 在 enumerate-interval 构造出整个区间的完整列表之前，什么也做不了。filter 会生成另一个列表，再传给 accumulate，最后才汇总成一个和。

第一个程序不需要这样大的中间存储，可以把它看作在增量地枚举区间，每生成一个素数就把它加进和里。

再看一个列表低效的例子：

(car (cdr (filter prime?
                  (enumerate-interval 10000 1000000))))

这段代码生成了一个巨大的整数列表和一个巨大的素数列表，而我们只想要第二个素数！

为什么需要流？

有了流，我们就可以操作序列，而不必承受把序列当列表操作的开销。流让我们两全其美：既能把程序优雅地写成序列操作，又能获得增量计算的效率。基本思想是：只把流构造一部分，然后把这部分构造传给消费流的程序。如果消费者试图访问流中尚未构造的部分，流会自动把自己再构造出刚好足够的一截，以产生所需的部分，从而维持「整条流都存在」的假象。换句话说，尽管我们写程序时仿佛在处理完整序列，但我们的流实现会自动且透明地把流的构造与使用交错起来。