Tabling

The need to extend Prolog to narrow the gap between declarative and procedural readings of programs has been urged long before. Tabling in Prolog is a technique that can get rid of infinite loops for bounded-term-size programs and possible redundant computations in the execution of Prolog programs [10,14]. With tabling, Prolog becomes more friendly to beginners and professional programmers alike. 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):-N>1,
          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 P1/N1,...,Pk/Nk

where each Pi (i=1,...,k) is a predicate symbol and Ni is an integer that denotes the arity of Pi. To declare all the predicates in a Program as tabled, add the following line to the beginning of the program:

      :-table_all.