惰性不足

win_hate

SICP 3.5 讨论了如何构造两个无穷流 S, T 构成的序对流 (S(i), T(j))，其中 i <=j。这个操作记为 (pairs S T)

书本的正文给出了了一个“三部分”的方案，把 (pairs S T) 分成三个部分：

•   (S(0), T(0))
•   (S(0), T(1)), (S(0), T(2)), (S(0), T(3)), ......
•   (pairs (cdr S), (cdr T))
  

下面的图是直观解释



一个可行的生成方式为：把第 2，3 部分两个流用 interleave 混合起来，然后把第一部分，即元素 (S(0), T(0)) 插入流首。对应代码为

1. 
   
2. (define (pairs s t)
   
3.   (cons-stream
   
4.    (list (stream-car s) (stream-car t))
   
5.    (interleave
   
6.     (stream-map (lambda (x) (list (stream-car s) x))
   
7.                (stream-cdr t))
   
8.     (pairs (stream-cdr s) (stream-cdr t)))))
   

复制代码

但这种划分方式有点别扭。如果把横线上方的看做一个流，横线下方的看作另一个流，再用 interleave 混合起来，则看上去要简洁得多。书本的习题 3.68 提出了这个“两部分”方案，并给出了代码

1. 
   
2. (define (pairs s t)
   
3.   (interleave
   
4.    (stream-map (lambda (x) (list (stream-car s) x))
   
5.                t)
   
6.    (pairs (stream-cdr s) (stream-cdr t))))
   

复制代码

可惜这段代码在标准 scheme 里并不能正常工作。因为在表准 scheme 中，函数对参数的求值是严格的。interleave 是函数，它会对第二个参数 pairs 严格求值；而 pairs 调用 interleave；interleave 再对 pairs 求值，....... 如是反复，直到耗尽全部资源。

“两部分” 的方案之所以失败，是因为标准 scheme 惰性不足。可以想象，如果用一个惰性求值的语言来实现 pairs，则 “两部分” 方案的方式也是可行的。我用 lazy-scheme 来测试了上面的代码，得到

1. 
   
2. > (define p (pairs integers integers))
   
3. 
   
4. > (display (take 10 p))
   
5. ((1 1) (2 2) (1 2) (3 3) (1 3) (2 3) (1 4) (4 4) (1 5) (2 4))
   

复制代码

回过头来看一下 “三部分” 的方案，容易看出，pairs 此时调用了 cons-stream，这是一个宏，它对参数的求值是惰性的。

不过仔细想一下，既然我们能构造出惰性的 cons-strem，难道我们就不能让 interlever 对参数的求值也延迟一下吗？这当然是可以的，一方面，我们可以像 cons-stream 那样把 interleave 实现为宏；另一方面，我们也可以主动使用 delay 把参数延迟后再送给 interleave。如果采用后一种办法，则 interleave 要在适当的时候主动 force 被延迟的值。

看看习题 3.68 的代码

1. 
   
2. (define (pairs s t)
   
3.   (interleave
   
4.    (stream-map (lambda (x) (list (stream-car s) x))
   
5.                t)
   
6.    (pairs (stream-cdr s) (stream-cdr t))))
   

复制代码

关键问题在于 interleave 会对 (pairs ...) 进行求值，如果把它延迟呢？反正 interleave 只需要在第一个参数里提取数据就可以产生输出了。

1. 
   
2. (define (lazy-pairs s t)
   
3.   (lazy-interleave
   
4.    (stream-map (lambda (x) (list (stream-car s) x))
   
5.                t)
   
6.    (delay (lazy-pairs (stream-cdr s) (stream-cdr t)))))
   

复制代码

如果这样，那么 interleave 的第一个参数是一个流，而第二个参数只是个 promise。 interleave 从第一个参数中提取一个元素，递归调用自身，交换两个参数的位置，当然原来的第一个参数要 cdr 一下。但重点是此时 promise 被放到第一个参数位置上了， 在interleave 试图从中提取数据时会出错，因为它是 promise 而不是流。 容易看出，可以在递归时对 promise 进行 force。于是我们得到修改过的 interleave，称为 lazy-interleave

1. 
   
2. (define (lazy-interleave s t)
   
3.   (cons-stream (car s)
   
4.                (lazy-interleave (force t) (cdr s))))
   

复制代码

测试一下：

1. 
   
2. > (define p (lazy-pairs integers integers))
   
3. > (take p 10)
   
4. ((1 1) (2 2) (1 2) (3 3) (1 3) (2 3) (1 4) (4 4) (1 5) (2 4))
   

复制代码

结果与用 lazy-scheme 计算出的一致。

[ 本帖最后由 win_hate 于 2009-3-7 15:19 编辑 ]

win_hate

有两个地方值得指出:

[1] “两部分” 方案与 "三部分” 方案理论上都能遍历全体序对，或者说：对于任意给定的序对，它一定会出现在流中。但两
者生成的序对在流中的位置是不同的;
[2] "三部分" 方案有它自己的作用，见习题 3.69 的讨论。

flw