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
npthat 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
means that Andy owes Bill some money. Then we use
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/2is cyclic. Intuitively it's clear that any call to
avoidswill 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 | ?-