Efficient Instance Retrieval of Subgoals for Subsumptive Tabled Evaluation of Logic Programs
Flávio Cruz and Ricardo Rocha
July 2011
Abstract
Tabled evaluation is an implementation technique that solves some
problems of traditional Prolog systems in dealing with recursion and
redundant computations. Most tabling engines determine if a tabled
subgoal will produce or consume answers by using variant checks. A
more refined method, named call subsumption, considers that a subgoal
A will consume from a subgoal B if A is subsumed by (an instance of)
B, thus allowing greater answer reuse. We recently developed an
extension, called Retroactive Call Subsumption, that improves upon
call subsumption by supporting bidirectional sharing of answers
between subsumed/subsuming subgoals. In this paper, we present both an
algorithm and an extension to the table space data structures to
efficiently implement instance retrieval of subgoals for subsumptive
tabled evaluation of logic programs. Experiments results using the
YapTab tabling system show that our implementation performs quite well
on some complex benchmarks and is robust enough to handle a large
number of subgoals without performance degradation.
Bibtex
@Article{cruz-iclp11,
author = {F. Cruz and R. Rocha},
title = {{Efficient Instance Retrieval of Subgoals for Subsumptive Tabled Evaluation of Logic Programs}},
journal = {Journal of Theory and Practice of Logic Programming,
27th International Conference on Logic Programming (ICLP 2011), Special Issue},
pages = {697--712},
volume = {11},
number = {4 \& 5},
month = {July},
year = {2011},
}
Download Paper
PDF file
Cambridge University Press
Computing Research Repository (CoRR)