On Applying Linear Tabling to Logic Programs

Miguel Areias

September 2010


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 file