CAT: the Copying Approach to Tabling
Bart Demoen, Konstantinos Sagonas · Lirias · 1999
The SLG-WAM is an abstract machine that can be characterized as a sharing approach to implementing tabling: The execution environments of suspended computations are interspersed in the WAM stacks. Stacks are frozen using a set of freeze registers, and the WAM trail mechanism is extended so that the suspended computations can be resumed. This technique has a reasonably small execution overhead, but it is not easy to implement on top of an existing Prolog system. It is also quite difficult to understand. We propose a new technique for the implementation of tabling: the copying approach to tabling. CAT does not impose any overhead to the execution of Prolog code and can be introduced into an existing Prolog system orthogonally. Also, CAT is easier to understand. We have implemented CAT in the XSB system by taking out SLG-WAM and adding CAT. We describe the additions needed for adopting CAT in a WAM implementation. 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 the SLG-WAM. We also briefly discuss issues related to memory management and to the scheduling.