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