The Setting
The construction concerns normalization candidates for dependent products in a component of the sort-profile graph, with a polarity attached to each variable. An argument extends both the substitution and the polarity assignment used to interpret a codomain.
A pure type specification consists of sorts , an arbitrary axiom relation , and an arbitrary product-rule relation .β¦ Its terms are variables, sorts, applications , annotated abstractions , and dependent products .β¦ Variable names are source notation; variables in the library have de Bruijn indices, with zero at the nearest binder, and contexts are newest-first lists. The judgement is pure type system typing, with the axiom, variable, weakening, product, abstraction, application, and conversion rules.β¦ Product formation uses triples in ; conversion replaces an expected type by a -convertible type that itself has a sort. A valid context is obtained from the empty context by extensions with for some sort .β¦
Full one-step reduction contracts to and is closed under application, annotations, and both binder bodies.β¦ A normal form is a term with no such reduct.β¦ Weak normalization means reaching a normal form in finitely many stepsβ¦; strong normalization means that no infinite reduction sequence starts at the term.β¦ Conversion is the least equivalence relation containing this reduction.β¦ A term is legal in when it occurs as either subject or expected type in a typing judgement.β¦ System weak normalization requires every legal term in every valid context to be weakly normalizing.β¦ Write for the chosen normal form when one exists, with a fixed fallback otherwise.β¦
The normal form sort profile and product output profile are the sets in (1). (1) A feasible profile is a nonempty set of sorts realized as by a normal term in a valid context .β¦ A feasible product profile triple consists of feasible profiles satisfying .β¦
The signed primary profile graph has a positive edge for feasible profiles with . Each feasible product profile triple gives a negative domain edge and a positive codomain edge . A signed directed walk is a finite walk, allowing repetitions, whose sign is the parity of its negative edges; the empty walk is positive.β¦ Directed reachability means the existence of such a walk of either sign.β¦ A strongly connected component is the set of vertices mutually reachable with some vertex .β¦
Tower Candidates and Environments
A saturated context tower is a sequence of valid contexts of length , each extending its predecessor by a type with a sort. Tower terms use fixed levels for free variables. At stage , index-to-level reversal sends to and fixes other indices; its action by variable renaming translates these free levels to context indices and leaves bound variables fixed. Tower typing means that some stage types both translated expressions.β¦ Saturation requires that every fixed-level type sorted at a stage be declared again at a stage , with , beyond any prescribed bound. The tower profile of a term in the tower is the set of sorts in (2). (2)β¦
The top candidate at a tower type in is the set in (3). (3) Write for left-associated iterated application to an argument list.β¦ Argument-list reduction reduces exactly one entry by one full stepβ¦; an argument list is strongly normalizing when this relation admits no infinite sequence from it.β¦ A tested stack at is an argument list generated by the empty stack at every type and by at when and is tested at .β¦ The ground candidate at a tower type in is the set in (4). (4) A normalization candidate at is a set with that is closed under head expansion.β¦ This closure means that belongs to whenever it has tower type , the terms and the argument list are strongly normalizing, and .β¦
A simultaneous substitution is a map from variable indices to terms that acts recursively on terms, with capture avoided under binders.β¦ Its lift fixes index zero and sends to with its free indices increased by one. Single-variable substitution sends zero to and to variable ; applying it to is the bound-variable instantiation . Write for the variable renaming that increases every free index by one. Context variable lookup reads a declarationβs type in the full context, increasing its free indices once for the declared variable and once for each newer declaration.β¦
A typed substitution is a substitution satisfying whenever context lookup assigns to in .β¦ A variable polarity assignment is a map .β¦ An environment is a pair with typed.β¦ Substitution extension and bit extension are defined by (5). (5) A one-variable environment extension of by is an environment satisfying (6); its new polarity is unrestricted. (6)β¦
The One-child Interpretation
An expected type in is a literal sort or an expression with for some sort .β¦ The recursive one-child interpretation is a set of tower terms. It takes the top candidate at unless both and lie in . In that active case, a product uses the raw product candidate: its functions belong to , and application to each term in the recursive domain interpretation must belong to the recursive codomain interpretation under and for each bit . For a nonproduct with a variable head, let be the index of that head variable. The interpretation then selects when and the lower candidate when ; with no variable head it selects the top candidate. The normal-form candidate interpretation of an expected type in under an environment is the set of tower terms defined in (7). (7)β¦
A component interpretation for and is a family of environments realizing every typed substitution and admitting an extension by whenever and , together with an interpretation of expected types by normalization candidates. Its laws are conversion invariance, the top interpretation outside , preservation under sorted weakening, product introduction, and specialization to a typed argument. Write for the class of these interpretations.
The Claim
Theorem 1. Let be weakly normalizing, let be a saturated context tower, and let be a set of profiles. Suppose , let , and assume that both and belong to . For every term , product membership is given by (8). (8)β¦
Suppose in addition that is a strongly connected component of the primary profile graph and no feasible product profile triple has all three entries in . The one-child component interpretation is (9). (9)β¦ For the product and environment above, suppose , , and . Specialization gives (10). (10)β¦
In the paper, the result reads: if no profile triple has all three vertices in , then the bit-parametrized candidates implement the candidate interface.
What Is Checked
The claims concern full reduction in a weakly normalizing pure type system, saturated context towers, and typed substitutions equipped with variable polarities; the component interpretation and specialization also require a primary component with no feasible product profile triple wholly inside it.