Single Time-Stamped Tries for Retroactive Call Subsumption
Flávio Cruz and Ricardo Rocha
July 2011
Abstract
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.
Bibtex
@InProceedings{cruz-ciclops11,
author = {F. Cruz and R. Rocha},
title = {{Single Time-Stamped Tries for Retroactive Call Subsumption}},
booktitle = {Proceedings of the 11th Colloquium on Implementation of Constraint and LOgic Programming
Systems (CICLOPS 2011)},
pages = {19--33},
editor = {S. Abreu and V. Santos Costa},
month = {July},
year = {2011},
address = {Lexington, Kentucky, USA},
}
Download Paper
PDF file
Computing Research Repository (CoRR)