ackermann Cale's translation.markdown

http://hpaste.org/86157 http://hpaste.org/86158

int f(int x, int y) {
  for (; 
       x >= cutoff; -- f1
       x--          -- f2
      ) {
    y = (y <= 0) ? 1 : f(x, y - 1); -- f3
  }
  return g(x,y); -- f4
}

We'll translate the control flow directly into mutually recursive functions which update the values of the x and y parameters as they reduce to each other.

f x y = f1 x y
f1 x y = if x >= cutoff then f3 x y else f4 x y
f2 x y = f1 (x-1) y
f3 x y = f2 x (if x <= 0 then 1 else f x (y-1))
f4 x y = g x y

Now we can simplify this equationally. f1 and f are equal, so we'll eliminate f1:

f x y = if x >= cutoff then f3 x y else f4 x y
f2 x y = f (x-1) y
f3 x y = f2 x (if x <= 0 then 1 else f x (y-1))
f4 x y = g x y

Also, f4 and g are equal, so we'll eliminate f4:

f x y = if x >= cutoff then f3 x y else g x y
f2 x y = f (x-1) y
f3 x y = f2 x (if x <= 0 then 1 else f x (y-1))

We'll expand the definition of f2 directly in f3 and eliminate that:

f x y = if x >= cutoff then f3 x y else g x y
f3 x y = f (x-1) (if x <= 0 then 1 else f x (y-1))

Now we can just splice in the definition of f3 x y and eliminate it:

f x y = if x >= cutoff
           then f (x-1) (if x <= 0 then 1 else f x (y-1))
           else g x y

I have no idea what this program is meant to compute -- it's quite possible that there's a better way, but this isn't so bad now.

import qualified Data.MemoCombinators as Memo

ackermann :: Integer -> Integer -> Integer
ackermann = Memo.memo2 Memo.integral Memo.integral ack
  where ack 0 n = n + 1
        ack m 0 = ackermann (m-1) 1
        ack 1 n = n + 2
        ack 2 n = 2*n + 3
        ack 3 n = 2^(n+3) - 3
        ack m n = ackermann (m-1) (ackermann m (n-1))

main = print $ ackermann 4 2

cabal instasll data-memocombinators

def ackermann(m, n):
    while m >= 4:
        if n == 0:
            n = 1
        else:
            n = ackermann(m, n - 1)
        m -= 1
    if m == 3:
        return (2 ** (n + 3)) - 3
    if m == 2:
        return (n * 2) + 3
    if m == 1:
        return n + 2
    # m == 0
    return n + 1

print ackermann(4,2)

#include <stdio.h>
int ack(int m, int n) {
    if (m == 0) return n+1;
    if (n == 0) return ack(m-1, 1);
    if (m == 1) return n+2;
    if (m == 2) return n+n+3;
    if (m == 3) return (1 << (n+3)) - 3;
    return ack(m-1, ack(m,n-1));
}

int main() {
  printf("%ld\n", ack(4,1));
  return 0;
}

ack 0 n = n + 1
ack m 0 = ack (m-1) 1
ack 1 n = n + 2
ack 2 n = 2*n + 3
ack 3 n = 2^(n+3) - 3
ack m n = ack (m-1) (ack m (n-1))