Title: Region-Based Memory Management 1

This paper describes a memory management discipline for programs that perform dynamic memory allocation and de-allocation. At runtime, all values are put into regions. The store consists of a stack of regions. All points of region allocation and deallocation are inferred automatically, using a type and e ect based program analysis. The scheme does not assume the presence of a garbage collector. The scheme was rst presented by Tofte and Talpin (1994) � subsequently, it has been tested in The ML Kit with Regions, a region-based, garbage-collection free implementation of the Standard ML Core language, which includes recursive datatypes, higher-order functions and updatable references (Birkedal et al. 96, Elsman and Hallenberg 95). This paper de nes a region-based dynamic semantics for a skeletal programming language extracted from Standard ML. We present the inference system which speci es where regions can be allocated and de-allocated and a detailed proof that the system is sound with respect to a standard semantics. We conclude by giving some advice on how to write programs that run well on a stack of regions, based on practical experience with the ML Kit. 3