Exercise-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) ;; 1024
(A 2 4) ;; 65536
(A 3 3) ;; 65536


(A 0 n)
2n


(A 1 n)
(A 0 (A 1 (- n 1)))
(A 0 (A 0 (A 1 (- n 2))))
(A 0 (A 0 (A 0 (A 1 (- n 3)))))
(A 0 (A 0 (A 0 … (A 0 (A 0 (A 1 1)))))) ;;now have n-1 (A 0.. defered
(A 0 (A 0 (A 0 … (A 0 (A 0 2))))) ;;(A 1 1) ==> 2
(A 0 (A 0 (A 0 … (A 0 2^2)))) ;;(A 0 x) ==> 2x
(A 0 (A 0 (A 0 … 2^3)))
(A 0 2^(n-1))
2^n

;; so (A 1 10) ==> 2^10

(A 2 n)
(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 1 (A 2 1)))))) ;have n-1 (A 1.. defered
(A 1 (A 1 (A 1 … (A 1 (A 1 2))))) ;(A 2 1) ==> 2
(A 1 (A 1 (A 1 … (A 1 (2^2))))) ;(A 1 x) ==> 2^x
(A 1 (A 1 (A 1 … 2^(2^2))))
2^(2^(2^…(2^2)))
;;;;;;;;
;; so (A 2 4) ==> 2^(2^(2^2)) = 2^(2^4) = 2^16


In another way,
(A 1 n)
(A 0 (A 1 (- n 1)))
(A 0 (g (- n 1))) ;; definition of (g n)
(f (g (- n 1))) ;; definition of (f n)
2 * (g (- n 1)) ;; result of the (f n)
2^n ;; mathematical induction; and, (g 1) = 2
;;;;;;;;;;
(A 2 n)
(A 1 (A 2 (- n 1)))
(A 1 (h (- n 1))) ;; definition of (h n)
(g (h (- n 1))) ;; definition of (g n)
2^(h (- n 1)) ;; result of (g n)
2^(2^ … (2^2)) ;; mathematical induction; and, (h 1) = 2