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).
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 is called, a check is first made to see whether is in the table. If so, is resolved against answers in the table; if not 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 is derived a check is made against the table for to see if the answer is there. If the answer isn't in the table for , the answer is added and scheduled to be returned to all instances where 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
$XSB_DIR/examplescontains 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.
<ctrl>-Cif 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.
$XSB_DIR/examplesdirectory 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
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.