勉強ノート - SICP(3)

　今回は問題1.9と1.10を解きましたよー。
　かなり根気が必要だったです・・・。

今回の重要そうなキーワード

線形再帰プロセス
線形反復プロセス

　手続きを展開したときに、いったんプロセスが膨れあがるように展開されていって収束するのが線形再帰。プロセスの展開が終了するまで一定なのが線形反復。

問題1.9

まず手続き１。

(define (+ a b)
    (if (= a 0)
        b
        (inc (+ (dec a) b))))

次に手続き２。

(define (+ a b)
    (if (= a 0)
        b
        (+ (dec a) (inc b))))

　incは引数を1加算する手続き。
　decは引数を1減算する手続き。
　で、上の手続きが(+ 4 5)を評価する時に生成するプロセスは？そのプロセスは反復的か再帰的か。

手続き1

(+ 4 5)
(inc (+ (dec 4) 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

　膨れてから収束するので、再帰的プロセス。

手続き2

(+ 4 5)
(+ (dec 4) (inc 5))
(+ (dec 3) (inc 6))
(+ (dec 2) (inc 7))
(+ (dec 1) (inc 8))
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)

　ひ、ひー（汗
　クソ面倒！！けど勉強だからね。ノートにびっちりトレースさせていただきました。

(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 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)

　これはここまで解いておけば大丈夫だろう・・・。

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)

　これは2番目と同じになった。というわけでここまで解けばＯＫ。

それを踏まえて、問題。

　次の関数の数学的定義を示せ。

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))

(define (k n) (* 5 n n))

　例えばkは $5n^2$ 。
　まず、f。xが0だと $2y$ になるので $2n$ 。
　つぎにg。(A 1 10)が1024になったことを考えると $2^{10}=1024$ なので $2^n$ だね。
　最後にh。gが $2^n$ で、2番目が(A 2 4)が(A 1 16)に展開されたってことは・・・65536!?(A 2 0)〜(A 2 3)の結果が分からないので、パソコンに処理させてみる。

(A 2 0) = 0
(A 2 1) = 2
(A 2 2) = 4
(A 2 3) = 16
(A 2 4) = 65536

　？？？
　よくわからないので手当たり次第に計算してみたところ、

(A 2 1)= $2$
(A 2 2)= $2^2$
(A 2 3)= $2^{2^2}$

　ってなる。

　え？これって数式で表せられんの？（汗
　というワケでめがっさ調べました！海外のブログも含め色々と。そしたら見つけましたよー。
　これは
　 $2 \uparrow \uparrow n$
　とこんな風に書けるっぽい(wikipedia:クヌースの矢印表記)。こんなの授業でやった記憶がない・・・。やっぱバカだとこういうところで時間が掛かるなぁ。