問題4.25-4.31
遅延評価のSchemeについてです。
4.25
> (define (unless condition usual-value exceptional-value) (if condition usual-value exceptional-value)) > (define (factorial n) (unless (= n 1) (* n (factorial (- n 1))) 1)) > (factorial 5)
これは終わりません。unlessは(* n (factorial (- n 1)))を評価しようとします。一見n=0の時に終わりそうですが、この時でも作用的順序の規則から(* n (factorial (- n 1)))を評価しなければならないので、いつまでたっても評価が終わらないということになります。
正規順序の評価の下では、これはちゃんと動きます。
4.26
unlessの実装は、単にifにして第二、第三引数を入れ替えればいいので省略します。
unlessが手続きであれば有用であるというのは、やはり高階手続きとして利用する時でしょうか。でも有用な場合と言われて思いつくものがないです。lambdaでラップすれば大抵の場合に使えるし。分からない。
4.27
遅延評価器を作りました。遅延評価器での次のセッション(この言葉使ってみたかった)を考えます。
;;; L-Eval input: (define count 0) ;;; L-Eval value: ok ;;; L-Eval input: (define (id x) (set! count (+ count 1)) x) ;;; L-Eval value: ok ;;; L-Eval input: (define w (id (id 10))) ;;; L-Eval value: ok ;;; L-Eval input: ...(*1) count ;;; L-Eval value: 1 ;;; L-Eval input: ...(*2) w ;;; L-Eval value: 10 ;;; L-Eval input: ...(*3) count ;;; L-Eval value: 2
メモ化によるものかな、と思いましたが、ググってみるとどうやら違うようです。
wのdefine時に外側のidが評価されるのでcountが1になり、w評価時に内側のidが評価されるのでcountが2になる、ということらしいです。次の例からも、どうやらそのようです。
;;; L-Eval input: (define w (id (id (id (id 10))))) ;;; L-Eval value: ok ;;; L-Eval input: count ;;; L-Eval value: 1 ;;; L-Eval input: w ;;; L-Eval value: 10 ;;; L-Eval input: count ;;; L-Eval value: 4 ;;; L-Eval input: w ;;; L-Eval value: 10 ;;; L-Eval input: count ;;; L-Eval value: 4
定義時は確かに値が必要ないからthunkが返ってくるだけなんですね。で、評価時にthunkを値が出るまで掘ると。w評価後にwに値が対応づけられるということですね。複雑だなぁ。
4.28
evalしてthunkが返ってきた場合がだめで、thunkが返ってくるのは遅延評価の引数の場合。だから引数に手続きがあるような手続きを定義するとだめなはず。
;;; L-Eval input: (define (map f lst) (if (null? lst) '() (cons (f (car lst)) (map f (cdr lst))))) ;;; L-Eval value: ok ;;; L-Eval input: (map (lambda (x) x) '(1 2 3 4 5)) . Unknown procedure type -- APPLY (thunk (lambda (x) x) #0=(((map #f #t false true car cdr cons null? list + - * / modulo = < > eq? not display newline) (procedure (f lst) ((if (null? lst) (quote ()) (cons (f (car lst)) (map f (cdr lst))))) #0#) #f #t #f #t (primitive #<primitive:car>) (primitive #<primitive:cdr>) (primitive #<primitive:cons>) (primitive #<primitive:null?>) (primitive #<primitive:list>) (primitive #<primitive:+>) (primitive #<primitive:->) (primitive #<primitive:*>) (primitive #<primitive:/>) (primitive #<primitive:modulo>) (primitive #<primitive:=>) (primitive #<primitive:<>) (primitive #<primitive:>>) (primitive #<primitive:eq?>) (primitive #<primitive:not>) (primitive #<primitive:display>) (primitive #<primitive:newline>))))
ということで、ダメですね。正規順序評価だからくそ長いエラーが出てきます。actual-valueを使うとちゃんとできます。
;;; L-Eval input: (define (map f lst) (if (null? lst) '() (cons (f (car lst)) (map f (cdr lst))))) ;;; L-Eval value: ok ;;; L-Eval input: (map (lambda (x) x) '(1 2 3 4 5)) ;;; L-Eval value: (1 2 3 4 5)
4.29
同じオブジェクトを何度も使いまわす場合遅くなるはず。だからこういう場合はメモ化を外すとかなり遅くなるはず。
;;; L-Eval input: (define (f n) (if (= n 0) 0 (+ n (f (- n 1))))) ;;; L-Eval value: ok ;;; L-Eval input: (f (f 100))
実際遅くなりました。次に、メモ化時と非メモ化時での応答の違いを見ます。countとidは4.27と同じ。
まず非メモ化時。
;;; L-Eval input: (define (square x) (* x x)) ;;; L-Eval value: ok ;;; L-Eval input: (square (id 10)) ;;; L-Eval value: 100 ;;; L-Eval input: count ;;; L-Eval value: 2
メモ化時。
;;; L-Eval input: (define (square x) (* x x)) ;;; L-Eval value: ok ;;; L-Eval input: (square (id 10)) ;;; L-Eval value: 100 ;;; L-Eval input: count ;;; L-Eval value: 1
squareが(* (id 10) (id 10))に展開されるので、メモ化版だと(id 10)がevaluated-thunkになるから(set! count (+ count 1))が評価されないってことですかね。たぶん。
4.30
うーん、遅延評価苦手かも。
a.
newlineもdisplayも基本手続きで、遅延評価されないから。
b.
元々のeval-sequenceでの評価。
;;; L-Eval input: (define (p1 x) (set! x (cons x '(2))) x) ;;; L-Eval value: ok ;;; L-Eval input: (define (p2 x) (define (p e) e x) (p (set! x (cons x '(2))))) ;;; L-Eval value: ok ;;; L-Eval input: (p1 1) ;;; L-Eval value: (1 2) ;;; L-Eval input: (p2 1) ;;; L-Eval value: 1
Cyなんとかのeval-sequenceによる評価。
;;; L-Eval input: (p1 1) ;;; L-Eval value: (1 2) ;;; L-Eval input: (p2 1) ;;; L-Eval value: (1 2)
c.
actual-valueの中のforce-itは、遅延オブジェクト以外はそのまま返すから。
d.
今までのSchemeと同じように書きたいとしたら、Cyの指摘は正しいんじゃないかな。
4.31
え、嫌。やりたくない…。省略。
だんだん難しくなってきました。4章が大変って聞いてたけど大変ですね。やっぱり。とりあえず今日はここまで。
