Tabling

For years, there has been a need to extend Prolog in order to narrow the gap between the declarative and procedural readings of programs. Tabling is a technique that can get rid of infinite loops for bounded-term-size programs. It can also eliminate redundant computations in the execution of Prolog programs [11,15]. With tabling, Prolog becomes more friendly to beginners and professional programmers alike. Tabling can alleviate their burden by curing 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. However, it will spawn 2^N calls, many of which are variants.

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

      :-table P1/N1,...,Pk/Nk

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

      :-table_all.