惰性不足

win_hate

SICP 3.5 討論了如何構(gòu)造兩個(gè)無(wú)窮流 S, T 構(gòu)成的序?qū)α?(S(i), T(j))，其中 i <=j。這個(gè)操作記為 (pairs S T)

書(shū)本的正文給出了了一個(gè)“三部分”的方案，把 (pairs S T) 分成三個(gè)部分：

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

下面的圖是直觀解釋



一個(gè)可行的生成方式為：把第 2，3 部分兩個(gè)流用 interleave 混合起來(lái)，然后把第一部分，即元素 (S(0), T(0)) 插入流首。對(duì)應(yīng)代碼為

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)))))
   

復(fù)制代碼

但這種劃分方式有點(diǎn)別扭。如果把橫線上方的看做一個(gè)流，橫線下方的看作另一個(gè)流，再用 interleave 混合起來(lái)，則看上去要簡(jiǎn)潔得多。書(shū)本的習(xí)題 3.68 提出了這個(gè)“兩部分”方案，并給出了代碼

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))))
   

復(fù)制代碼

可惜這段代碼在標(biāo)準(zhǔn) scheme 里并不能正常工作。因?yàn)樵诒頊?zhǔn) scheme 中，函數(shù)對(duì)參數(shù)的求值是嚴(yán)格的。interleave 是函數(shù)，它會(huì)對(duì)第二個(gè)參數(shù) pairs 嚴(yán)格求值；而 pairs 調(diào)用 interleave；interleave 再對(duì) pairs 求值，....... 如是反復(fù)，直到耗盡全部資源。

“兩部分” 的方案之所以失敗，是因?yàn)闃?biāo)準(zhǔn) scheme 惰性不足�？梢韵胂�，如果用一個(gè)惰性求值的語(yǔ)言來(lái)實(shí)現(xiàn) pairs，則 “兩部分” 方案的方式也是可行的。我用 lazy-scheme 來(lái)測(cè)試了上面的代碼，得到

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))
   

復(fù)制代碼

回過(guò)頭來(lái)看一下 “三部分” 的方案，容易看出，pairs 此時(shí)調(diào)用了 cons-stream，這是一個(gè)宏，它對(duì)參數(shù)的求值是惰性的。

不過(guò)仔細(xì)想一下，既然我們能構(gòu)造出惰性的 cons-strem，難道我們就不能讓 interlever 對(duì)參數(shù)的求值也延遲一下嗎？這當(dāng)然是可以的，一方面，我們可以像 cons-stream 那樣把 interleave 實(shí)現(xiàn)為宏；另一方面，我們也可以主動(dòng)使用 delay 把參數(shù)延遲后再送給 interleave。如果采用后一種辦法，則 interleave 要在適當(dāng)?shù)臅r(shí)候主動(dòng) force 被延遲的值。

看看習(xí)題 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))))
   

復(fù)制代碼

關(guān)鍵問(wèn)題在于 interleave 會(huì)對(duì) (pairs ...) 進(jìn)行求值，如果把它延遲呢？反正 interleave 只需要在第一個(gè)參數(shù)里提取數(shù)據(jù)就可以產(chǎn)生輸出了。

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)))))
   

復(fù)制代碼

如果這樣，那么 interleave 的第一個(gè)參數(shù)是一個(gè)流，而第二個(gè)參數(shù)只是個(gè) promise。 interleave 從第一個(gè)參數(shù)中提取一個(gè)元素，遞歸調(diào)用自身，交換兩個(gè)參數(shù)的位置，當(dāng)然原來(lái)的第一個(gè)參數(shù)要 cdr 一下。但重點(diǎn)是此時(shí) promise 被放到第一個(gè)參數(shù)位置上了， 在interleave 試圖從中提取數(shù)據(jù)時(shí)會(huì)出錯(cuò)，因?yàn)樗��?promise 而不是流。 容易看出，可以在遞歸時(shí)對(duì) promise 進(jìn)行 force。于是我們得到修改過(guò)的 interleave，稱為 lazy-interleave

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

復(fù)制代碼

測(cè)試一下：

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))
   

復(fù)制代碼

結(jié)果與用 lazy-scheme 計(jì)算出的一致。

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

win_hate

有兩個(gè)地方值得指出:

[1] “兩部分” 方案與 "三部分” 方案理論上都能遍歷全體序?qū)�，或者說(shuō)：對(duì)于任意給定的序?qū)�，它一定�?huì)出現(xiàn)在流中。但兩
者生成的序?qū)υ诹髦械奈恢檬遣煌��?
[2] "三部分" 方案有它自己的作用，見(jiàn)習(xí)題 3.69 的討論。

flw