Retroactive Subsumption-Based Tabled Evaluation of Logic Programs
Flávio Cruz and Ricardo Rocha
September 2010
Abstract
Tabled evaluation is a recognized and powerful implementation
technique that overcomes some limitations of traditional Prolog
systems in dealing with recursion and redundant
sub-computations. Tabling based systems use call similarity to
determine if a tabled subgoal will produce their own answers or if it
will consume from another subgoal. While call variance has been a very
popular approach, call subsumption can yield superior time performance
and space improvements as it allows greater reuse of answers. However,
the call order of the subgoals can greatly affect the success and
applicability of the call subsumption technique. In this work, we
present an extension, named Retroactive Call Subsumption, that
supports call subsumption by allowing full sharing of answers between
subsumed/subsuming subgoals, independently on the order in which they
are called. Our experiments using the YapTab tabling engine show
considerable gains in evaluation time for some applications, at the
expense of a very small overhead for the programs that cannot benefit
from it.
Bibtex
@InProceedings{cruz-jelia10,
author = {F. Cruz and R. Rocha},
title = {{Retroactive Subsumption-Based Tabled Evaluation of Logic Programs}},
booktitle = {Proceedings of the 12th European Conference on Logics in Artificial Intelligence (JELIA 2010)},
pages = {130--142},
number = {6341},
series = {LNAI},
publisher = {Springer},
editor = {T. Janhunen and I. Niemelä},
month = {September},
year = {2010},
address = {Helsinki, Finland},
}
Download Paper
PDF file
Springer