Click on the title to obtain a gzip-ed PostScript version of the paper (57K).
Abstract:
The Copying Approach to Tabling, abbrv. CAT, is an alternative to
SLG-WAM and based on total copying of the areas that the SLG-WAM
freezes to preserve execution states of suspended computations. The
disadvantage of CAT as pointed out in a previous paper is that in the
worst case, CAT must copy so much that it becomes arbitrarily worse
than the SLG-WAM. Remedies to this problem have been studied, but a
completely satisfactory solution has not emerged. Here, a hybrid
approach is presented: CHAT.
Its design was guided by the requirement that for non-tabled (i.e.
Prolog) execution no changes to the underlying WAM engine need to be
made. CHAT combines certain features of the SLG-WAM with features
of CAT, but also introduces a technique for freezing WAM stacks
without the use of the SLG-WAM's freeze registers that is of
independent interest. Empirical results indicate that CHAT is a
better choice for implementing the control of tabling than SLG-WAM
or CAT. However, programs with arbitrarily worse behaviour exist.