Ackermann defunctionalized

Here are five ways to write the Ackermann function.

In math:

In direct style:

(define ack
  (lambda (n m)
    (cond
      [(zero? n) (add1 m)]
      [(zero? m) (ack (sub1 n) 1)]
      [else (ack (sub1 n)
                 (ack n (sub1 m)))])))

In continuation-passing style:

(define ack
  (lambda (n m)
    (ack-cps n m (empty-k))))

(define ack-cps
  (lambda (n m k)
    (cond
      [(zero? n) (k (add1 m))]
      [(zero? m) (ack-cps (sub1 n)
                          1
                          k)]
      [else (ack-cps n
                     (sub1 m)
                     (lambda (v) (ack-cps (sub1 n) v k)))])))

(define empty-k
  (lambda ()
    (lambda (v) v)))

In CPS with continuations represented as data:

(define ack
  (lambda (n m)
    (ack-cps n m (empty-k))))

(define ack-cps
  (lambda (n m k)
    (cond
      [(zero? n) (ack-apply-k k (add1 m))]
      [(zero? m) (ack-cps (sub1 n) 1 k)]
      [else (ack-cps n
                     (sub1 m)
                     (ack-make-k n k))])))

(define empty-k
  (lambda ()
    `(empty-k)))

(define ack-make-k
  (lambda (n k)
    `(ack-make-k ,n ,k)))

(define ack-apply-k
  (lambda (k v)
    (pmatch k
      [(empty-k) v]
      [(ack-make-k ,n ,k) (ack-cps (sub1 n) v k)])))

In four registers or so:

(define ack-n)
(define ack-m)
(define ack-k)
(define ack-v)

(define ack
  (lambda (local-n local-m)
    (begin
      (set! ack-n local-n)
      (set! ack-m local-m)
      (set! ack-k `(empty-k))
      (ack-reg))))

(define ack-reg
  (lambda () ; ack-n ack-m ack-k
    (cond
      [(zero? ack-n) (set! ack-v (add1 ack-m)) (ack-apply-k)]
      [(zero? ack-m) (set! ack-n (sub1 ack-n)) (set! ack-m 1) (ack-reg)]
      [else (set! ack-k `(ack-make-k ,ack-n ,ack-k))
            (set! ack-m (sub1 ack-m))
            (ack-reg)])))

(define ack-apply-k
  (lambda () ; ack-k ack-v
    (pmatch ack-k
      [(empty-k) ack-v]
      [(ack-make-k ,local-n ,local-k)
       (set! ack-k local-k) (set! ack-m ack-v) (set! ack-n (sub1 local-n))
       (ack-reg)])))

Left as an exercise for the reader:

What are set-bangs and function calls with no arguments? (Well, aside from "ridiculous Scheme", I mean.) They're assignment statements and gotos, more or less. Which means that you could now pretty straightforwardly write this in the assembly language of your choice.