理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

Infinite Streams が面白すぎる件

遅延評価を利用した無限ストリームの章に入りました (3.5.2).
無限ストリームを利用すると,その名の通り,無限長のものが扱えるようになる.例えば以下は無限長である自然数のリスト.

; SICP と記述を合わせるために,cons-stream を stream-cons のエイリアスとする
(use util.stream)
(define cons-stream stream-cons)

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))

上記の定義はわりと直感的で,1 という要素と,2 を生成することが ``約束'' されたdelayed-object のペアを生成するというもの(だと思う)です.

ただ,遅延評価を用いると再帰的な定義も可能になります.

(define ones (cons-stream 1 ones))

これも SICP にそのまま出てくる例ではありますが,ones は cons-stream を行う段階では評価されません (あくまで,評価されることが ``約束'' されるだけ).(stream-cdr が呼ばれた段階で,ones の定義が評価対象となり,1 と,再度 ones を評価することを ``約束'' した delayed-object のペアが生成されるという運び.結局 ones はいくらでも 1 を取り出せる無限ストリームになっています.

この辺になってだんだん理解が怪しくなる

フィボナッチ数列の無限ストリームについての一つの定義.

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

delayed-object とか抜きにして,fibs を無限ストリームとして (stream-ref fibs 3) が呼ばれるときのことを考えると分かりやすい.下手に「いつこれが評価されて...」などと考えると思考がヤバくなる!