?

Log in

No account? Create an account
Ackermann defunctionalized - 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|, ]

Here are five ways to write the Ackermann function.

In math:

(borrowed from Wikipedia)

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.

LinkReply

Comments:
[User Picture]From: jes5199
2008-10-23 06:10 am (UTC)
you learning compilers?
(Reply) (Thread)
[User Picture]From: lindseykuper
2008-10-23 03:07 pm (UTC)

That's what Alex said, too.

It would seem so!
(Reply) (Parent) (Thread)
[User Picture]From: oniugnip
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)
(Reply) (Thread)
[User Picture]From: lindseykuper
2008-10-31 07:27 pm (UTC)

Re: two more ways?

a compiler writer is you, very soon!

If I take Dybvig's class, then "very soon" means "by the end of May at the latest".
(Reply) (Parent) (Thread)