ストリームの実装と問題3.50-3.51
今回からストリームを扱います。
ストリームの処理系への導入
プログラムに時の概念を導入するもう一つの方法として、ストリームというものを使うことを考えます。
動かそうと思ったのですが、ストリームを作る時に使用する遅延オブジェクトを生成する特殊形式の手続きdelayとストリームを生成するcons-streamが処理系依存のようで、goshだと上手くいかないようです。
ぼくはgoshでなくてDrSchemeの中のPrettyBIgを使っているのですが、この環境だとdelayとforceは
> (define a (delay 8)) > a #<struct:promise> > (force a) 8 > (define b (delay (delay 88))) > b #<struct:promise> > (force b) #<struct:promise> > (force (force b)) 88 > (define f (delay (lambda (x) (* x x)))) > f #<struct:promise> > (f 3) procedure application: expected procedure, given: #<struct:promise>; arguments were: 3 > ((force f) 3) 9
こんな感じに動きます。ぼくがSICPを読んだ範囲ではこういう挙動で大体おっけーのように理解したので、とりあえずdelayとforceはこの環境のまま進めても大丈夫なようです。
問題はcons-streamなんですが、PrettyBig中にcons-streamが特殊形式の手続きとして実装されていません。
cons-streamは通常手続きとして実装しようとすると第二引数が評価されてしまうため、以下のような無限ストリーム
(define ones (cons-stream 1 ones))
を扱うことができません(というか無限ストリームに限らず、引数が全て評価されてからリストになるから遅延評価の意味がなくなる)。
SICPには特殊形式の定義ができるような基本手続きがかかれていなかったので、第4章の超言語的抽象みたくschemeの上にschemeの処理系を作ってそこに特殊形式cons-streamを実装するしかないんだろうか、などと思っていたんですが、グーグル先生のおかげでdefine-syntax, syntax-rulesなる手続きを見つけることができました。
http://www.shido.info/lisp/scheme_syntax.html
これらの手続きの説明は上URLに詳しく書かれていますのでそちらを参考にしてください。
これらを使うと、cons-streamは
(define-syntax cons-stream (syntax-rules () ((_ a b) (cons a (delay b)))))
のようなマクロとして書くことができ、無限ストリームも
> (define ones (cons-stream 1 ones)) > ones (1 . #<struct:promise>) > (stream-ref ones 100) 1 > (stream-ref ones 10000) 1 > (define twos (cons-stream 2 twos)) > (stream-map + ones twos) (3 . #<struct:promise>) > (stream-ref (stream-map + ones twos) 1000) 3
このようにちゃんと扱うことができます。
で思ったのですが、特殊形式を定義できるのだからdelayやforceも実装できるはずです。
ということでやってみました。
(define-syntax delay (syntax-rules () ((_ exp) (lambda () exp)))) (define (force delayed-object) (delayed-object)) > (define ones (cons-stream 1 ones)) > ones (1 . #<procedure>) > (stream-cdr ones) (1 . #<procedure>) > (stream-ref ones 100) 1 > (define twos (cons-stream 2 twos)) > (stream-map + ones twos) (3 . #<procedure>) > (stream-ref (stream-map + ones twos) 10000) 3
ということで、lambdaによる式のパッケージ化でdelayとforceを作ることができました。
これにメモ化を導入すればSICPが想定するdelayとforceになっているはずです。たぶん。
せっかく作ったけど遅延オブジェクトが#
3.50
mapのストリーム版の実装です。既に上で散々使ってるので、定義だけ書きます。
(define (stream-map proc . argstreams) (if (stream-null? (car argstreams)) the-empty-stream (cons-stream (apply proc (map stream-car argstreams)) (apply stream-map (cons proc (map stream-cdr argstreams))))))
3.51
> (define (show x) (display-line x) x) > (define x (stream-map show (stream-enumerate-interval 0 10))) 0
上で出てきた0はshowによるもの。
(stream-map show (stream-enumerate-interval 0 10))で(stream-enumerate-interval 0 10)のうちの唯一遅延オブジェクトでない最初の0に作用した結果。
するとxには1,2,...,10を格納している遅延オブジェクトが評価されたらshowを作用させるという流れが入っていると考えられる。
> (stream-ref x 5) 1 2 3 4 5 5
上の1,2,3,4,5はshowによるもので最後の5はstream-refが返した値。
stream-refはxの先頭を0として5番目のストリームの遅延オブジェクトを評価して返すので、0から5までのうちの遅延オブジェクト(1,2,3,4,5)は評価される。するとxは遅延オブジェクトの評価にshowを作用させるのを待っていたので、それぞれの遅延オブジェクトにshowが適用され、1,2,3,4,5の印字を得る。
> (stream-ref x 7) 1 2 3 4 5 6 7 7
これも全く同じことなので説明は省く。
すごく眠いです。今日はここまで。
