The Setting
Substituting terms for the variables of a typed expression changes both the expression and its expected type. A component interpretation assigns candidates to these substituted types, while admissibility prescribes different conditions on variable images according to their sort profiles.
Fix a pure type system specification , with arbitrary axiom and product-rule relations.✦ Its terms are variables, sort constants, applications, annotated abstractions , and dependent products .✦ Named variables are source notation; contexts are newest-first lists and variables use de Bruijn indices, with zero referring to the nearest binder. The typing judgement is generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules. Product formation uses a triple ; abstraction requires its product type to have a sort, and conversion requires the new expected type to have a sort. A valid context is a context obtained from the empty context by successive extensions with for some sort .✦
Full one-step reduction contracts to and is closed under all term constructors, including annotations and binder bodies.✦ Its generated equivalence relation is convertibility, written .✦ A term is normal if it has no one-step reduct.✦ Write when no infinite reduction starts at .✦ A term is weakly normalizing if a normal term is reachable from it by finitely many reductions; denotes the chosen normal form when one exists, with a fixed fallback otherwise.✦ A neutral term is a term consisting of a variable followed by any finite list of arguments.✦
A legal term in a context is a term that occurs as either the subject or the expected type of a typing judgement in .✦ The pure type system is system weakly normalizing if every legal term in every valid context is weakly normalizing; assume this property for .✦ An expected type in is a literal sort or a term satisfying for some sort .✦
For a term and a substitution assigning terms to free indices, the substituted term is obtained by replacing the free indices of by their images under , lifting under binders to avoid capture.✦ For a term and a map of indices, the renamed term is obtained by replacing the free indices of according to , lifting under binders to avoid capture. The bound variable instance of a term by a term is the term obtained by the single-variable substitution sending zero to and each successor to the variable .✦ The extension of a substitution by a term is the substitution that sends zero to and to .✦ Write for left-associated iterated application.✦ Argument list reduction reduces exactly one entry by one step✦; a strongly normalizing argument list is a list of terms that admits no infinite sequence of argument list reductions.
A saturated context tower is a family of valid contexts of length , each extending its predecessor by a type having a sort. For fixed-level free names, let when , and otherwise; this is index to level reversal.✦ Saturation requires that whenever , arbitrarily large stages satisfy . Bound variables remain de Bruijn indices. The tower typing judgement is defined by (1). (1)✦
Context variable lookup gives the declared type of index as viewed in the full context, shifting free indices once for each intervening extension.✦ A tower typed substitution from is an assignment satisfying (2). (2)✦
Candidates and Processed Profiles
The top candidate and ground candidate at a term are the sets of terms in (3), where a tested argument stack at is written . (3) A tested stack at a term is an argument list generated by the clauses in (4). (4)✦
A set of terms has head expansion closure at if, whenever , the terms are strongly normalizing, and is a strongly normalizing argument list, the condition in (5) holds.✦ A normalization candidate at a term is a set of terms with and head expansion closure at .✦ (5)
The normal-form sort profiles and of a term in a finite context and the tower are the sets of sorts in (6). A source actual type is a term that is either a literal sort or a normal term with for some sort .✦ (6) A feasible sort profile is a nonempty set of sorts satisfying for some valid context and normal term . A feasible product profile triple consists of feasible profiles with , where the product output profile is given by (7).✦ (7)✦
The signed primary profile graph has a positive edge for feasible profiles with . Each feasible product profile triple gives a negative edge and a positive edge . A signed directed walk in the primary profile graph is a finite walk, allowing repeated edges, whose sign is the parity of its negative edges; the empty walk is positive.✦ Directed reachability means existence of such a walk of either parity.✦
A processed profile region relative to a current region is a set of profiles satisfying (8).✦ The last condition is the processed invariant. (8)
The Component Interpretation
A component interpretation for assigns to each context a family of environments , with raw images for an environment . Every is a tower typed substitution, and every tower typed substitution from is the image assignment of some environment. The extension relation relates to and requires . Such an extension exists whenever and .
The interpretation is a set of terms assigned to and . For an expected type , it is a normalization candidate at . Interpretations of convertible expected types are equal. The outside law is (9), for every expected . (9) Under an extension with , the weakening law for an expected type is (10); increases each free index by one. (10)
The product introduction law applies when and both and belong to . For , the introduction condition is (11). (11) For the same product typing and profile conditions, specialization requires that if , , and , then .
An admissible environment relative to satisfies (12) for every context variable lookup . (12)✦
The transported candidate membership predicate is defined by (13). (13)✦ The substitution transport property of a term is the condition in (14). (14)✦
The Claim
Theorem 1. Let be system weakly normalizing, a saturated context tower, and a processed profile region relative to . Let be a component interpretation for . For a strongly normalizing term , the substitution transport property is (15). (15)✦
In the paper, the result reads: assuming the processed invariant on and an implementation of the three interface requirements of Section 3.3 for the current component , if , is strongly normalizing, and is an admissible environment with raw substitution , then .
What Is Checked
The statement is over full reduction and typing for an arbitrary pure type specification, system weak normalization, a saturated context tower, processed profile regions, and a component interpretation with its admissible environments and transport predicate.