A non-algorithmic approach to garbage collection for the WAM heap is developed. A set of garbage collections compatible with the WAM is specified in two steps: the first step makes the useful data for each continuation private and ensures that only useful terms survive garbage collection. The second step completes garbage collection by extending the intuitive notion of folding of identical structures. The role of the trail in the folding process is crucial and it is shown for the ordinary WAM trail as well as for a value trail. New and unexpected opportunities for recovering memory are discovered to be compatible with this view of garbage collection. This approach leads to better understanding of the usefulness logic in the WAM, it is a good start for the formal specification of the garbage collection process and it shows a potential for new compile time analyses that can improve run time memory management. Choice point trimming is used as a vehicle to show selective liveness of data, so its relation to the more common stack maps is established.
展开▼
