Ackermann Function Expansions

[programming, lisp]

@2021-04-16,*2021-04-16

I don't know if I would call it fun, but SICP made me do it. I will say though, recursive function expansion can make some pretty trees.

;; The Ackermannn function in all of it's glory. (Scheme)
;; https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html
(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else
         (A (- x 1) (A x (- y 1))))))
;; h as an Ackermann variant
(define (h n) (A 2 n))
;; expansion 1
(= (h 1)
   (A 2 1)
   2)
;; expansion 2
(= (h 2)
   (A 2 2)
   (A 1 (A 2 1))
   (A 1 2)
   (A 0 (A 1 1))
   (A 0 2)
   4)
;; expansion 3
(= (h 3)
   (A 2 3)
   (A 1 (A 2 2))
   (A 1 (A 0 (A 2 1)))
   (A 1 (A 0 2))
   (A 1 4)
   (A 0 (A 1 3))
   (A 0 (A 0 (A 1 2)))
   (A 0 (A 0 (A 0 (A 1 1))))
   (A 0 (A 0 (A 0 2)))
   (A 0 (A 0 4))
   (A 0 8)
   16))
;; expansion 4
(= (h 4)
   (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 0 (A 1 15))
   (A 0 (A 0 (A 1 14)))
   (A 0 (A 0 (A 0 (A 1 13))))
   (A 0 (A 0 (A 0 (A 0 (A 1 12)))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10)))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9))))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8)))))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7))))))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6)))))))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 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 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 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 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 (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 (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 (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 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64))))))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128)))))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256))))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512)))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))
   (A 0 (A 0 (A 0 (A 0 (A 0 2048)))))
   (A 0 (A 0 (A 0 (A 0 4096))))
   (A 0 (A 0 (A 0 8192)))
   (A 0 (A 0 16384))
   (A 0 32768)
   65536)