The Setting
A data type can be represented along different retained data paths. The comparison concerns formulas obtained by observing a represented value and by testing an encoded predicate against it.
Fix a pure type specification , with arbitrary axiom relation and product-rule relation .β¦ Pure terms are variables, sorts, applications, annotated abstractions , and dependent products .β¦ Labelled terms attach an argument and result label to each application, abstraction, and product.β¦ Erasure deletes these labels.β¦ Named variables below denote de Bruijn variables, with index zero the newest variable; contexts are newest-first.
In either syntax, a valid context is obtained from the empty context by adjoining a type with for some sort . Typing is the relation generated by the axiom and variable rules, weakening, product formation along , abstraction and application, and conversion to a sorted expected type. In the labelled syntax, abstraction and application use the label of their dependent product.
Full reduction contracts to and acts in every component, including annotations and binder bodies; labelled head contraction requires the application and abstraction to have the same label. Convertibility is the equivalence relation generated by this reduction. A term is normal when it admits no reduction step, and weakly normalizing when finitely many steps reach a normal term. Write for its chosen full normal form when one exists, with a fixed default otherwise.β¦
Capture-avoiding renaming acts on free variables and fixes each newly bound variable. Simultaneous substitution replaces free variables by assigned terms, lifting the assignment under binders. Instantiation substitutes for the distinguished newest variable and lowers the older indices; its single-variable substitution sends zero to and to variable . For open terms and , their composition is , with ambient variables retained.β¦
The modes are data, written , and proof, written .β¦ The labels , , and have argument and result modes , , and , respectively. A mode assignment assigns a mode to every variable. The mode discipline assigns variables their prescribed modes and sorts data mode. An application with label has the result mode of under when has that mode and has the argument mode of under . An abstraction with label has the result mode of under when has data mode under and has the result mode of under extended by assigning the argument mode of . A product has data-mode domain and codomain, with the codomain checked under that extension, and has data mode. A data-only term is one whose constructor labels are all .β¦
Sorting at a profile is the condition in (1); it permits additional sorting judgments. (1)β¦ The normal form sort profile, axiom profile, and product output profile are the sets in (2). (2) A feasible sort profile is a nonempty set equal to for some valid pure context and normal pure term .β¦ A feasible product profile triple consists of feasible profiles with .β¦
Fix a collection of sort profiles. The primary signed graph has positive edges for strict inclusions between feasible profiles. Each feasible product profile triple supplies a negative edge and a positive edge . Positive reachability means a finite, possibly empty path using only positive edges.β¦ An observation layer is a profile positively reachable from a nonempty with .β¦ A direct observation layer is an observation layer for which is a feasible product profile triple with .β¦ A logical terminal profile is a profile occurring in a feasible product profile triple with .β¦
A fixed feasible witness family assigns a type and a value to every profile. At every feasible , the type is data-only, its erasure is normal, and holds; also , and both and have data mode under .
Logical Formulas
A mode-preserving context embedding is a variable renaming into a valid context that preserves each variableβs type and mode.β¦ Context lookup assigns the variable at index its declared type with every free index raised by , accounting for its own declaration and the newer declarations.β¦
Proof mode inhabitation of a formula means that some satisfies and .β¦ A typed open proof transformer from to is a term with in proof mode, where the temporary variable has proof mode and is weakened into the extended context.β¦ Write for the existence of such a transformer. Typed logical equivalence is the relation in (3). (3)β¦
A proof wrapper is a finite sequence of positive and negative extensions, starting with the identity, each extension retaining one term.β¦ Relative to and , its path starts at a profile . Its current target may be restricted to any subset without changing the wrapper. A triple permits a positive extension to retaining ; a triple permits a negative extension retaining when . The parity is the number of negative extensions modulo two. A wrapper contains a negative step precisely when at least one extension is negative.β¦
A quantifier wrapper route for a base and domain consists of a feasible triple and even proof wrapper paths from to and from to .β¦ An ambient logical calculus consists of a witness family with typed open proof transformers between and for every pair of logical terminal profiles. It also chooses a feasible triple with , even proof wrapper paths from to and from to , and a quantifier wrapper route for every direct observation layer.
A witness continuation for a term is the following condition: after every mode-preserving context embedding and for every logical terminal profile , the existence of a typed open proof transformer from the renamed to the renamed entails proof mode inhabitation of that renamed .β¦ Stable witness extraction for means that after every such embedding, a witness continuation for the renamed entails proof mode inhabitation of the renamed itself.β¦
An interpretable formula for is a term sorted at , of data mode, that admits stable witness extraction.β¦ A stable formula family over a type is an open term such that, after every mode-preserving context embedding , each data-mode argument with gives an interpretable instance for the transported calculus.β¦ The renaming fixes its distinguished variable and renames the ambient variables. Transport along renames the witness types and values, transports the typed open proof transformers between terminal witness types, and renames the proof wrappers and quantifier routes. It preserves the base, domain, and product profiles, their feasible product profile triple, and their membership in .
Data Paths and Channels
A positive data path is a finite sequence of positive steps, each retaining a chosen type and dummy value.β¦ Relative to , it starts with the identity at , permits restriction of the current target to any subset, and extends to along a triple using .β¦
A data path tail consists of a sort , a positive data path, and encoding and decoding proof wrappers. It is formed relative to with endpoint when , is nonempty, its positive path is formed from that axiom profile to , and its encoding and decoding proof paths are formed with even parity from to and back, respectively. The decoding path must contain a negative step.
A retained data path is a path that starts with the identity and is extended by positive steps retaining a type and dummy value, or negative steps retaining a data path tail.β¦ Its parity counts negative steps modulo two. A formed retained data path relative to is a retained data path that starts at , permits restriction of its current target to a subset, and admits a positive extension to along with retained terms . A negative extension to uses a feasible product profile triple and a formed data path tail relative to ending at .
The wrapped type is at the identity. A positive step with annotation replaces the preceding wrapped type by the data function type from to that type; a negative step replaces it by the data function type from that type to the tailβs carrier. The builder returns at the identity and forms a constant data abstraction at a positive step. At a negative step, it abstracts over the preceding wrapped type, observes that bound input against , and sends the resulting formula through the tailβs encoding. Capture-avoiding shifts preserve the distinguished input when is a callback.
The observation instantiates by at the identity. At a positive step it applies to the retained dummy value and observes the result along the preceding path. At a negative step it applies to the argument built along the preceding path from , then reads the result through the tailβs decoding. Renaming a data path renames its retained terms and tails and preserves its steps.β¦
For an odd path , the observation callback is the open term in (4). Reencoding from an odd path to an odd path is the builder expression in the same display. (4) The open reencoding is with distinguished and all ambient variables weakened.β¦
An observation channel consists of odd logical, raw, and predicate data paths.β¦ It is formed from through profiles when those paths are formed from to , from to , and from to , respectively.β¦ Its logical and raw types, conversions, and roundtrip are defined in (5). (5) The encoded predicate and channel evaluation are the expressions in (6), using open composition for the callback supplied to the predicate builder. (6)
The Claim
Theorem 1. Let be an ambient logical calculus in , and let be a formed observation channel from through . Suppose holds, has data mode, and with of data mode. For every data-mode term with , the observation law (7) holds: (7)β¦ Suppose additionally that for some sort , and that is a stable formula family over . Then the evaluation law (8) holds: (8)β¦
What Is Checked
The statements concern formed observation channels relative to an ambient logical calculus, profile-sorted data-mode types and typed data-mode inputs; predicate evaluation additionally requires a sort for the raw channel type and a stable formula family over the logical channel type.
Renaming along a mode-preserving context embedding preserves witness normality, sorting, typing, and data modes.