Next: Variant and Subsumptive Tabling Up: Using Tabling in XSB: Previous: XSB as a Prolog   Contents   Index

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.

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

where is a predicate symbol and is an integer representing the arity of . 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.


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 is called a subgoal, and is expanded using program clauses as in SLD resolution (Prolog). Subsequent instances of are referred to as subgoals and are expanded using answers in the table for instead of program clauses. Because 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.

Subsections

Next: Variant and Subsumptive Tabling Up: Using Tabling in XSB: Previous: XSB as a Prolog   Contents   Index
Baoqiu Cui
2000-04-23