BETTER STATIC MEMORY MANAGEMENT - IMPROVING REGION-BASED ANALYSIS OF HIGHER-ORDER LANGUAGES

Static memory management replaces runtime garbage collection with comp ile-time annotations that make all memory allocation and deallocation explicit in a program. We improve upon the Tofte/Talpin region-based s cheme for compile-time memory management [TT94]. In the Tofte/Talpin a pproach, all values, including closures, are stored in regions. Region lifetimes coincide with lexical scope, thus forming a runtime stack o f regions and eliminating the need for garbage collection. We relax th e requirement that region lifetimes be lexical. Rather, regions are al located late and deallocated as early as possible by explicit memory o perations. The placement of allocation and deallocation annotations is determined by solving a system of constraints that expresses all poss ible annotations. Experiments show that our approach reduces memory re quirements significantly, in some cases asymptotically.