ふつうの言語で Lazy list について考える(2)。

前に書いた stream の実装はどうなっているのだろうと気になったんだけど、難しくてライブラリのソースコードは全然読めませんでした。そこで、http://practical-scheme.net/gauche/man/gauche-refj_54.html#SEC100 にある遅延評価の使い方の例を見て、手作りで stream を作って遊んでみます。例えば '(1 2 3) を cons を使って書くと

(cons 1 (cons 2 (cons 3 '())))

になるけど、(stream 1 2 3) は

(delay (cons 1 (delay (cons 2 (delay (cons 3 (delay '())))))))

になります。delay は式をすぐ実行せずに、あとで force に呼ばれた時に実行されるオブジェクト (promise) を作る文です。ケチな事に、stream のライブラリは自作ストリームに反応しないので、Gauche マニュアルにあるやつをそのまま使います。この ltake は stream-take と違って普通のリストを返します。

(define (lcar lis) (car (force lis)))
(define (lcdr lis) (cdr (force lis)))

(define (ltake lis n)  ;; lazy take
  (if (<= n 0) '() (cons (lcar lis) (ltake (lcdr lis) (- n 1)))))

これもマニュアルとほとんど一緒ですが、先日の map を使わないフィボナッチ数列は

(define lfib
  (let loop ((a 0) (b 1))
    (delay (cons b (loop b (+ a b))))))

です。ライブラリを使うより簡単な気がする。。。

gosh> (ltake lfib 10)
(1 1 2 3 5 8 13 21 34 55)

さて、どうしてこういう事が気になったかというと、http://srfi.schemers.org/srfi-45/srfi-45.html に書いてある事を理解したかったからです。しかし、やっぱりさっぱり意味が分かりませんでした。一応 delay と lazy の違いを挙げておくと、delay の場合 force された時に promise が一度評価されますが、lazy の場合さらに評価された結果が promise ならば再帰的にその promise も評価する所が違います。

gosh> (force (lazy (delay 3)))
3
gosh> (force (lazy (lazy 3)))
3
gosh> (force (delay (delay 3)))
#<promise 0x532880>
gosh> (force (delay (lazy 3)))
#<promise 0x532770>

という事は、promise が連なるような状況じゃ無い限り lazy の動作は delay と同じという事になり、私にはそのようなわざわざ promise の中に promise を入れるような状況が思いつかないのです。まあいいか、後で困った時に考えます。