Call Subsumption Mechanisms for Tabled Logic Programs

Flávio Cruz

June 2010

---

Abstract

Tabling is a particularly successful resolution mechanism that overcomes some limitations of the SLD resolution method found in Prolog systems, namely, in dealing with recursion and redundant sub-computations. In tabling, first calls to tabled subgoals are evaluated through program resolution, while similar calls are evaluated by consuming answers stored in the table space by the corresponding similar subgoal. In general, we can distinguish between two main approaches to determine if a subgoal A is similar to a subgoal B: variant-based tabling and subsumption-based tabling. In variant-based tabling, A is similar to B if they are the same up to variable renaming. In subsumption-based tabling, A is similar to B when A is subsumed by B (or B subsumes A). This stems from a simple principle: if A is subsumed by B and SA and SB are the respective answer sets, then SA ⊆ SB . While subsumption-based tabling (or call subsumption) can yield superior time performance by allowing greater answer reuse, its efficient implementation is harder than variant-based tabling, which makes tabling engines with variant checks much more popular in the logic community.
This thesis first addresses the porting and integration of the Time Stamped Tries mechanism from the SLG-WAM tabling engine into the YapTab tabling engine. Our performance results show that our integration efforts were successful, with comparable speedups when using subsumptive-based tabling against variant-based tabling.
In the second part of this thesis we present the design, implementation, and evaluation of a novel extension based on subsumption-based tabling called Retroactive Call Subsumption (RCS). RCS overcomes some limitations of traditional call subsumption, namely, the fact that the call order of the subgoals can greatly affect its success and applicability. RCS allows full sharing of answers, independently of the order they are called by selectively pruning and restarting the evaluation of subsumed subgoals. Our results show considerable gains for programs that can take advantage of RCS, while programs that do not benefit from it show a small overhead using the new mechanisms.

Bibtex

@MastersThesis{cruz-msc,
  author =  {F. Cruz},
  title =   {{Call Subsumption Mechanisms for Tabled Logic Programs}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {June},
  year =    {2010},
  type =    {{MSc Thesis}},
}

Download Thesis

PDF file