An Improved Continuation Call-Based Implementation of Tabling

Pablo Chico, Manuel Carro, Manuel V. Hermenegildo, Cláudio Silva and Ricardo Rocha

January 2008


Abstract

Tabled evaluation has been proved an effective method to improve several aspects of goal-oriented query evaluation, including termination and complexity. Several native implementations of tabled evaluation have been developed which offer good performance, but many of them require significant changes to the underlying Prolog implementation, including the compiler and the abstract machine. Approaches based on program transformation, which tend to minimize changes to both the Prolog compiler and the abstract machine, have also been proposed, but they often result in lower efficiency. We explore some techniques aimed at combining the best of these worlds, i.e., developing an extensible implementation which requires minimal modifications to the compiler and the abstract machine, and with reasonably good performance. Our preliminary experiments indicate promising results.

Bibtex

@InProceedings{chico-padl08,
  author =    {P. Chico and M. Carro and M. V. Hermenegildo and C. Silva and R. Rocha},
  title =     {{An Improved Continuation Call-Based Implementation of Tabling}},
  booktitle = {Proceedings of the 10th International Symposium on Practical Aspects of Declarative 
               Languages (PADL 2008)},
  pages =     {197--213},
  number =    {4902},
  series =    {LNCS},
  publisher = {Springer},
  editor =    {P. Hudak and D. S. Warren},
  month =     {January},
  year =      {2008},
  address =   {San Francisco, California, USA},
}

Download Paper

PDF file
Springer