SICP 読み (297) 5.4 積極制御評価器
今日は長距離移動があるんですが、朝勉強。
問題 5.28
色々ヤッてるんですが、ev-sequence のナニが微妙。
具体的に
ev-sequence (assign exp (op first-exp) (reg unev)) (test (op last-exp?) (reg unev)) (branch (label ev-sequence-last-exp)) (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-last-exp (restore continue) (goto (label eval-dispatch))
と
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))
の違いが具体的にイメージできてないかも。全然理解できていない訳ではないんですが、なんとなーく気持ち悪い感じがある、と言えば良いのでしょうか。
とりあえず、盛り込んで動作確認。
;;; EC-Eval input:
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok
;;; EC-Eval input:
(factorial 1)
(total-pushes = 18 maximum-depth = 11)
;;; EC-Eval value:
1
;;; EC-Eval input:
(factorial 2)
(total-pushes = 52 maximum-depth = 19)
;;; EC-Eval value:
2
;;; EC-Eval input:
(factorial 3)
(total-pushes = 86 maximum-depth = 27)
;;; EC-Eval value:
6
;;; EC-Eval input:
(factorial 4)
(total-pushes = 120 maximum-depth = 35)
;;; EC-Eval value:
24
;;; EC-Eval input:あるいは
;;; EC-Eval input:
(define (factorial n)
(define (iter p c)
(if (> c n)
p
(iter (* c p)
(+ c 1))))
(iter 1 1))
(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok
;;; EC-Eval input:
(factorial 1)
(total-pushes = 70 maximum-depth = 17)
;;; EC-Eval value:
1
;;; EC-Eval input:
(factorial 2)
(total-pushes = 107 maximum-depth = 20)
;;; EC-Eval value:
2
;;; EC-Eval input:
(factorial 3)
(total-pushes = 144 maximum-depth = 23)
;;; EC-Eval value:
6
;;; EC-Eval input:
(factorial 4)
(total-pushes = 181 maximum-depth = 26)
;;; EC-Eval value:
24
;;; EC-Eval input:うーん。再帰版なソレは単純に回数が、というのは分かるんですが上記の末尾再帰な違いがイメージできないのが微妙な所以でしょうか。
で比べてみたら、push 回数自体はさほど変わらんのか。最大深さが上記の版では増えている。なんとなくオチてはいますが日本語にできん。(弱
つづき
成程たしかに goto だ。上記の上側の末尾再帰な ev-seq は最後の式の評価は eval 方面にいってらっしゃい戻ってくるなよ式なんですが、下側の ev-seq は最後の式を評価した後に ev-seq に戻ってくる形になっている。
ので、scheme な繰返し式の再帰呼び出しも評価器の中では再帰呼び出しになってしまっているのか。素晴しい。
問題 5.29
なんとなくヒマなので fibonacci 計算してみる。
;;; EC-Eval input:
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok
;;; EC-Eval input:
(fib 2)
(total-pushes = 72 maximum-depth = 13)
;;; EC-Eval value:
1
;;; EC-Eval input:
(fib 3)
(total-pushes = 128 maximum-depth = 18)
;;; EC-Eval value:
2
;;; EC-Eval input:
(fib 4)
(total-pushes = 240 maximum-depth = 23)
;;; EC-Eval value:
3
;;; EC-Eval input:
(fib 5)
(total-pushes = 408 maximum-depth = 28)
;;; EC-Eval value:
5
;;; EC-Eval input:
(fib 6)
(total-pushes = 688 maximum-depth = 33)
;;; EC-Eval value:
8
;;; EC-Eval input:
(fib 7)
(total-pushes = 1136 maximum-depth = 38)
;;; EC-Eval value:
13
;;; EC-Eval input:
(fib 8)
(total-pushes = 1864 maximum-depth = 43)
;;; EC-Eval value:
21
;;; EC-Eval input:最大深さは 5 づつ増分。b.は事前に目を通した時は意味分からなくてスルーかな、と思っていたのですが、面白そうなので試してみよう。
- S(4) が 240 で S(3) は 128、S(2) は 72 なので S(4) = S(3) + S(2) + k の k は 40 になる
- S(5) は 408 なんで S(5) = S(4) + S(3) + k の k は 40 だ
- S(6) は 688 で S(6) = S(5) + S(4) + k の k はこれまた 40
- S(7) は 1136 で k はこれも 40
次の設問が微妙。
