next up previous contents
Next: XSB tabled execution as Up: Programming in Tabled Prolog Previous: Summary

Tabling and Datalog Programming

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) :-
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:

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]

| ?- avoids(andy,Y).

Y = bill;

Y = carl;

| ?-

next up previous contents
Next: XSB tabled execution as Up: Programming in Tabled Prolog Previous: Summary
David S. Warren