The Setting
Consider a typing tree for an annotated term together with a raw substitution into a saturated context tower. The questions are whether structural goodness depends on the chosen convertible images, and when normal syntax has good active values and readouts.
Let be a pure type system with arbitrary axiom and product-rule relations. Terms have annotated abstractions and dependent products . Write for beta convertibility, and for a chosen beta normal form when is weakly normalizing. Normality and strong normalization refer to full beta reduction, including annotations and binder bodies. A context is valid when each declaration has a sort in the preceding context.✦ A legal term is a term that occurs as a subject or an expected type in a typing judgment✦; system weak normalization is the property that every legal term in every valid context has a beta normal form.✦
A saturated context tower is a sequence of valid contexts of length at stage , extended by one sortable declaration at each stage, in which each type sortable in an earlier prefix, with fixed free levels, is declared again beyond every prescribed stage.✦ The judgment means that holds at some finite stage after translating free levels to that stage’s variable indices.✦ Ordinary contexts use newest declarations first and variables indexed by natural numbers. A typing tree retains the formation choices and conversions at every node, including each chosen product-rule triple.✦
Define the profiles and product outputs by (1); a feasible profile is a nonempty profile of 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 between feasible profiles, and, for each feasible triple, a negative edge and a positive edge .✦ A signed walk has the parity of its number of negative edges✦; directed reachability allows either parity✦, whereas positive reachability uses only positive edges.✦ Empty walks are allowed. The axiom profile of a sort is the set of its axiom successors.
Fix a family of profiles. The observation layers of the family are the profiles positively reachable in the primary graph from a nonempty with .✦ The secondary graph has the positive primary edges between observation layers, and a negative edge for each feasible triple whose three profiles are observation layers.✦ A direct layer is an observation layer occurring in a triple with .✦ An active layer is an observation layer that reaches a direct layer in the secondary graph; write for this condition.✦ A plain layer is an observation layer with walks of both parities to direct layers.✦ A free layer of sign is a nonplain profile with a walk of parity to a direct layer.✦
A strongly connected component consists of all vertices mutually reachable with one of its vertices.✦ A forbidden configuration is a secondary strongly connected component of plain layers containing a negative edge, together with a feasible triple and a sort such that , is nonempty, and positively reaches in the primary graph.✦ Component relevance of a term in a context is the condition in (2), where denotes primary directed reachability. (2)✦
Values, Readouts, and Goodness
A tower-typed raw substitution assigns an arbitrary term to each variable, with whenever the context lookup at is .✦ Two tower-typed raw substitutions are compatible when for every .✦ A declaration-preserving renaming is a map of variables sending each lookup to a lookup ; denotes the renamed typing tree in a valid .
A normalization candidate at is a set satisfying the bounds in (3) and closed under typed head expansion.✦ For a type , write for the strongly normalizing terms typed at in the tower.✦ A tested stack is an argument list that is empty at any type, or has first argument at a product and a remaining tested stack at .✦ Iterated application is written . (3) A candidate at is closed under typed head expansion when it contains whenever this term has tower type , its annotation , body , argument and remaining argument list are strongly normalizing, and . Argument list reduction is the relation on argument lists that changes one entry by a beta step.✦ An actual type is a normal sortable term or a literal sort. A candidate assignment is a function assigning a candidate to every actual type; denote the space of these assignments by .✦ The ground candidate consists of the terms of tower type whose application to every tested stack at is strongly normalizing.✦
The observation constructions use system weak normalization and exclusion of a forbidden configuration. A normalized active type is a normal sortable type with active profile✦; a normalized plain type is a normal sortable type with plain profile. An application key at a normalized active or normalized plain type is a choice of and a normal argument with and active profile at . The target of an application key at with argument is .
The plain observation schema has these keys and targets, with a domain parameter precisely when the key’s domain is active.✦ A finite continuation path is a finite sequence of keys following their targets.✦ The payload occurrences of a finite continuation path are occurrences that select the domain parameters on that path.✦ A plain observation at is a function assigning a base result to each finite continuation path and every assignment of recursive plain observations to its payload occurrences. With base , write this space as . Its prefix decomposition in (4) separates the empty path from the first key; is the recursive plain space at the domain of when that domain is active, and is a one-element space otherwise. (4)✦ A tagged plain observation at a type is a pair with .✦ The top candidate assignment sends each actual type to .✦ The distinguished plain space element with base is the recursive plain observation whose table is constantly .✦ The default actual plain observation at takes this constant value to be the top candidate assignment.✦
A free observation frame consists of an expression key and an optional payload, either a tagged plain observation or an observation of the opposite sign.✦ A finite continuation stack is a finite list of continuing free frames✦, and a terminal exit stack is a finite list of continuing free frames followed by a terminal frame.✦ A free table is a function assigning a candidate assignment to each finite continuation stack and an optional tagged plain observation to each terminal exit stack.✦ If is this table space with opposite observations in , its finite stages and signed spaces are as in (5). $$F_0=\varnothing,\qquad F_{n+1}=\mathcal T(\mathcal T(F_n)),\qquad F^-=\varinjlim_n F_n,\qquad F^+=\mathcal T(F^-).$$(5) A raw observation is an observation with a plain, positive, or negative tag.✦ A raw observation fits a type when its plain tag names exactly , or its signed tag agrees with a free layer of that sign at .✦ A typed value at is a raw observation fitting .✦ The base assignment of a raw observation is the first coordinate of (4) in the plain case, the empty continuing result in the positive case, and the empty continuing result of its represented behaviour in the negative case.✦
Table reindexing along a map sends a free table over opposite observations in to a table over opposite observations in by applying to every opposite payload before evaluating either kind of stack.✦ The observation stage successor maps into : its map out of the empty stage is unique, and its map at the next stage reindexes tables twice along the preceding successor map.✦ The observation stage inclusion from to , for , is the composite of the intervening stage successor maps.✦ The finite stage embedding sends an observation in to its class in the negative observation space .✦ Finite stage restriction at sends a positive observation to the table obtained by reindexing it along the embedding of into .✦ Finite stage behaviour sends an observation in to a table over positive opposite observations; at a successor stage it reindexes the table along restriction to the preceding stage.✦
A constant free table with base and exit value returns on every continuation stack and on every exit stack, and is the default positive observation with these values. The default negative observation with these values is the image of that constant table from the first finite stage.✦
A typed observation environment on consists of a typed raw substitution and optional observation parameters fitting each normalized substituted declaration type.✦ An absent parameter requires an inactive declaration. Extension by a term typed at and a matching optional parameter gives an environment on , keeping the raw term as the new image.✦ Write and . For a tree , its substituted actual expression under is , a normal sortable term in the tower.✦ For a tree , its substituted actual type under is , which is a normal sortable term or a literal sort.
Structural evaluation of in gives a preliminary result consisting of , a typed observation at when , and , a candidate at . The base readout is when , with , and is active; otherwise it is .✦ A distinguished observation is the canonical typed observation at a normalized active type.✦ Prescribing a base changes the empty observation and keeps the distinguished nonempty observations.✦ Projection of a fitting raw value keeps it; projection of any other raw value gives the distinguished value.✦
The candidate coordinate update of an assignment at an actual type by a candidate replaces by and retains every other coordinate.✦
The base evaluation result for a typing judgment and environment pairs the supplied active values with their base readout.✦ The optional evaluation parameter of a preliminary result is its raw value when the normalized substituted expected type has active profile, and is absent otherwise.✦
Variable evaluation uses the environment parameter, and sort evaluation has a distinguished active value and top readout.✦ A lambda observation action is a function sending each application key and compatible optional payload to a typed value at its target.✦ Abstraction evaluation uses the body’s result in the extended environment as this action.✦ Application evaluation supplies a typed value at the normalized instantiated target, using the function and argument results. Plain application uses the continuation coordinate in (4).✦ Free application continues by slicing a table, or exits to a plain observation. Its gate requires a matching application key and domain payload, with a plain target exactly in the exit case.✦ A checked exit projects a present plain observation and uses the distinguished value for an absent exit.✦
The slice of a free table at a frame is the table obtained by prefixing that frame to every continuation stack and to the continuing part of every exit stack.✦ The negative observation slice of at a frame over positive opposite observations is a negative observation whose represented behaviour is the slice of the represented behaviour of .✦
A raw lambda table takes a base, a body action from frames over positive opposite observations to negative observations, and an exit action on those frames. Its empty continuing result is the base; after a first continuing frame it uses the represented behaviour of the selected body, and on a lone terminal frame it uses the exit action.✦
The lambda observation value of an action at a normalized active type is the typed observation at formed by the corresponding plain or signed free lambda construction.✦ For a normalized active type with plain profile, the plain lambda prefix of an action is the typed observation whose continuation at each key is the action on that key and its compatible optional payload, with the instantiated body as target.✦
The lambda exit operation for an action and a free frame decodes the frame payload and tests the exit gate. It returns the action’s target value as a tagged plain observation when that gate holds, and is absent otherwise.✦
At a positive free type, the positive lambda continuation of an action at a positive frame is the positive observation supplied by the action when the continuation gate holds after decoding the payload; otherwise it is the default positive observation with top candidate assignment and absent exit.✦ At a negative free type, the negative lambda continuation of an action at a negative frame is the negative observation supplied by the action when the continuation gate holds after decoding the payload; otherwise it is the default negative observation with top candidate assignment and absent exit.✦
The positive lambda table of an action at a positive free type has the top candidate assignment as its empty continuing result and follows the positive lambda continuation after a first continuing frame. Its exit at a lone terminal frame is the lambda exit operation, and after continuing frames it follows the same continuation on the residual exit stack. The negative lambda behaviour of an action at a negative free type is the raw lambda table with top candidate assignment as base, negative lambda continuation as body action, and the lambda exit operation with negative frame payloads as exit action.✦ Negative behaviour packing sends a free table over positive opposite observations to a negative observation having that represented behaviour when one exists; otherwise it returns the default negative observation with top candidate assignment and absent exit.✦
For a product, fix domain and body typings, chosen sorts satisfying , and an environment. Its normalized domain and body are and . Given a domain candidate and body candidates for every typed argument and compatible payload, its tester set is when , and otherwise.✦ At a typed argument , its fiber family consists exactly of the payload-indexed body candidates when , and consists only of the top candidate otherwise; an untyped argument has no fibers.✦ The product candidate consists of the terms in sending every tester into every corresponding fiber.✦ Product evaluation uses this candidate as its readout and updates its exact coordinate in the observation’s candidate assignment.✦ For a normalized active type supplied by a product instance, the normalized argument frame of with and active instantiated target is the application key with domain , body and argument .
The recursive goodness pair of a tree under a raw substitution is denoted by (6); its components are propositions, distinct from evaluation values and candidates. (6) At a variable, value goodness is automatic; at a sort, both components are automatic. For a product with result sort , let be the condition requiring domain readout goodness when the substituted domain profile lies in , and body readout goodness under every typed raw argument extension whose body profile lies in . Its value condition requires when both the substituted product profile and lie in , while its readout condition requires when the product profile lies in . An abstraction’s value condition requires body value goodness under every typed raw argument extension with active target. An application’s value condition requires function value goodness and, when the domain is active, argument value goodness, provided the substituted function type is active; otherwise it requires neutrality of the application. Variables, abstractions, and applications use the base readout condition with their respective value conditions.
The Claim
Theorem 1. Let be a typing tree in a saturated context tower setting with profile family . For compatible typed raw substitutions , the equivalences in (7) hold. (7)✦ For a declaration-preserving renaming with valid and any raw substitution , the goodness pair satisfies (8). (8)✦ Suppose is beta normal and is typed. Then (9) holds, with the second clause for every sort . (9)✦ For structural evaluation, suppose system weak normalization holds and there is no forbidden configuration. Let and let be a typed observation environment. If , , and , the readout is given by (10). (10)✦ For and any raw substitution , suppose , , and . Then (11) holds. (11)✦
In the paper, the result reads: goodness has the structural invariances of Lemma 28; when the actual expression profile and lie in the paper’s component and is active, is the base projection at every syntactic shape and its goodness is equivalent to goodness; every normal syntax tree has good active under every typed raw substitution, and a normal tree has good when its generic expression profile lies in the paper’s family .
What Is Checked
The claims concern typing trees and their declaration-preserving renamings, typed raw substitutions and their pointwise convertibility, the recursively defined goodness pair, and structural evaluation in typed observation environments. Renaming lifts across a binder✦, preserves beta convertibility✦, and transports a typing tree to the renamed judgment.✦ A function’s product type has a sort.✦ Normalizing a product instance preserves its product structure✦; a tester typed at its normalized domain is typed at the raw substituted domain✦, and substitution in a frame environment has exactly the frame’s normalized target type.✦
Excluding a forbidden configuration makes the plain schema’s domain dependencies well-founded, including dependencies reached after finite continuations.✦ The finite free stages form a directed system✦. A continuation with nonplain target preserves the source’s free sign.✦ The product test construction yields a normalization candidate with every matching body payload included. The optional plain payload determined by a plain key’s frame parameters fits that key’s domain. Every payload occurrence along a finite continuation path gives a recursive domain dependency on the path’s starting node.