Ackermann function (Prolog)
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 Prolog. In Prolog, functions are defined as relations while both the arguments and the result are given to the relation as parameters. In this article, ackermann(M, N, A) denotes that 'A is the value of .'
Source code
The source code is composed of three cases explained above.
1. if m = 0
<<ackermann.pl>>= ackermann(0, N, A) :- A is N + 1.
Note that the is operator assigns the arithmetic operation to the variable.
2. if m > 0 and n = 0
<<ackermann.pl>>= ackermann(M, 0, A) :- M > 0, M1 is M - 1, ackermann(M1, 1, A).
3. if m > 0 and n > 0
<<ackermann.pl>>= ackermann(M, N, A) :- M > 0, N > 0, M1 is M - 1, N1 is N - 1, ackermann(M, N1, Temp), ackermann(M1, Temp, A).
This case is a little tricky. As logic programming languages do not support functional composition, we have to employ a temporary variable Temp for .
Tricky version
In this version we use the ! (the cut operator) to avoid unnecessary backtracking. Also
the try_asserta/1 predicate is an effort to save intermediate results thus using them when needed,
some useless comparisons checks are removed too.
tricky_ackermann.pl
:- dynamic acr/3.
try_asserta(F) :- % if we already have the result do nothing
F,
!.
try_asserta(F) :- % if we do not have the result store it
!,
asserta(F).
ackermann(M, N, A) :- % use precomputed result if that exists
acr(M, N, A),
!.
ackermann(0, N, A) :- % special case
!,
A is N + 1,
try_asserta(acr(0, N, A)).
ackermann(M, 0, A) :- % special case
!,
M1 is M - 1,
ackermann(M1, 1, A),
try_asserta(acr(M, 0, A)),
try_asserta(acr(M1, 1, A)).
ackermann(M, N, A) :- % main recursions
!,
M1 is M - 1,
N1 is N - 1,
ackermann(M, N1, Temp),
try_asserta(acr(M, N1, Temp)),
ackermann(M1, Temp, A),
try_asserta(acr(M, N, A)),
try_asserta(acr(M1, Temp, A)).
Execution result
This section contains a number of execution results of the Ackermann function implementation in Prolog.
crypto@crypto ~/gcd_prolog $ prolog Welcome to SWI-Prolog (Multi-threaded, Version 5.2.6) Copyright (c) 1990-2003 University of Amsterdam. SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- ['ackermann.pl']. % ackermann.pl compiled 0.00 sec, 1,112 bytes Yes ?- ackermann(0, 0, A). A = 1 Yes ?- ackermann(1, 6, A). A = 8 Yes ?- ackermann(2, 3, A). A = 9 Yes ?- ackermann(3, 3, A). A = 61 Yes ?- ackermann(4, 3, A). ERROR: Out of local stack ?-