Compact Lists for Tabled Evaluation

João Raimundo and Ricardo Rocha

January 2010

---

Abstract

A critical component in the implementation of an efficient tabling system is the design of the data structures and algorithms to access and manipulate tabled data. Arguably, the most successful data structure for tabling is tries, which is regarded as a very compact and efficient data structure for term representation. Despite these good properties, we found that, for list terms, we can design even more compact and efficient representations. We thus propose a new representation of list terms for tries that avoids the recursive nature of the WAM representation of list terms in which tries are based. Our experimental results using the YapTab tabling system show a significant reduction in the memory usage for the trie data structures and considerable gains in the running time for storing and loading list terms.

Bibtex

@InProceedings{raimundo-padl10,
  author =    {J. Raimundo and R. Rocha},
  title =     {{Compact Lists for Tabled Evaluation}},
  booktitle = {Proceedings of the 12th International Symposium on Practical Aspects of Declarative 
               Languages (PADL 2010)},
  pages =     {249--263},
  number =    {5937},
  series =    {LNCS},
  publisher = {Springer},
  editor =    {M. Carro and R. Peña},
  month =     {January},
  year =      {2010},
  address =   {Madrid, Spain},
}

Download Paper

PDF file
Springer

Download Slides

PDF file