Franklyn Turbak, Allyn Dimock, Robert Muller, and J. B. Wells. Compiling with Polymorphic and Polyvariant Flow Types. ACM SIGPLAN Workshop on Types in Compilation (TIC '97), June, 1997.
Optimizing compilers for function-oriented and object-oriented languages exploit type and flow information for efficient implementation. Although type and flow information (both control and data flow) are inseparably intertwined, compilers usually compute and represent them separately. Partially, this has been a result of the usual polymorphic type systems using forall and exists quantifiers, which are difficult to use in combination with flow annotations.

In the Church Project, we are experimenting with intermediate languages that integrate type and flow information into a single flow type framework. This integration facilitates the preservation of flow and type information through program transformations. In this paper we describeλCIL, an intermediate language supporting polymorphic types and polyvariant flow information and describe its application in program optimiziation. We are experimenting with this intermediate language in a flow and type-directed compiler for a functional language. The types ofλCILencode flow information (1) via labels that approximate sources and sinks of values and (2) via intersection and union types, finitary versions of universal and existential types that support type polymorphism and (in combination with the labels) polyvariant flow analysis. Accurate flow types expose opportunities for a wide range of optimizing program transformations.

[PS] [PDF]