Ackermann function (Alice ML)

From LiteratePrograms

Other implementations: Alice ML | C | Erlang | Forth | Haskell | Java | OCaml | Prolog | Python

This page explains how to implement the Ackermann function in Alice ML.

Contents 1 Source code 2 Execution result 3 Precomputed for small m 4 Unlimited Integer Sizes

Source code

We begin the code by defining a recursive function named ackermann, using pattern matching on the function parameters to handle the three cases given in the definition of the Ackermann function.

<<ackermann.aml>>=
fun ackermann (0, n) = n + 1
  | ackermann (m, 0) if (m > 0) = ackermann(m-1, 1)
  | ackermann (m, n) if (m > 0 andalso n > 0) = ackermann(m-1, ackermann(m, n-1))
  | ackermann _ = raise Domain

The first case we handle is the base case of the recursion, when m = 0.

fun ackermann (0, n) = n + 1

For the second case, when m > 0 and n = 0, we make a simple recursive call to the ackermann function.

  | ackermann (m, 0) if (m > 0) = ackermann (m-1, 1)

In the third case, when m, n > 0, a pair of recursive calls are made. The first call determines the new value of n, and the second call which uses this new value along with the new value of m (a simple decrement).

  | ackermann (m, n) if (m > 0 andalso n > 0) = ackermann (m-1, ackermann (m, n-1))

Finally, we add a final case to our pattern matching to catch all other cases. This is done for two reasons. First, Ackermann's function is only defined for non-negative integers. While that may be fine in math, when it comes to programming, one should be aware that invalid inputs may be used. These cases should be caught and handled. Here we raise a Domain exception that can be handled by the caller of ackermann. Secondly, when using guards in pattern matching, Alice ML will determine that not all possible cases are covered, and it issues a warning. Using the universal match pattern, _, we can catch any cases not covered by the above patterns (in this case anything involving negative integers).

  | ackermann _ = raise Domain

Execution result

In this section we show the output of a few applications of ackermann:

- ackermann (0, 0);
val it : int = 1
- ackermann (1, 1);
val it : int = 3
- ackermann (2, 13);
val it : int = 29
- ackermann (3, 1);
val it : int = 13
- ackermann (3, 7);
val it : int = 1021
- ackermann (3, 9);
val it : int = 4093
- ackermann (~1, 9);
Uncaught exception
   Domain

Note, however, that due to the tremendous growth rate of Ackermann's function, the number of recursive calls to ackermann quickly becomes too much to handle, even for relatively small values of m and n.

Precomputed for small m

It is possible to prove the following useful formulas for small values of the input m:

A(0,n) = n + 1
A(1,n) = n + 2
A(2,n) = 2n + 3
A(3,n) = 2^{n + 3} − 3

Using these, we can drastically reduce runtime not only for these inputs, but for larger inputs which make recursive calls with these inputs. We perform the exponentiation using a power function that takes integers for arguments (the standard Math.pow function is real*real->real):

<<ackermann.aml>>=
fun int_pow (base, exponent) =
   let
      fun iter_pow (i, 0, sum) = sum
        | iter_pow (i, n, sum) if (n > 0) = iter_pow(i, n-1, i*sum)
        | iter_pow _ = raise Domain
   in
      iter_pow(base, exponent, 1)
   end

fun fast_ackermann (0, n) = n + 1
  | fast_ackermann (1, n) if (n > 0) = n + 2
  | fast_ackermann (2, n) if (n > 0) = 2*n + 3
  | fast_ackermann (3, n) if (n > 0) = int_pow(2, n+3) - 3
  | fast_ackermann (m, 0) if (m > 0) = fast_ackermann(m-1, 1)
  | fast_ackermann (m, n) if (m > 0 andalso n > 0) =
      fast_ackermann(m-1, fast_ackermann(m, n-1))
  | fast_ackermann _ = raise Domain

The fast_ackermann function allows us to rapidly compute some larger results.

- fast_ackermann (3, 26);
val it : int = 536870909
- fast_ackermann (4, 1);
val it : int = 65533
- fast_ackermann (3, 27);
Uncaught exception
   Overflow
- fast_ackermann (4, 2);
Uncaught exception
   Overflow

Unlimited Integer Sizes

The standard size of an integer in Alice ML is restricted to 31 bits (Int.minInt = ~1073741824 to Int.maxInt =1073741823). In order to handle numbers outside of this range, the type for the numbers should be changed to IntInf. Since Alice ML doesn't currently support IntInf constants, we'll declare some values to hold 0, 1, 2, and 3.

<<ackermann.aml>>=
val inf_0 = IntInf.fromInt 0
val inf_1 = IntInf.fromInt 1
val inf_2 = IntInf.fromInt 2
val inf_3 = IntInf.fromInt 3

fun inf_pow (base, exponent) =
   let
      fun iter_pow (i, n, sum) if (n = inf_0) = sum : IntInf.t
        | iter_pow (i, n, sum) if (n > inf_0) = iter_pow(i, n - inf_1, i*sum)
        | iter_pow _ = raise Domain
   in
      iter_pow(base, exponent, inf_1)
   end

fun inf_ackermann (m, n) if (m = inf_0) =
      n + inf_1
  | inf_ackermann (m, n) if (m = inf_1 andalso n > inf_0) =
      n + inf_2
  | inf_ackermann (m, n) if (m = inf_2 andalso n > inf_0) =
      (inf_2 * n) + inf_3
  | inf_ackermann (m, n) if (m = inf_3 andalso n > inf_0) =
      inf_pow(inf_2, n + inf_3) - inf_3
  | inf_ackermann (m, n) if (m > inf_0 andalso n = inf_0) =
      inf_ackermann(m - inf_1, inf_1)
  | inf_ackermann (m, n) if (m > inf_0 andalso n > inf_0) =
      inf_ackermann(m - inf_1, inf_ackermann(m, n - inf_1))
  | inf_ackermann _ = raise Domain

The inf_ackermann allows us to compute results with a large number of digits:

- inf_ackermann (IntInf.fromInt 3, IntInf.fromInt 65536);
val it : IntInf.int =
1602.....3885 (* total 19730 digits *)
- inf_ackermann (IntInf.fromInt 4, IntInf.fromInt 2);
val it : IntInf.int =
2003.....6733 (* total 19729 digits *)

Download code