Ackermann function (OCaml)
From LiteratePrograms
The Ackermann function or Ackermann-Péter function is defined recursively for non-negative integers m and n as follows:
- 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}"/>
In the theory of computation, the Ackermann function is a simple example of a recursive function that is not primitively recursive. Note that this function grows very quickly -- even A(4, 3)
cannot be feasibly computed on ordinary computers.
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