A Very Compact and Efficient Representation of List Terms for Tabled Logic Programs

João Raimundo and Ricardo Rocha

November 2009

---

Abstract

Tabling is an implementation technique that overcomes some limitations of traditional Prolog systems in dealing with redundant sub-computations and recursion. 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 impressive gains in the running time for storing and loading list terms.

Bibtex

@InProceedings{raimundo-inap09-local,
  author =    {J. Raimundo and R. Rocha},
  title =     {{A Very Compact and Efficient Representation of List Terms for Tabled Logic Program}},
  booktitle = {Local Proceedings of the International Conference on Applications of Declarative 
               Programming and Knowledge Management (INAP 2009)},
  pages =     {157--170},
  editor =    {S. Abreu and D. Seipel},
  month =     {November},
  year =      {2009},
  address =   {Évora, Portugal},
}

Download Paper

PDF file