The Setting
Let be a pure type specification, with arbitrary axiom relation and product-rule relation .✦ Terms are variables, sorts, applications, annotated abstractions , and dependent products .✦ Full one-step reduction contracts to and permits reduction in every subterm, including annotations and binder bodies.✦ Convertibility is the equivalence relation generated by these steps.✦
A valid context is a finite context obtained from the empty context by repeatedly extending a context with a declaration whenever for some sort .✦ The judgement uses the axiom, variable, weakening, product, abstraction, application and conversion rules of . A stored typing tree is a finite derivation retaining the declaration lookup or axiom at a leaf, the chosen domain and body sorts and product-rule output at a product, and the conversions to the expected types. An abstraction retains its annotation and body trees and its product formation judgement; an application retains its function and argument trees and its instantiated target.
The variable names here are source notation. Contexts in the library are newest-first, and variables use de Bruijn indices. Declaration lookup shifts a stored declaration type into the full context.✦ Simultaneous substitution is capture-avoiding: beneath a binder its lift fixes index zero and shifts the images of the old indices.✦ Single-variable substitution sends zero to the argument and decrements the remaining indices; bound-variable instantiation is the resulting substitution into a body. Variable renaming uses the corresponding lift under binders.
A term is normal when it has no full step✦, weakly normalizing when it reaches a normal term✦, and strongly normalizing, written , when no infinite full reduction begins at it.✦ Assume system weak normalization: in every valid context both the subject and the expected type of every typing judgement are weakly normalizing.✦ These are the legal terms. Write for the chosen normal form whenever this assumption supplies its specification.
A saturated context tower is an increasing sequence of valid contexts of length at stage , each extended by a sortable declaration, in which every type sortable at a stage is declared again arbitrarily far along the tower.✦ Tower terms use fixed levels for free variables. Tower typing means that some finite stage types both expressions after index to level reversal, which sends to and fixes the other indices.✦
Profiles and Observation Layers
The normal-form sort profiles and the axiom and product output profiles are the sets in (1). A feasible profile is a nonempty set of sorts of the form for a normal term in a valid context .✦ (1) A feasible product profile triple consists of feasible profiles with .✦ The primary signed graph has positive edges for strict inclusions of feasible profiles, and, for each feasible product profile triple, a negative edge and a positive edge .✦
A signed directed walk has parity equal to the number of its negative edges modulo two; the empty walk is positive.✦ Directed reachability permits either parity✦, whereas positive reachability uses only positive edges.✦ A strongly connected component is the set of vertices mutually reachable with one of its vertices.✦ The observation layers of a family of profiles are the profiles positively reachable in the primary graph from a nonempty with .✦ The secondary signed graph has the positive primary edges between observation layers and the negative domain edges of product profile triples whose three profiles are observation layers.✦
A direct observation layer is an observation layer occurring in a product profile triple with .✦ An observation layer is active if it reaches a direct layer in the secondary graph.✦ A plain layer is an observation layer with walks of both parities to direct layers, which may be different.✦ A nonplain profile is a free layer of sign if it has a walk of parity to a direct layer.✦
A forbidden configuration is a secondary strongly connected component of plain layers containing a negative edge, together with a feasible product profile triple and a sort such that and the nonempty has positive primary reachability to .✦ Assume that no such configuration exists for and .
Candidates and Observation Spaces
Write for left-associated iterated application.✦ An argument list reduces when one of its components takes a full step✦, and is strongly normalizing when no infinite sequence of such list reductions starts from it.✦ The top and ground candidates at are defined in (2). A tested stack is empty at any type, or has first argument at , where is the set of strongly normalizing terms of tower type , and a tail tested at .✦ (2) A normalization candidate at is a set with closed under head expansion: if has tower type , its annotation, body, argument and further argument list are strongly normalizing, and , then .✦ An actual type is a normal sortable expression or a literal sort.✦ A candidate assignment chooses a candidate at each actual type ✦; the top assignment chooses .✦ Updating a coordinate replaces just the candidate at that actual type.✦
A normalized active type is a normal sortable expression whose profile is active✦; a normalized plain type is a normal sortable expression whose profile is plain.✦ An application key at an active type is a choice of a decomposition and a normal argument with active instantiated target.✦ Its target type is .✦ A plain application key at a normalized plain type is an application key at .✦ The actual plain schema uses these keys and targets, with a domain node present precisely when its profile is active.✦
A plain observation schema is an assignment of keys, targets and optional domains to nodes.✦ A finite continuation path follows finitely many targets✦; its payload occurrences select the frames with a present domain.✦ Path parameters assign a value at the appropriate domain to every occurrence.✦ For a family of parameter spaces and a key with domain , single-frame parameters are values in ; a key without a domain has the unique empty assignment.✦ Path-parameter extension joins these to the remaining path parameters✦, and the empty path has its unique empty assignment.✦ The recursive dependency means that occurs as a domain after finitely many continuing frames from .✦
For a schema with well-founded dependency and base , its recursive plain space consists of plain observation tables as in (3).✦ Here denotes path parameters with values in the recursive spaces, and denotes the single-frame parameters for a key . Unfolding identifies a space with this table, and its prefix decomposition separates the empty observation from the continuation coordinates. (3) The actual plain observation spaces use the actual plain schema and candidate assignments as bases.✦ A distinguished element of an actual plain observation space is an observation with a constant table✦; the default actual plain observation is the distinguished element whose table has the top assignment as its constant value.✦ A tagged plain observation is a pair consisting of a normalized plain type and an observation in the actual plain observation space at that type.✦
A free observation frame is a key with a payload that is absent, plain, or an opposite value.✦ A continuation stack is a finite list of frames✦, and an exit stack is a continuation stack together with a terminal frame.✦ For keys , plain payloads , bases , and exit results , let be the space of tables assigning a result in to each continuation stack with opposite values in , and a result in to each exit stack.✦ The signed free spaces are given by (4). (4) Payload mapping changes opposite values and preserves plain values and absence✦; frame and stack mapping retain the keys. Table reindexing precomposes with these maps.✦ The observation stage successor uses reindexing twice, and its iterates are the stage inclusions. Finite-stage embedding gives the classes in ; restriction reindexes a positive table along an embedding. Finite-stage behavior uses restriction, and represented negative behavior assigns to each negative observation its table over positive opposite values.✦ A table slice prefixes a frame to its stacks.✦ Negative slicing selects a negative observation with the sliced represented behavior.✦ Default positive observations are constant tables✦; default negative observations embed constant tables at stage one.✦
Actual positive and negative observations take expressions as keys, tagged plain observations as plain payloads, candidate assignments as bases, and optional tagged plain observations as exits. A raw observation has a plain, positive, or negative tag.✦ Compatibility at requires the exact type on a plain tag, a positive free profile on a positive tag, and a negative free profile on a negative tag.✦ A typed observation value at is a compatible raw observation.✦ Optional payload compatibility requires absence at inactive domains and a compatible present value otherwise.✦ Active payload extraction retrieves that value; plain payload conversion relates compatible optional payloads to single frame parameters. Signed frame payload conversion preserves plain tags and treats a value of the opposite sign as the opposite payload. A positive application frame consists of an expression key and a payload that is absent, a tagged plain observation, or an actual negative observation.✦ A negative application frame consists of an expression key and a payload that is absent, a tagged plain observation, or an actual positive observation.✦ Positive frame payload decoding sends absence to absence, a tagged plain payload to a present plain raw observation, and an actual negative payload to a present negative raw observation.✦ Negative frame payload decoding sends absence to absence, a tagged plain payload to a present plain raw observation, and an actual positive payload to a present positive raw observation.✦
The base assignment of an observation is its empty observation, obtained through the plain prefix decomposition or the appropriate free table.✦ Plain value injection and extraction relate plain spaces to typed values; signed extraction retrieves the positive or negative observation. A distinguished typed value is a typed observation value constructed from the default observation.✦ Typed projection keeps a compatible raw value and otherwise selects the distinguished value.✦ The prescribed base observation at a normalized active type with candidate assignment is a typed value whose empty observation is and whose nonempty observations agree with the distinguished value at .✦ Plain observation tagging at a normalized active type with plain profile sends a typed value to the tagged plain observation consisting of that same normalized plain type and its extracted plain observation.✦
A lambda observation action is an assignment of a typed target value to every active application key and compatible payload.✦ A free application gate is a condition on an expression key, a payload and an exit flag: the key and payload must match an active application key with a compatible payload, and the flag must be true exactly when its target is plain.✦ Signed lambda continuations use the action at a continuation gate and otherwise the signed default. The lambda exit operation returns the tagged plain action value at an exit gate and otherwise no exit.✦ A raw lambda table has its prescribed base on the empty stack and follows its body action after a first frame.✦ The positive lambda table uses the top base and these continuations and exits.✦ At a normalized active type with negative free profile, 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 using negative frame payload decoding as exit action.✦ Negative behavior packing chooses a negative observation representing this table when one exists and otherwise the negative default.✦ The plain lambda prefix takes its continuation coordinates from the action.✦ The lambda observation value selects the appropriate plain or signed construction.✦
Observation value application follows the plain continuation coordinate, a signed continuation slice, or a checked exit according to the source and target profiles.✦ A checked exit is an operation that projects a present plain result to the target and otherwise uses the distinguished value.✦
Evaluation and Goodness
A typed observation environment from to consists of a raw substitution and optional observation parameters . For each declaration lookup of at type , it requires and payload compatibility of with .✦ The images need not be strongly normalizing. Environment extension adjoins a raw typed argument and its compatible parameter.✦ If , the substituted actual expression under is the actual type .✦ If , the substituted actual expected type is ✦, which gives a normalized active type when its profile is active.✦
A product instance is a choice of a domain , a body , formation sorts with their product rule, and an environment.✦ Its substituted domain is ✦, its substituted body uses the lifted substitution, and its raw instantiated target at is , where extends by the raw argument.✦ Their normal forms are denoted , , and . Product instances arise from stored formation data or from a function typing at a product. Product instance extension adjoins an argument and compatible payload✦; an application frame environment uses the argument of its key.✦ The normalized argument frame instead uses the chosen normal form of a typed argument.✦
Given a domain candidate and payload-indexed body candidates at , the tester set is when and otherwise.✦ The fiber family is empty unless ; for such an argument it comprises the candidates for all optional payloads compatible with when , and is otherwise.✦ The indexed product test defining the product candidate is (5), with the tester set. (5)✦
Structural preevaluation follows a stored typing tree and its chosen formation roles. Preevaluation gives an active observation value at and a candidate readout at ; write the raw observation value and candidate set as and , with the assumption that the normalized expected type is active. Its optional evaluation parameter is present exactly in this active case.✦ A preliminary evaluation result for under consists of a typed observation value at whenever this type is active, together with a candidate readout at .✦
The variable result takes its value from the environment parameter.✦ For a sort, the active value is distinguished and the readout is top.✦ The domain read and all compatible payload-indexed body reads determine the product candidate, which is then used to update the corresponding candidate coordinate of the product observation.✦ For an abstraction, the result uses the lambda observation action obtained by evaluating its body in the frame environments.✦ The application result applies the function’s observation using the argument’s optional evaluation parameter.✦
A base evaluation result combines its active values with the base candidate readout.✦ That readout uses the value’s base assignment at when , the original expected type is a literal sort with , and is active; otherwise it is the top candidate.✦
Recursive evaluation goodness assigns a value condition and a readout condition to a stored tree under a raw substitution. At a variable the value condition is automatic and the readout condition is the base readout condition; at a sort both are automatic. For a product with result sort , let require domain readout goodness when its substituted profile is in , and body readout goodness at every raw typed argument whose substituted body profile is in . Product value goodness requires when both and the substituted product profile is in ; product readout goodness requires when that product profile is in .
For an abstraction, value goodness requires body value goodness under every raw typed argument with active target. For an application with active substituted function type, it requires function value goodness and, when the domain is active, argument value goodness; with inactive function type it requires the application to be neutral. The readout condition for an abstraction or application is its base readout condition with the indicated value requirement.
For trees and , good observation transport is the forward preservation property (6). The conditions range over every typed observation environment , with its raw substitution ; in the value clause, denotes the assumption that is active. (6)✦
The Claim
Theorem 1 (Lemma 31). Assume system weak normalization for , let be a saturated context tower, and let be a strongly connected component of the primary signed graph with no forbidden configuration. For a stored tree and a full step , the reduction transport assertion is (7). (7)✦
What Is Checked
The assertion is stated over stored typing trees, raw typed substitutions into a saturated tower, and compatible observation environments, under system weak normalization and the specified component and configuration hypotheses.
Stored trees recover their typing judgements, including a final expected sort that need not itself have a sort.✦ A function’s product type has a formation sort.✦
The actual plain dependencies are well-founded under the configuration exclusion.✦
The finite observation stage inclusions form a directed system.✦
Decoded plain payloads satisfy domain compatibility.✦ Typed values at plain types admit plain representations✦, and values at signed free types have the corresponding signed tags. A nonplain continuation target retains its source free sign.✦
For product instances, normalization preserves the product structure✦, a normalized-domain tester remains typed at the raw domain✦, and frame substitution has exactly the normalized target of the application key.✦
The indexed product tests used in evaluation are normalization candidates.