SICP 読書ノート#56 - 4.2.2 遅延評価の解釈系 (pp.238-243)
前節の正規順序による評価を実現するために、Scheme評価器に遅延評価を組み込みます。
thunkとは？
thunk(サンク)とは遅延評価オブジェクトそのものです。
Racketでもdelayでthunkをつくることができる。(promiseという名前だが)
racket@> (define x (delay (+ a b))) racket@> x #<promise:x>
この時点でxはthunkそのものであり、(+ a b)はまだ評価されていない。
racket@> (define a 1) racket@> (define b 2) racket@> (force x) 3
この(force x)でthunkが持っている式が評価される。
racket@> x
#<promise!3>
得られた結果はthunkにメモされる。
racket@> (define a 4) racket@> (define b 5) racket@> (force x) 3
一度結果がメモ化されるとthunkはその値を返すので、a、bの値を変えても(force x)の結果は変わらない。
thunkの実装
本文に倣って実装してみる。
;;; set-car!/set-cdr!を使うのでr5rsをrequireする必要がある (require r5rs) ;;; 遅延オブジェクトの生成 (define (delay-it exp env) (list 'thunk exp env)) ;;; 遅延オブジェクトの評価 (define (force-it obj) (cond ((tagged-list? obj 'evaluated-thunk) (cadr obj)) ;; its value ((tagged-list? obj 'thunk) ((let ((value (force-it (eval-proc exp env)))) (set-car! obj 'evaluated-thunk) (set-car! (cdr obj) value) ;; replace expression with its value (set-cdr! (cdr obj) '()) ;; forget environment value))) (else obj))) ;; not delayed object
遅延評価器を動作させる
てっきり§4.1.7の構文解析と実行を分離した評価器を使うかと思ったら、§4.1.1の最初に出た評価器に対しての修正だったので萎えてしまった。。
せっかくthunkを実装したけど、いまさら最初の評価器を触るのは面倒すぎるので、SICPのサイトにあるサンプルコードを流用させてもらいました。
1. SICP本家からサンプルコードをダウンロード
% curl -O https://mitpress.mit.edu/sicp/code/ch4-leval.scm % curl -O https://mitpress.mit.edu/sicp/code/ch4-mceval.scm
2. Racket処理系で解釈できるようにいくつか修正
ch4-leval.scm
- ファイルの先頭に
#lang racketのシェバンを追加 evalをeval-proc、applyをapply-procに変更 (Racketは二重定義を許さないため)ch4-mceval.scmのロード処理をloadからincludeに変更
(require racket/include) (include "ch4-mceval.scm")
- メモなし版/メモあり版のどちらかを採用する
;; non-memoizing version of force-it (define (force-it obj) (if (thunk? obj) (actual-value (thunk-exp obj) (thunk-env obj)) obj)) ;; memoizing version of force-it (define (force-it obj) (cond ((thunk? obj) (let ((result (actual-value (thunk-exp obj) (thunk-env obj)))) (set-car! obj 'evaluated-thunk) (set-car! (cdr obj) result) ; replace exp with its value (set-cdr! (cdr obj) '()) ; forget unneeded env result)) ((evaluated-thunk? obj) (thunk-value obj)) (else obj)))
- ファイルの終端に以下を追加
(define the-global-environment (setup-environment)) (driver-loop)
ch4-mceval.scm
- ファイルの先頭に
(require r5rs)を追加 evalをeval-procに変更ch4-leval.scmとかぶっている定義をコメントアウトevalapplyeval-ifprimitive-proceduresinput-promptoutput-promptdriver-loop
3. 遅延評価器を起動
ch4-leval.scmをロードすると遅延評価器のREPLが起きて入力プロンプトが表示される。
racket@> ,enter "ch4-leval.scm" 'METACIRCULAR-EVALUATOR-LOADED 'LAZY-EVALUATOR-LOADED ;;; L-Eval input:
試しにテキスト本文のコードを打ち込んでみる。
;;; L-Eval input: (define (try a b) (if (= a 0) 1 b)) ;;; L-Eval value: ok ;;; L-Eval input: (try 0 (/ 1 0)) ;;; L-Eval value: 1
ちゃんと動いている。
問題 4.27
(define count 0) (define (id x) (set! count (+ count 1)) x) (define w (id (id 10)))
に対して、
> count ;; => ??? > w ;; => ??? > count ;; => ???
の結果は次の通り。
| 遅延評価なし | 遅延評価あり | |
|---|---|---|
| count | 2 | 1 |
| w | 10 | 10 |
| count | 2 | 2 |
遅延評価ありの場合の (define w (id (id 10))) は、
defineはspecial formのため、外側のidは即座に評価される- 外側の
idはcompound procedureのため、内側のidは遅延評価される
ので、最初のcountは1となる。
その後でwを評価する際に、遅延されたidが評価されるため二回目のcountは2となる。
問題 4.29
a.
すごい既視感があるんだけど、フィボナッチ数と計算とか。
計算の中でf(k)のkが何度も出るようなパターンでは、メモ化するとしないで全然違う。一概には言えないが、オーダーでいうとO(n)とO(n)〜O(n^2)くらいは違うはず。
b.
(define count 0) (define (id x) (set! count (+ count 1)) x) (define (square x) (* x x))
とした場合、メモ化ありなしで、
> (square (id 10)) ;; => ??? > count ;; => ???
の応答結果はどう違うか？
結果は以下の通り。
| メモ化あり | メモ化なし | |
|---|---|---|
| (square ...) | 100 | 100 |
| count | 1 | 2 |
まず (square ...) はcompound procedureなので次のように簡約される。
(square (id 10)) => (* <thunk (id 10)> <thunk (id 10)>) => (* (force <thunk (id 10)>) (force <thunk (id 10)>)) ;; ここでthunkを評価 => (* 10 10) => 100
メモ化ありの場合(id 10)の結果はメモ化されるので二回目の(id 10)の評価で内部の処理は走らない、メモ化なしだと走る、のでcountの結果が異なる。
問題 4.30
転校したCプログラマのCy D. Fect = side effectですか(笑)
a.
確かに、
(define (for-each proc items) (if (null? items) 'done (begin (proc (car items)) (for-each proc (cdr items)))))
のprocの評価の際に渡される(car items)はthunkとなるが、
(for-each (lambda (x) (newline) (display x)) (list 57 321 88))
displayはprimitive procedureなので、そこでthunkが評価され正しく出力される。
b.
(define (p1 x) (set! x (cons x '(2))) x) (define (p2 x) (define (p e) e x) (p (set! x (cons x '(2)))))
において、元々のeval-sequenceでの結果は以下の通り。
;;; L-Eval input: (p1 1) ;;; L-Eval value: (1 2) ;;; L-Eval input: (p2 1) ;;; L-Eval value: 1
普通に考えると(p2 1) => (1 2)となってほしいところが、(p2 1) => 1となってしまう。
Cyが提案したeval-sequenceでの結果は以下の通り。(p2 1) => (1 2)となる。
;;; L-Eval input: (p1 1) ;;; L-Eval value: (1 2) ;;; L-Eval input: (p2 1) ;;; L-Eval value: (1 2)
理由は、(p (set! x (cons x '(2)))の手続きpはcompound procedureのため、引数は(set! x (cons x '(2)))はthunkとして渡される。
手続きpの本体は、
(define (p e) e x)
となっており、元々のeval-sequenceは途中の式のeを評価しないため、先程のthunkはそのままとなり、上記のような結果となる。
c.
- 元々のeval-sequenceは、displayがprimitive procedureのため
- Cyのeval-sequenceは、シーケンス内の途中式を必ずforceするため
とforceするタイミングは厳密には違うが、実行結果は同じとなる。
d.
本文のアプローチは、シーケンスが途中式を評価しないことをプログラマが頭に入れておく必要があり、なかなか悩ましい。
Cyのアプローチは、シーケンスで必ず途中式が評価されるものの、そもそも引数の遅延がその時点で破られてしまうため、評価器としての用途をそもそも満たしていない。
遅延評価器という意味では本文のアプローチが正しいと思うが、上記の制約があるため使いこなすのが難しいといったところか。
問題 4.30
パス。こんな評価器もしあっても使いこなせないわ(笑)
次回は「§4.2.3 遅延評価リストとしてのストリーム」から。
