|Did you know ...||Search Documentation:|
|Example 2: avoiding non-termination|
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
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
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.