Ex. 4.16
内部defineの実装
a. lookup-variable-value(p.225) の変更
(define (lookup-variable-value var env)
(define (env-loop env)
(define (scan vars vals)
(cond ((null? vars)
(env-loop (enclosing-environment env)))
((eq? var (car vars))
(if (eq? (car vals) '*unassigned*) ;; *unassigned* の処理追加。このif以外は元と同じ
(error "Unassigned variable" var)
(car vals)))
(else (scan (cdr vars)(cdr vals)))))
(if (eq? env the-empty-environment)
(error "Unbound variable" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))
b. scan-out-defines の追加
方針：2パスで作る。1パス目で変数をかき集めて、2パス目で変換式を作る。
(define (scan-out-defines exps)
(let ((lll '()) ;; (u *unassigned*) (v *unassigned*) ... のリストを集める
(sss '()) ;; (set! u <e1>) (set! v <e2>) ... のリストを集める
(bbb '())) ;; 本文を集める
(define (loop exps)
(if (last-exp? exps)
(set! bbb exps)
(let ((var (definition-variable (first-exp exps)))
(val (definition-value (first-exp exps))))
(set! lll (cons (list var ''*unassigned*) lll))
(set! sss (cons (list 'set! var val) sss))
(loop (rest-exps exps)))))
(loop exps) ;; 1パス目で変数を集める
(cons 'let (cons lll (append sss bbb))))) ;; 2パス目で変換式作る
Ex. 4.17
内部define を逐次的に解釈したときの環境
内部define を let に変換したときの環境
let に変換したときに、フレームが増える理由：
let は、lambda に変換されるので、lambdaが2重になる。
lambda １つにつき、実行時に１つフレームを作るので、結局フレームも2重になる。
どちらも同じ結果になるのは、<e3> の実行フレームの内容が同じだからである。
フレーム増やさずに、内部define を同時にする方法：
let を使うとどうしてもフレームが増えるので、define と set! を使ってみる
(lambda <vars> (define u <e1>) (define v <e2>) <e3>)
を、このように変換する。
(lambda <vars> (define u '*unassigned*) (define v '*unassigned*) (set! u <e1>) (set! v <e2>) <e3>)
Ex. 4.18
内部define を2重の let で変換した場合
solve を2重の let で変換すると
(define (solve f y0 dt)
(let ((y '*unassigned*)
(dy '*unassigned*))
(let ((a (integral (delay dy) y0 dt))
(b (stream-map f y)))
(set! y a)
(set! dy b)
y)))
となる。dy の評価は、let式 で a に代入されるときに1回、set!式で y に代入されるときに1回の合計2回評価される。delay が効くのは、最初の1回だけで、2回目は dy がそのまま評価される。 2回目 dy が評価されるとき dy は *unassigned* なのでエラーになる。
Ex. 4.17のように、solve を1重の let で変換すると
(define (solve f y0 dt)
(let ((y '*unassigned*)
(dy '*unassigned*))
(set! y (integral (delay dy) y0 dt))
(set! dy (stream-map f y))
y)))
となる。この場合、dy の評価は、set!式 で y に代入されるとき1回だけで、このときdelay が効いているので、エラーにならない。
ところで、この問題の2重の let の意味がわからない。こうしたほうがよい場合があるのだろうか？
Ex. 4.19
徹底的に遅延評価するという見方なら、Eva の解釈が正しい。
場合によって遅延したり、しなかったりするのが一番困る。
Eva の解釈に沿った置き換え
(let ((a 1))
(define (f x)
(define b (delay (+ a x))) ;; a が見えないよう delay する
(define a 5)
(+ a b))
(f 10))
この例だといけそうな気がするが、define とか、 let とかが入り組んでくるとうまくいかなくなる。
きちんとした解決は、eval を遅延評価にしてしまうことであろう。
Ex. 4.20
letrec 構文の追加
a. letrec を let 式に変換する。
変換方法は、こんな感じ
(letrec ((u 2)(v 3)) (+ u v))→
(let ((u '*unassigned*)
(v '*unassigned*))
(set! u 2)
(set! v 3)
(+ u v))
実装は、省略。
b. 問題の意図は letrec の使用上の制限について注意することである。
通常のSchemeでも、letrec については、このような使用上の制限がある。
(letrec ((var1 val1)(var2 val2)...)...)
において、各val は、他の var を直接参照してはならない。ということ。
問題の letrec 実行時の環境図は、こんな感じ。
letrec を let で変換したときの環境図
これらの環境図から分かるのは、 どこもおかしなところはなく、Louis の言うとおり、この f は正常に動作するであろうということである。
しかし、よく見ると even?, odd? は、 lambda 式で、lambda 式の中から互いを参照している。lambda 式の中からの参照でなく、直接参照した場合はどうなるのであろうか? Louisの考えはこの点が抜けている。
直接参照というのは、こんな場合である。
(define (f x)
(letrec ((a b)
(b 2))
(+ x a b))
で、これは、もちろんエラーになる。(a b) を評価する時点で、b の未定義エラーになる。
Ex. 4.21
Ex. 4.20で言っていたのは、 letrec は変数を互いに直接参照できないことであった。
Louiseは、この点を見落としていたが、逆に言えば、Louiseのように参照を lambda 式のなかに埋め込んでしまえば、直接参照を避けて変数の相互参照が可能であるということである。結局 Louiseは letrec の制限を正しく回避していたことになる。
で、変数の定義を lambda 式にするのならば、わざわざ letrec を使わなくても、最初から lambda 式だけで書けるのではないか。というのがこの問題の主旨である。
a. ループ用の内部定義関数を、引数にすればよい。
(lambda (n)
((lambda (fib)
(fib fib 0 1 n))
(lambda (fb a b k)
(if (= k 0)
b
(fb b (+ a b) (- k 1))))))
こんな感じ？動かしてないけど、、、
b.相互参照ありの再帰
(define (f x)
((lambda (even? odd?)
(even? even? odd? x))
(lambda (ev? od? n)
(if (= n 0) true (od? ev? od? (- n 1))) ;; こっちがeven?
(lambda (ev? od? n)
(if (= n 0) false (ev? ev? od? (- n 1))))) ;; こっちがodd?
こんな感じかな。試してないけど。
ポイントは、define とか、let で変数を保存していたが、その代替品として、関数(メタ関数)の引数を変数の記憶場所に使えるということである。(若しくは、もともと関数の引数にしか記憶作用がなくて、define、let はそれを利用してるだけと言ったほうがいいかもしれない)