5.2 Definite Programs

Definite programs, also called Horn Clause Programs, are Prolog programs without negation or aggregation. In XSB, this means without the \+/1, fail_if/1, not/1, tnot/1 or aggregation 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 an edge from Z to Y, or if there is an edge 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) [24,56,4,58,59]. The ideas behind these algorithms can be described in the following manner. Calls to tabled predicates, such as path(1,Y) in the above example, are stored in a searchable structure together with their proven instances. This collection of tabled subgoals paired with their answers, generally referred to as a table, is consulted whenever a new call, $C$, to a tabled predicate is issued. If $C$ is sufficiently similar to a tabled subgoal $S$, then the set of answers, ${\cal A}$, associated with $S$ may be used to satisfy $C$. In such instances, $C$ is resolved against the answers in ${\cal A}$, and hence we refer to $C$ as a consumer of ${\cal A}$ (or $S$). If there is no such $S$, then $C$ is entered into the table and is resolved against program clauses as in Prolog -- i.e., using SLD resolution. As each answer is derived during this process, it is inserted into the table entry associated with $C$ if it contains information not already in ${\cal A}$. We hence refer to $C$ as a generator, or producer, as resolution of $C$ in this manner produces the answers stored in its table entry. If the answer is in fact added to this set, then it is additionally scheduled to be returned to all consumers of $C$. If instead it is rejected as redundant, then the evaluation simply fails and backtracks to generate more answers.

Notice that since consuming subgoals resolve against unique answers rather than repeatedly against program clauses, tabling will terminate whenever

1. a finite number of subgoals are encountered during query evaluation, and
2. each of these subgoals has 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.

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

$$\verb\vert:- table \vert 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$. For static predicates, this is directive added to a file containing the predicate(s) to be tabled, compiles them to use tabling. For dynamic predicates, the executable directive

$$\verb\vert ?- table \vert p/n.$$

causes p/n to be tabled if no clauses have been asserted for p/n.