Program representation size in an intermediate language with intersection and union types

Abstract. The CIL compiler for core Standard ML compiles whole pro-grams using a novel typed intermediate language (TIL) with intersec-tion and union types and ow labels on both terms and types. The CIL term representation duplicates portions of the program where intersec-tion types are introduced and union types are eliminated. This dupli-cation 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 quantication. 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 suÆciently ne-grained ow analyses together with standard hash-consing techniques. The data also suggests that non-duplicating formulations of intersection (and union) types would not achieve signicantly better space complexity