The Setting
A normal annotated term can have typing trees with different formation sorts or conversion steps. Evaluating such a tree involves both the expected type and the observation parameters supplied for its free variables. The term being evaluated is normal before those variables are replaced by actual terms.
Fix a pure type specification , where is the set of sorts and and are arbitrary axiom and product-rule relations.✦ Terms are variables, sorts, applications , annotated abstractions , and dependent products .✦ Named variables are source notation; terms use de Bruijn indices, with index zero bound by the nearest binder, and contexts are newest-first lists. Variable renaming acts recursively under binders, where its lift fixes zero and shifts the renamed free indices.✦ Simultaneous substitution is capture-avoiding. Its lift fixes the bound variable and shifts the images of free variables✦; bound variable instantiation uses the single-variable substitution sending zero to and each successor to its predecessor.
Full one-step reduction contains head contraction and reduction in every application component, annotation and binder body. A normal term is a term admitting no full one-step beta reduction, and denotes the equivalence relation generated by reduction.✦ Weak normalization means that some finite reduction reaches a normal term✦; its chosen normal form is . Strong normalization means that no infinite full reduction begins at the term.✦ Argument list reduction changes exactly one component by one beta step✦; a strongly normalizing argument list admits no infinite sequence of these changes.✦ Write for left-associated iterated application.
Typing uses the axiom relation, variable introduction and weakening, product formation with a triple in , abstraction and application. Conversion changes the expected type to a sorted beta-convertible type. A valid context is obtained from the empty context by adjoining a declaration with for some sort .✦ Declaration lookup gives a variable’s type in the full context, shifting its free indices across each newer declaration.✦ A legal term occurs as a subject or an expected type in a typing judgment.✦ Assume system weak normalization: in every valid context, both subjects and expected types of typing judgments are weakly normalizing.✦
A saturated context tower is a nested sequence of valid contexts of length at stage , each extended by a sorted declaration. Every expression with a sort in a finite prefix, written with fixed free levels, is declared again beyond every prescribed stage. Tower typing means that some finite prefix types both the subject and the expected type after changing free levels to indices.✦ At length this reversal sends a level to and fixes indices outside that range; bound variables retain their de Bruijn indices.✦
Profiles and Observation Layers
The normal form sort profile is the set of all sorts typing .✦ The tower profile uses tower typing in place of typing in .✦ For a sort and profiles and , the axiom successor profile and product output profile are given with these profiles in (1). (1) A feasible profile is a nonempty realized by a normal term in a valid context.✦ A feasible product profile triple consists of feasible profiles satisfying .✦
The primary signed graph has feasible profiles as vertices. Its inclusion edges , for , are positive. A feasible product profile triple gives a negative domain edge and a positive codomain edge . A signed directed walk is a finite walk whose parity counts its negative edges, with the empty walk positive.✦ Directed reachability allows either parity✦; positive reachability uses only positive edges.✦ A strongly connected component is the set of vertices mutually reachable with one of its vertices.✦
Fix a family of profiles. An observation layer is a feasible profile positively reachable in the primary graph from a nonempty with .✦ The secondary signed graph has observation layers as vertices. Its positive edges are the positive primary edges between these layers. Its negative edges come from feasible triples all of whose profiles are observation layers. A direct observation layer is an observation layer with a feasible triple for some .✦
An active layer is an observation layer with a directed walk in the secondary graph to a direct layer.✦ A plain layer is an observation layer with directed walks in the secondary graph of both parities to direct layers, possibly with different endpoints. A free layer of sign is a nonplain profile with a walk of parity to a direct layer.✦ A forbidden configuration is a strongly connected component of the secondary graph consisting entirely of plain layers and containing a negative edge, together with a feasible triple and a sort such that and the nonempty has positive primary reachability to .✦ Assume that and admit no forbidden configuration.
Candidates and Observation Spaces
The top candidate consists of the strongly normalizing terms with tower type .✦ Tested argument stacks at include the empty stack. A stack is tested at when and is tested at . The ground candidate at is the set of terms with tower type whose application to every tested argument stack at is strongly normalizing. A normalization candidate at is a set satisfying the bounds in (2) and head expansion closure. (2) Head expansion closure means that a typed term belongs to whenever its head contractum belongs to , the terms are strongly normalizing, and is a strongly normalizing argument list.✦
An actual type is a term that is either normal and has some tower sort, or is a literal sort. A candidate assignment is a function on actual types whose value at each actual type is a normalization candidate at .✦ Write for the space of these assignments. The top assignment gives at every coordinate.✦ A coordinate update replaces that candidate and retains the other coordinates.✦
A plain observation schema on nodes is a family of key sets indexed by , with a target and an optional domain for each key.✦ A finite continuation path in a plain observation schema is a finite sequence of keys following successive targets.✦ A payload occurrence on a finite continuation path is a choice of a present domain at one of its keys.✦ For a family of spaces indexed by domain nodes, path parameters are families assigning an element of to every payload occurrence with domain on the path; single-frame parameters are such families for a path consisting of one key. Empty path parameters are unique. Prepending a frame combines its parameters with the remaining path parameters, and restriction to the first frame and the tail recovers the two parts. A plain observation table at a node of a plain observation schema is a function assigning a value in a fixed base space to every path from with its path parameters.✦
The recursive domain dependency relation on the nodes of a plain observation schema holds when occurs as a domain after finitely many continuations from .✦ For well-founded dependency and base , the recursive plain observation space has the recursive table form (3); here denotes the path parameters just defined. Plain space unfolding identifies an observation with this table. (3) The distinguished element of the recursive plain observation space at is the observation with constant table value . The plain prefix decomposition separates the empty observation from each first-frame continuation: (4)✦ The coordinates in (4) use parameter extension to prefix a frame and parameter restriction to split a nonempty path.
A normalized plain type is a normal tower-sorted term with plain profile.✦ A plain application key at a normalized plain type is a choice of a decomposition and a normal argument with , whose instantiated target has active profile. Its plain target node is ✦; an active domain gives its plain domain node.✦ The actual plain schema is the plain observation schema whose nodes are normalized plain types and whose keys are plain application keys, with a domain present exactly when its profile is active.✦ Its recursive spaces are the actual plain observation spaces.✦ Their unfolding and actual plain prefix decomposition are (3) and (4) for this schema.
For key space , plain payload space and opposite space , a free observation frame is a key with an optional payload, either absent, plain in , or opposite in .✦ A continuation stack is a finite list of free observation frames, and an exit stack is a finite list of free observation frames followed by one terminal frame. For a base space and an exit result space , a free table is a pair of functions assigning a result in to each continuation stack and a result in to each exit stack.✦ Denote its space by , keeping fixed.
Payload mapping along changes only opposite payloads.✦ Frame mapping retains keys; continuation and exit stack mapping apply this to their frames. Table reindexing along precomposes both table components with these stack maps.✦ The observation table slice at a frame prefixes that frame to the continuing part of either kind of stack.✦ A constant observation table is a free table that returns a fixed base value on all continuation stacks and a fixed exit value on all exit stacks.✦
The finite observation stages and signed free spaces are defined by (5). Successor maps start at the empty stage and at each later stage reindex tables twice along the preceding successor map✦; stage inclusions iterate these maps.✦ The negative space is their direct limit, with finite-stage embeddings, and the positive space is a table space over the negative space.✦ $$X_0=\varnothing,\qquad X_{n+1}=\mathscr T(\mathscr T(X_n)),\qquad \mathcal M=\varinjlim_n X_n,\qquad \mathcal L=\mathscr T(\mathcal M).$$(5) Finite-stage restriction reindexes a positive table along a stage embedding. Finite-stage behavior is empty at zero and, at a successor stage, reindexes along the preceding restriction.✦ Represented negative behavior is the map from to tables over induced by finite-stage behavior.✦ A negative observation slice is a negative element representing a slice of this behavior.✦ The default positive observation is a constant table✦; the default negative observation embeds the corresponding stage-one constant table.✦
Values and Environments
For the actual observations, keys are terms, bases are candidate assignments , plain payloads are tagged actual plain observations over , and exits are optional tagged plain observations. A tagged plain observation consists of its normalized plain type and an element of that type’s actual plain space.✦ Actual positive and negative observations are the spaces and in (5) with these choices. A raw observation value is a tagged plain observation, an actual positive observation, or an actual negative observation, distinguished by its tag.✦
For an actual type and a raw observation value , observation tag compatibility requires a plain tag to have exactly type , a positive tag to have positive free profile at , and a negative tag to have negative free profile there.✦ For a term , a typed observation value at is a raw observation value satisfying .✦ Plain value injection attaches its plain type tag✦; plain value extraction recovers the observation at that type.✦ Positive and negative value extraction recover the corresponding signed observation. Plain observation tagging returns the normalized plain type together with its extracted observation.✦
The base assignment of a raw value is its empty observation: for a plain value it is the first plain prefix coordinate, for a positive value its empty continuing result, and for a negative value that result in its represented behavior.✦ The default actual plain observation has constant top assignment.✦ At a normalized active type, meaning a normal sorted type with active profile, the distinguished observation value is its canonical typed observation value. A prescribed base observation replaces its empty observation by a given assignment, retaining all its nonempty default observations.✦ Typed value projection retains a raw value when its tag fits, and otherwise returns the distinguished value.✦ A checked exit value projects a present plain exit and uses the distinguished value for an absent exit.✦
Optional payload compatibility for a term and an optional raw observation value is the condition in (6). Active payload extraction returns its typed value when the domain is active.✦ (6)✦ A typed observation environment from to is a raw image substitution and an optional parameter assignment satisfying (7). The first condition is tower-typed substitution; declaration lookup views in the full source context. (7)✦ Environment extension by with tower type and a matching payload sends the new zero index to raw and its payload, and successors to the old images and parameters.✦ For , the substituted actual type is .✦ For , the substituted actual expression is .✦ When its profile is active, a substituted actual type is also a normalized active type. A normalized active type with plain profile gives its corresponding plain node.✦
An active application key at a normalized active type is a choice of a decomposition and a normal argument with , with active instantiated target.✦ Its active target type is .✦ At a plain source this is also a plain application key.✦ Plain payload decoding produces the tagged plain domain observation when the domain is active, and absence otherwise✦; plain payload encoding assigns the corresponding single-frame parameters. A positive frame has an absent, plain, or negative payload✦; a negative frame has an absent, plain, or positive payload.✦ Their payload decoding attaches the corresponding raw tags, and their payload encoding retains the matching tags of compatible optional raw values.
A free application gate at , argument , payload and exit flag requires an active key with argument and a compatible domain payload. Its target is plain exactly when the flag specifies an exit. A gated application key is an active application key satisfying a free application gate.✦ A lambda observation action is a function assigning a typed value at the active target to each active key and each compatible optional payload.✦
Plain observation application takes the relevant continuation coordinate of the plain prefix decomposition.✦ A plain lambda prefix has the lambda action as its continuation coordinates, using the encoded payloads and the instantiated body as target.✦ Positive and negative lambda continuations apply the action at a continuing gate and extract its signed result; when that gate fails they give the corresponding default. The lambda exit operation returns the action’s tagged plain observation at an exit gate, and absence otherwise.✦
A raw lambda table has its specified base on the empty stack. On a nonempty continuation stack it uses the represented negative behavior of the body action at the first frame; its exits use the exit action at a lone terminal frame and that body behavior after a continuing frame. Negative lambda behavior is this raw table with top assignment, negative lambda continuation and the decoded lambda exit operation.✦ Negative behavior packing chooses a negative observation with the given behavior when one exists, and the default negative observation otherwise.✦ A positive lambda table has the analogous empty base and positive continuations, with decoded lambda exits.✦ The lambda observation value uses the plain prefix or the signed lambda construction at its type.✦ Observation value application uses the next plain coordinate, a free continuation slice, or a checked plain exit, according to its source and target.✦
Structural Evaluation
A stored typing tree for is a finite tree retaining the judgment’s generation choices. A variable node retains its declaration and conversion to ; a sort node retains a chosen axiom successor and conversion. A product node retains domain and body trees at chosen sorts and the product rule. An abstraction retains its annotation and body trees, a sorted product type and conversion to that product; an application retains function and argument trees and conversion to the instantiated target.
Structural preevaluation evaluates a stored typing tree for in a typed observation environment .✦ Its preliminary result has an active value at whenever that expected type has active profile, and a candidate readout at .✦ The readout is a set of terms, distinct from the observation value. Its optional evaluation parameter is the optional raw value in (8). (8)
A product instance is a collection consisting of a domain , a body , a source context and an environment, with formation judgments at chosen sorts satisfying .✦ The substituted domain of a product instance is , and its substituted body is , where denotes the lifted substitution that fixes the bound variable. Denote their normal forms by and . Its raw instantiated target at substitutes raw for zero and for each successor in ✦; write for that target’s normal form. The instance extends its environment by and a compatible payload.✦ Payload-indexed body candidates for a product instance are families assigning a candidate at to every tower-typed and every compatible payload, including all choices of that payload.✦
Given a domain candidate , the product tester set is when , and otherwise. For a typed argument , the product candidate fibers are all its payload-indexed body candidates when , and the singleton otherwise. The fiber family is empty for an argument without type .✦ The indexed product test defining the product test candidate is (9). (9) The evaluated product candidate uses the domain read and the body reads in every matching extended environment in (9).✦ Product evaluation takes this candidate as its readout and updates the exact product coordinate in its observation base.✦ The stored product formation judgments give its product instance; instances from a product formation or a function with product type choose the corresponding formation sorts. A normalized argument frame uses as its key.✦ The application frame environment extends the instance environment by the key’s argument and matching payload.✦
The base candidate readout of a typing judgment and its active observation value uses that value’s base assignment at precisely when , the expected type is literally a sort with , and the substituted expected type has active profile.✦ Otherwise it is . A base evaluation result consists of the active values and this readout.✦ Sort evaluation uses the distinguished active value and the top readout.✦ Variable evaluation takes its active value from the corresponding environment parameter.✦ Abstraction evaluation is a base result with the lambda observation value supplied by its abstraction observation action.✦ That action uses the body evaluations on the domain extension, together with the product typing and conversion to the expected type.✦ Application evaluation is a base result using the function and argument evaluations, their product and domain typings, and conversion to the instantiated target.✦ For an application with , and , the application observation value in is a typed observation value at whenever this type has active profile.
The Claim
Theorem 1. Let be beta normal, let and be stored typing trees for and , and let be one typed observation environment from to . The parameter equality in (10) assumes . The readout equality assumes that and are literal sorts, for arbitrary . (10)✦
What Is Checked
The claim is stated over full beta-normal annotated terms, stored typing trees and raw typed observation environments in a saturated context tower, under system weak normalization and exclusion of forbidden configurations. Every stored tree recovers its typing judgment.✦ A function’s dependent product type has some sort, supplying the product formation used by its instance.✦
For the actual plain schema these dependencies are well-founded under the stated assumptions, including dependencies after any finite continuation.✦ Decoded plain payloads satisfy domain compatibility.✦ At a normalized plain type, every typed value is a plain value injection✦. An active application key from a free source retains its sign whenever its target is nonplain.✦
The finite free observation stages and inclusions form a directed system.✦ Slicing a represented negative behavior is again representable by a negative observation.✦ Product instance normalization preserves the dependent product structure.✦ A tester typed at the normalized domain remains typed at the raw substituted domain.✦ The normalized body after substitution by an application frame environment is exactly the active target type.✦ The product test construction gives a normalization candidate for its domain and payload-indexed body candidates.✦