On Applying Program Transformation to Implement Tabled Evaluation in Prolog
Cláudio Silva
March 2007
Abstract
Tabling is a technique of resolution that overcomes some limitations
of traditional Prolog systems in dealing with recursion and redundant
sub-computations. Tabling consists of storing intermediate answers for
subgoals so that they can be reused when a repeated subgoal appears
during the resolution process. We can distinguish two main categories
of tabling mechanisms:
delaying-based tabling and
linear
tabling. Delaying-based tabling mechanisms need to preserve the
state of suspended tabled subgoals in order to ensure that all answers
are correctly computed. 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 thesis we present the design, implementation and evaluation of
three different delaying-based and linear tabling mechanisms to
support tabled evaluation in Prolog, and for that we apply source
level transformations to a tabled program. The transformed program
then uses external tabling primitives that provide direct control over
the search strategy. To implement the tabling primitives we took
advantage of the C language interface of the Yap Prolog system.
Performance results, on a set of common benchmarks for tabled
execution, allows us to make a first and fair comparison between these
different tabling mechanisms and, therefore, better understand the
advantages and weaknesses of each. Our results show that
delaying-based tabling obtains better results than linear tabling and,
in particular, for programs with complex dependencies, delaying-based
tabling clearly outperforms linear tabling. Our results also show that
our delaying-based mechanism is comparable to the state-of-the-art
YapTab system, that implements tabling support at the low-level
engine. We thus argue that our approach is a good choice to
incorporate tabling into any Prolog system. It requires neither
advanced knowledge of the implementation details of tabling nor time
consuming or complex modifications to the low-level engine.
Bibtex
@MastersThesis{silva-msc,
author = {C. Silva},
title = {{On Applying Program Transformation to Implement Tabled Evaluation in Prolog}},
school = {University of Porto},
address = {Portugal},
month = {March},
year = {2007},
type = {{MSc Thesis}},
}
Download Thesis
PDF file