SLD resolution easily results in an infinite loop due to left
recursion, a goal that (indirectly) calls a variant of itself or
cycles in the input data. Thus, if we have a series of connection/2
statements that define railway connections between two cities, we cannot
use the most natural logical definition to express that we can travel
between two cities:
% :- 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').
After enabling tabling however, the above works just fine as
illustrated in the session below. Where is the magic and what is the
price we paid? The magic is, again, the fact that new goals to the
tabled predicate suspend. So, all recursive goals are suspended.
Eventually, a table for connection(’Amsterdam’, X)
is created with the two direct connections from Amsterdam. Now, it
resumes the first clause using the tabled solutions, continuing the last
connection/2 subgoal with connection(’Schiphol’, X)
and connection(’Haarlem’, X). These two go
through the same process, creating new suspended recursive calls and
creating tables for the connections from Schiphol and Haarlem.
Eventually, we end up with a set of tables for each call variant that is
involved in computing the transitive closure of the network starting in
Amsterdam. However, if the Japanese rail network would have been in our
data as well, we would not have produced tables for that.
1 ?- connection('Amsterdam', X).
X = 'Haarlem' ;
X = 'Schiphol' ;
X = 'Amsterdam' ;
X = 'Leiden'.
Again, the fact that a simple table/1
directive turns the pure logical specification into a fairly efficient
algorithm is a clear advantage. Without tabling the program needs to be stratified,
introducing a base layer with the raw connections, a second layer that
introduces the commutative property of a railway (if you can
travel from
A to B you can also travel from B to A
and a final layer that realises transitivity (if you can travel
from A to B and from B to C
you can also travel from A to C). The third and
final layer must keep track which cities you have already visited to
avoid traveling in circles. The transformed program however uses little
memory (the list of already visited cities and the still open choices)
and does not need to deal with maintaining consistency between the
tables and ground facts.
0 
