<div class="notebook">
<div class="nb-cell markdown">
# Using tabling (SLG resolution)
This notebook illustrates SWI-Prolog tabling, implementing the examples from the
[manual page](http://www.swi-prolog.org/pldoc/man?section=tabling). Please consult this page for additional background information.
## Computing Fibonacci numbers
The nth-Fibonacci number is the sum of the two preceding ones, where the Fibonacci number of 0 and 1 are both 1.
### First, the simple way
The most natural definition for the N-th Fibonacci number in Prolog is below. Unfortunately, the _complexity_ of this is O(2^N), making it only suitable for the few Fibonacci numbers.
</div>
<div class="nb-cell program">
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.
</div>
<div class="nb-cell query">
time(fib(30, Fib)).
</div>
<div class="nb-cell markdown">
### Now using tabling
By simply adding a table/1 directive, repetitive computation of lower numbers is avoided. Note that this effectively also inverts the order of computation, were we
compute low Fibonacci first.
</div>
<div class="nb-cell program">
:- 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.
</div>
<div class="nb-cell query">
time(fib(30, Fib)).
</div>
<div class="nb-cell query">
time(fib(1000, Fib)).
</div>
<div class="nb-cell markdown">
## Computing connections in a graph
Tabling also avoids non-termination of the computation due to _left recursion_, i.e., a goal calling (possibly indirectly) a copy of itself. Finally, tabling avoids producing the same results twice by ignoring any (intermediate) result that is already in its tables. This means that, for example, connections in a railway network can be evaluated without _stratification_ and _cycle detection_ being added by the user. Here is an example.
</div>
<div class="nb-cell program">
:- table connection/2.
connection(X, Y) :-
connection(X, Z),
connection(Z, Y).
connection(X, Y) :-
connection(Y, X).
connection('Amsterdam', 'Schiphol').
connection('Amsterdam', 'Haarlem').
connection('Schiphol', 'Leiden').
connection('Haarlem', 'Leiden').
</div>
<div class="nb-cell query" data-tabled="true">
connection('Amsterdam', X).
</div>
<div class="nb-cell markdown">
### About Tabling in SWI-Prolog
Tabling in SWI-Prolog is based on _delimited continuations_. The initiative to this
comes from Tom Schrijvers, Benoit Desouter and Bart Demoen. See
- [Tabling as a library with delimited control](http://dx.doi.org/10.1017/S1471068415000137)
- [Delimited continuations for prolog](http://dx.doi.org/10.1017/S1471068413000331)
</div>
</div>