The Setting
A context declaration supplies a type for a variable that may occur in both the subject and the expected type of a judgement. Context conversion concerns changing the declared type while keeping those terms fixed.
A pure type specification consists of a collection of sorts, an arbitrary axiom relation , and an arbitrary product-rule relation .β¦ The terms over are generated by variables, sort constants, application , annotated abstraction , and dependent product .β¦ Variables have de Bruijn indices; refers to the nearest binder, and the names in abstractions and products are named source notation. A context is a finite list of declaration types in newest-first order; denotes extension of by the newest declaration type .
Substitution and Typing
For a map , the renaming of a term is the term obtained by replacing by .β¦ It fixes sorts and acts recursively on applications and binder domains; binder bodies use the lifted map defined in (1). The shift of a term is the term obtained by increasing every free index by one. (1)
For an assignment , where is the collection of terms over , the simultaneous substitution in a term is the term obtained by replacing by . It fixes sorts and acts recursively on applications and binder domains, using the lifted substitution in binder bodies. For terms and , the single-variable substitution and bound-variable instantiation are given with this lift in (2); instantiation replaces index zero by and decrements higher free indices. (2)
One-step reduction on terms over is the least relation containing the contraction in (3) and closed under reduction in either part of an application, in an abstractionβs annotation and body, and in a dependent productβs domain and codomain.β¦ The convertibility relation on terms over is the smallest equivalence relation containing one-step reduction .β¦ (3)
The typing relation , between a context and terms over , is the least relation generated by the axiom, variable, weakening, product, abstraction, application and conversion rules in (4).β¦ (4)
A valid context for is a context generated from the empty context by extending a valid context by a type whenever for some sort .β¦ Context equivalence is the relation on contexts defined by (5), requiring validity of both contexts and agreement of their typing judgements.β¦ (5)
The Claim
Theorem 1 (Head conversion). Let and for sorts , and suppose that . The context equivalence is (6): (6)β¦ (7)
What Is Checked
Head conversion is stated over the full typing relation of an arbitrary pure type specification, with both declaration types sorted in the common context and related by convertibility.
Equality of terms is decidable whenever equality of sorts is decidable.