The Setting
Substitution changes both a term and the types at which it is observed. An observation substitution must account for the actual replacement terms and for the parameters attached to their declarations.
Let be a pure type specification, with arbitrary axiom and product-rule relations. Terms include annotated abstractions and dependent products . Assume system weak normalization: every term occurring as a subject or an expected type in a typing judgment in a valid context has a normal form.✦ Write for its chosen normal form when one exists and a fixed fallback otherwise.✦ Full reduction acts in annotations and binder bodies as well as applications; convertibility is its equivalence closure. A valid context is obtained from the empty context by adjoining declarations whose types have some sort.✦
A saturated context tower is a tower of valid contexts whose prefixes have length equal to their stage, extend by one sortable declaration, and declare each sortable fixed-level type arbitrarily far along the tower.✦ The judgment means that some prefix types both expressions after translating their free levels to indices.✦ Contexts below are newest-first lists with de Bruijn indices, and denotes a declaration’s type viewed in the full context, including its index shifts.✦ Simultaneous substitution lifts beneath binders, fixing the bound index zero and shifting the free indices of each replacement.
The normal form profiles and the axiom and product output profiles are those in (1). (1) A feasible profile is a nonempty for a normal in a valid .✦ A feasible product triple consists of feasible profiles with .✦ The primary signed graph has positive edges for strict inclusions of feasible profiles, negative edges for feasible product triples, and positive edges for those triples.✦
Fix a family of profiles. The observation layers of a family of profiles are the profiles reachable along positive primary edges from a nonempty with .✦ The secondary graph retains positive primary edges between observation layers and has a negative edge when is a feasible product triple entirely in .✦ A direct layer is an observation layer for which there are profiles forming a feasible product triple .✦ An active layer is a profile with a directed secondary walk from to a direct layer; write .✦ A walk’s sign is the parity of its negative edges, with the empty walk positive.✦ A plain layer is a profile with secondary walks of both signs from to direct layers.✦ A free layer of sign is a profile that is not plain and has a secondary walk of sign to a direct layer.✦
A strongly connected component consists of exactly the vertices mutually reachable with one of its vertices.✦ For the observation spaces, exclude a forbidden configuration: a strongly connected secondary component consisting of plain layers, containing a negative edge, and admitting a feasible product triple and a sort with , nonempty , and a positive primary walk from to .✦
Observation Environments and Substitutions
The top family consists of the strongly normalizing terms typed at in .✦ A tested stack at a type is an argument list that is empty or, at , begins with and continues with a tested stack at .✦ The ground family consists of terms typed at whose application to every tested argument stack is strongly normalizing.✦ A normalization candidate at is a set between and closed under typed head expansion when the annotation, abstraction body and contracted argument are strongly normalizing and the remaining argument list is strongly normalizing.✦ Argument list reduction reduces one argument by one step✦; a strongly normalizing argument list admits no infinite sequence of these steps.✦ An actual type is a normal sortable expression or a literal sort.✦ A candidate assignment chooses a normalization candidate at each actual type.✦
For a domain , body , tester set and family of sets of terms, the indexed product test consists of the terms in that send every into every member of .✦
The top candidate assignment chooses at every actual type .✦
A normalized active type is a normal sortable type with active profile.✦ A plain observation at a normalized active type with plain profile is a recursively parameterized table of candidate assignments on finite application paths.✦ An application key for a type is a decomposition of as together with a normal term with and active target .✦ Its domain parameter is present when is active. A tagged plain observation is a pair consisting of a normalized plain type and a plain observation table at that type.✦ The prefix decomposition of a plain observation at consists of its candidate assignment at the empty path and, for every application key, a continuation sending each choice of its domain parameter to a plain observation at the target.✦ For a plain application key, an active domain is itself a normalized plain type✦; its domain parameter is a plain observation at .
A free observation frame has an expression as key and a payload that is absent, plain, or of the opposite free sign.✦ A continuation stack is a finite list of free observation frames✦, and an exit stack consists of continuing frames followed by a terminal exit frame.✦ A free observation table is a function assigning candidate assignments to continuation stacks and optional tagged plain observations to exit stacks.✦ The negative space is the direct limit of finite stages, starting from the empty stage and taking two successive table spaces at each step✦; the positive space is the table space with negative opposite values.✦ Negative observations have represented table behaviors with positive opposite values.✦ The slice of a free observation 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.✦
For a candidate assignment and an optional tagged plain observation , the constant observation table with base and exit result is the table returning on every continuation stack and on every exit stack.✦ The default positive observation with base and exit result is the constant table with those values in the positive observation space.✦ The default negative observation with base and exit result is the negative observation represented by the stage-one constant table with those values.✦
For a negative observation and a frame with positive opposite values, the negative observation slice of at that frame is a negative observation representing the slice of the represented behavior of .✦
A raw observation is tagged plain, positive or negative.✦ A typed observation value at is a raw observation compatible with : a plain tag has type exactly , while a positive or negative tag requires the corresponding free profile of .✦ Write for these typed values and for compatibility. The optional payload condition in (2) distinguishes inactive declarations. (2)✦ A free application gate at for an expression key , optional payload and exit flag holds when an active application key at has argument and a compatible payload at its domain, and its target is plain exactly when the exit flag is true.✦
A typed observation environment on is a raw actual substitution and an optional observation assignment satisfying (3) at each declaration. (3)✦ A tower typed substitution on is a raw actual substitution satisfying the typing condition in (3) at each declaration.✦
A stored typing tree for is a finite derivation retaining its chosen variable declaration, sort axiom or formation rule and the root conversion.✦ Structural observation evaluation follows this tree. Its outputs are the observation value and candidate readout in (4); the value is available under the activity condition displayed there. (4)✦ The optional evaluation parameter is the raw value of when the target is active and is absent otherwise.✦ Write for a typed value’s raw observation and for a candidate’s set of terms.
Write for extended by a newest declaration of type . A product instance consists of a context , domain , body , an environment on , and sorts with , and .✦ Write , and for its normalized substituted domain, normalized substituted body and normalized instantiated target at . A family of payload-indexed body candidates for a product instance assigns a candidate at to every with and every optional observation payload compatible with .✦ For a product instance and a candidate at , the product tester set is when , and is otherwise.✦ The product candidate fibers at are empty unless . For a typed , they consist of all the body candidate sets indexed by compatible payloads when , and otherwise consist of the single set . The product test candidate for a product instance, domain candidate and payload-indexed body candidates is the indexed product test at with their product tester set and product candidate fibers; it is a normalization candidate.✦ When is a normalized active type, a term typed at whose instantiated target is active determines a normalized argument frame: the active application key with argument and normalized target .✦ For a product instance with normalized product , an active application key at and a compatible optional domain payload determine its application frame environment by extending with the key’s argument and that payload.✦
Updating a candidate assignment at an actual type replaces its candidate at by the specified candidate and retains all its other coordinates.✦ The observation base assignment of a raw value is the candidate assignment at the empty observation: the first coordinate of a plain prefix, the empty-stack continuing result of a positive table, or that result in a negative value’s represented behavior.✦ Write for the raw substitution of . For a subject , expected type , typed observation environment and raw observation value, the base candidate readout is that value’s observation base assignment evaluated at when that subject’s profile belongs to , the original expected type is a literal sort with , and is active. In every other case it is .
The default plain observation at a normalized plain type is the constant plain table with the top candidate assignment as its value.✦ The distinguished observation at a normalized active type is its canonical typed observation value in .✦ Typed value projection at a normalized active type retains a raw observation when holds, and otherwise returns the distinguished observation at .✦ The checked exit value at a normalized active type is the distinguished observation when the exit is absent, and otherwise is the typed value projection at of the exiting plain tag.✦ The prescribed base observation at a normalized active type with candidate assignment is a typed observation value whose empty observation is and whose nonempty observations agree with the distinguished default.✦
Plain observation application takes a typed value at a normalized plain type, an active application key and a compatible optional domain payload to the typed observation at the target selected by its plain prefix continuation.✦ Observation value application sends a typed value at a normalized active type, an active application key and a compatible optional domain payload to a typed value at the key’s active target, using a plain continuation, a free continuation slice or a checked exit according to the source and target tags.✦
A lambda observation action at a normalized active type assigns a typed observation value at the active target to every active application key at and every compatible optional payload at its domain.✦ For a lambda observation action, a lambda exit decodes a frame payload and returns the plain tag of that action at the gated key when the free application gate holds with exit flag true; otherwise it is absent.✦ The plain lambda prefix at a normalized plain type is the typed observation whose continuation at each application key applies the lambda action with its unique optional domain payload, at the instantiated target.✦ The continuation gate is the free application gate with exit flag false. The positive lambda continuation follows the positive value supplied by the lambda action when the continuation gate holds after decoding the frame payload; otherwise it returns the default positive observation with top candidate assignment and absent exit.✦ The negative lambda continuation follows the negative value supplied by the lambda action when the continuation gate holds after decoding the frame payload; otherwise it returns the default negative observation with top candidate assignment and absent exit.✦
A raw lambda table has a base result, a negative body observation selected by each first frame, and an exit action: it returns the base on the empty continuation, the exit action on a lone terminal frame, and otherwise the selected body’s represented behavior on the remaining stack.✦ The positive lambda table has top candidate assignment at the empty continuation, follows the positive lambda continuation on a nonempty continuation, and uses the lambda exit on a lone terminal frame; after an initial continuing frame, its exit result is read from the selected continuation on the remaining exit stack.✦ The negative lambda behavior is the raw lambda table with top candidate assignment as its base, negative lambda continuation as its body action and lambda exit after negative frame payload decoding as its exit action.✦ Negative behavior packing chooses a negative observation representing a given table when one exists, and otherwise returns the default negative observation with top candidate assignment and absent exit.✦ The lambda observation value at a normalized active type is the typed value formed from its lambda action by the plain prefix or the corresponding signed free lambda construction.✦
Variable evaluation takes its observation value from the corresponding environment parameter, using the stored declaration and root conversion.✦ Sort evaluation gives the distinguished observation whenever its substituted expected type is active, and its candidate readout is the top normalization candidate.✦ Abstraction evaluation uses the body evaluations in every typed observation environment on the domain extension to form its abstraction action; its active value is the lambda observation value with that action, and its readout is the base candidate readout.✦ Application evaluation uses the function and argument evaluations, their stored typings and the conversion to the instantiated target; its active value is the application observation value and its readout is the base candidate readout.✦ The evaluated product candidate is the candidate at the normalized substituted product obtained from the domain readout and all matching payload-indexed body readouts through the product test.✦ Product evaluation takes its readout from the evaluated product candidate, and its product observation updates the coordinate of that exact product with this candidate.✦
Value goodness and readout goodness are respectively the value and readout conditions of recursive evaluation goodness on the stored tree under the raw substitution . At an abstraction, value goodness requires value goodness of the body at every typed argument with active instantiated target. A neutral term is a variable followed by zero or more applications.✦ At an application with active function type it requires value goodness of the function and, for an active domain, of the argument; with inactive function type it requires neutrality of the original application. For a product whose substituted profile belongs to , readout goodness requires readout goodness of the domain when its profile belongs to , and of each typed instantiated body when its profile belongs to . Its value condition requires these same conditions when both the product profile and its chosen result-sort singleton belong to .
A stored substitution along a simultaneous substitution from to a valid assigns each a tree for .✦ Write for the substituted tree, and abbreviate it by . Substitution composition and extension use (5). (5) For a raw actual substitution on , the activity guard is the declaration condition in (6). (6)✦ Replacement goodness is the condition in (7) on the replacement trees at active declaration types. (7)✦ Environments on and on satisfy the assignment relation when their raw substitutions and observation parameters obey (8); here denote the two assignments of . (8)✦ For a tree of , let be the single substitution sending zero to and to variable , and let be its stored substitution from to . The environment extension on sends zero to with parameter and retains at successor indices.✦
A stored substitution from to lifts from to whenever for some sort , along the substitution that fixes the newest variable and shifts each older replacement into the extended context.✦
A declaration preserving renaming from to is a map of indices such that every declaration gives the declaration , where denotes variable renaming.✦ For a declaration preserving renaming into a valid context , renaming a stored tree for gives a stored tree for , preserving its shape and renaming its binder annotations.✦
The Claim
Theorem 1. Let be a stored tree for , let be valid, and let be a stored substitution along from to . Let be a tower typed substitution on and set . Assume and . When is active and holds, the first conclusion in (9) holds; when holds, the second holds. (9)✦
Let be typed observation environments satisfying and . Under , when both substituted expected types have active profiles, the first equality in (10) holds; under , the second holds. (10)✦
For a single substitution and any raw substitution , suppose that is active whenever it belongs to . Then the single substitution satisfies (11). (11)✦
Let be a stored tree for . Suppose holds whenever is active. Its stored single substitution then has the replacement goodness in (12). (12)✦
For every typed observation environment on , its extension by satisfies the assignment law (13). (13)✦
What Is Checked
The goodness laws are stated over stored typing substitutions and raw tower typed substitutions; the evaluation law also uses compatible observation environments and the exclusion of the forbidden configuration. Stored trees recover their typing judgments✦, and substitution by a tower typed substitution preserves the typings of both subjects and expected types.✦ Variable renaming preserves convertibility. Simultaneous substitution preserves convertibility. Whenever , the product has some sort in .
The dependencies of plain observations on their actual domain parameters are well-founded, including domains encountered after finitely many continuing frames.✦ The optional evaluation parameter satisfies payload compatibility at the normalized substituted expected type.✦ A nonplain active target of an application key at a free type has the same free sign as its source.✦ Normalizing the substituted product of a product instance gives the product of its normalized substituted domain and body.✦
A declaration preserving renaming from to lifts to one from to , fixing zero and sending each successor index to the successor of its renamed index.✦
Every term typed at the normalized domain of a product instance is also typed at its substituted domain before normalization.✦ For a product instance whose normalized product is an active type, substituting its application frame environment into its body and normalizing gives exactly the active target type of that frame’s application key.✦