The Setting
Labels on applications, abstractions and dependent products distinguish the modes of an argument and a result. Erasure removes these labels from a typed term and its expected type. The structural metatheory concerns typing before erasure and the relation between labelled reduction and ordinary reduction.
A pure type specification consists of a collection of sorts, an axiom relation , and a product-rule relation .✦ The two modes are and .✦ A label is one of , with argument and result modes given by (1). (1)
A labelled term over is a variable, a sort, an application , an annotated abstraction , or a dependent product .✦ Binder names denote capture-avoiding syntax; indexed notation uses de Bruijn variables , with nearest its binder, and newest-first contexts. For a renaming of variable indices, the renamed term is obtained from by replacing each free index by and preserving labels; under a binder, the lift of fixes zero and sends to .✦
A simultaneous substitution is an assignment of a term to each variable index. The term substitutes these images throughout , preserving labels and avoiding capture.✦ Write for successor renaming. The lift under a binder and the single substitution used for instantiation are given by (2); the same operations apply to ordinary terms. (2)
Write for the erasure of a labelled term , as in (3). The erasure of a labelled context is the ordinary context obtained by erasing each entry of . (3)✦
Labelled one-step reduction is the compatible closure of (4), including every annotation and binder body.✦ Write for its reflexive transitive closure and for its equivalence closure. Ordinary reduction , its closure , and ordinary convertibility use the corresponding unlabelled head contraction and compatible closure. (4)
An ordinary term is normal, written , if it has no one-step reduct.✦ An ordinary term is weakly normalizing, written , if a normal term is reachable from by .✦
Typing and Modes
Labelled typing is the judgment generated by the axiom, variable, weakening, product, abstraction, application and conversion rules.✦ In newest-first notation, is the empty context and is the extension of by . An axiom gives . If , the variable rule gives ; weakening shifts both the subject and its expected type when extending by . If , , and , the product has sort . If and the product has a sort in , the abstraction has type . If and , the application has type in . Conversion replaces an expected type by a -convertible type that has a sort in . Ordinary typing uses these rules without labels.✦
A valid context is either the empty context or an extension of a valid context by a term with a sort in ; write for this condition.✦ Context lookup gives the type of index in the whole context: its rules are and whenever .✦ A typed substitution is an assignment satisfying (5). (5)✦
A mode context is an assignment of a mode to each variable index. The extension of a mode context by a mode is the mode context that sends zero to and to .✦ A term has mode under a mode context , written , according to the rules in (6). (6)✦
The generation condition describes the immediate typing data for the outer constructor of . For , it requires a lookup with . For , it requires an axiom with . For , it requires , , and . For , it requires , , and . For , it requires , , , and . All the types and sorts mentioned in each case are existentially chosen.
The Claim
Theorem 1 (Structural metatheory and erasure). Let be a pure type specification. For any labelled judgment , context validity and regularity are expressed by (7) and (8). (7)✦ (8)✦
For this judgment, let be valid and let be a typed substitution. Substitution has the conclusion (9). (9)✦
Suppose , , , and . Context head conversion gives (10). (10)✦
Every judgment has the generation property (11). (11)✦
Suppose and . Subject reduction gives (12). (12)✦
For arbitrary labelled terms with and , confluence is (13). (13)✦
Suppose . Product compatibility has the conclusion (14). (14)✦
For , erasure preserves typing as in (15). If , a labelled step lifting that reduction exists as in (16). (15)✦ (16)✦
Suppose , , and . A reduct with normal erasure satisfies (17). (17)✦
What Is Checked
The claims concern labelled terms and typing over arbitrary axiom and product-rule relations, capture-avoiding substitution, and full compatible reduction; the normal erasure statement additionally assumes the mode judgment and weak normalization of the erased subject.