The Setting
An observation environment supplies raw terms for the variables of a typing derivation and observation parameters at its active declarations. Structural evaluation assigns an observation to the expected type and a normalization candidate to the substituted subject. The two outputs concern different terms, even when the subject is itself a type.
Fix a pure type specification , with arbitrary axiom and product-rule relations. Terms are variables, sorts, applications , annotated abstractions and dependent products .✦ Names in these expressions are source notation; variable positions in a context use de Bruijn indices, starting at zero, and contexts are newest-first. Write for declaration lookup with viewed in the full context, including its index shifts.✦ A valid context is obtained from the empty context by extensions with for some sort .✦
Write for the equivalence relation generated by full beta reduction, including reduction in every annotation and binder body.✦ Assume system weak normalization: in each valid context, both the subjects and the expected types of typing judgements have beta normal forms.✦ Write for the chosen normal form of such a term, and for capture-avoiding simultaneous substitution. Under a binder its lift fixes zero and sends to with its free indices increased by one.✦ Renaming uses the analogous lift of an index map, fixing zero and sending to ; denotes bound variable instantiation. A term is legal in when it occurs as either the subject or the expected type of a typing judgement in .
A saturated context tower is a sequence of valid prefixes of length , each extended by one sortable declaration, in which every sortable type expressed with fixed free levels is declared again beyond every stage bound.✦ Tower typing means typing at some prefix after converting both and from levels to indices.✦ At length this conversion sends to and fixes the other indices.✦ The normal form profiles and the axiom and product output profiles are (1) A feasible profile is a nonempty profile in (1) realized by a normal term in a valid context.✦ A feasible product profile triple consists of feasible profiles with .✦
Observation Layers
The primary signed graph has positive edges for strict inclusions of feasible profiles. A feasible product profile triple gives a negative edge and a positive edge . A signed walk has the parity of its number of negative edges; the empty walk has even parity. Write for reachability with either parity, and for a walk using only positive edges. A strongly connected component consists of exactly the vertices mutually reachable with one of its vertices.✦
For a family of profiles, the observation layers are the profiles positively reachable in the primary graph from a nonempty with .✦ The secondary graph has these layers as vertices. Its positive edges are the primary positive edges between them, and its negative edges come from feasible product profile triples all of whose profiles are observation layers.✦ A direct layer for a family of profiles is an observation layer admitting a feasible product profile triple with .✦ Write for the direct layers and for a secondary walk of parity . The active, plain and signed free layers are defined by (2)
Assume there is no forbidden configuration for . Such a configuration is a secondary strongly connected component consisting of plain layers and containing a negative edge, together with a feasible product profile triple and a sort for which , is nonempty, and in the primary graph.✦
Candidates and Observation Values
A term is strongly normalizing when no infinite sequence of full beta reductions starts at it.✦ An argument list is strongly normalizing when the relation reducing one component at a time admits no infinite sequence.✦ Write for left-associated iterated application.✦ The top and ground sets at in the tower are (3) The empty stack is tested at every type; is tested at when and is tested at .✦ A normalization candidate at is a set with in (3), closed under typed head expansion: membership of entails membership of when the latter has tower type , the annotation , body and argument are strongly normalizing, and is a strongly normalizing argument list.✦
An actual type is a normal term sorted in , or a literal sort.✦ A candidate assignment assigns a normalization candidate to every actual type .✦ The top assignment chooses at each coordinate; a coordinate update replaces just that candidate. A normalized active type is a normal, sorted term with ; a normalized plain type is a normal, sorted term with .
A plain application key at a normalized plain type chooses a decomposition and a normal argument with and active target .✦ Its target node is that normal form✦, and its domain node is when the domain is active, with no domain otherwise. A plain schema is a system of nodes equipped with keys, targets and optional domains.✦ A finite continuation path successively follows targets✦; a payload occurrence selects a domain at one of its frames.✦ Path parameters assign a recursive observation at each such occurrence.✦ For a plain schema with well-founded recursive domain dependency, a base space and a node , the recursive plain space consists of tables valued in on continuation paths from and their recursive path parameters.✦ Its unfolding is its recursive table, with prefix decomposition (4)✦ where is the single frame parameter space. The distinguished element is the constant table.✦ A tagged plain observation consists of its normalized plain type and a plain observation with candidate assignments as base.✦ The actual plain schema has normalized plain types as nodes, with the plain application keys, target nodes and optional domain nodes just described.✦
Free observations have positive and negative signs. A free frame consists of a term key and a payload, which is absent or contains a plain observation or an observation of the sign opposite to that of the free observation containing the frame.✦ A continuing stack is a finite list of frames✦; an exit stack adds a terminal frame.✦ A free table assigns a candidate assignment to each continuing stack and an optional tagged plain observation to each exit stack.✦ The finite stages start with the empty space and at each successor take tables whose opposite values are tables over the preceding stage.✦ Negative observations form the direct limit of these stages✦; positive observations are tables over negative observations.✦ Represented negative behavior is a table over positive observations. Slicing a table prefixes one frame to either kind of stack.✦ The constant tables give the default signed observations, with the negative default represented at the first stage. A raw lambda table with base , body action assigning a negative observation to each frame over positive observations, and exit action is a table over positive observations. Its empty continuing result is ; after a first frame it follows the represented behavior of on the remaining stack, while a lone terminal frame has exit result .✦
A raw observation has a plain, positive or negative tag.✦ A typed observation value at is a raw observation compatible with : a plain tag has exactly type , while a positive tag has parity zero, a negative tag has parity one, and a signed tag of parity requires .✦ An optional payload fits when it is absent at an inactive profile, or present with a compatible tag.✦ The base of a raw observation is its empty continuing observation, using (4) in the plain case and represented behavior in the negative case.✦ The distinguished typed observation uses the top assignment and default continuations.✦ Projection to an active type keeps a compatible raw observation and uses the distinguished observation otherwise.✦ For a normalized active type and candidate assignment , the prescribed base observation at has empty observation and retains every nonempty observation of the distinguished observation.✦
Environments and Structural Evaluation
A typed observation environment from to consists of a raw substitution and optional raw observations satisfying (5)✦ For a new declaration , an argument with tower type and a payload fitting extend to by sending zero to and each successor to the old image and payload. The substituted actual type of a judgement is ; when active it is also a normalized active type. For a sorted subject the substituted actual expression is .✦
Image compatibility means convertibility of images at every position of .✦ Compatibility of environments on , reindexing from to , and identity of data across these contexts mean, respectively, (6) The last equality in (6) concerns the entire assignments, including positions beyond the contexts.
A declaration-preserving renaming is an index map satisfying (7) Context equivalence means that both contexts are valid and exactly when , for every subject and expected type .✦ A typing tree for is a finite derivation retaining its declaration lookups, chosen axiom successors and product formation sorts, and conversions to the expected types.✦ Write for its renaming along (7) into a valid , for its context conversion along , and for its root retargeting when and .
Structural evaluation follows the chosen formation roles of . Its preliminary result has an active observation value at whenever that type is active, and a candidate at .✦ Write for the underlying raw observation and for the underlying set of terms. Its optional parameter is (8)✦
Variable evaluation takes its value from the declaration’s environment parameter.✦ Sort evaluation uses the distinguished active observation and the top readout.✦
A product instance consists of a context , a typed observation environment on , a domain and body with and , and a chosen result sort with .✦ Its substituted body uses the lifted substitution.✦ Its domain, body and instantiated targets have chosen normal forms. Product evaluation uses the domain readout as testers when the domain profile belongs to , and otherwise uses the top set.✦ The candidate fiber family is empty at an argument without tower type at the normalized domain. At a typed argument it consists exactly of the body candidate sets arising from all fitting payloads when the normalized target profile belongs to , and otherwise consists of the top set at that target alone. The product test consists of top terms sending every tester into every corresponding fiber.✦ Its observation updates the product’s exact candidate coordinate.
An active application key at a normalized active type chooses a decomposition and a normal argument with , such that is active; this normalized instantiated body is its active target type.✦ A lambda action at a normalized active type is a function assigning a typed target observation to every active application key at and fitting payload.✦ Abstraction evaluation uses the body evaluations in extended environments to give this action. The plain lambda uses the continuation coordinates of (4). For a normalized active type , a free application gate at a term , optional raw observation and exit flag holds when there is an active application key at whose argument is and whose domain admits as a fitting payload, and its target is plain exactly when the exit flag is true.✦ Signed continuation uses the same free sign✦, and failed gates use the defaults. Application evaluation applies the function observation to the normalized argument key and its payload, through a plain continuation, a free slice or an exit projected to the target type.
Negative behavior packing chooses a negative observation representing a table over positive observations when one exists. Otherwise it returns the default negative observation with the top candidate assignment and an absent exit.
For a plain application key, plain payload encoding sends a fitting optional raw observation to its single frame parameters, retaining the matching plain observation when the domain is active.✦
At an active application key whose source type is positively free, positive frame payload encoding sends a fitting optional raw observation to an absent payload, a tagged plain observation or a negative observation, retaining its matching tag.✦ At an active application key whose source type is negatively free, negative frame payload encoding sends a fitting optional raw observation to an absent payload, a tagged plain observation or a positive observation, retaining its matching tag.✦
Positive frame payload decoding sends absence to an absent raw payload, a negative observation to a present negatively tagged raw payload, and a plain observation to a present plainly tagged raw payload.✦ Negative frame payload decoding sends absence to an absent raw payload, a positive observation to a present positively tagged raw payload, and a plain observation to a present plainly tagged raw payload.✦
For a lambda action at , the lambda exit operation decodes a frame payload and tests the exit gate. At a successful gate it returns the tagged plain observation supplied by the action at the witnessing key; otherwise it returns no exit observation.✦
For a positively free type and lambda action, the positive lambda table has top candidate assignment at the empty continuing stack and follows the positive lambda continuation after a first frame. Its exit at a lone terminal frame is the lambda exit operation with positive payload decoding, and its exits after a first continuing frame follow that continuation on the remaining exit stack.
For a negatively free type and lambda action, the negative lambda behavior is the raw lambda table with top candidate assignment as base, negative lambda continuation as body action, and the lambda exit operation with negative payload decoding as exit action.✦
The checked exit value at an active type is the distinguished observation when the exit is absent, and otherwise is the projection to of the returned tagged plain observation.✦
For a base evaluation result, the readout uses the observation’s base coordinate at the substituted actual expression precisely when the subject profile belongs to , the expected type is a literal sort with , and the expected type is active. Otherwise it is the top candidate.
The Claim
Theorem 1. Let be a saturated context tower for the weakly normalizing specification , and let have no forbidden configuration. Let be a typing tree for .
Suppose is a strongly connected component of the primary graph, and are typed observation environments on with . Their outputs satisfy (9): (9)✦
Let be valid, let preserve declarations, and let be environments on with . Renamed evaluation satisfies (10): (10)✦
Suppose , and let be environments on these contexts with . Evaluation in the converted context satisfies (11): (11)✦
Suppose and . Let be an environment on for which both and are active. Retargeted evaluation satisfies (12): (12)✦
What Is Checked
The statements concern finite typing trees with their chosen formation roles, tower-typed raw substitutions and fitting optional payloads, under system weak normalization and exclusion of a forbidden configuration; the compatibility statement additionally assumes that is a primary strongly connected component.
Declaration-preserving renamings lift through context extension✦, and renaming preserves beta convertibility.✦
Typing trees recover their typing judgements.✦
In a plain schema, a node depends on each domain node reached after a finite continuation path from it.✦ For the actual plain schema this relation is well-founded✦, and each path payload occurrence gives such a dependency.✦
Negative observation behavior remains representable after slicing.✦
For a product instance, normalizing its substituted product gives the product of its normalized domain and body.✦ An argument typed at the normalized domain remains typed at the raw substituted domain✦, and the body normal form under its frame environment is exactly the active key’s target type.✦ The corresponding indexed product tests are normalization candidates.
Whenever , the product itself has a sort in .✦
For every plain application key, its frame parameters determine an optional plain observation payload that fits its domain.✦