Heap Garbage Collection in XSB: Practice and Experience

Starting from a theoretical understanding of the issues involved in the implementation of a heap garbage collector in a logic programming system with built-in tabling, and from an actual collector that did not take tabling (i.e. suspended computations) into account we have build two working heap garbage collectors (one mark&slide, one mark&copy) for XSB on top of a CHAT implementation model for the suspension/resumption of consumers. We discuss implementation issues and decisions that are general to heap garbage collections for the WAM and issues that are specific to an implementation with tabling: as such, this paper documents our implementation and can serve as guidance for anyone attempting a similar feat. We report on the behaviour of the garbage collectors on different kinds of programs. In particular we present figures on the extent of internal fragmentation and the effectiveness of early reset in Prolog systems which were made possible through having implemented the garbage coll..