On Applying Program Transformation to Implement Suspension-Based Tabling in Prolog

Ricardo Rocha, Cláudio Silva and Ricardo Lopes

September 2007

---

Abstract

A common approach used to include tabling support into existing Prolog systems is to modify and extend the low-level engine. A different approach is to apply source level transformations to a tabled program and then use external tabling primitives that provide direct control over the search strategy to implement tabled evaluation. In this work, we present a suspension-based tabling mechanism based on program transformation and we use the C language interface, available in most Prolog systems, to implement the tabling primitives. In particular, we use the C interface of the Yap Prolog system to build external Prolog modules implementing the support for tabled evaluation. To evaluate the impact of our approach, we ran it against the state-of-the-art YapTab system, that implements tabling support at the low-level engine. Initial results are very interesting and very promising. We thus argue that our approach is a good alternative 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. Moreover, both source level transformations and tabling primitives can be easily ported to other Prolog systems with a C language interface.

Bibtex

@InProceedings{rocha-iclp07,
  author =    {R. Rocha and C. Silva and R. Lopes},
  title =     {{On Applying Program Transformation to Implement Suspension-Based Tabling in Prolog}},
  booktitle = {Proceedings of the 23rd International Conference on Logic Programming (ICLP 2007)},
  pages =     {444--445},
  number =    {4670},
  series =    {LNCS},
  publisher = {Springer},
  editor =    {V. Dahl and I. Niemelä},
  month =     {September},
  year =      {2007},
  address =   {Porto, Portugal},
}

Download Paper

PDF file
Springer

Download Slides

PDF file

Download Poster

PDF file