On Applying Linear Tabling to Logic Programs
Abstract
Logic programming languages, such as Prolog, are derived from Horn
Clause Logic and provide a well understood resolution based inference
mechanism. Although Prolog is a popular and successful language, its
potential is limited by the SLD resolution method on which it is
based. SLD resolution was proven to be inefficient when dealing with
infinite loops and redundant subcomputations. Tabled evaluation is a
recognized and powerful technique that overcomes those limitations on
traditional Prolog systems based on SLD resolution. We can distinguish
two main categories of tabling mechanisms: suspension-based tabling
and linear-based tabling. While suspension-based mechanisms are
considered to obtain better results in general, they have more memory
space requirements and are more complex and hard to implement than
linear tabling mechanisms.
The work presented on this thesis was focused on making a deep study
about linear tabling, in order to understand how different linear
tabling strategies can affect the evaluation flow of tabled programs
and improve its overall performance. 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 linear tabling strategies. Our
implementation shares the underlying execution environment and most of
the data structures used to implement tabling in the YapTab engine,
which is the actual suspension-based tabling mechanism of the Yap
Prolog system. All these common features allows us to make a first and
fair comparison between the linear tabling strategies, used solely or
combined with the other, and YapTab’s suspension-based mechanism, in
order to better understand the advantages and weaknesses of each
feature. The obtained results confirmed that suspension-based
mechanisms have, in general, better performance than linear tabling
and that the difference between both mechanisms can be highly reduced
by using the correct combination of linear tabling strategies.
Bibtex
@MastersThesis{areias-msc, author = {M. Areias}, title = {{On Applying Linear Tabling to Logic Programs}}, school = {University of Porto}, address = {Portugal}, month = {September}, year = {2010}, type = {{MSc Thesis}}, }
Download Thesis
PDF fileRepositório Aberto-UP