Implementation of Suspension-Based Tabling in Prolog using External Primitives

Ricardo Rocha, Cláudio Silva and Ricardo Lopes

December 2007

---

Abstract

We present the design, implementation and evaluation of a suspension-based tabling mechanism that supports tabled evaluation by applying source level transformations to a tabled program. The transformed program then uses external tabling primitives that provide direct control over the evaluation strategy. To implement the tabling primitives we took advantage of the C language interface of the Yap Prolog system. Initial results show that our suspension-based mechanism is comparable to the state-of-the-art YapTab system, that implements tabling support at the low-level engine. This is an interesting result because YapTab also implements a suspension-based mechanism, uses the same data structures to implement the table space and is implemented on top of Yap. 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.

Bibtex

@InProceedings{rocha-epia07-local,
  author =    {R. Rocha and C. Silva and R. Lopes},
  title =     {{Implementation of Suspension-Based Tabling in Prolog using External Primitives}},
  booktitle = {Local Proceedings of the 13th Portuguese Conference on Artificial Intelligence (EPIA 2007)},
  pages =     {11--22},
  editor =    {J. Neves and M. Santos and J. Machado},
  month =     {December},
  year =      {2007},
  address =   {Guimarães, Portugal},
}

Download Paper

PDF file

Download Slides

PDF file