Research

People

Publications

Software

Support

Links

Internal

Optimal Type Lifting

Last modified: Tue Mar 14 19:31:29 2000 GMT.

Authors

Abstract

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.

Published

• In the Second International Workshops on Types in Compilation, Kyoto, Japan, pages 156-177, March 1998. Lecture Notes in Computer Science Vol 1473, Springer-Verlag.
  • Gzipped Postscript [125k]
    
  • PDF
    
  • BibTeX Entry
    
• Technical Report YALEU/DCS/TR-1159, Department of Computer Science, Yale University, August 1998.
  • Gzipped Postscript [189k]
  • PDF
  • BibTeX Entry