sicpマラソン2日目(1)

sicp scheme
[メモ]
  • 再帰的プロセス＝置き換えモデルで遅延演算が膨張・収縮 (1.2.1)
  • 反復的プロセス＝置き換えモデルで一定数の状態変数のみ更新、伸び縮みしない (1.2.1)
  • 線形再帰的プロセス＝計算に必要な情報量(遅延演算の列の長さ)とステップ数が線形に成長 (1.2.1)
  • 線形反復的プロセス＝計算に必要な情報量が一定(状態変数)、ステップ数は線形に成長 (1.2.1)
  • 再帰的手続き＝手続き定義が構文上で自身を使う (1.2.1)
  • プロセス(process)≠手続き(procedure) (1.2.1)
  • 末尾再帰的＝反復的プロセスが再帰的手続きで記述していても固定スペース(消費記憶量)で実行できる実装 (1.2.1)
[演習問題]

1.9 パターン0、パターン1で(+ 4 5)を評価

## パターン0
(define (+ a b)
        (if (= a 0)
            b
            (inc (+ (dec a) b))))

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

パターン0は再帰的プロセス

## パターン1
(define (+ a b)
        (if (= a 0)
            b
            (+ (dec a) (inc b))))

(+ 4 5)
==>(+ 3 6)
==>(+ 2 7)
==>(+ 1 8)
==>(+ 0 9)
==>9

パターン1は反復的プロセス
1.10 Ackermann関数

(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 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))))))))))    ## y=1なので(A 1 1)==>2
==>(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))          ## x=0なので(A 0 2)==>2*2
==>(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))                ## 2^3=8
==>(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))                      ## 2^4=16
==>(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))                           ## 2^5=32
==>(A 0 (A 0 (A 0 (A 0 (A 0 32)))))                                 ## 2^6=64
==>(A 0 (A 0 (A 0 (A 0 64))))                                       ## 2^7=128
==>(A 0 (A 0 (A 0 128)))                                            ## 2^8=256
==>(A 0 (A 0 256))                                                  ## 2^9=512
==>(A 0 512)                                                        ## 2^10=1024
1024

(A 1 10)==>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))))          ## y=1なので(A 2 1)==>2
==>(A 1 (A 1 (A 1 2)))
==>(A 1 (A 1 (A 0 (A 1 1))))          ## y=1なので(A 1 1)==>2
==>(A 1 (A 1 (A 0 2)))                ## x=0なので(A 0 2)==>2*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)))))    ## y=1なので(A 1 1)==>2
==>(A 1 (A 0 (A 0 (A 0 2))))          ## x=0なので(A 0 2)==>2*2
==>(A 1 (A 0 (A 0 4)))                ## 2^3=8
==>(A 1 (A 0 8))                      ## 2^4=16
==>(A 1 16)                           ## (A 1 16)==>(A 0 (A 1 15)) ... と置き換えていってもいいけど
                                      ## (A 1 10)は2^10なので(A 1 16)は2^16と予想できる
                                      ## 2^16=65536
==>65536

(A 2 4)==>65536

(A 3 3)
==>(A 2 (A 3 2))
==>(A 2 (A 2 (A 3 1)))                ## y=1なので(A 3 1)==>2
==>(A 2 (A 2 2))
==>(A 2 (A 1 (A 2 1)))                ## y=1なので(A 2 1)==>2
==>(A 2 (A 1 2))
==>(A 2 (A 0 (A 1 1)))                ## y=1なので(A 1 1)==>2
==>(A 2 (A 0 2))                      ## x=0なので(A 0 2)==>2*2
==>(A 2 4)                            ## 前問から(A 2 4)==>65536
==>65536

(A 3 3)==>65536

## (define (f n) (A 0 n))
(A 0 n)                               ## Aの定義から
==>2*n

## (define (g n) (A 1 n))
(A 1 n)                               ## (A 1 10)から
==>2^n

## (define (h n) (A 2 n))
(A 2 n)
==>(A 1 (A 2 (- n 1)))                ## (A 1 n)==>2^nから
==>2^(A 2 (- n 1))
==>2^(A 1 (A 2 (- n 2)))
==>2^2^(A 2 (- n 2))
...
==>2^2^2...2^(A 2 1)                  ## y=1なので(A 2 1)==>2
==>2^2^2...2^2                        ## 全部でn個

以上から手続きf,g,nの数学的意義は下記の様になる

(f n) ... 2n
(g n) ... 2^n
(h n) ... 2^2^2...2^2
          ----n個----