On Combining Linear-Based Strategies for Tabled Evaluation of Logic Programs
Miguel Areias and Ricardo Rocha
July 2011
Abstract
Tabled evaluation is a recognized and powerful technique that
overcomes some limitations of traditional Prolog systems in dealing
with recursion and redundant sub-computations. We can distinguish two
main categories of tabling mechanisms: suspension-based tabling and
linear tabling. While suspension-based mechanisms are considered to
obtain better results in general, they have more memory space
requirements and are more complex and harder to implement than linear
tabling mechanisms. Arguably, the SLDT and DRA strategies are the two
most successful extensions to standard linear tabled evaluation. In
this work, we propose a new strategy, named DRS, and we present a
framework, on top of the Yap system, that supports the combination of
all these three strategies. Our implementation shares the underlying
execution environment and most of the data structures used to
implement tabling in Yap. We thus argue that all these common features
allows us to make a first and fair comparison between these different
linear tabling strategies and, therefore, better understand the
advantages and weaknesses of each, when used solely or combined with
the others.
Bibtex
@Article{areias-iclp11,
author = {M. Areias and R. Rocha},
title = {{On Combining Linear-Based Strategies for 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 = {681--696},
volume = {11},
number = {4 \& 5},
month = {July},
year = {2011},
}
Download Paper
PDF file
Cambridge University Press
Computing Research Repository (CoRR)