The Setting
For a dependent function, strong normalization of the function is compared with strong normalization after every tested sequence of applications. A component interpretation controls this comparison within a region of sort profiles.
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 .β¦ The judgement is generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules of .β¦ A valid context is built from the empty context by adjoining when for some sort .β¦
Full one-step reduction contracts to and is closed under every term constructor, including annotations and binder bodies.β¦ Here is the single-variable substitution instantiating the bound variable, and denotes capture-avoiding simultaneous substitution. Renaming acts on free variables with capture avoided.β¦ The equivalence generated by this reduction is convertibility, written .β¦
A normal term is a term with no one-step reduct.β¦ A weakly normalizing term is a term with a normal reduct, written for its chosen normal form. A strongly normalizing term is a term from which no infinite full reduction starts; this condition is written .β¦ A legal term in is a term that occurs as either the subject or the expected type of a typing judgement in .β¦ System weak normalization means that every legal term in every valid context is weakly normalizing.β¦ An expected type in is a term that is a literal sort or satisfies for some sort .β¦
A saturated context tower is a chain of valid contexts of length , each extended by a sorted declaration at the next stage. Every type over fixed free levels that is sorted at some stage is declared again beyond every later bound. Tower typing means that the subject and expected type admit ordinary typing in some finite prefix, after translating their fixed free levels to that prefixβs newest-first variable indices.β¦ Named variables in the formulas denote these terms.
Ground Tests and Candidates
For a term , the top candidate in is the set of typed strongly normalizing terms defined by (1). (1)β¦
Write for left-associated iterated application, with .β¦ A tested argument stack at is a list of terms generated by (2). (2) The ground tested-stack candidate is the set in (3). (3)β¦
Argument-list reduction is the relation on argument lists in which exactly one argument changes by one full step.β¦ A strongly normalizing argument list is an argument list that admits no infinite sequence of argument-list reductions; write for this condition.β¦ A set of terms is closed under head expansion at when it satisfies (4) for every annotation , body , argument , and further argument list . (4)β¦ A normalization candidate at is a set with that is closed under head expansion at .
Profiles and Processed Regions
The normal-form sort profile and the tower profile are the sets in (5); they retain all possible sort witnesses. (5) A feasible sort profile is a nonempty set realized as by a normal term in a valid context .β¦ The product output profile of sets of sorts and is the set of sorts defined by (6). (6) A feasible product profile triple consists of feasible profiles with .β¦
The signed primary profile graph has exactly the edges in (7). (7)β¦ A signed directed walk is a finite directed walk whose sign is the parity of its number of negative edges; the empty walk is positive.β¦ Directed reachability means that such a walk exists, with either sign.β¦
Fix a current region . A source actual type is either a normal term with for some sort , or a literal sort.β¦ A processed profile region relative to is a set of profiles satisfying (8). (8)β¦
The Component Interpretation
Assume system weak normalization for . A tower-typed raw substitution from to is an assignment of a term to each context variable that satisfies whenever context lookup assigns the type , viewed in the full context.β¦ A component interpretation for assigns to each context a set of environments with tower-typed image substitutions , and represents every tower-typed raw substitution by an environment.
The extension relation relates an environment over to one over whose image substitution sends to and retains the old images. Such an extension exists whenever and .
The interpretation of an expected type is a normalization candidate at . Convertible expected types have equal interpretations. The outside law is (9) for every expected type . (9) Weakening preserves along whenever and is expected in , with renamed into the extended context.
For the product laws, put and . Both laws apply when , , and . Product introduction is the condition (10), with ranging over environments on . (10) Specialization is (11) for every with . (11)
The Claim
Theorem 1. Let be a system weakly normalizing pure type specification, let be a saturated context tower, and let a component interpretation for be given. For a source actual type with , the candidates satisfy (12). (12)β¦
What Is Checked
The claim is stated over the full reduction and typing judgements of an arbitrary pure type specification, a saturated context tower, and a component interpretation under system weak normalization.