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