Click on the title to obtain a gzip-ed PostScript version of the paper (96K).
Abstract:
Tabling can be implemented in a (WAM-based) Prolog system by means of
SLG-WAM: consumers suspend and their state is preserved by freezing
the execution stacks. XSB is a system that currently implements
tabling based on the SLG-WAM. The memory model is quite complex and
attempts to understand the notion of usefulness of data in XSB well
enough to build a precise garbage collector have failed in the past.
CAT is a recent alternative to SLG-WAM: it suspends consumers by
copying parts of the execution stacks. The memory model is simpler
and the design of a more precise garbage collector became feasible.
CAT also provided the necessary insights in the usefulness of data in
the context of the SLG-WAM. This paper describes the memory
management of tabled logic programming systems, whether based on the
SLG-WAM or on CAT. Since CAT can perform arbitrarily worse than
SLG-WAM space-wise, also a minor garbage collection on creation of the
CAT areas is described and its effectiveness is discussed.