SICP 読書ノート#75 - 5.4 積極制御評価機 (pp.327-338)

積極制御評価機 (explicit-control evaluator) とは、 レジスタマシンシミュレータ上で動作する マシン語で実装されたScheme処理系のことのよう。

Schemeプログラム→積極制御評価機→レジスタマシン→Scheme処理系 と、さらに抽象化が増してきた。

実装としては、§4.1.1〜§4.1.3ででてきた超循環評価機を レジスタマシン語に書き直したような感じなので、 コードを比較すればなんとなく概要は理解できる。

評価機をRacketで動作させる

Racketではset-car!、set-cdr!が使えないため、いつものごとく MITのサンプルコードは そのままでは動かず、以下のように書き直した。

https://github.com/uents/sicp/tree/master/ch5.4-explicit-control-evaluator

ただ、主にはenvironmentの実装をhashに書き換えたくらいで、 それ以外はほぼそのままでOK。

末尾再帰

超循環評価機では、末尾再帰するかどうかは、下回りの処理系に依存していたが、 積極的制御評価機では、評価機の実装でそれを決めることができる。

つまり、末尾再帰が何なのか、ここでついに明らかになりました！

テキストの積極制御評価機は末尾再帰をサポートしているとのことなので、試してみる。

;;; EC-Eval input:
(define (fact-iter n)
  (define (iter n val)
    (if (= n 1)
        val
        (iter (- n 1) (* n val))))
  (iter n 1))
  
;;; EC-Eval value:
ok

;;; EC-Eval input:
(fact-iter 5)
'(total-pushes = 169 max-depth = 10 curr-depth = 0)

;;; EC-Eval value:
120

;;; EC-Eval input:
(fact-iter 10)
'(total-pushes = 344 max-depth = 10 curr-depth = 0)

;;; EC-Eval value:
3628800

f(5)でもf(10)でもスタックの最大深さは同じなので、末尾再帰できてそう。

次に、末尾再帰を行わない方のev-sequence。 シーケンスに入る度にレジスタの内容を必ずスタックに詰め込んでいる。

;; non-tail-recursive version
ev-sequence
     (test (op no-more-exps?) (reg unev))
     (branch (label ev-sequence-end))
     (assign exp (op first-exp) (reg unev))
     (save unev)
     (save env)
     (assign continue (label ev-sequence-continue))
     (goto (label eval-dispatch))

ev-sequence-continue
     (restore env)
     (restore unev)
     (assign unev (op rest-exps) (reg unev))
     (goto (label ev-sequence))

ev-sequence-end
     (restore continue)
     (goto (reg continue))

テスト結果。f(5)とf(10)でスタックの最大深さが変わっていて、 末尾再帰できていないことがわかる。

;;; EC-Eval input:
(fact-iter 5)
'(total-pushes = 181 max-depth = 26 curr-depth = 0)

;;; EC-Eval value:
120

;;; EC-Eval input:
(fact-iter 10)
'(total-pushes = 366 max-depth = 41 curr-depth = 0)

;;; EC-Eval value:
3628800

問題 5.26

あれ、さっきやったことと似たような問題がでてきた...

以下のfactorial手続きを使って、評価機の末尾特性を監視する。

(define (factorial n)
  (define (iter product counter)
    (if (> counter n) product
        (iter (* counter product) (+ counter 1)))) (iter 1 1))

nをいくつか与えて最大深さとプッシュ総数をを調べて見る。

n	n!	最大深さ	プッシュ総数
1	1	10	64
2	2	10	99
3	6	10	134
5	120	10	204
10	3628800	10	379

a.

nの値に関係なく10となる。

b.

push総数のオーダーはぱっと見ではO(n)。 iterativeに処理が進むはずなので、nに比例するのは当たり前か。

各項の差分を見ると等しいので、等差数列か？高１で出たな、懐かしい。

具体的には、nに対するプッシュ総数をp(n)とすると、 p(n) = 35*(n-1) + 64 と表わされる。

問題 5.27

問題 5.26と同じように以下の手続きを評価機に与えて、 nに対する最大深さとプッシュ総数を調べる。

(define (factorial n)
  (if (= n 1) 1 (* (factorial (- n 1)) n)))

結果は以下の通り。

n	n!	最大深さ	プッシュ総数
1	1	8	16
2	2	13	48
3	6	18	80
5	120	28	144
10	3628800	53	304

最大深さはd(n) = 5*(n-1) + 8、プッシュ総数はp(n) = 32*(n-1) + 16となる。

オーダーで表にすると以下のようになるので、

	最大深さ	プッシュ総数
階乗(再帰)	O(n)	O(n)
階乗(反復)	O(1)	O(n)

• 記憶領域(スタック)の消費の観点では、階乗(反復)の方が優れている
• 計算量の観点では、両者とも左程変わらない

ということがわかる。

残りの問題はすっ飛ばします。いよいよ最後のセクション「§5.5 翻訳系」へ。

---

※「SICP読書ノート」の目次はこちら