Computer Science – Programming Languages
Scientific paper
2011-12-16
Computer Science
Programming Languages
Online Proceedings of the 11th International Colloquium on Implementation of Constraint LOgic Programming Systems (CICLOPS 201
Scientific paper
Tabling is an evaluation strategy for Prolog programs that works by storing answers in a table space and then by using them in similar subgoals. Some tabling engines use call by subsumption, where it is determined that a subgoal will consume answers from a more general subgoal in order to reduce the search space and increase efficiency. We designed an extension, named Retroactive Call Subsumption (RCS), that implements call by subsumption independently of the call order, thus allowing a more general subgoal to force previous called subgoals to become answer consumers. For this extension, we propose a new table space design, the Single Time Stamped Trie (STST), that is organized to make answer sharing across subsumed/subsuming subgoals simple and efficient. In this paper, we present the new STST table space design and we discuss the main modifications made to the original Time Stamped Tries approach to non-retroactive call by subsumption. In experimental results, with programs that stress some deficiencies of the new STST design, some overheads may be observed, however the results achieved with more realistic programs greatly offset these overheads.
Cruz Flavio
Rocha Ricardo
No associations
LandOfFree
Single Time-Stamped Tries for Retroactive Call Subsumption does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Single Time-Stamped Tries for Retroactive Call Subsumption, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single Time-Stamped Tries for Retroactive Call Subsumption will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-136730