Allyn Dimock, Ian Westmacott, Robert Muller, Franklyn Turbak,
J. B. Wells, and Jeffrey Considine.
<b>Program Representation Size in an Intermediate
Language with Intersection and Union Types.</b>
<i>Third Workshop on Types in Compilation (TIC'2000)</i>
Published as <i>Lecture Notes in Computer Science 2071</i>,
Robert Harper (Ed.)<hr>The CIL compiler for core Standard ML compiles whole programs using a
novel typed intermediate language (TIL) with intersection and union types
and flow labels on both terms and types.  The CIL term 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 customized data representations.
However, duplication incurs compile-time space costs that are potentially
much greater than are incurred in TILs employing type-level abstraction 
or quantification.  In this paper, we present empirical data on the 
compile-time space costs of using CIL as an intermediate language.  The
data shows that these costs can be made tractable by using sufficiently 
fine-grained flow analyses together with standard hash-consing techniques.  
The data also suggests that non-duplicating formulations of intersection 
(and union) types would not achieve significantly better space complexity.<hr>[<a href="tic00.ps">PS</a>]  [<a href="tic00.pdf">PDF</a>]