Flexible type analysis

Run-time type dispatch enables a variety of advanced optimization technique s for polymorphic languages, including tag-free garbage collection, unboxed function arguments, and flattened data structures. However, modern type-pr eserving compilers transform types between stages of compilation, making ty pe dispatch prohibitively complex at low levels of typed compilation. It is crucial therefore for type analysis;st these low levels to refer to the ty pes of previous stages. Unfortunately, no current intermediate language sup ports this facility. To fill this gap, we present the language LX, which provides a rich languag e of type constructors supporting type analysis (possibly of previous-stage types) as a programming idiom. This language is quite flexible, supporting a variety of other applications such as analysis of quantified types, anal ysis with incomplete type information, and type classes. We also show that LX is compatible with a type-erasure semantics.