| Home > Publications > Reports > Informatics (CW) |
CW 330
Bart Demoen
A fresh look at garbage collection for Prolog
Abstract
Garbage collection in the context of the WAM is reconsidered independent of garbage collection algorithms. A set of garbage collections compatible with the WAM is specified in two steps: the first step make the useful data for each continuation private and ensures that no garbage terms survive any collection. The second step completes garbage collection by extending the notion of folding of identical structures. The role of the trail in the folding process is crucial and shown for the ordinary WAM trail as well as for a value-trail. Particular requirements on the folding step lead to particular garbage collection algorithms, but new and unexpected opportunities for recovering memory are discovered to be compatible with this view of garbage collection. Even though this does not lead directly to new practical algorithms, it is a start for a better understanding of the usefulness logic in the WAM and shows new potential for compile time analysis that can improve run time memory management. An improvement to the treatment of value-trailed locations during marking is also given.
report.pdf / mailto: B. Demoen