# Ackermann defunctionalized

Here are five ways to write the Ackermann function.

In math: In direct style:

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

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

(define ack-cps
(lambda (n m k)
(cond
[(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.

Tags:
• #### Join us at the Programming Languages Mentoring Workshop at ICFP next month

New blog post, in which it is time for my annual exhortation. This entry was originally posted at…

• #### How to create an .srt caption file for a video

New blog post, in which I serve in my capacity as ICFP accessibility co-chair, or something. This entry was originally posted at…

New blog post, in which I dispense advice. This entry was originally posted at https://lindseykuper.dreamwidth.org/35335.html. Please comment…

• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic