In the previous chapter we saw several limitations of Prolog. When we considered grammars in Prolog, we found that the parser provided by Prolog ``for free'' is a recursive descent parser and not one of the better ones that we'd really like to have. When looking at deductive databases, we found that some perfectly reasonable programs go into an infinite loop, for example transitive closure on a cyclic graph. We had to go to some lengths to program around these limitations, and even then the results were not completely satisfying.
XSB implements a feature not (yet) found in any other Prolog system. It is the notion of tabling, also sometimes called memoization or lemmatization. The idea is very simple: never make the same procedure call twice: the first time a call is made, remember all the answers it returns, and if it's ever made again, use those previously computed answers to satisfy the later request. In XSB the programmer indicates what calls should be tabled by using a compiler directive, such as:
:- table np/2.
This example requests that all calls to the procedure np that
has two arguments should be tabled. Predicates that have such
declarations in a given program are called tabled predicates.
A simple example of a use of tabling is in the case of a definition of
transitive closure in a graph. Assume that we have a set of facts
that define a predicate owes. The fact owes(andy,bill)
means that Andy owes Bill some money. Then we use owes to
define a predicate avoids as we did in the previous chapter. A
person avoids anyone he or she owes money to, as well as avoiding
anyone they avoid.
:- table avoids/2.
avoids(Source,Target) :- owes(Source,Target).
avoids(Source,Target) :-
owes(Source,Intermediate),
avoids(Intermediate,Target).
Here we are assuming that the edges of a directed graph are stored in
a predicate owes/2. The rules in this program are the same as
those used in Prolog to define ancestor. The difference is that in
XSB we can make the table declaration, and this declaration guarantees
that this predicate will be correctly computed, even if the graph in
owes/2 is cyclic. Intuitively it's clear that any call
to avoids will terminate because there are only finitely
many possible calls for any finite graph, and since tabling guarantees
that no call is ever evaluated more than once, eventually all the
necessary calls will be made and the computation will terminate. The
problem with Prolog was that in a cyclic graph the same call was made
and evaluated infinitely many times.
Indeed, executing this program on the graph:
owes(andy,bill). owes(bill,carl). owes(carl,bill).for the query
avoids(andy,X), which we saw go into an infinite
loop without the table declaration, yields the following under XSB:
warren% xsb XSB Version 1.4.2 (95/4/6) [sequential, single word, optimal mode] | ?- [graph]. [Compiling ./graph] [graph compiled, cpu time used: 0.589 seconds] [graph loaded] yes | ?- avoids(andy,Y). Y = bill; Y = carl; no | ?-