問題5.23-5.30

sicp

レジスタ計算機言語でがりがりとScheme評価器を作ります。
４章で使った抽象が役に立ちます。というかあれをもっと低いレベルに落としたのが積極評価機ぽいです。
４章のコードをそのままコピペして積極評価機を動かそうとすると、applyを書き換えていたのでエラーになります。evalとapplyは使わないのでコメントアウトしたり削除したりするとちゃんと動きます。

> (start eceval)


;;; EC-Eval input:
(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))
;;; EC-Eval value:
ok

;;; EC-Eval input:
(append '(a b c) '(d e f))
;;; EC-Eval value:
(a b c d e f)

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

;;; EC-Eval input:
(fact 10)
;;; EC-Eval value:
3628800

やっぱり動くと楽しいですね。

5.23

まずopでcond->ifなんかを使えるようにします。次にeval-dispatchラベルの処理にこんな風に追加します。

...
  (test (op cond?) (reg exp))
  (branch (label ev-cond))
...

単純に４章で書いたことをレジスタ計算機で処理できるように変換してます。
あとはラベルev-condを書けばいいです。

...
  ev-cond
  (assign exp (op cond->if) (reg exp))
  (goto (label eval-dispatch))
...

実行します。

> (start eceval)


;;; EC-Eval input:
(define (fib n)
  (cond ((= n 0) 1)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) (fib (- n 2))))))
;;; EC-Eval value:
ok

;;; EC-Eval input:
(fib 5)
;;; EC-Eval value:
8

;;; EC-Eval input:
(fib 10)
;;; EC-Eval value:
89

;;; EC-Eval input:
(fib 20)
;;; EC-Eval value:
10946

5.24

しません

5.25

いやです

5.26

a.
;;; EC-Eval input:
(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product) (+ counter 1))))
  (iter 1 1))
(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 10)
(total-pushes = 379 maximum-depth = 10)
;;; EC-Eval value:
3628800

;;; EC-Eval input:
(factorial 20)
(total-pushes = 729 maximum-depth = 10)
;;; EC-Eval value:
2432902008176640000

;;; EC-Eval input:
(factorial 30)
(total-pushes = 1079 maximum-depth = 10)
;;; EC-Eval value:
265252859812191058636308480000000

ということで、最大深さは10のようです。反復だからnに関係ないです。

b.

上の結果から、35n+29じゃないかな。

;;; EC-Eval input:
(factorial 1)
(total-pushes = 64 maximum-depth = 10)
;;; EC-Eval value:
1

;;; EC-Eval input:
(factorial 2)
(total-pushes = 99 maximum-depth = 10)
;;; EC-Eval value:
2

;;; EC-Eval input:
(factorial 5)
(total-pushes = 204 maximum-depth = 10)
;;; EC-Eval value:
120

;;; EC-Eval input:
(factorial 0)
(total-pushes = 29 maximum-depth = 8)
;;; EC-Eval value:
1

ぽいですね。

5.27

;;; 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 = 16 maximum-depth = 8)
;;; EC-Eval value:
1

;;; EC-Eval input:
(factorial 5)
(total-pushes = 144 maximum-depth = 28)
;;; EC-Eval value:
120

;;; EC-Eval input:
(factorial 10)
(total-pushes = 304 maximum-depth = 53)
;;; EC-Eval value:
3628800

;;; EC-Eval input:
(factorial 20)
(total-pushes = 624 maximum-depth = 103)
;;; EC-Eval value:
2432902008176640000

ということで、最大深さは5n+3、プッシュ演算の総数は32n-16のようです。これで、１章でやったことがやっと計算機レベルで確認できました。

5.28

p333のev-sequenceに代えて実験します。まずは再帰プロセス。

;;; EC-Eval input:
(define (f n)
  (if (= n 1) 1 (* n (f (- n 1)))))
(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok

;;; EC-Eval input:
(f 1)
(total-pushes = 18 maximum-depth = 11)
;;; EC-Eval value:
1

;;; EC-Eval input:
(f 3)
(total-pushes = 86 maximum-depth = 23)
;;; EC-Eval value:
6

;;; EC-Eval input:
(f 10)
(total-pushes = 324 maximum-depth = 65)
;;; EC-Eval value:
3628800

当然ですがあんまり変わらないです。次に反復プロセス。

;;; EC-Eval input:
(define (f 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:
(f 1)
(total-pushes = 70 maximum-depth = 17)
;;; EC-Eval value:
1

;;; EC-Eval input:
(f 5)
(total-pushes = 218 maximum-depth = 29)
;;; EC-Eval value:
120

;;; EC-Eval input:
(f 10)
(total-pushes = 403 maximum-depth = 44)
;;; EC-Eval value:
3628800

最大深さがnについて線形に増加するようになります。ということで元のに戻しておきます。

5.29

;;; 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 10)
(total-pushes = 4944 maximum-depth = 53)
;;; EC-Eval value:
55

;;; EC-Eval input:
(fib 20)
(total-pushes = 612936 maximum-depth = 103)
;;; EC-Eval value:
6765
a.

上の結果から分かるとおり、factorialの再帰的プロセスと同じで5n+3です。

b.

上見ると$S(n) = S(n-1) + S(n-2) + 40$ってなってますね。なんでk=40ぽいです。このkは、一回のFibの計算時のプッシュ量です。たぶん。
で、

n 2 3 4 5 6 7 8
S(n) 72 128 240 408 688 1136 1864
Fib(n) 1 2 3 5 8 13 21

$S(n)=aFib(n+1)+b$と仮定すると、$S(3) - S(2) = a\{Fib(4) - Fib(3)\} = a$なので$a=56$
すると$S(n)=56Fib(n+1)+b$となり、n=2を代入すると$b=-40$
よって$S(n)=56Fib(n+1)-40$となります。
$Fib(n)$は指数関数なので、この手続きは指数関数的にプッシュ量が増えていく(つまり時間も指数関数的に増大)と思われます。

5.30

しません。

今日はここまで。