Tabling

The need to extend Prolog to narrow the gap between declarative and procedural reading of programs has been urged long before. Tabling in Prolog is a technique that can get rid of infinite loops for execution of Prolog programs. With tabling, Prolog becomes more friendly to beginners, and even for professional programmers, tabling can alleviate their burden to cure infinite loops and redundant computations. Consider the following example:

       reach(X,Y):-edge(X,Y).
       reach(X,Y):-reach(X,Z),edge(Z,Y).

where the predicate edge defines a relation and reach defines the transitive closure of the relation. Without tabling, a query like reach(X,Y) would fall into an infinite loop. Consider another example:

       fib(0, 1).
       fib(1, 1).
       fib(N,F):-
          N1 is N-1, 
          N2 is N-2,
          fib(N1,F1),
          fib(N2,F2),
          F is F1+F2.

A query fib(N,X), where N is an integer, will not fall into an infinite loop, but will spawn $2^N$ calls, many of which are variants.

The main idea of tabling is to memorize the answers to some calls, called tabled calls, and use the answers to resolve subsequent variant calls. In B-Prolog, tabled predicates are declared explicitly by declarations in the following form:

		 		  :-table $p_1/n_1$, $\ldots$, $p_k/n_k$ 

where each $p_i$(i=1,$\ldots$,k) is a predicate symbol and $n_i$ is an integer that denotes the arity of $p_i$.

A tabled call is resolved as follows: When there are answers available in the table for the call, the call consumes the answers one by one; otherwise, if the call appears the first time, i.e., there is no former variant call, then the call, like a usual Prolog call, produces answers by using the clauses; If the call is a variant of some former call, then the call steals the choice point from the former call and turns to produce answers by using the remaining clauses that have not yet been tried by the former call. After the call produces an answer, it also consumes one. Answers in the table are used in a first-generated-first-used fashion. Backtracking is strictly chronological and cut is allowed anywhere. A failure occurs when a call have exhausted all the answers in its table and cannot produce any new answers by using the clauses.

A data area, called table area, is used to store tabled calls and their answers. The following predicate initializes the table area.

       initialize_table

The table area is initialized automatically in the beginning and after each top-level query. The amount of memory allocated to the table area is 20000 words. See the Chapter on Memory Management about how to change this amount.

Tabled calls are stored in a hash table, called subgoal table, and for each tabled call and its variants, a hash table, called answer table, is used to store the answers for the call. The bucket size for the subgoal table is 331 and that for answer tables is 31. To change these values, use the following built-in predicate:

       table_bucket_sizes(SubgoalTableSize,AnswerTableSize)

where SubgoalTableSize and AnswerTableSize are new sizes for the subgoal table and answer tables, respectively.