流是延迟的列表

流的构造与选择

从表面上看，流就是给操作过程换了名字的列表。它有一个构造函数 cons-stream，以及两个选择函数 stream-car 和 stream-cdr，满足如下约束：

• (stream-car (cons-stream x y)) 返回 x
• (stream-cdr (cons-stream x y)) 返回 y

为了构造出我们真正使用的流，我们要安排 cdr 在 stream-cdr 访问它时才求值，而不是在流构造时求值。

作为数据抽象，流和列表是一样的，区别在于元素求值的时机。普通列表在构造时，car 和 cdr 都会求值；而流要等到选择时才对 cdr 求值。

我们对流的实现基于一种特殊形式 delay。求值 (delay exp) 不会求表达式 exp，而是返回一个所谓的延迟对象（delayed object），可以把它理解为「在将来某个时候求值 exp」的承诺（promise）。与 delay 相伴，还有一个过程 force：它接受一个延迟对象作为参数并执行求值——实际上是迫使这个延迟兑现它的承诺。我们先看看如何用它们构造流，delay 和 force 的实现留到后面。

cons-stream 是一种特殊形式，(cons-stream a b) 等价于 (cons a (delay b))。

也就是说，我们将用「普通的 car + 延迟的 cdr」这样的序对来构造流。这就是 stream-car 和 stream-cdr 的定义：

(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))

注意 cons-stream 是特殊形式。如果它不是，调用 (cons-stream a b) 时就会先求值 b，b 也就不会被延迟了。

the-empty-stream

有一个可区分的对象 the-empty-stream，它不可能是任何 cons-stream 操作的结果，并且可以用谓词 stream-null? 来识别。

流版的列表过程

我们可以像使用列表一样使用流来表示按顺序排列的聚合数据，也可以为 list-ref、map、for-each 等过程构造流版本。

stream-ref

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

如果定义

(define x (cons-stream 0 (cons-stream 1 (cons-stream 2 the-empty-stream))))

那么 (stream-ref x 0) 返回 0，(stream-ref x 2) 返回 2。（注意 $n$ 从 0 开始计数。）

stream-map

(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons-stream (proc (stream-car s))
                   (stream-map proc (stream-cdr s)))))

如果 $x$ 与上面相同，那么 (stream-map square x) 返回由 (0 1 4) 组成的流。

stream-for-each

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

stream-for-each 很适合用来查看流的内容。下面这个过程可能会有帮助：

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (newline)
  (display x))

用流进行计算

换用流，重新表述前面见过的第二个素数计算：

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

首先以 10000 和 1000000 为参数调用 stream-enumerate-interval，创建从 10000 到 1000000 的数字流。

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

返回的结果是 (cons 10000 (delay (stream-enumerate-interval 10001 1000000)))。这是由一个序对表示的流，它的 car 是 10000，cdr 则是「必要时继续枚举区间剩余部分」的承诺。现在用 stream-filter 过滤它：

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

stream-filter 检查流的 stream-car（即序对的 car）10000。它不是素数，于是 stream-filter 转去检查输入流的 stream-cdr。对 stream-cdr 的调用强制求值那个延迟的 stream-enumerate-interval，此时返回

(cons 10001
      (delay (stream-enumerate-interval 10002 1000000)))

stream-filter 再看这条流的 stream-car，即 10001，发现也不是素数，于是继续强制求值下一个 stream-cdr，如此反复，直到 stream-enumerate-interval 产生素数 10007。这时 stream-filter 按其定义返回

(cons-stream (stream-car stream)
             (stream-filter pred (stream-cdr stream)))

也就是

(cons 10007
      (delay
        (stream-filter
         prime?
         (cons 10008
               (delay
                 (stream-enumerate-interval 10009
                                            1000000))))))

这个结果接着传给原表达式里的 stream-cdr。它强制求值那个延迟的 stream-filter，后者又不断强制求值延迟的 stream-enumerate-interval，直到找到下一个素数 10009。最后，传给原表达式中 stream-car 的结果是

(cons 10009
      (delay
        (stream-filter
         prime?
         (cons 10010
               (delay
                 (stream-enumerate-interval 10011
                                            1000000))))))

stream-car 返回 10009，计算完成。整个过程中，只为找到第二个素数而测试了必要数量的整数，区间也只枚举到喂给素数过滤器所需的位置。

实现 delay 和 force

尽管 delay 和 force 看起来神秘，实现其实很直白。delay 必须把一个表达式打包起来，以便之后按需求值；这只需把该表达式当作一个过程体来处理即可。delay 可以是特殊形式，使得

(delay exp)

是下面形式的语法糖：

(lambda () exp)

force 只是调用 delay 产生的那个无参过程，因此可以把 force 实现成普通过程：

(define (force delayed-object)
  (delayed-object))

再次强调：delay 必须是特殊形式。否则调用 (delay b) 时，b 会在我们执行过程体之前就被求值。

这个实现足以让 delay 和 force 按宣传的方式工作，但还有一个重要的优化可以加。很多应用中，同一个延迟对象会被强制求值多次。在涉及流的递归程序里，这可能带来严重的低效。解决办法是：让延迟对象第一次被强制求值时，把算出的值存下来；之后再强制求值，直接返回存好的值，不再重复计算。换句话说，我们把 delay 实现成一个专门用于记忆化（memoized）的过程。一种做法是用下面这个过程：它接受一个无参过程，返回该过程的记忆化版本——第一次运行时保存计算结果，之后直接返回该结果。

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

然后这样定义 delay，使 (delay exp) 等价于

(memo-proc (lambda () exp))

而 force 保持不变。

要点总结

本节你学到了：

1. 流是什么；
2. 流的一些实用应用；
3. 如何实现 delay 和 force。

接下来

进入下一小节，学习无穷列表！