Typing in pure type systems

LSV Jutting - Information and Computation, 1993 - Elsevier
LSV Jutting
Information and Computation, 1993Elsevier
Abstract Pure Type Systems (also called Generalized Type Systems) describe the functional
structure of typed systems. They were introduced by S. Berardi and J. Terlouw in order to
give a uniform and simple approach to the theory of typed lambda calculi underlying these
systems. Among the systems which fall under this concept are the systems in Barendregt′ s
cube, various AUTOMATH systems (if the mechanism of definitions is regarded as belonging
to a meta-language), and some logical systems. In Pure Type Systems the typing of terms is …
Abstract
Abstract Pure Type Systems (also called Generalized Type Systems) describe the functional structure of typed systems. They were introduced by S. Berardi and J. Terlouw in order to give a uniform and simple approach to the theory of typed lambda calculi underlying these systems. Among the systems which fall under this concept are the systems in Barendregt′ s cube, various AUTOMATH systems (if the mechanism of definitions is regarded as belonging to a meta-language), and some logical systems. In Pure Type Systems the typing of terms is governed by sets of axioms and rules, different sets of axioms and rules giving rise to different systems. In Geuvers and Nederhof (J. Funct. Programming1 (2), 155-189 (1991)) it is shown that in a subclass, the class of functional systems, the type of a term is unique up to β-equivalence. In functional systems also a" thickening lemma" is proved, which we call" strengthening": If Γ 1, x: A, Γ 2⊢ b: B and x∉ FV (Γ 2)∪ FV (b)∪ FV (B) then Γ 1 Γ 2⊢ b: B. Strengthening has been proved for the AUTOMATH systems by van Daalen and for the theory ECC by Luo. We analyse typing in non-functional systems. We show that, although the type of a term in such systems is not unique, the various possible types have a simple common structure. In fact if a term has types A and B which are not β-equivalent, then A≥ Π x 1: C 1... Π x m: C m. s 1 and B≥ Π x 1: C 1... Π x m: C m. s 2 where s 1 and s 2 and are sorts. As a consequence strengthening holds too, and we have also uniqueness of domains: If Γ⊢ a: Π x: A 1. B 1 and Γ⊢ a: Π x: A 2. B 2 then A 1= β A 2. Finally we prove decidability: if all terms in a Pure Type System normalize and the set of sorts of that system is finite then the typing relation is decidable.
Elsevier