Ackermann function (OCaml)

From LiteratePrograms

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

This page explains how to implement the Ackermann function in OCaml. For this example, we will be using OCaml's "function" syntax for defining functions. We choose this style as it most closely resembles the problem definition.

Source code

We begin the code by defining a recursive value named ackermann and indicate that this value will be a function

<<ackermann.ml>>=
let rec ackermann = function

First, we add a case to catch the cases when either argument is negative, because the Ackermann 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 an exception with an informative message that can be handled by the caller of ackermann.

<<ackermann.ml>>=
| m,n when m < 0 || n < 0 -> invalid_arg "Ackermann's function is only defined over the non-negative integers"

We then use pattern matching on the function's parameter to handle the three cases given in the definition of the Ackermann function. The first case we handle is the base case of the recursion, when m = 0. Note that because of the way we are doing the pattern matching, our function takes a single tuple as input.

<<ackermann.ml>>=
| 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.ml>>=  
| 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.ml>>=  
| m,n -> ackermann (m-1,ackermann (m,n-1))

Execution result

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

# ackermann (0,0);;
- : int = 1
# ackermann (1,1);;
- : int = 3
# ackermann (2,13);;
- : int = 29
# ackermann (3,1);;
- : int = 13
# ackermann (3,7);;
- : int = 1021
# ackermann (3,9);;
- : int = 4093
# ackermann (-1,9);;
Exception:
Invalid_argument
 "Ackermann's function is only defined over the non-negative integers".

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.

# ackermann (4,1);;
Stack overflow during evaluation (looping recursion?).

We can resolve this problem in the usual way in OCaml which is to rewrite the code in a tail-recursive way:

let rec find_option h v =
  try Some(Hashtbl.find h v)
  with Not_found -> None
let rec a bounds caller todo m n =
  match m, n with
  | 0, n ->
      let r = (n+1) in
      ( match todo with
        | [] -> r
        | (m,n)::todo ->
            List.iter (fun k ->
              if not(Hashtbl.mem bounds k)
              then Hashtbl.add bounds k r) caller;
            a bounds [] todo m n )
  | m, 0 ->
      a bounds caller todo (m-1) 1
  | m, n ->
      match find_option bounds (m, n-1) with
      | Some a_rec ->
          let caller = (m,n)::caller in
          a bounds caller todo (m-1) a_rec
      | None ->
          let todo = (m,n)::todo
          and caller = [(m, n-1)] in
          a bounds caller todo m (n-1)
let a = a (Hashtbl.create 42 (* arbitrary *) ) [] [] ;;

This one uses the arbitrary precision, the tail-recursion, and the optimisation explain on the Wikipedia page about (m,n) = (3,_).

open Big_int
let one  = unit_big_int
let zero = zero_big_int
let succ = succ_big_int
let pred = pred_big_int
let add = add_big_int
let sub = sub_big_int
let eq = eq_big_int
let three = succ(succ one)
let power = power_int_positive_big_int
let eq2 (a1,a2) (b1,b2) =
  (eq a1 b1) && (eq a2 b2)
module H = Hashtbl.Make
  (struct
     type t = Big_int.big_int * Big_int.big_int
     let equal = eq2
     let hash (x,y) = Hashtbl.hash
       (Big_int.string_of_big_int x ^ "," ^
          Big_int.string_of_big_int y)
       (* probably not a very good hash function *)
   end)
let rec find_option h v =
  try Some (H.find h v)
  with Not_found -> None
let rec a bounds caller todo m n =
  let may_tail r =
    let k = (m,n) in
    match todo with
    | [] -> r
    | (m,n)::todo ->
        List.iter (fun k ->
                     if not (H.mem bounds k)
                     then H.add bounds k r) (k::caller);
        a bounds [] todo m n
  in
  match m, n with
  | m, n when eq m zero ->
      let r = (succ n) in
      may_tail r
  | m, n when eq n zero ->
      let caller = (m,n)::caller in
      a bounds caller todo (pred m) one
  | m, n when eq m three ->
      let r = sub (power 2 (add n three)) three in
      may_tail r
  | m, n ->
      match find_option bounds (m, pred n) with
      | Some a_rec ->
          let caller = (m,n)::caller in
          a bounds caller todo (pred m) a_rec
      | None ->
          let todo = (m,n)::todo in
          let caller = [(m, pred n)] in
          a bounds caller todo m (pred n)
let a = a (H.create 42 (* arbitrary *)) [] [] ;;

We can use this last version this way:

let () =
  let m, n =
    try
      big_int_of_string Sys.argv.(1),
      big_int_of_string Sys.argv.(2)
    with _ ->
      Printf.eprintf "usage: %s <int> <int>\n" Sys.argv.(0);
      exit 1
  in
  let r = a m n in
  Printf.printf "(a %s %s) = %s\n"
      (string_of_big_int m)
      (string_of_big_int n)
      (string_of_big_int r);
;;

compile with:

ocamlopt -o acker nums.cmxa acker.ml