Safe Garbage Collection = Regions + Intensional Type Analysis

Abstract:

We present a technique to implement type-safe garbage collectors by
combining existing type systems used for compiling type-safe languages. We
adapt the type systems used in region inference and intensional type
analysis to construct a safe stop-and-copy garbage collector for
higher-order polymorphic languages. Rather than using region inference as
the primary method of storage management, we show how it can be used to
implement a garbage collector which is provably safe. We also introduce a
new region calculus with non-nested object life-times which is significantly
simpler than previous calculi. Our approach also formalizes more of the
interface between garbage collectors and code generators. The efficiency of
our safe collectors are algorithmically competitive with unsafe collectors.