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 continuationpassing style:
(define ack
(lambda (n m)
(ackcps n m (emptyk))))
(define ackcps
(lambda (n m k)
(cond
[(zero? n) (k (add1 m))]
[(zero? m) (ackcps (sub1 n)
1
k)]
[else (ackcps n
(sub1 m)
(lambda (v) (ackcps (sub1 n) v k)))])))
(define emptyk
(lambda ()
(lambda (v) v)))
In CPS with continuations represented as data:
(define ack
(lambda (n m)
(ackcps n m (emptyk))))
(define ackcps
(lambda (n m k)
(cond
[(zero? n) (ackapplyk k (add1 m))]
[(zero? m) (ackcps (sub1 n) 1 k)]
[else (ackcps n
(sub1 m)
(ackmakek n k))])))
(define emptyk
(lambda ()
`(emptyk)))
(define ackmakek
(lambda (n k)
`(ackmakek ,n ,k)))
(define ackapplyk
(lambda (k v)
(pmatch k
[(emptyk) v]
[(ackmakek ,n ,k) (ackcps (sub1 n) v k)])))
In four registers or so:
(define ackn)
(define ackm)
(define ackk)
(define ackv)
(define ack
(lambda (localn localm)
(begin
(set! ackn localn)
(set! ackm localm)
(set! ackk `(emptyk))
(ackreg))))
(define ackreg
(lambda () ; ackn ackm ackk
(cond
[(zero? ackn) (set! ackv (add1 ackm)) (ackapplyk)]
[(zero? ackm) (set! ackn (sub1 ackn)) (set! ackm 1) (ackreg)]
[else (set! ackk `(ackmakek ,ackn ,ackk))
(set! ackm (sub1 ackm))
(ackreg)])))
(define ackapplyk
(lambda () ; ackk ackv
(pmatch ackk
[(emptyk) ackv]
[(ackmakek ,localn ,localk)
(set! ackk localk) (set! ackm ackv) (set! ackn (sub1 localn))
(ackreg)])))
Left as an exercise for the reader:
What are setbangs 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.
