The Setting
Substitution into a dependent type may change its sort profile and the observation parameters available for testing its terms. The component interpretation assigns normalization candidates to the resulting actual types.
Let be a pure type specification, with arbitrary axiom and product-rule relations, and let be finite.β¦ Terms are variables, sorts, applications, annotated abstractions , and dependent products .β¦ The variable names in these formulas are source notation; ordinary contexts use de Bruijn indices and newest-first lists. A valid context is the empty context or an extension of a valid context with for some sort .β¦ The judgement is generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules of .β¦
Full one-step reduction contracts to and permits reduction in every subterm, including annotations and binder bodies.β¦ Convertibility is its equivalence closure.β¦ A normal term has no immediate reduct; a weakly normalizing term reaches a normal term, and a strongly normalizing term admits no infinite reduction sequence. The choice is the full normal form when one exists and a fixed fallback otherwise.β¦ A term is legal in when it occurs as either subject or expected type in a judgement there.β¦ Assume system weak normalization: every legal term in every valid context is weakly normalizing.β¦ An expected type in is an expression that is either a literal sort or satisfies for some .β¦
A substitution assigns raw terms to variables; denotes capture-avoiding simultaneous substitution.β¦ Under a binder its lift fixes the bound variable and shifts the free indices in every image.β¦ The single-variable substitution giving sends zero to and decrements higher indices.β¦ An extension sends the new zero index to and each successor index to its old image.β¦ Renaming acts on free variables and uses the corresponding lift under binders; write for renaming by successor.β¦ Iterated application is left-associated.β¦
Fix a saturated context tower . Its stage is a valid context of length , and each stage extends its predecessor by a sortable declaration. Every sortable expression with fixed free levels is declared again beyond every stage bound at which it is available. Tower typing means that some finite stage types both expressions after translating their free levels to indices: at stage , a level becomes , and larger indices are unchanged.β¦ A typed substitution from to assigns to each variable with declaration type , viewed in the full context, an image of tower type .β¦
The normal-form sort profiles and the axiom and product output profiles are the sets in (1). (1) A feasible profile is a nonempty set for a normal term in a valid context.β¦ A feasible product profile triple consists of feasible profiles with .β¦
The primary signed graph is a signed directed graph on feasible profiles, with a positive edge for a strict inclusion of feasible profiles. Each feasible product triple contributes a negative domain edge and a positive codomain edge . A signed directed walk is a finite walk whose parity counts its negative edges; the empty walk has even parity.β¦ Directed reachability permits either parity, whereas positive reachability uses only positive edges. A strongly connected component is the set of vertices mutually reachable with some fixed vertex.β¦
Let be a family of profiles. Its observation layers are the profiles positively reachable in the primary graph from some nonempty with .β¦ The secondary signed graph has the positive primary edges between observation layers; a feasible triple of observation layers also contributes its negative domain edge.β¦ A direct layer is an observation layer admitting a feasible triple with .β¦ An active layer reaches a direct layer in the secondary graph.β¦ A plain layer has walks to direct layers of both parities.β¦ A free layer of sign is a nonplain profile with a walk of parity to a direct layer.β¦
A forbidden configuration consists of a secondary strongly connected component of plain layers containing a negative edge, together with a feasible triple and a sort such that , , and positively reaches in the primary graph.β¦ Assume that no such configuration exists.
Normalization Candidates
The top candidate consists of the typed strongly normalizing terms in (2). Argument-list reduction reduces one component by one full beta step; a strongly normalizing argument list admits no infinite sequence of these reductions. (2)β¦ A tested stack at is an argument list that is either empty or, when , has first argument and a remaining stack tested at . The ground candidate is the set in (3). (3)β¦ A normalization candidate at is a set with that is closed under typed head expansion.β¦ This closure admits whenever it has type , the annotation, body, and first argument are strongly normalizing, the remaining argument list is strongly normalizing, and .β¦ Write for these candidates.
An actual type is a normal sortable tower expression or a literal sort.β¦ A candidate assignment is a family indexed by actual types , with a member of at each index.β¦ The top assignment chooses at each coordinate; replaces just the coordinate at .
Plain and Free Observations
A plain observation schema on a set of nodes is an assignment to each node of a set of keys , a target in for each key, and an optional domain in .β¦ A continuation path is a finite sequence of successive keys.β¦ A payload occurrence on a path selects a key on that path with a present domain.β¦ The recursive domain dependency means that occurs as a domain after finitely many continuations from .β¦ For a parameter family , single-frame parameters are assignments of a value in to a present domain of ; path parameters assign such a value to every payload occurrence. Empty paths have unique parameters. Prefixing a path combines its first frame parameters with its remaining parameters.β¦
For a parameter family and base set , the plain table space is the set of functions assigning a result in to each path from and its parameters.β¦ When is well-founded, the recursive plain space is given by (4); its unfolding is the identification with this table space. (4)β¦ The prefix decomposition is (5). The distinguished element with base is the constant table.β¦ (5)β¦
For the actual plain schema, a node is a normal sortable type with plain profile .β¦ A plain application key consists of a decomposition and a normal argument with and active profile .β¦ Its target is .β¦ Its domain node is when is active, and its domain is absent otherwise. Write for the resulting actual plain observation space with candidate assignments as bases. A tagged plain observation is a pair with .β¦ The default actual plain observation is the constant table with base .β¦
For key set , plain payload set , and opposite-value set , an optional frame payload is absent, an element of , or an element of .β¦ A free observation frame pairs a key with such a payload.β¦ A continuation stack is a finite list of frames; an exit stack is a continuation stack followed by one further frame designated as terminal. With bases and exit results , the free table space consists of a -valued function on continuation stacks and an -valued function on exit stacks.β¦ Mapping opposite values leaves keys and plain payloads fixed, and acts componentwise on stacks. Reindexing a table along a map precomposes its stack arguments.β¦
The finite stages and signed spaces are defined in (6). The successor map is empty at stage zero and thereafter reindexes tables twice along the preceding successor map.β¦ Stage inclusions iterate these successors.β¦ $$Z_0=\varnothing,\qquad Z_{k+1}=\mathcal F(\mathcal F(Z_k)),\qquad \mathcal M=\varinjlim_k Z_k,\qquad \mathcal Q=\mathcal F(\mathcal M).$$(6) The finite-stage embedding sends to its class in .β¦ Restriction of a positive table to stage reindexes along this embedding.β¦ Finite-stage behavior at stage reindexes along restriction to stage ; represented negative behavior is its induced map on the direct limit. A table slice prefixes one frame to the continuing part of each stack.β¦ The negative slice chooses a representative of the sliced negative behavior.β¦
A constant table is a free table that returns fixed and on the two kinds of stack.β¦ The default positive observation is that table, and the default negative observation is its stage-one class. A raw lambda table has a base , a body action from frames over to , and an exit action to . It returns on the empty continuation, follows the selected bodyβs represented behavior after a first frame, and uses the exit action on a lone terminal frame.β¦
The actual signed spaces use terms as keys, tagged plain observations as plain payloads, candidate assignments as bases, and optional tagged plain observations as exit results. Denote the resulting positive and negative spaces by and . Their application frames have opposite payloads in and , respectively.
Typed Values and Environments
A normalized active type is a normal sortable tower type with active profile.β¦ An active actual type is a normalized active type, and a plain normalized active type is a plain node.
A raw observation value is an observation with a plain, positive, or negative tag.β¦ A typed value at , written , is a raw value whose tag fits : a plain tag records exactly , a positive tag requires a positive free profile, and a negative tag requires a negative free profile.β¦ The base assignment of a typed value at is the candidate assignment at its empty observation: the first plain prefix coordinate, the empty positive continuation, or the empty continuation of represented negative behavior.β¦
An optional payload fits a domain when it is absent at an inactive domain, or is present with a raw value fitting .β¦ At an active domain its value can be extracted as a typed value.β¦ Plain value injection tags an element of ; plain extraction selects its representing observation. Positive and negative extraction select the corresponding signed observations. For a normalized active type with plain profile and a typed value , plain tagging is the tagged plain observation consisting of the plain node of and the plain observation representing .β¦ Typed projection at an active type keeps a fitting raw value and otherwise returns the distinguished value obtained by tagging the default observation appropriate to that type.β¦ A checked exit projects a present plain result and uses the distinguished value for an absent result.β¦
An active application key at consists of a decomposition and a normal argument with and active profile , where is active. A plain source permits its conversion to a plain application key.β¦ Its active target is .β¦ Plain payload decoding returns the domainβs plain tag when its domain is active and returns absence otherwise; plain payload encoding supplies the corresponding single frame parameters. Positive frame encoding retains a plain tag or an opposite negative value; negative frame encoding retains a plain tag or an opposite positive value. The respective decoders restore these raw tags and preserve absence.
A free application gate at , key , payload , and an exit flag holds when an active application key has argument , its domain admits , and its target is plain exactly when the exit flag is set.β¦ The gated key for a free application gate is a chosen active application key satisfying the gateβs argument, payload, and exit conditions.β¦ A lambda action at is a family of typed target values indexed by active application keys and fitting domain payloads.β¦ Plain lambda prefixing places this action in the continuation coordinates of the plain prefix decomposition.β¦
For a free source of either sign, lambda continuation returns the corresponding signed extraction of the action at a continuation gate; at a failing gate it returns the signed default with base and no exit. The lambda exit operation returns a plain tagging of the action at an exit gate and returns absence otherwise.β¦ The positive lambda table uses these operations, with empty base .β¦ Negative lambda behavior is the raw lambda table with negative continuation and the lambda exit operation.β¦ The observation associated with a negative behavior is a chosen representative when one exists and the negative default otherwise.β¦ Lambda observation values use the plain prefix or the appropriate signed lambda construction.β¦
For a typed value at a normalized active type , an active application key at , and an optional payload fitting the domain of , observation application returns a typed value at the target of by the plain continuation coordinate, a free continuation slice, or a checked exit.β¦ A prescribed-base observation at an active type is a typed observation value whose empty observation is a given candidate assignment and whose nonempty observations are those of the distinguished value at that type.β¦
A typed observation environment over consists of a typed raw substitution and an optional raw parameter at every index, fitting at each declaration type found at .β¦ Write for these environments. Environment images are raw actual terms. The substituted actual expression of is , and the substituted actual type of is ; when the latter is active it also determines the substituted active type.
Environment extension by a typed raw term and a fitting parameter sends zero to and successor indices to the old images and parameters.β¦ The extension relation in (7) leaves the new parameter unrestricted except for the requirement that be a typed observation environment, with the new parameter fitting the substituted declaration type in . (7) Two environments over are compatible when their images are convertible at every index below and their parameters agree there.β¦ Environments over possibly different contexts have the same data when their entire image and parameter maps agree.β¦ Contexts are equivalent when both are valid and have exactly the same judgements , with subject and expected type unchanged.β¦
Product Tests and Evaluation
A product instance consists of a context , domain , body , a typed observation environment , and chosen formation sorts with , , and .β¦ Product formation supplies such an instance; a function judgement at also supplies one. For an instance , its raw domain, raw body, and raw instantiated target, and their normalizations, are defined in (8). (8) Here is the lifted substitution. Extending the instance by and a fitting payload uses the same raw .β¦ When is active, the normalized argument frame has argument .β¦ An active frame at the normalized product similarly determines its frame environment by extension with its argument and payload.β¦
Payload-indexed body candidates form a family of candidates at indexed by every with and every fitting payload at .β¦ For a domain candidate , the tester set and fibers are (9); denotes the fitting optional payloads. (9) The indexed product test for a domain set and candidate families is (10). For a domain candidate at and payload-indexed body candidates , the product test candidate of is the normalization candidate at given by (10), with tester set and fibers .β¦ (10)β¦
A typing derivation tree for records the variable declaration or sort axiom and each chosen formation role, with the conversion to the expected type at each node.β¦ A product node includes its domain and body sorts and the chosen product rule; an abstraction includes its annotation and body judgements and the product sort; an application includes its function and argument judgements and instantiated expected type.
A preliminary evaluation result for at has an observation value whenever is active, and a candidate readout . The optional evaluation parameter for a preliminary evaluation result for at is the raw observation value in the active case and absence otherwise.β¦ The base readout reads the candidate coordinate at of the valueβs base assignment when the actual subject profile lies in , the expected type is literally a sort with , and the actual expected type is active; otherwise it is .β¦ The base evaluation result pairs a supplied active value with this readout.β¦
Structural observation evaluation follows the typing derivation tree.β¦ Variable evaluation uses the corresponding environment parameter.β¦ Sort evaluation uses the distinguished active value and the top readout.β¦ Application evaluation applies the functionβs observation to the normalized argument frame and the argumentβs optional evaluation parameter.β¦ Abstraction evaluation uses the body evaluations in extended environments as its lambda action, followed by the base evaluation result.β¦
Product evaluation forms its evaluated product candidate from the domain readout and all fitting-payload body readouts in (10).β¦ This candidate is its readout; its product observation updates the exact candidate coordinate.β¦ The normal-form candidate readout of an expression is the candidate obtained by evaluating a chosen typing tree for the generic normal form and reading its candidate at .β¦
For an expression in and an observation environment over , the observation interpretation is the set in (11). (11)β¦
A component interpretation over is a system of environments, their raw substitutions, an extension relation, and interpretations that realizes every typed raw substitution and admits extension by every typed image of a sortable declaration. Its extension relation extends the raw substitution by the new image. At expected types its interpretations are candidates, respect conversion and sorted weakening, and equal the top candidate whenever either the generic or actual profile lies outside . At a sorted product whose generic and actual profiles lie in , it admits product introduction from typed strongly normalizing functions passing every domain test in every extension, and specialization at typed source arguments whose actual images pass the domain test. Write for these interpretations.
The Claim
Theorem 1 (Observation component laws). Assume system weak normalization for the finite specification , let be a saturated context tower, and let be a primary strongly connected component with no forbidden configuration.
The observation component interpretation is (12). (12)β¦ For every expression and observation environment over its context, the candidate law is (13). (13)β¦
Let satisfy , and suppose that and belong to . For any term , product membership is characterized by (14). (14)β¦ For a source argument , assume and . The specialization law is (15). (15)β¦
Let be an expected type in . For compatible environments over , interpretation invariance is (16). (16)β¦ For equivalent contexts and environments over , over with the same data, recontextualization is (17). (17)β¦
In the paper, the result reads: under system-wide weak normalization and the graph exclusion of the Β§Β 5 setting, the interpretation gives candidates invariant under weakening and context conversion, with nonempty parameter extensions and the product test clause, and, for a generic normal product with profile in and whose actual image passes its domain test, a passing test of a candidate member entails , while the ordinary typed strongly normalizing clause applies when the instantiated actual profile lies in the paperβs ordinary profile class .
What Is Checked
The claim is stated over the finite pure type specification, its full beta reduction and typing judgements, a saturated context tower, the primary component and secondary graph exclusion, and the observation environments with their typed raw substitutions.
The actual plain schema has well-founded recursive domain dependencies, including those reached after finitely many continuations.β¦
The finite signed observation stages and their inclusions form a directed system.β¦ Slicing represented negative behavior again has a negative representative.β¦
Decoded plain payloads fit their domains.β¦ An active application key whose source has a free sign and whose target is nonplain retains that sign at its target.β¦
Every typing judgement admits a typing derivation treeβ¦, from which its subject and expected type judgement is recovered. For each product instance, normalization preserves the product structureβ¦, a tester typed at the normalized domain remains typed at the raw domainβ¦, and substitution of the body in a frame environment has exactly the frameβs normalized target.β¦