計算機プログラムの構造と解釈

SICP

1.9

;パターン1
(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))
;生成されるプロセス
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5)))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
;;再帰的である。

;パターン2
(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))
;生成されるプロセス
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9
;;反復的である。

1.10

(define (A x y)
  (cond ((= y 0) 0)
	((= x 0) (* 2 y))
	((= y 1) 2)
	(else (A (- x 1)
		 (A x (- y 1))))))

(A 1 10)
(A 2 4)
(A 3 3)

うわなんだこれ。
再帰の中にもう一個再帰が入ってる。再帰の再帰みたいな。
すげー。たのしい。
とりあえず難しいのでjsに直してみる

function A(x,y){
    if(y==0) return 0;
    if(x==0) return 2*y;
    if(y==1) return 2;
    return A(x-1,A(x,y-1));
}

A(1,10);
A(2,4);
A(3,3);

こうしてみてもわかんないなー。
頭の中だけで解けるのか？


とりあえず置き換えプロセスにしてみよう。

;1問目
(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
1024

(A 1 10) -> 1024

;2問目
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)
;;ここで、1問目の(A 1 10)は帰ってくる式を見るに2の10乗となっていた。
;;また、1問目の展開式を見るにここでは最終的展開は以下の式となると考えられる。
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))))))))
;;よって2の16乗となると考えられる。
65536

(A 2 4) -> 65536

;3問目
(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
;;ここで、↑の式は↓の式に展開できる。
(A 2 (A 0 2))
(A 2 4)
;;ここで、↑の式は2問目の式と等価である。
;;よって
65536

(A 3 3) -> 65536

このレベルが頭の中でわかるようになったら、世界が違うんだろうなー

;4問目
(define (f n) (A 0 n))
;(f n)は2*nを計算する。

;5問目
(define (g n) (A 1 n))
;(g n)は2のn乗を計算する。

;6問目
(define (h n) (A 2 n))
;2問目と五問目をから、
;(A 2 4) は 2の(A 2 3)乗である。
;さらに展開すると、(A 2 4)は
;2の(2の(2の2乗)乗)乗である。
;ちなみにこういった計算式の書き方は思い浮かばない。
;所詮文系か･･･。orz

やってみておもってるんだけど、この本なんか難しくない？