The Setting
Let be a pure type specification, with arbitrary axiom relation and product-rule relation .✦ Dependent products may have several sort witnesses. The setting for typed data channels retains labelled terms along signed paths and uses feasible sort profiles to specify routes for formula quantifiers.
Pure type system terms are variables, sort constants, applications , annotated abstractions , and dependent products .✦ Variables have de Bruijn indices, with zero referring to the nearest binder; displayed bound names are named notation. Contexts are finite lists in newest-first order.
A labelled term is a term with a label attached to each application, abstraction and product.✦ The modes are data and proof .✦ A label records its argument and result modes: has modes , has , and has . Write and for these two modes. A labelled term is data-only when every labelled constructor in it has label .✦ The label erasure of a labelled term is the underlying term obtained by deleting all labels.✦
Renaming by replaces index by . Simultaneous substitution by replaces index by . Both operations fix sorts and act recursively, preserving labels when present. Under a binder, renaming fixes zero and sends to ; substitution fixes zero and shifts every free index of by one at index . The single-variable substitution determined by sends zero to and to variable . The instantiation of a term by a term is the term obtained by applying the single-variable substitution determined by to , in either syntax.
Full reduction contracts to and is closed under every term component, including annotations and binder bodies.✦ Labelled reduction additionally requires the application and abstraction in a head contraction to have the same label.✦ In each syntax, convertibility is the equivalence relation generated by its reduction relation.
For a context , the typing judgement assigns an expected type to a subject . Its rules are the axiom, variable, weakening, dependent product, abstraction, application and conversion rules for . Context extension shifts free indices in the variable and weakening rules. A product uses a triple sorting its domain, codomain and product; an abstraction requires its product type to have a sort. Application instantiates the codomain, and conversion requires the new expected type to have a sort. Labelled typing uses the same rules, retains the product’s label in abstraction and application, and uses labelled convertibility.✦
A mode environment assigns modes to variables. For a mode environment and a mode , the extended mode environment is the map assigning to zero and to .✦ The mode discipline gives variable mode and every sort data mode. An application with label requires its function to have mode and its argument mode ; its result has mode . An abstraction requires a data annotation and a body of result mode under . A product has data mode and requires a data domain and a data codomain under that same extension.
Profiles and Witnesses
A valid unlabelled context is a finite list obtained from the empty context by extensions from to whenever for some sort .✦
A term is -normal when it has no one-step reduct.✦ A weakly normalizing term is a term that reaches a normal term in finitely many steps; denotes its chosen full -normal form.
For a context , a weakly normalizing term , and subsets and of , the normal form sort profile and the product output profile are the subsets of defined in (1). (1) A feasible sort profile is a nonempty subset of equal to for some valid unlabelled context and normal term .✦ A feasible product profile triple consists of feasible profiles with .✦
For a labelled context , sorting a labelled term at a profile means for every ; further sorting judgements are permitted.✦ A fixed feasible witness family in is a family of pairs of labelled terms such that, at every feasible , is data-only, is normal, and is sorted at in . Its value satisfies , and both and have data mode under .
Retained Paths
Let be the proof wrapper syntax over : finite expressions generated by the identity and positive and negative extensions and , each adjoining a fixed labelled term to a preceding wrapper .✦ The wrappers and their annotations remain fixed under substitution of inputs and enlargement of their sorting profiles.
Fix a witness family and a collection of profiles. A proof wrapper path relates source profile to target profile with wrapper and parity . The proof wrapper path relation is the least relation given by (2), with subscripts suppressed and the word “feasible” denoting a feasible product profile triple. (2)✦
A positive data path is a finite path generated by the identity and extensions retaining two fixed labelled terms, an annotation and its original dummy argument.✦ A data path tail is a tuple with , , and encoding and decoding wrappers .✦
A retained data path is a finite path generated by an even identity, positive extensions retaining two fixed labelled terms, and negative extensions retaining a data path tail. Positive extensions preserve parity and negative extensions reverse it. The values zero and one denote even and odd parity, respectively.
The Definition
Definition 1. An observation channel over is a triple of odd retained data paths, with logical, raw and predicate components as in (3). (3)✦
A double channel over is an ordered pair of odd retained data paths as in (4). (4)✦
A common probe over is the tuple of fixed syntax in (5), where is its seed sort and its initial parity. (5)✦
Fix , a labelled context , a mode environment , a feasible witness family in , and a collection of profiles. A quantifier wrapper route for base profile and domain profile is a choice of codomain and product profiles and even proof wrapper paths satisfying (6). (6)✦
A universal quantifier code over is a pair of fixed input and output proof wrappers as in (7). (7)✦
What Is Checked
The definitions concern labelled syntax over arbitrary sort collections and, for quantifier wrapper routes, a pure type specification with a fixed feasible witness family in a labelled context, a mode environment and a collection of sort profiles.