The Setting
The question is when interpretations of types control termination of dependent applications and of legal expressions. Let be a pure type specification, with arbitrary axiom and product-rule relations. Its terms are variables, sorts, applications , annotated abstractions , and dependent products .✦
Full one-step reduction is the relation on terms that contracts to the capture-avoiding instantiation and is closed under all term constructors, including annotations and binder bodies.✦ A term is normal if it has no one-step beta reduct.✦ A term is weakly normalizing if it has a normal reduct, denoted . A term is strongly normalizing, written , if it admits no infinite reduction sequence. Beta convertibility is the equivalence relation generated by .✦
The judgement is generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules of .✦ A valid context of is a context obtained from the empty context by extensions with for some sort .✦ A legal expression in a context is a term that occurs either as the subject or as the expected type of a typing judgement in .✦ System weak normalization and system strong normalization require, respectively, weak normalization and strong normalization of every legal expression in every valid context. An expected type in is a literal sort or satisfies for some .✦
Named binders are source notation. Finite contexts are newest-first, with de Bruijn index zero at the nearest binder. Simultaneous substitution replaces free variables by their images and lifts under binders to avoid capture. The single-variable substitution determined by a term sends index zero to and each successor index to the variable of index ; applying it to gives the bound-variable instantiation . Renaming acts on variables, with its lift fixing the bound variable.✦ Write for a declared type viewed in the full context, and for the substitution sending the newest variable to and each older variable to its image under .
Towers, Profiles, and Candidates
A saturated context tower is a family of valid contexts of length , each next context extending the preceding one by a sorted type, in which every type sorted at a stage is declared again beyond every prescribed bound.✦ Tower terms use fixed free levels: at stage , level is translated to index , with larger indices unchanged and renaming lifted under binders.✦ Tower typing is the judgement that some finite stage types both translated expressions.✦ A typed substitution is a substitution satisfying for every context variable .✦
The normal form sort profiles and of a term in a context and in the tower are the sets in (1). (1) A feasible sort profile of is a nonempty set of sorts equal to for some normal in a valid context . A feasible product profile triple consists of three feasible profiles with , where the product output profile is defined by (2). (2)
The signed primary graph has sets of sorts as vertices. Its positive inclusion edges are for feasible with . Each feasible product profile triple gives a negative edge and a positive edge . A signed directed walk is a finite walk, allowing repetitions, whose sign is the parity of its number of negative edges; the empty walk is positive.✦ Directed reachability means the existence of a walk of either sign.✦ A strongly connected component of the primary graph is the set of vertices mutually reachable with some vertex .✦
Write for left-associated iterated application, with .✦ Argument list reduction reduces exactly one argument by one beta step, and a strongly normalizing argument list admits no infinite sequence of such reductions. The top candidate at is the set of typed strongly normalizing terms in (3). (3) The tested stacks form the least family of argument lists satisfying (4). (4)✦ The ground candidate is the set of typed terms passing all tested stacks in (5). (5)✦
A set has head expansion closure at when (6) holds whenever the term on its right has tower type , the terms are strongly normalizing, and is a strongly normalizing argument list. (6)✦ A normalization candidate at is a set with and head expansion closure at . An actual type is a term that is either normal and satisfies for some sort , or is a literal sort.✦
The Component Interface
Fix a weakly normalizing system , a saturated tower , and a set of profiles. A component interpretation interface at is a family of environments , with typed substitution images , representing every typed substitution, together with an extension relation and interpretations subject to the following conditions.
An extension relates an environment over to one over and has images . Whenever and , such an extension exists. For each expected type , is a normalization candidate at . Its conversion, outside-component, and weakening conditions are (7), with expected types in the first line, expected in the second, and , expected, and in the third; denotes renaming into the extended context. (7)
The product introduction and specialization conditions concern with and both . Product introduction is (8) for . (8) Specialization is (9) whenever , , and . (9)
The Claim
Theorem 1. Let be finite, let be system weakly normalizing, and let be a saturated context tower. Suppose that a component interpretation interface exists for every strongly connected component of the primary graph. For every actual type , the ground candidate satisfies (10)✦
For an arbitrary sort set , let be system weakly normalizing and let be a saturated context tower whose ground and top candidates agree at every actual type. Suppose and , with and strongly normalizing. Then (11)✦
For an arbitrary pure type specification , suppose every application with and is strongly normalizing whenever and are strongly normalizing. Then (12)✦
In the paper, the result reads: if the interface can be implemented at every strongly connected component, every legal expression of is strongly normalizing.
What Is Checked
The ground equality (10) is stated over a finite sort set, a saturated tower, system weak normalization, and interfaces at all primary components; the application assertion (11) is stated over tower ground equality and system weak normalization; the system assertion (12) assumes closure of strong normalization under typed application.