SICP 読み (127) 3.5.1 ストリームは遅延リスト
この部分を書いている時点では実機で確認してません。おそらくはそれまでボケまくるはずです。(何
問題 3.51 のつづき
前提になっている手続きの定義を控えておく。最低限必要なのは以下。
(define-syntax cons-stream
(syntax-rules ()
((_ a b) (cons a (delay b)))))
(define-syntax delay
(syntax-rules ()
((_ p) (memo-proc (lambda () p)))))
(define (force delayed-object) (delayed-object))
(define (memo-proc p)
(let ((already-run? #f) (result #f))
(lambda ()
(if (not already-run?)
(begin (set! result (p))
(set! already-run? #t)
result)
result))))
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
(define (stream-null? s) (null? s))
(define the-empty-stream '())
(define (display-line x)
(display x)
(newline))
(define (show x)
(display-line x)
x)
(define (stream-ref s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))
(define (stream-map p s)
(if (stream-null? s)
the-empty-stream
(cons-stream (p (stream-car s))
(stream-map p (stream-cdr s)))))
(define (stream-enumerate-interval l h)
(if (> l h)
the-empty-stream
(cons-stream
l
(stream-enumerate-interval (+ l 1) h))))
(define x (stream-map show (stream-enumerate-interval 0 10)))
(stream-ref x 5)
(stream-ref x 7)で、まずは
(define x (stream-map show (stream-enumerate-interval 0 10)))
が評価される時の動作を。ってか、define が評価される時には x が束縛される stream-map は実際には何かに置き換わるはずだなぁ。x が束縛されているのは右側にある式ではなくて式を評価した何か、になっていると思うんだけどダウト??
こんな確認の仕方をしてみたんですがどうか。
gosh> (define y 0) y gosh> (define x (+ y 2)) x gosh> y 0 gosh> x 2 gosh> (define y 2) y gosh> x 2 gosh> y 2 gosh>
上記によれば、x が束縛されているのは (+ y 2) という式ではなくて、y が 0 の時点で (+ y 2) が評価された値になっている。
なかなか進まない
で、
(stream-map show (stream-enumerate-interval 0 10))
を順に評価してみます。まず stream-enumerate-interval が戻すのは
(cons-stream 0 (stream-enumerate-interval 1 10))
これは中の式がナニされる前に以下に置き換わると思っていて良いかなぁ。
(cons 0 (delay (stream-enumerate-interval 1 10)))
あるいは delay 以下も lambda な手続きオブジェクトで置き換えられているはずなんですが、見づらくなるんでこのままにしときます。force に渡されるまでここは評価されない、と。
てコトは、上記が stream-map に渡されるんですな。
(stream-map show (cons 0 (delay (stream-enumerate-interval 1 10))))
まだ昨晩と同じです。よかった。(何
これを評価すると、stream-null? は #f を戻すので以下ですか??
(cons-stream (show (stream-car (cons 0 (delay
(stream-enumerate-interval 1 10)))))
(stream-map show (stream-cdr (cons 0 (delay
(stream-enumerate-interval 1 10))))))見づらい。ここで昨晩はいっちゃんてっぺんの cons-stream をナニしている。
(cons (show (stream-car (cons 0 (delay (stream-enumerate-interval 1 10)))))
(delay (stream-map show (stream-cdr (cons 0 (delay
(stream-enumerate-interval 1 10)))))))こうなると 2 番目の引数は評価が止まるな。これが正解だろうな。特殊形式は先に評価される、というソレに思い至っていたんですが良いのでしょうか。
で、show が評価される、と。
(cons (show 0)
(delay (stream-map show (stream-cdr (cons 0 (delay
(stream-enumerate-interval 1 10)))))))で、show が評価されて以下が x に束縛、というのが答えかなぁ。
(cons 0
(delay (stream-map show (stream-cdr (cons 0 (delay
(stream-enumerate-interval 1 10)))))))上記は昨晩とは違いますなぁ。delay の中身はそのまんま、というのが差分。
という事で最初のステップは以下な感じでしょうか。
gosh> (define x (stream-map show (stream-enumerate-interval 0 10))) 0 x gosh>
で、x に束縛されているのは上記の式。ただ、delay 以下はクロージャが、な出力になるはずです。どーゆー出力なのかは現時点で微妙。
次
次は上記を踏まえて
(stream-ref x 5)
がどのような軌跡を辿るか、ですか。
(stream-ref (cons 0
(delay
(stream-map show
(stream-cdr (cons 0
(delay
(stream-enumerate-interval 1 10)))))))
5)な、長い。で、stream-ref にて n が 0 でないので以下。
(stream-ref (force (delay
(stream-map show
(stream-cdr
(cons 0
(delay
(stream-enumerate-interval 1 10)))))))
4)ええと、実行が保留されていた stream-map が動くワケです。式が長いので stream-map にフォーカスして見てみます。
(stream-map show
(stream-cdr (cons 0
(delay (stream-enumerate-interval 1 10)))))これも stream-cdr がナニされる必要あり。
(stream-map show
(force (delay (stream-enumerate-interval 1 10))))で、stream-enumerate-interval 復活。
(stream-map show
(cons-stream 1 (stream-enumerate-interval 2 10)))cons-stream を評価。
(stream-map show
(cons 1 (delay (stream-enumerate-interval 2 10))))で、stream-map に渡される。stream-null? は #f なので以下。
(cons-stream (show (stream-car (cons 1 (delay
(stream-enumerate-interval 2 10)))))
(stream-map show (stream-cdr (cons 1 (delay
(stream-enumerate-interval 2 10))))))で、例によってここでは先頭の cons-stream を評価。
(cons (show (stream-car (cons 1 (delay (stream-enumerate-interval 2 10)))))
(delay (stream-map show (stream-cdr (cons 1 (delay
(stream-enumerate-interval 2 10)))))))で、show の引数の stream-car を評価。
(cons (show 1)
(delay (stream-map show (stream-cdr (cons 1 (delay
(stream-enumerate-interval 2 10)))))))で、show が 1 を出力して以下のソレが stream-ref に渡ります。
(cons 1
(delay (stream-map show (stream-cdr (cons 1 (delay
(stream-enumerate-interval 2 10)))))))元に戻ります。
(stream-ref
(cons 1
(delay (stream-map show (stream-cdr (cons 1 (delay
(stream-enumerate-interval 2 10)))))))
4)だんだん面倒になってきた。ただ、
(stream-ref x 5)
は
(stream-ref
(cons 0
(delay (stream-map show (stream-cdr (cons 0 (delay
(stream-enumerate-interval 1 10)))))))
5)であり、これが
(stream-ref
(cons 1
(delay (stream-map show (stream-cdr (cons 1 (delay
(stream-enumerate-interval 2 10)))))))
4)になった (この時に 1 を印字) んで後は stream-ref の第二引数が 0 になった時点の stream-car
が戻る値であろう、という類推は可能なはず。なので次は
(stream-ref
(cons 2
(delay (stream-map show (stream-cdr (cons 2 (delay
(stream-enumerate-interval 3 10)))))))
3)になり (この時に 2 が印字) その次が
(stream-ref
(cons 3
(delay (stream-map show (stream-cdr (cons 3 (delay
(stream-enumerate-interval 4 10)))))))
2)になって (この時に 3 を印字) またまた次が
(stream-ref
(cons 4
(delay (stream-map show (stream-cdr (cons 4 (delay
(stream-enumerate-interval 5 10)))))))
1)n
になって (この時に 4 を印字) 次にようやく
(stream-ref
(cons 5
(delay (stream-map show (stream-cdr (cons 5 (delay
(stream-enumerate-interval 6 10)))))))
0)になる訳で、これが評価されると car の 5 が戻ってようやく手続き終了。ので、手続きを実行した時には以下なソレなんだろうか。
gosh> (stream-ref x 5) 1 2 3 4 5 gosh>
むむ。こればかりはヤッてみないと分からんな。
とりあえず検討終了
実機確認はまだです。とりあえず通しで解釈系はこんな印字か。
gosh> (define x (stream-map show (stream-enumerate-interval 0 10))) 0 x gosh> (stream-ref x 5) 1 2 3 4 5 gosh> (stream-ref x 7) 1 2 3 4 5 6 7 gosh>
って、メモ化されてるから (stream-ref x 7) ではこんな感じになるのか。
gosh> (stream-ref x 7) 6 7 gosh>
さ、控えを作ったので動かしてみましょうね。
動かした
ち、違った。実際の印字は以下。
gosh> (define x (stream-map show (stream-enumerate-interval 0 10))) 0 x gosh> (stream-ref x 5) 1 2 3 4 5 5 gosh> (stream-ref x 7) 6 7 7 gosh>
むむむ。何がまずかったんだ。今から反省を含め、再検証ッス。
ナチュラル
うーん。検討を略した時に
(stream-ref x 5)
が
(stream-ref <略> 4)
になって_略_な部分の評価が始まるんですが、そこの考慮がヌケていますな。_略_な部分が評価されている途中で show が呼ばれるんで 5 も出ないと駄目。
やはりこーゆー作業は面倒になって手をヌいた時点で微妙になりますな。短気はいけません。(を
しかしこれ、脚注 59 にもある通り、正にワナにハマってる感じだなぁ。ええ年こいて恥ずかしい限りッス。(とほほほ
しかも評価だの展開だのというあたりのソレが全然違ってたとしたら恥ずかしいなんてレベルではないかもしれん。怖いよう。
もう少し
次の問題も相当ハードル高いので、きちんと整理しておいた方が良さげ。
- ストリームは cdr 側には_残り_がある。テキストには_遅延式_とあるな。
- ストリームを使う手続きでは、繰返し (再帰) を行なう時に_遅延式_を評価して_残り_を取得して再帰呼び出しを呼び出す。
- 逆に言えば、繰返す場合には再帰呼び出しを行なう前に_遅延式_が評価され、手続きに渡される。
なんつーかストリームって本当に凄いんだけど、こーゆー意地悪問題は嫌だなぁ。でも、これ位のソレが脳内変換される位な訓練が必要ってコトなんだろうか。昨日も紙に書きかけて嫌になったんだよなぁ。手続きの名前長いし。
次は脳内変換を試みてみよう。今はスデに酒がはいってるので駄目。(何
