School of Computing

Garbage collecting shared environment closure reducers

Stephen Thomas and Richard Jones

Technical Report 31-94, Computing Laboratory, University of Kent at Canterbury, December 1994.


Shared environment closure reducers such as Fairbairn and Wray's TIM incur a comparatively low cost when creating a suspension, and so provide an elegant method for implementing lazy functional evaluation. However, comparatively little attention has been given to the problems involved in identifying which portions of a shared environment are needed (and ignoring those which are not) during a garbage collection. Proper consideration of this issue has subtle consequences when implementing a storage manager in a TIM-like system. We describe the problem and illustrate the negative consequences of ignoring it.

We go on to describe a solution in which the compiler determines statically which portions of that code's environment are required for each piece of code it generates, and emits information to assist the run-time storage manager to scavenge environments selectively. We also describe a technique for expressing this information directly as executable code, and demonstrate that a garbage collector implemented in this way can perform significantly better than an equivalent, table-driven interpretive collector.

Bibtex Record

author = {Stephen Thomas and Richard Jones},
title = {Garbage Collecting Shared Environment Closure Reducers},
month = {December},
year = {1994},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {},
    institution = {Computing Laboratory, University of Kent at Canterbury},
    number = {31-94},
    type = {Technical Report},

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014