A Simple Table Space Design for Retroactive Call Subsumption

Flávio Cruz and Ricardo Rocha

October 2011

---

Abstract

Tabling is an implementation technique where answers from subgoals are stored in a table space area in order to be reused later by similar subgoals. Most tabling engines use call by variance to test subgoal similarity by means of simple variable renaming. Call by subsumption is a more sophisticated similarity test where subsumed subgoals can use answers from subsuming subgoals, therefore increasing answer reuse and attaining better execution times in general. However, call by subsumption is highly dependent on the call order of the subgoals. A recent strategy, called Retroactive Call Subsumption (RCS), supports call by subsumption by allowing full sharing of answers between subsumed/subsuming subgoals, independently on the order in which they are called. For this strategy, we propose a new table space design, the Single Time Stamped Trie (STST), that makes answer sharing across subsumed/subsuming subgoals simple and efficient. In this paper, we present the STST design and how it fits within the RCS framework. In experimental results, we observed some overheads in programs that stress the drawbacks of STST when RCS is not applied, but its design's simplicity outweighs these disadvantages when programs take advantage of RCS evaluation.

Bibtex

@InProceedings{cruz-epia11-local,
  author =    {F. Cruz and R. Rocha},
  title =     {{A Simple Table Space Design for Retroactive Call Subsumption}},
  booktitle = {Local Proceedings of the 15th Portuguese Conference on Artificial Intelligence (EPIA 2011)},
  pages =     {253--267},
  editor =    {L. Antunes and H. S. Pinto},
  month =     {October},
  year =      {2011},
  address =   {Lisboa, Portugal},
}

Download Paper

PDF file

Download Slides

PDF file