Abstract

We present a type inference system for pure λ-calculus which includes, in addition to arrow types, also universal and existential type quantifiers, intersection and union types, and type recursion. The interest of this system lies in the fact that it offers a possibility to study in a unified framework a wide range of type constructors. We investigate the main syntactical properties of the system, including an analysis of the preservation of types under parallel reduction strategies, leading to a form of the subject-reduction property. We describe a model for this system where types are special subsets of a D∞ model for λ-calculus, without imposing any formal contractiveness constraint on types of the kind considered for a closely related system by MacQueen, Plotkin and Sethi