MIT Department of Electrical Engineering & Computer Science

DATE: MONDAY, APRIL 3, 1995

TIME: Refreshments at 2:00
TALK AT 2:15

PLACE: NE43-518

Type-Based Implementations of High-Level Programming Languages

Greg Morrisett
Carnegie Mellon University

Compilers for modern programming languages such as Standard ML (SML) and Modula-3 must emit code to manipulate objects with unknown or variable types. Most compilers force objects of variable type to fit into a "universal" representation so that one piece of code be generated to manipulate the object, regardless of its actual type. But a universal representation requires indirection and/or tags on values; these restrictions waste space, destroy locality, and force additional instructions to be executed. Furthermore, these restrictions prevent direct access to the untagged, flattened data structures imported from the "real" world of the operating system, C and Fortran libraries, communications hardware, etc.

I have addressed these issues by re-examining the role of types in the compilation of modern programming languages. Instead of restricting representations so that types can be ignored, I have developed a sophisticated typed intermediate language that allows types to be examined at compile, link, or even run time. This allows routines with variably-typed objects to select the appropriate operations needed to manipulate these objects in their natural representation. Compilation of a source language is specified as a type-directed translation to this intermediate form. The compilation is carefully arranged to support aggressive optimization of the resulting code.

To demonstrate the applicability of my approach, I am constructing a new compiler for SML that supports flattened, multi-argument functions and results, unboxed, untagged integers an floating-point values, flattened arrays, tag-free overloaded operators such as polymorphic equality, and tag-free garbage collection.

HOST: Prof. Stephen Ward