Secure Internet Programming - menu
Secure Internet Programming
Princeton University
Department of Computer Science

Provably Safe Garbage Collection
Daniel Wang, Andrew Appel

We are developing techniques to implement type-safe garbage collectors by combining existing type systems used for compiling type-safe languages. We have adapted 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 use it to implement a garbage collector which is provably safe. We have developed 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.

Type-Preserving Garbage Collectors, Daniel C. Wang and Andrew W. Appel, January 2001.

Safe Garbage Collection = Regions + Intensional Type Analysis, Daniel C. Wang and Andrew W. Appel, July 1999.