Efficient Storing Mechanisms for Tabled Logic Programs
João Raimundo
December 2010
Abstract
Programming languages are an unique method to communicate with
machines. Declarative languages, such as logic programming languages,
provide features like a high-level and declarative syntax, simplifying
the communication between man-and-machine. Arguably, Prolog is the
most famous and used logic programming language. Prolog uses SLD
resolution in order to provide good performance in the computation of
complex real world problems. Although SLD resolution proved to be very
effective, in some cases, this procedure show some restrictions when
dealing with infinite loops and redundant sub-computations.
One of the most successful techniques proposed to overcome SLD's
susceptibility, is tabling. The tabling mechanism consists in storing
the subgoals and the respective answers of a program in a table space
in such a way that, in later stages of a program's evaluation,
repeated subgoal calls use the answers stored in the tables, avoiding
the subgoal re-evaluation. Tabling success largely depends on the
implementation of the table space, its data structures and
algorithms. Arguably, the most successful data structure for tabling
is tries. Nevertheless, when tabling is used in applications that have
large quantities of data, it can lead to overgrown tables and quickly
fill up the system's memory.
With this research, we try to provide alternative designs and
structures, not only to the table space organization but also to the
tabled data representation. We do so, by proposing a new design for
the table space organization where all terms in tabled subgoal calls
and tabled answers are represented only once in a common global trie
instead of being spread over several different trie data structures,
suggesting three different approaches. At tabled data representation,
we propose a new representation of list terms for tries that avoids
the recursive nature of the WAM representation of list terms in which
tries are based.
The results obtained in our experiments when using the YapTab tabling
system, show significant reductions on memory usage, without
compromising running time. Memory usage is reduced when using any of
the three different global trie designs and also in the new
representation of list terms, providing the necessary data to make it
clear that our proposals can provide more compact and efficient
representations of the table space, when applying tabling mechanisms
to Prolog.
Bibtex
@MastersThesis{raimundo-msc,
author = {J. Raimundo},
title = {{Efficient Storing Mechanisms for Tabled Logic Programs}},
school = {University of Porto},
address = {Portugal},
month = {December},
year = {2010},
type = {{MSc Thesis}},
}
Download Thesis
PDF file