One Table Fits All

Jorge Costa and Ricardo Rocha

January 2009


Abstract

Tabling is an implementation technique that overcomes some limitations of traditional Prolog systems in dealing with redundant sub-computations and recursion. The performance of tabled evaluation largely depends on the implementation of the table space. Arguably, the most successful data structure for tabling is tries. However, while tries are efficient for variant based tabled evaluation, they are limited in their ability to recognize and represent repeated answers for different calls. In this paper, we propose a new design for the table space where tabled subgoal calls and/or answers are stored only once in a common global trie instead of being spread over several different tries. Our preliminary experiments using the YapTab tabling system show very promising reductions on memory usage.

Bibtex

@InProceedings{costa-padl09,
  author =    {J. Costa and R. Rocha},
  title =     {{One Table Fits All}},
  booktitle = {Proceedings of the 11th International Symposium on Practical Aspects of Declarative 
               Languages (PADL 2009)},
  pages =     {195--208},
  number =    {5418},
  series =    {LNCS},
  publisher = {Springer},
  editor =    {A. Gill and T. Swift},
  month =     {January},
  year =      {2009},
  address =   {Savannah, Georgia, USA},
}

Download Paper

PDF file
Springer

Download Slides

PDF file