Abstract:
The use of tabling in logic programming has been recognized as a powerful evaluation technique, since it allows bottom-up evaluation to be incorporated within a top-down framework, combining the advantages of both. Systems based on tabling have begun to emerge only recently and early experience with them suggest that table based resolution methods are practically viable. Therefore techniques to enhance the performance of tabling systems are becoming important.Currently available tabling systems are mostly based on variant checks and hence are limited in their ability to recognize reusable subcomputations. Tabling systems based on call subsumption can yield superior performance by recognizing a larger set of reusable computations. However, a straightforward adaptation of the mechanisms used in variant-based systems to reuse these computations can in fact result in considerable performance degradation. In this paper we propose a novel organization of tables using Dynamic Threaded Sequential Automata (DTSA) which permits efficient reuse of previously computed results in a subsumptive system. We describe an implementation of the tables using DTSA and the associated access mechanisms. We also report experimental results which show that a subsumptive tabling system implemented by extending the XSB logic programming system with our table access techniques can perform significantly better than the original variant-based system.
Bibtex Entry:
@inproceedings{RRR:JICSLP96, author = {P. Rao and C. R. Ramakrishnan and I. V. Ramakrishnan}, title = {A Thread in Time Saves Tabling Time}, booktitle = {Joint International Conference/Symposium on Logic Programming}, publisher = {MIT Press}, pages = {112--126}, year = {1996} }
| Full Paper: | [pdf] |
C. R. Ramakrishnan
(cram@cs.sunysb.edu)