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.