The Setting
A typing judgement relates an expression to an expected type, and both may contain redexes. Normalizing a subject and normalizing its expected type are distinct operations. The outer shape of an expression also matters when that expression is normal and has a sort as its type.
A pure type specification consists of a collection of sorts, an axiom relation , and a product-rule relation .✦ Both relations are arbitrary. The terms over are generated by the grammar in (1), where denotes a variable and a sort: (1)✦ The variables in (1) are written with names; in de Bruijn notation, index zero denotes the nearest enclosing binder. Contexts are finite lists in newest-first order, with denoting extension of .
A variable renaming is a map on variable indices, acting recursively on terms.✦ Under a binder its lift fixes zero and sends to . A simultaneous substitution is a map from variable indices to terms, extended recursively to terms.✦ Its lift under a binder fixes index zero and replaces index by with its free indices increased by one. Both operations act on the annotations as well as the bodies of abstractions and products. The single-variable substitution determined by a term sends zero to and each to the variable of index .✦ Bound-variable instantiation of a body by a term is the capture-avoiding action on of the single-variable substitution determined by , written in named notation.✦
One-step reduction is the least relation containing the contraction in (2) and closed under every term constructor, including abstraction annotations and the domains and bodies of dependent products: (2)✦ Write for zero or more such steps. convertibility is the smallest equivalence relation containing .✦
The typing judgement is the least relation generated by the rules in (3), where denotes the empty context and context extension uses a fresh variable : (3)✦ A valid context is a finite list generated from the empty context by adjoining to a valid context whenever for some sort .✦ A legal term in is a term occurring as a subject or an expected type of a typing judgement, as specified in (4): (4)✦
A term is normal if it has no one-step reduct.✦ A term is weakly normalizing if some normal term is reachable from by .✦ For a weakly normalizing term , a chosen normal form is a normal term reachable from by , as specified in (5): (5)✦ A system is weakly normalizing if every legal term in every valid context is weakly normalizing, including subjects and expected types.✦
A neutral term is a variable applied to zero or more arguments, each argument being an arbitrary term.✦
The Claim
Theorem 1. Let be a weakly normalizing pure type system and suppose . The subject and expected type conclusions are (6) and (7), respectively: (6)✦ (7)✦ For any pure type system, suppose for a sort and is normal. Its shape satisfies (8): (8)✦ For weakly normalizing terms and with , their chosen normal forms satisfy (9): (9)✦
What Is Checked
The typing conclusions concern the judgement in (3) under system weak normalization; the shape conclusion assumes sorted typing and normality, while the conversion conclusion concerns weakly normalizing terms independently of typing. Equality of the terms in (1) is decidable whenever equality of sorts in is decidable.