No account? Create an account
 Lindsey Kuper [entries|archive|friends|userinfo] Lindsey Kuper

 [ website | composition.al ] [ userinfo | livejournal userinfo ] [ archive | journal archive ]

Ackermann defunctionalized [Oct. 22nd, 2008|10:41 pm]
Lindsey Kuper
 [ Tags | b521, programming ]

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. From: 2008-10-23 06:10 am (UTC) (Link)
you learning compilers? From:
2008-10-23 03:07 pm (UTC)

### That's what Alex said, too.

It would seem so! From:
2008-10-24 12:08 am (UTC)

### two more ways?

♥! This is really wild -- a compiler writer is you, very soon! Zach asked about you earlier tonight -- he was duly impressed when I pointed him over this way :D

Two more ways, same as your first one.
ack.hs:
```ack m n
| m == 0 = n + 1
| m > 0 && n == 0 = ack (m - 1) 1
| m > 0 && n > 0 = ack (m - 1) (ack m (n - 1))
```
ack.logo (given any language, you can use that language like Pascal, but all the hip kids do number crunching in Logo?):
```to ack :m :n
if equal? :m 0 [ output (:n + 1) ]

if (and (greater? :m 0)
(equal? :n 0)) [ output ack (m - 1) 1 ]

if (and (greater? :m 0)
(greater? :n 0)) [ output ack (m-1) (ack m (n-1)) ]
end```

Edited at 2008-10-24 12:10 am (UTC) From: 