Garbage Collection (GC)

Appeared in Volume 9/3, August 1996

ctv@cs.vu.nl
Cees T. Visser
12th April 1996

Can anyone suggest some pointers to techniques for heap garbage collection in Prolog? Papers from a historical, as well as a "state-of-the-art", point of view are welcome.

conway@munta.cs.mu.oz.au
Thomas Charles Conway
15th April 1996

The best paper that I have read on GC is Paul Wilson's survey:
ftp://ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps

While it is not specific to Prolog implementations, it is a "must read" for anyone who is serious about understanding how their programs use memory, and how programming language implementations support, or impede, good use of memory resources.

thomasl@csd.uu.se
Thomas Lindgren
15th April 1996

Take a look at Bekker et al in IWMM'92 (LNCS 637) for a survey of sequential Prolog GC.

Most collectors are compacting, as far as I know. The standard reference, if you want to look at the implementation, is probably that used in SICStus Prolog: Appleby et al, in CACM, June 1988.

A simple generational copying collector for Prolog was described by Johan Bevemyr and myself in PLILP'94 (LNCS 844). The article can be found on my home page (http://www.csd.uu.se/~thomasl/).

Paul Tarau's BinProlog also incorporates (another form of) copying collectors, done with Bart Demoen and Geert Engels.

tarau@cs.kuleuven.ac.be
Paul Tarau
15th April 1996

GC in Prolog involves a lot of issues not present in other languages. I would suggest taking a look at:

"Segment Preserving Copying Garbage Collection for WAM based Prolog", Bart Demoen and Geert Engels and Paul Tarau, Proc. of the 1996 ACM Symp. on Applied Computing, ACM Press, Philadelphia, Feb, 1996

This describes a copying garbage collector (i.e it works in time proportional to the size of useful data) which preserves segments (and still recuperates space on backtracking). Having these two features together in a WAM-based Prolog is fairly tricky, but once you get it right it's probably the best technology around.

This work is integrated into BinProlog 5.00, so you can try it out and benchmark it. Quietness option -q0 will show some GC messages and statistics.