The Setting
The candidates assigned to a dependent product must account for its domain and its codomain with opposite variances. The primary graph records these dependencies between sort profiles. The construction concerns a strongly connected component of this graph.
A pure type specification consists of a set of sorts and arbitrary axiom and product-rule relations.✦ A term of the pure type specification is an expression generated by variables, sort constants, application, annotated abstraction , and dependent product .✦ We write named variables for de Bruijn variables and extend contexts on the left, so that their declarations are in newest-first order. The judgement uses the typing rules of , including conversion by convertibility. A valid context is a finite sequence of declarations built from the empty context by adjoining a type to a previously constructed context whenever for some sort .✦
Full reduction is the relation on terms that contracts to and permits reduction in every annotation and binder body.✦ Convertibility is the equivalence relation on terms generated by full reduction.✦ A normal term is a term with no immediate reduct✦; a weakly normalizing term is a term that reaches a normal term✦; a strongly normalizing term is a term that admits no infinite reduction sequence.✦ For every term , write for its chosen full normal form when one exists, and for a fixed arbitrary term otherwise.✦ A legal term in a context is a term that occurs as either the subject or the expected type of a typing judgement in .✦ System weak normalization of a pure type specification is the property that every legal term in every valid context is weakly normalizing.✦ An expected type in a context is either a literal sort or a term with for some sort .✦
A saturated context tower is a sequence of valid contexts of length at stage , each extended by one sorted declaration at the next stage, in which every type available at a finite stage is declared again arbitrarily late.✦ Free names are held fixed along the tower. Tower typing means that the judgement for both and holds in some finite prefix, after translating those free names to context indices.✦ The normal form sort profiles are (1) A feasible profile is a nonempty set of sorts occurring as in (1) for a normal term in a valid context.✦
The product output profile and feasible product triples are specified by (2) A feasible product triple is a triple of feasible profiles satisfying (2).✦ The primary graph has a positive edge for feasible profiles with ; each triple in (2) gives a negative edge and a positive edge .✦ A signed directed walk has the parity of its number of negative edges, with the empty walk even.✦ Directed reachability from to means that a signed directed walk from to exists, with either parity.✦ A strongly connected component of the primary graph is the set of vertices mutually reachable with a chosen root .✦ Choose a root-to- walk for each and let be its parity; put outside .✦
Candidates and the Signed Step
The top set at a tower type consists of its typed strongly normalizing terms: (3)✦ A tested argument stack at a tower type is the empty list, or a list at with from (3) and tested at .✦ Write for left-associated iterated application.✦ The ground set and the bounds on a candidate at are (4) A normalization candidate at a tower type is a set satisfying (4) and head expansion closure at .✦ A set of terms of tower type is closed under head expansion if a redex with trailing arguments belongs to whenever its contraction belongs to , provided the redex with those arguments has tower type , its annotation, body and contracted argument are strongly normalizing, and the trailing argument list is strongly normalizing.✦ Argument list reduction reduces one entry by one full step✦; a strongly normalizing argument list admits no infinite sequence of such reductions.✦
For a domain , a codomain , a set of arguments and a family of sets of terms, the indexed product test is (5)✦ Signed candidates use inclusion for sign and reverse inclusion for sign , with the same underlying candidate sets.✦ A signed candidate vector is a family assigning a candidate to each term , ordered with sign .✦ The order on vectors is pointwise in these signed orders. Component lookup is (6)✦ Using (5) and (6), the signed candidate operator assigns the following set, with the signed order at : (7)✦
Environments and the Component Interface
A typed substitution is a map assigning a raw term to each context variable such that , with viewed in the full context by variable lookup.✦ Simultaneous substitution is capture-avoiding, as is bound variable instantiation . Variable renaming acts on free variables and is lifted under binders.✦ The extension of a substitution is the substitution assigning to the newest variable and retaining the old images for the remaining variables; in indices it sends to and to .✦
The environments used here are all typed substitutions from into .✦ For environments and , write for the images of , and for . For a least signed fixed point of the operator in (7), the actual interpretation and its environmental interpretation are (8)
A component interface for is a tuple consisting of environments representing every typed substitution, an extension relation agreeing with substitution extension, and an interpretation of expected types by candidates at their substituted normal forms. Whenever and , an extension must exist. The interpretation must respect conversion of expected types and weakening along such an extension. Whenever either or lies outside , the interpretation must equal .
The product laws of a component interface apply when and both and belong to . If and for every and every extension , product introduction puts in the product interpretation. If , and , specialization requires . Write for the class of component interfaces with these laws.
The Claim
Theorem 1 (Proposition 22). Let satisfy system weak normalization, let be a saturated context tower for , and let be a strongly connected component of the primary graph with no odd closed walk based at a vertex of . For signed vectors , (9)✦ The least signed fixed point is (10)✦ The environments and interpretation in (8) give a component interface (11)✦
In the paper, the result reads: if , denoted there, has no odd closed walk, it admits the candidate interface.
What Is Checked
The assertions (9), (10) and (11) are stated over full reduction and tower typing for a weakly normalizing specification, with signs chosen on a primary component having no odd closed walk. The top set is a normalization candidate at every .✦ For the construction in (8), is a candidate even for an arbitrary term ✦; the outside equality also holds for arbitrary whenever .✦