|Did you know ...||Search Documentation:|
|library(tabling): Tabled execution (SLG)|
provides support for Tabled execution of one or more Prolog
predicates, also called SLG resolution. Tabling a predicate
provides two properties:
Tabling is particularly suited to simplify inference over a highly entangled set of predicates that express axioms and rules in a static (not changing) world. When using SLD resolution for such problems, it is hard to ensure termination and avoid frequent recomputation of intermediate results. A solution is to use Datalog style bottom-up evaluation, i.e., applying rules on the axioms and derived facts until a fixed point is reached. However, bottom-up evaluation typically derives many facts that are never used. Tabling provides a goal oriented resolution strategy for such problems and is enabled simply by adding a table/1 directive to the program.
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,
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
preceeding 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:
:- use_module(library(tabling)). :- 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
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
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).
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:
% :- use_module(library(tabling)). % :- 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.
Tabling as defined above has a serious limitation. Although the definition of connection/2 from section section A.35.2 can compute the transitive closure of connected cities, it cannot provide you with a route to travel. The reason is that there are infinitely many routes if there are cycles in the network and each new route found will be added to the answer table and cause the tabled execution's completion algorithm to search for more routes, eventually running out of memory.
The solution to this problem is called mode directed tabling
term answer subsumption is used by XSB and mode directed
tabling by YAP and B-Prolog. The idea is that some arguments are
considered `outputs', where multiple values for the same `input' are
combined. Possibly answer aggregation would have been a better
name. In this execution model one or more arguments are not
added to the table. Instead, we remember a single aggregated
value for these arguments. The example below is derived from
section A.35.2 and
returns the connection as a list of cities. This argument is defined as
a moded argument using the
mode is compatible to XSB Prolog. This causes the tabling
engine each time that it finds an new path to call shortest/3 and keep
the shortest route.
:- use_module(library(tabling)). :- table connection(_,_,lattice(shortest/3)). shortest(P1, P2, P):- length(P1, L1), length(P2, L2), ( L1 < L2 -> P = P1 ; P = P2 ). connection(X, Y, [X,Y]) :- connection(X, Y). connection(X, Y, P) :- connection(X, Z, P0), connection(Z, Y), append(P0, [Y], P).
The mode declation scheme is equivalent to XSB with partial
compatibility support for YAP and B-Prolog. The
mode is the most general mode. The YAP
mode is not yet supported. The list below describes the supported modes
and indicates the portability.
index(YAP) or a
(B-Prolog) declare that the argument is tabled normally.
call(PI, +Old, +Answer)succeeds. For example,
po('<'/2)accumulates the largest result. In SWI-Prolog the arity (2) may be omitted, resulting in
first(YAP) declare to keep the first answer for this argument.
last(YAP) declares to keep the last answer.
min(YAP) declares to keep the smallest answer according to the standard order of terms (see @</2). Note that in SWI-Prolog the standard order of terms orders numbers by value.
max(YAP) declares to keep the largest answer according to the standard order of terms (see @>/2). Note that in SWI-Prolog the standard order of terms orders numbers by value.
sum(YAP) declares to sum numeric answers.
:- table edge/2, statement//1.
In addition to using predicate indicators, a predicate can be declared for mode directed tabling using a term where each argument declares the intended mode. For example:
:- table connection(_,_,min).
Mode directed tabling is discussed in the general introduction section about tabling.
permission_error(abolish, table, all)if tabling is in progress.
The SWI-Prolog implementation uses Delimited continuations (see section 4.10 to realise suspension of variant calls. The initial version was written by Benoit Desouter and described in Desouter et al., 2015. We moved the main data structures required for tabling, the answer tables (see section 4.14.4) and the worklist to SWI-Prolog's C core. Mode directed tabling (section A.35.3) is based on a prototype implementation by Fabrizio Riguzzi.
The table/1 directive causes the creation of a wrapper calling the renamed original predicate. For example, the program in section A.35.2 is translated into the following program. We give this information to improve your understanding of the current tabling implementation. Future versions are likely to use a more low-level translation that is not based on wrappers.
connection(A, B) :- start_tabling(user:connection(A, B), 'connection tabled'(A, B)). 'connection tabled'(X, Y) :- connection(X, Z), connection(Z, Y). 'connection tabled'(X, Y) :- connection(Y, X). 'connection tabled'('Amsterdam', 'Schiphol'). 'connection tabled'('Amsterdam', 'Haarlem'). 'connection tabled'('Schiphol', 'Leiden'). 'connection tabled'('Haarlem', 'Leiden').
The current implementation is merely a first prototype. It needs several enhancements before we can consider it a serious competitor to Prolog systems with mature tabling such as XSB, YAP and B-Prolog. In particular,
The Fibonacci sample code is not correct, since the most general query
?- fib(X, Y). incorrectly succeeds with only a single solution, although there are infinitely many which are produced when using the predicate in different modes.
One correct solution is to throw instantiation errors if the query is more general than those that the system can handle correctly.