問題1.10, p.20

サンプルコード

;code/problem-1-10.scm

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

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

#?=(f 3)
#?=(g 10)
#?=(h 4)

実行例

#?="./problem-1-10.scm":10:(A 1 10)
#?-    1024
#?="./problem-1-10.scm":11:(A 2 4)
#?-    65536
#?="./problem-1-10.scm":12:(A 3 3)
#?-    65536
  • \(f(n) = 2n\)

  • \(g(n)\)を評価したときに生成されるプロセスを書き下してみると、

    (g n)
    => (A 1 n)
    => (A (- 1 1) (A 1 (- n 1)))
    => (A 0 (A 1 (- n 1)))
    => (* 2 (A 1 (- n 1)))
    => (* 2 (* 2 ((A 1 (- n 2)))))
    => (* 2 (* 2 (* 2 (- n 3))))
    => (* 2 (* 2 (* 2 (* 2 (- n 4)))))
    => (* 2 (* 2 (* 2 (* 2 (* 2 (- n 5))))))
    => (* 2 (* 2 (* 2 (* 2 ... 2))))
    

    のようになる。これを数式で書き表すと、\(g(n)=2^{n}\)となる。

  • \(h(n)\)を評価したときに生成されるプロセスを書き下してみると、

    (h n)
    => (A 2 n)
    => (A (- 2 1) (A 2 (- n 1)))
    => (A 1 (A 2 (- n 1)))
    => (A 1 (A 1 (A 2 (- n 2))))
    => (A 1 (A 1 (A 1 (A 2 (- n 3))))
    => (A 1 (A 1 (A 1 (A 1 (A 2 (- n 4))))))
    => (A 1 (A 1 (A 1 (A 1 (A 1 (A 2 (- y 5)))))))
    => (A 1 (A 1 (A 1 (A 1 (A 1 ... (A 2 0))))))
    => (A 1 (A 1 (A 1 (A 1 (A 1 ... 0)))))
    

    のようになる。\(A(1, n) = g(n)\)であることを考えると、\(h(n) = 2 ^{2 ^ {2 ^ {2 ^ { ... 2}}}}\)のような形の、2のn回のべき乗となる。