597 SEMANTIC ANALYSES FOR STORAGE MANAGEMENT OPTIMIZATIONS IN FUNCTIONAL LANGUAGE IMPLEMENTATIONS Y. G. Park, February 1992 One of the major overheads in implementing functional languages is the storage management overhead due to dynamic allocation and automatic reclamation of indefinite-extent storage. This dissertation investigates the problems of statically inferring lifetime information about dynamically-allocated objects in higher-order polymorphic functional languages, both strict and non-strict, and of applying that information to reduce the storage management overhead. We have developed a set of compile-time semantic analyses for a higher-order, monomorphic, strict functional language based on denotational semantics and abstract interpretation. They are 1) escape analysis, which provides information about the relative lifetimes of objects such as arguments and local objects defined within a function with respect to an activation of the function call, 2) refined escape analysis which, as a refinement of escape analysis, provides information about the lifetimes of components of aggregate structures, and 3) reference escape analysis which provides information about the relative lifetimes of references created within a function with respect to an activation of the function. We also have developed a compile-time semantic analysis called order-of-demand analysis for higher-order, monomorphic, non-strict functional languages, which provides information about the order in which the values of bound variables are demanded and thus allows one to compute a range of information including strictness, evaluation-order, and evaluationstatus information. Using the notion of polymorphic invariance, we describe a method for analyzing a polymorphic language by using the analyses for a monomorphic language. We then extend those analyses for a strict language to a non-strict language using non-strict program transformation and evaluation-status information. Based on statically inferred escape information, we propose a combination of storage management optimization techniques including stack allocation, explicit reclamation, in-place reuse, reference counting elimination, block allocation/reclamation, and improving generational garbage collection.