Linear tabling and the strategies

B-Prolog employs a tabling mechanism, called linear tabling [21], which relies on iterative computation, rather than suspension, in order to compute fixpoints. In linear tabling, a cluster of inter-dependent subgoals, as represented by a top-most looping subgoal, is iteratively evaluated until no subgoal in the cluster can produce any new answers.

B-Prolog supports the lazy strategy, which only allows a cluster of subgoals to return answers after the fixpoint has been reached. The lazy consumption strategy is suited for finding all answers, due to the locality of the search. For example, when the subgoal p(Y) is encountered in the goal ``p(X),p(Y)'', the subtree for p(X) must have been completely explored. For certain applications, such as planning, it is unreasonable to find all of the answers, because either the set is infinite, or only one answer is needed. For example, for the goal ``p(X),!,q(X)'', the lazy strategy produces all of the answers for p(X), even though only one is needed; therefore, table modes should be used in order to let p(X) generate the required number of answers.

Neng-Fa Zhou 2013-01-25