惰性不足

win_hate

SICP 3.5 討論了如何構(gòu)造兩個無窮流 S, T 構(gòu)成的序?qū)α?(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)) 插入流首。對應(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ù)制代碼

但這種劃分方式有點別扭。如果把橫線上方的看做一個流，橫線下方的看作另一個流，再用 interleave 混合起來，則看上去要簡潔得多。書本的習(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ù)制代碼

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

“兩部分” 的方案之所以失敗，是因為標(biāo)準(zhǔn) scheme 惰性不足�？梢韵胂�，如果用一個惰性求值的語言來實現(xiàn) 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))
   

復(fù)制代碼

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

不過仔細想一下，既然我們能構(gòu)造出惰性的 cons-strem，難道我們就不能讓 interlever 對參數(shù)的求值也延遲一下嗎？這當(dāng)然是可以的，一方面，我們可以像 cons-stream 那樣把 interleave 實現(xiàn)為宏；另一方面，我們也可以主動使用 delay 把參數(shù)延遲后再送給 interleave。如果采用后一種辦法，則 interleave 要在適當(dāng)?shù)臅r候主動 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)鍵問題在于 interleave 會對 (pairs ...) 進行求值，如果把它延遲呢？反正 interleave 只需要在第一個參數(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 的第一個參數(shù)是一個流，而第二個參數(shù)只是個 promise。 interleave 從第一個參數(shù)中提取一個元素，遞歸調(diào)用自身，交換兩個參數(shù)的位置，當(dāng)然原來的第一個參數(shù)要 cdr 一下。但重點是此時 promise 被放到第一個參數(shù)位置上了， 在interleave 試圖從中提取數(shù)據(jù)時會出錯，因為它是 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))))
   

復(fù)制代碼

測試一下：

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 計算出的一致。

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

win_hate

有兩個地方值得指出:

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

flw