SICP 読み (188) 4.2.2 遅延評価の解釈系
直前エントリな reverse は手動 eval が面倒なんで繰り返しなソレではなく、再帰版で検討してみる。
(define (reverse l)
(if (null? (cdr l))
(list (car l))
(append (reverse (cdr l)) (list (car l)))))l がやたらに出てくる。これはこれで微妙。とりあえず上記の式を eval (というか actual-value か) すると、(procedure (l) (if 式) env) みたいな式が reverse に束縛される、はず。で、(reverse (list 1 2 3)) な式を評価器に吸わせるトコから話を始めてみます。
この式は application 認定なので、reverse を actual-value したものと引数が apply に渡されます。こんな感じ。
(apply (procedure (l) (if 式) env) ((list 1 2 3)) env)
apply においては compound-procedure 認定で以下が適用。
(eval-sequence
((if (null? (cdr l))
(list (car l))
(append (reverse (cdr l)) (list (car l)))))
(extend-environment
(l)
(list-of-delayed-args ((list 1 2 3)) env)
env))l に delay された (list 1 2 3) が束縛された環境で if 式が eval されます。正確には (thunk (list 1 2 3) env) か。その環境で eval-if がナニ。という事でまず if-predicate な (null? (cdr l)) が actual-value に渡る。式全体が eval されるのですが、この式は application 認定なソレ。null? は the-global-environment に手続きが束縛されておりますので、primitive な式が apply に渡す actual-value から戻ります。
apply においては primitive-procedure 認定なので、引数リストはそれぞれ actual-value されるんですが、ここでも eval の中で application 認定されて、cdr も primitive 認定。で、引数の l が cdr に引数リストを actual-value する時に eval から戻った (thunk (list 1 2 3) env) を force-it する事になります。
ここで memoize な force-it であれば中身の (list 1 2 3) を eval したナニと共に l の束縛を (evaluated-thunk (1 2 3)) に書き換えてしまいます。で、どちらの force-it も '(1 2 3) を戻して cdr に渡る、と。cdr は (2 3) というリストを戻して null? に渡しますが、null? はそこで #f を戻しますので eval-if では if-alternative な (append (reverse (cdr l)) (list (car l))) を eval する事になります。
二周目直前
と言いつつ、append は gauche で用意されているソレを使っているので、そのまま二周目に入ってしまいそう。eval では application 認定されるので apply に append が eval された primitive な式と引数リストが渡されます。それを受け取った apply においては primitive-procedure 認定なんで引数リストは list-of-arg-values に渡されます。
(apply-primitive-procedure (primitive 略) (list-of-arg-values ((reverse (cdr l)) (list (car l))) env) env)
引数リストは先頭から順に actual-value に渡されます。ちなみにこの時点で l は memoize 版であれば (evaluated-thunk (1 2 3)) で、そうでない版であれば (thunk (list 1 2 3) env) に束縛されているはず。
二周目
まず最初の引数 (reverse (cdr l)) を actual-value します。これは途中をはしょって以下のソレになるはず。
(eval-sequence
((if (null? (cdr l))
(list (car l))
(append (reverse (cdr l)) (list (car l)))))
(extend-environment
(l)
(list-of-delayed-args ((cdr l)) env)
env))eval-sequence な環境は l に (thunk (cdr l) env) が束縛されたナニ。ちなみに thunk の中の env では l が (evaluated-thunk (1 2 3)) 又は (thunk (list 1 2 3) env) が束縛されているはずです。これを前提に二周目。
まず、if 式が eval されて eval-if が適用。まず、if-predicate な式を actual-value します。
(actual-value (null? (cdr l)) env)
ちなみに上の式の環境は直前に書いてある通り。とは言えとりあえず eval されて application 認定な後に null? が actual-value されて primitive な式が戻って apply の中で apply-primitive-procedure 認定 (ぎゃー)。引数リスト ((cdr l)) が list-of-arg-values ですぐに評価。ちょっと微妙に中略なんですが、l が actual-value で 束縛されている (thunk (cdr l) env) を (3) なリストにして戻します。
ちょっと中略し杉。上記の式における l は (thunk (cdr l) env) が束縛されていて、thunk な式の中の l は (evaluated-thunk (1 2 3)) 又は (thunk (list 1 2 3) env) が束縛されているのは上述の通り。で、カワを剥いで eval されたものがさらに cdr された結果、(3) というリストになる、という理解でビンゴかなぁ。
てか、上記 actual-value 式の l は (evaluated-thunk (2 3)) 又は (thunk (cdr l) env) に束縛、という事になるのかな。memoize でない版はこの状態で処理が進むと非常に面倒臭そげ。というのも上述の通り、(thunk (cdr l) env) の中の l は (thunk (list 1 2 3) env) が束縛されている。このネストはこのケースで言えば reverse が終わるまでこのまんまだと思われます。
つづき
で、上の式 (null? (cdr l)) は #f 認定なので if-alternative な式が再度評価、となります。上記で言えば_二周目直前_な部分と言えば良いでしょうか。そろそろリキが無くなってきた。ただ、再帰の中で使いマワシ、といのは O(n) が O(n^2) になる程のインパクトではないけれど、件数が多ければ影響は大きいと言えるのではないかな、と。
で、実機で確認してみました。リストの要素数が 10000 くらいになるとダンマリになるので 10 件から 1000 件くらいまでになっています。多分マシンリソースが最低なんだと思いますが。以下の手続きをわし的評価器に吸わせています。
(define (ll n end)
(define (ll-iter n e result)
(if (> n end)
result
(ll-iter (+ n 1) end (append result (list n)))))
(ll-iter n end '()))
(define (reverse l)
(if (null? (cdr l))
(list (car l))
(append (reverse (cdr l)) (list (car l)))))
(define l (ll 1 1000))
(reverse l)上記は 1000 件版になっていますが、l を定義する時の ll の引数を 10 から順に 100、1000 としています。まず、memoize 版
$ time gosh lib/4.1.2.scm <./test.scm >/dev/null real 0m0.065s user 0m0.048s sys 0m0.012s $ time gosh lib/4.1.2.scm <./test.scm >/dev/null real 0m0.090s user 0m0.084s sys 0m0.008s $ time gosh lib/4.1.2.scm <./test.scm >/dev/null real 0m0.836s user 0m0.564s sys 0m0.052s $
以下が memoize しない版。
$ time gosh lib/4.1.2.scm <./test.scm >/dev/null real 0m0.060s user 0m0.056s sys 0m0.004s $ time gosh lib/4.1.2.scm <./test.scm >/dev/null real 0m0.086s user 0m0.080s sys 0m0.008s $ time gosh lib/4.1.2.scm <./test.scm >/dev/null real 0m2.530s user 0m0.568s sys 0m0.040s $
うーん。大した差が無いように見えるんですが ...
# って処理時間自体は相当差はありますが。
guile でもやってみたんですが、差が無いな、と思ったら Stack overflow してやがる。1000 件な時点で駄目。gauche スゲぇな。てーか時間かけて色々検討してるんですが、相当な大ボケをぶちカマしてるんだろうな、この結果を見るに。
しかも gauche は連続して実行すると速度が上がるな。例えば 1000 件な memoize ナシの様子が以下。
$ time gosh lib/4.1.2.scm < test.scm >/dev/null real 0m5.709s user 0m0.564s sys 0m0.068s $ time gosh lib/4.1.2.scm < test.scm >/dev/null real 0m2.075s user 0m0.512s sys 0m0.056s $ time gosh lib/4.1.2.scm < test.scm >/dev/null real 0m0.610s user 0m0.524s sys 0m0.028s $ time gosh lib/4.1.2.scm < test.scm >/dev/null real 0m0.779s user 0m0.536s sys 0m0.040s $
あるいは memoize 版が以下。
$ time gosh lib/4.1.2.scm < test.scm >/dev/null real 0m1.803s user 0m0.556s sys 0m0.036s $ time gosh lib/4.1.2.scm < test.scm >/dev/null real 0m0.622s user 0m0.580s sys 0m0.024s $ time gosh lib/4.1.2.scm < test.scm >/dev/null real 0m0.595s user 0m0.572s sys 0m0.016s $ time gosh lib/4.1.2.scm < test.scm >/dev/null real 0m0.604s user 0m0.572s sys 0m0.016s $
gosh で何らかのキャッシュをしてるんだという事にすると (根拠ナシ) 数値的には差は出てはいるんですが、なんか釈然としないなぁ。
