As a first classical example we use tabling for memoizing
intermediate results. We use Fibonacci numbers to illustrate the
approach. The Fibonacci number I is defined as the sum of the
Fibonacci numbers for I-1 and I-2, while the
Fibonacci number of 0 and 1 are both defined to be 1. This can be
translated naturally into Prolog:
fib(0, 1) :- !.
fib(1, 1) :- !.
fib(N, F) :-
N > 1,
N1 is N-1,
N2 is N-2,
fib(N1, F1),
fib(N2, F2),
F is F1+F2.
The complexity of executing this using SLD resolution however is 2^N
and thus becomes prohibitively slow rather quickly, e.g., the execution
time for N=30 is already 0.4 seconds. Using tabling, fib(N,F)
for each value of N is computed only once and the algorithm
becomes linear. Tabling effectively inverts the execution order for this
case: it suspends the final addition (F is F1+F2) until the two
preceding Fibonacci numbers have been added to the answer tables. Thus,
we can reduce the complexity from the show-stopping 2^N to
linear by adding a tabling directive and otherwise not changing the
algorithm. The code becomes:
:- table fib/2.
fib(0, 1) :- !.
fib(1, 1) :- !.
fib(N, F) :-
N > 1,
N1 is N-1,
N2 is N-2,
fib(N1, F1),
fib(N2, F2),
F is F1+F2.
The price that we pay is that a table fib(I,F) is
created for each I in 0..N. The execution time for N=30
is now 1 millisecond and computing the Fibonacci number for N=1000
is doable (output edited for readability).
1 ?- time(fib(1000, X)).
% 52,991 inferences, 0.013 CPU in 0.013 seconds
X = 70330367711422815821835254877183549770181269836358
73274260490508715453711819693357974224949456261173
34877504492417659910881863632654502236471060120533
74121273867339111198139373125598767690091902245245
323403501.
In the case of Fibonacci numbers we can still rather easily achieve
linear complexity using program transformation, where we use bottom-up
instead of top-down evaluation, i.e., we compute fib(N,F)
for growing N, where we pass the last two Fibonacci numbers
to the next iteration. Not having to create the tables and not having to
suspend and resume goals makes this implementation about 25 times faster
than the tabled one. However, even in this simple case the
transformation is not obvious and it is far more difficult to recognise
the algorithm as an implementation of Fibonacci numbers.
fib(0, 1) :- !.
fib(1, 1) :- !.
fib(N, F) :-
fib(1,1,1,N,F).
fib(_F, F1, N, N, F1) :- !.
fib(F0, F1, I, N, F) :-
F2 is F0+F1,
I2 is I + 1,
fib(F1, F2, I2, N, F).
0 
