The FLINT Project

Research

People

Publications

Software

Support

Links

Internal

Optimal Type Lifting

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

Authors

Bratin Saha
Zhong Shao

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.
  • Technical Report YALEU/DCS/TR-1159, Department of Computer Science, Yale University, August 1998.


Copyright © 1996-2017 The FLINT Group <flint at cs dot yale dot edu>
Yale University Department of Computer Science
Validate this page
colophon