Lecture Notes in Computer Science, 2001, Volume 2071/2001, 27-52, DOI: 10.1007/3-540-45332-6_2

Program Representation Size in an Intermediate Language with Intersection and Union Types

Allyn Dimock, Ian Westmacott, Robert Muller, Franklyn Turbak, J. B. Wells and Jeffrey Considine

View Related Documents

Abstract

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.
Partially supported by NSF grant CCR-9417382.
Partially supported by Sun grant EDUD-7826-990410-US.
Partially supported by NSF CISE/CCR ESS grant 9806747.
Partially supported by a Faculty Fellowship of the Carroll School of Management, Boston College.
Partially supported by EPSRC grants GR/L 36963 and GR/L 15685.

Fulltext Preview

Image of the first page of the fulltext document