Click on the title to obtain a gzip-ed PostScript version of the paper (88K).
Note however, that the copyright of this paper is held by Springer as it is
published in the volume with the
PLILP'98
proceedings. An electronic version of these proceedings can be accessed
somewhere in the
LNCS series Homepage.
Abstract:
The SLG-WAM implements tabling by freezing
the WAM stacks: this implementation technique has a reasonably small
execution overhead, but is not easy to implement on top of an existing
Prolog system.
We here propose a new approach to the implementation of tabling: the
Copying Approach to Tabling. CAT interferes absolutely not with normal
Prolog execution and can be introduced in an existing Prolog system
orthogonally. We have implemented CAT starting from XSB (i.e. taking
out SLG-WAM and adding CAT) and the results show that in practical
programs CAT slightly outperforms the SLG-WAM.
We give a detailed account of the additions to be made to a WAM
implementation for adopting CAT. We show a case in which CAT performs
arbitrarily worse than SLG-WAM, but on the other hand we present
empirical evidence that CAT is competitive and often faster than
SLG-WAM. We discuss issues related to memory management and the
impact of the scheduling strategy.