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
とかぶっている定義をコメントアウトeval
apply
eval-if
primitive-procedures
input-prompt
output-prompt
driver-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 遅延評価リストとしてのストリーム」から。