Tabling in Definite Programs

Definite programs, also called Horn Clause Programs, are those programs without negation -- In XSB, this means without the \+/1, fail_if/1, not/1 or tnot/1 operators. Consider the Prolog program

path(X,Y) :- path(X,Z), edge(Z,Y).
path(X,Y) :- edge(X,Y).

together with the query ?- path(1,Y). This program has a simple, declarative meaning: there is a path from X to Y if there is a path from X to some node Z and there is a path from Z to Y, or if there is a direct path from X to Y. Prolog, however enters into an infinite loop when computing an answer to this query. The inability of Prolog to answer such queries, which arise frequently, comprises one of its major limitations as an implementation of logic.

A number of approaches have been developed to address this problem by reusing partial answers to the query path(1,Y) [17,43,3,45,46]. The ideas behind these algorithms can be described in the following manner. First, the implementation keeps track of all calls to tabled predicates, (or tabled subgoals such as path(1,Y) in the above example. Whenever a new tabled subgoal $S$ is called, a check is first made to see whether $S$ is in the table. If so, $S$ is resolved against answers in the table; if not $S$ is entered into the table and the subgoal is resolved against program clauses, as in Prolog. Answers are handled in the same way. When an answer to a tabled subgoal $S$ is derived a check is made against the table for $S$ to see if the answer is there. If the answer isn't in the table for $S$, the answer is added and scheduled to be returned to all instances where $S$ has been called; if the answer is already in the table, the evaluation simply fails and backtracks to generate more answers.

Predicates can be declared tabled in a variety of ways. A common form is the compiler directive

$${\tt\mbox{:-} table\ } p_1/n_1, \ldots, p_k/n_k.$$

where $p_i$ is a predicate symbol and $n_i$ is an integer representing the arity of $p_i$. This directive can be added to the file containing the predicate to be tabled and then to compile the file.

Exercise 5.2.1   Unless otherwise noted, the file table_examples.P in the directory $XSB_DIR/examples contains all code for the running examples in this section. Consult the file into XSB and type the query

         ?- path(1,Y).

and continue hitting semi-colons until you have exhausted all answers. Type the query again. Can you guess why the order of answers is different? Now type

         ?- abolish_all_tables.

and retry the path query.

Exercise 5.2.2   If you are curious, try rewriting the path query as it would be written in Prolog. Will it now terminate for the provided edge/2 relation? (Remember, in XSB you can always hit <ctrl>-C if you go into an infinite loop).

The return of answers in tabling aids in filtering out redundant computations - indeed it is this property which makes tabling terminate for many classes of programs. The same generation program furnishes a case of the usefulness of tabling for optimizing a Prolog program.

Exercise 5.2.3   If you are still curious, load in the file cyl.P in the $XSB_DIR/examples directory using the command.

         ?- load_dync(cyl.P).

and then type the query

         ?- same_generation(X,X),fail.

Now rewrite the same_generation/2 program so that it does not use tabling and retry the same query what happens? (Be patient -- or use <ctrl>-C).

The examples stress two differences between tabling and SLD resolution beyond termination properties. First, that each solution to tabled subgoal is returned only once -- a property that is helpful not only for path/2 but also for same_generation/2 which terminates in Prolog. Second, because answers are sometimes obtained using program clauses and sometimes using answers, answers may be returned in an unaccustomed order.

In the language of tabling, the first instance of a tabled subgoal $S$ is called a $generator$ subgoal, and is expanded using program clauses as in SLD resolution (Prolog). Subsequent instances of $S$ are referred to as $consuming$ subgoals and are expanded using answers in the table for $S$ instead of program clauses. Because $consuming$ subgoals resolve against unique answers rather than repeatedly against program clauses, tabling will terminate whenever (1) a finite number of subgoals are encountered in query evaluation, (2) each of these subgoals have a finite number of answers. Indeed, it can be proven that for any program with the bounded term depth property (roughly, where all terms generated in a program have a maximum depth), SLG computation will terminate. These programs include the important class of Datalog programs.