A system supporting both variant- and subsumption-based tabled evaluations of logic programs

Tabled resolution methods increase the declarativeness and efficiency of logic programs by reusing previously computed answers to satisfy new subgoal occurrences. Under variant-based tabling, answers are shared only between subgoals that can be made identical through variable renaming. A more complex tabling strategy based on subsumption has the potential to yield superior performance by additionally sharing answers with more specific subgoals. However, realizing this potential in practice requires the ability to efficiently index into dynamically expanding answer sets.; We begin with the presentation of an efficient subsumption-based tabling technique characterized by the use of a novel data structure, which we call the Time-Stamped Trie, for representing tabled answer sets and a distinctive approach to the access mechanisms supporting answer resolution. The latter can be characterized by a set-at-a-time relevant answer identification process together with a tuple-at-a-time selection function. Both experimental and theoretical results are presented which show this technique to be superior to the previous subsumptive tabling method in both time and space. Most importantly, the maximum table space utilized by our approach during an evaluation is only twice that required by a variant-based evaluation, whose space efficiency has previously been demonstrated.; The practicality of this technique merited its incorporation into the publicly-available variant-based XSB tabled logic programming system. Integration into this system is facilitated through the development of a new table interface engine and the tables. Because of its generality, we believe this architecture can serve as the basis for supporting engine-table interaction in most any tabled logic programming system. Implementation of the TST-based tabling subsystem as well as application of the interface architecture are discussed at length. The resulting XSB system provides users with the ability to choose a tabling strategy on a per predicate basis and can perform evaluations involving either or both types of tabled subgoals within a single computation. Additional modifications are detailed which permit evaluations of normal logic programs in which subsumptive subgoals are not part of negative dependency cycles. Further, we introduce a new technique, called eager evaluation, which potentially simplifies dependencies on these subgoals thereby avoiding the creation of negative cycles in certain instances.