Some Pragmatic Aspects of Compiling Standard ML with Intersection and Union Types

October 18, 2000
12:30 pm - 1:30 pm
Halligan 111
Speaker: Bob Muller, Boston College
Host: Dr. A. Couch

Abstract

Explicitly typed intermediate languages (TILs) facilitate the safe and efficient compilation of programming languages. The type information in the intermediate representation can be used to guide program analyses and transformations andto support run-time operations such as garbage collection. Typed intermediate languages are also an important debugging aid in the compiler development process and there is growing recognition of their importance in certifying compilers. As part of the Church Project, we have developed the CIL compiler for core SML'97. The CIL compiler employs a TIL using a novel formulation of intersection and union types as well as flow label annotations on both terms and types. The types and annotations approximate the flow of values from the points where theyare defined to the points where they are used. The flow annotations can be used to construct type safe data representations tailored specifically to source/sink pairs and to implement efficient control structures. The CIL intermediate representation duplicates portions of the program where intersection types are introduced and union types are eliminated. This duplication makes it easier to represent type information and to introduce multiple representation conventions. In this talk, I will present an overview of the CIL compiler as well as some empirical data on the compile-time space costs of using CIL as an intermediate language. The data shows that the duplicating nature of CIL has acceptable compile-time space performance in practice.