Heap Garbage Collection in XSB: Practice and Experience

Click on the title to obtain a gzip-ed PostScript version of the paper (90K).


Starting from a theoretical understanding of the usefulness logic of a logic programming system with built-in tabling, and from a collector that did not take the characteristics of a tabled abstract machine into account we have build two heap garbage collectors (one mark & slide, one mark & copy) for XSB on top of the CHAT implementation model for the suspension/resumption of consumers. Based on this experience we discuss implementation issues that are general to heap garbage collection for the WAM and also issues that are specific to an implementation with tabling: as such, this paper documents our own 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. We also present figures on the extent of internal fragmentation and the effectiveness of early reset in Prolog systems with and without tabling.