CAT

CAT: The copying approach to tabling. The SLGWAM 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 SLGWAM 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 SLGWAM, but on the other hand we present empirical evidence that CAT is competitive and often faster than the SLGWAM. We also briefly discuss issues related to memory management and to the scheduling.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element