Recently, the iterative approach named linear tabling has received considerable attention because of its simplicity, ease of implementation, and good space efficiency. Linear tabling is a framework from which different methods can be derived based on the strategies used in handling looping subgoals. One decision concerns when answers are consumed and returned. This paper describes two strategies, namely, lazy and eager strategies, and compares them both qualitatively and quantitatively. The results indicate that, while the lazy strategy has good locality and is well suited for finding all solutions, the eager strategy is comparable in speed with the lazy strategy and is well suited for programs with cuts. Linear tabling relies on depth-first iterative deepening rather than suspension to compute fixpoints. Each cluster of inter-dependent subgoals as represented by a top-most looping subgoal is iteratively evaluated until no subgoal in it can produce any new answers. Naive re-evaluation of all looping subgoals, albeit simple, may be computationally unacceptable. In this paper, we also introduce semi-naive optimization, an effective technique employed in bottom-up evaluation of logic programs to avoid redundant joins of answers, into linear tabling. We give the conditions for the technique to be safe (i.e. sound and complete) and propose an optimization technique called early answer promotion to enhance its effectiveness. Benchmarking in B-Prolog demonstrates that with this optimization linear tabling compares favorably well in speed with the state-of-the-art implementation of SLG.
Semi-naive optimization does not solve all the problems of recomputation in linear tabling. Recall the Warren's example: Assume there is a very costly non-tabled subgoal preceding p(X,Z) , then the subgoal has to be executed in each iteration even with semi-naive optimization. This example demonstrates the acuteness of the problem of recomputation because the number of iterations needed to reach the fixpoint is not constant. One treatment would be to table the subgoal to avoid recomputation, as suggested in @cite_15 , but tabling extra predicates can cause other problems such as over consumption of table space.
@cite_15
2155945137
Tabled logic programming (LP) systems have been applied to elegantly and quickly solving very complex problems (e.g., model checking). However, techniquescurren tly employed for incorporating tabling in an existing LP system are quite complex and require considerable change to the LP system. We present a simple technique for incorporating tabling in existing LP systems based on dynamically reordering clauses containing variant callsat run-time. Our simple technique allows tabled evaluation to be performed with a single SLD tree and without the use of complex operations such as freezing of stacks and heap. It can be incorporated in an existing logic programming system with a small amount of effort. Our scheme also facilitates exploitation of parallelism from tabled LP systems. Results of incorporating our scheme in the commercial ALS Prolog system are reported.