The Setting
The distinction between data and proof applies to variables in a context and to arguments of dependent products. A converter declaration assigns a type to a proof variable, with a target as its input type.
Fix a sort collection . Pure type system terms over are generated by variables, sort constants, application, annotated abstraction and dependent product, as in (1), where . (1)✦ Named binders in (1) stand for de Bruijn notation: variables have natural number indices, and index zero refers to the nearest enclosing binder.
The modes are data and proof .✦ An argument and result label is one of , and , denoting data/data, data/proof and proof/proof, respectively.✦ A labelled term over is a term with the syntax of (1) and a label from , and on every application, abstraction and dependent product.✦ Write for a product with label . The label erasure of a labelled term is the unlabelled term obtained by deleting every label and preserving the remaining syntax.✦
For a term over and a substitution assigning a term over to each variable index, the simultaneous substitution is the term obtained by replacing each variable of index by and fixing sort constants.✦ It acts recursively on applications and on binder domains; in a binder body it uses the lifted substitution, which fixes the new variable and increases every free index in each older image by one. For terms and over , the single-variable substitution is the map from variable indices to terms over , and the bound-variable instantiation is the term over , specified by (2). (2) where the on the right denotes the variable of index .
Full one-step reduction on terms over is the least relation containing the head contraction in (3) and closed under reduction in either subterm of an application, annotated abstraction or dependent product. (3)✦ A normal form is a term with no one-step reduct.✦
A data-only term over is a labelled term whose every application, abstraction and dependent product has label .✦ Write for this condition. A positive telescope over is a labelled term in the least class specified by (4), where the domain is arbitrary. (4)✦
For a labelled term over and a map , the labelled variable renaming is the labelled term over obtained by replacing each variable index by and preserving sorts and labels.✦ It acts recursively on subterms, using under each binder the lifted renaming that fixes the newly bound variable and shifts the renamed indices of older variables. Write for renaming by .
A labelled context over is a newest-first list of labelled terms over ; adjoins the newest declaration . Labelled context lookup is the least relation specified by (5). (5)✦
The Definition
Definition 1. A normal positive target over is a labelled term satisfying (6). (6)✦
A converter proof context over is a labelled context with a mode assignment satisfying (7); the codomain is arbitrary. (7)✦
What Is Checked
The definitions concern labelled terms over an arbitrary sort collection and newest-first contexts equipped with assignments of data and proof modes. Equality of modes and labels is decidable; equality of labelled and unlabelled terms is decidable whenever equality of sorts is decidable.