Optimal Type Lifting
Last modified: Tue Mar 14 19:31:29 2000 GMT.
Modern compilers for ML-like polymorphic languages have used explicit run-time type passing to support advanced optimizations such as intensional type analysis, dynamic type dispatch, and tagless garbage collection. Unfortunately, maintaining type information at run time can incur large overhead to the time and space usage of a program. In this paper, we present an optimal type-lifting algorithm that lifts all type applications in a program to the top level. Our algorithm eliminates all run-time type constructions within ane core-language functions. In fact, it guarantees that the number of types built at run time is strictly a compile-time constant. We present our algorithm as a type-preserving source-to-source transformation and show how to extend it to handle the entire SML'97 with higher-order modules.
Copyright © 1996-2021 The FLINT Group
<flint at cs dot yale dot edu>
Yale University Department of Computer Science