An Efficient Implementation of Linear Tabling Based on Dynamic Reordering of Alternatives
Miguel Areias and Ricardo Rocha
January 2010
Abstract
Tabling is a technique of resolution 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. In
suspension-based tabling, a tabled evaluation can be seen as a
sequence of sub-computations that suspend and later resume. Linear
tabling mechanisms maintain a single execution tree where tabled
subgoals always extend the current computation without requiring
suspension and resumption of sub-computations. In this work, we
present a new and efficient implementation of linear tabling, but for
that we have extended an already existent suspension-based
implementation, the YapTab engine. Our design is based on dynamic
reordering of alternatives but it innovates by considering a strategy
that schedules the re-evaluation of tabled calls in a similar manner
to the suspension-based strategies of YapTab. Our implementation also
shares the underlying execution environment and most of the data
structures used to implement tabling in YapTab. We thus argue that all
these common features allows us to make a first and fair comparison
between suspension-based and linear tabling and, therefore, better
understand the advantages and weaknesses of each.
Bibtex
@InProceedings{areias-padl10,
author = {M. Areias and R. Rocha},
title = {{An Efficient Implementation of Linear Tabling Based on Dynamic Reordering of Alternatives}},
booktitle = {Proceedings of the 12th International Symposium on Practical Aspects of Declarative
Languages (PADL 2010)},
pages = {279--293},
number = {5937},
series = {LNCS},
publisher = {Springer},
editor = {M. Carro and R. Peña},
month = {January},
year = {2010},
address = {Madrid, Spain},
}
Download Paper
PDF file
Springer
Download Slides
PDF file