Permalink
Fetching contributors…
Cannot retrieve contributors at this time
225 lines (160 sloc) 7.98 KB

Language reference

|RedPRL| documents contain expressions written in multiple languages: the :ref:`top-level vernacular <top-level-vernacular>`, the :ref:`object language <object-language>`, and the :ref:`tactic language <tactic-language>`.

Top-level vernacular

The top-level vernacular is a very simple language of commands that interact with the signature: this language is for declaring :ref:`new theorems <def-theorem>`, :ref:`definitional extensions <def-operator>` and :ref:`tactics <def-tactic>`; the top-level vernacular can also be used to print out an object from the signature. This is the language that one writes in a .prl file.

Defining theorems

A theorem in |RedPRL| is given by a type (an object language expression) together with a tactic script which establishes that the given type is inhabited; when a theorem is declared, the tactic script is executed against the goal, and if the result is successful, the generated evidence is added to the signature.

theorem OpName(#p : ...) :
  // goal here (object language expression)
by {
  // script here (tactic expression)
}.

Most definitions in a |RedPRL| signature will take the form of theorems; but other forms of definition may be preferable, :ref:`depending on circumstances <thm-vs-def>`.

Defining new operators

The most primitive way to define a new operator in |RedPRL| is to use the define command. A definition is specified by giving an operator name (which must be capitalized), together with a (possibly empty) sequence of parameters together with their valences, and an object-language term which shall be the definiens:

define OpName(#p : [dim].exp, ...) : exp =
  // object language expression here
.

A parameter is referenced using a metavariable (which is distinguished syntactically using the # sigil); the valence of a parameter specifies binding structure, with [tau1,tau2].tau being the valence of a binder of sort tau that binds a variable of sort tau1 and a variable of sort tau2.

A simple definition of sort exp without parameters can be abbreviated as follows:

define OpName =
  // object language expression here
.

Definitions of this kind are not subject to any typing conditions in CHTT; instead, if you use a primitive definition within a proof, you will have to prove that it is well-typed.

Defining tactics

A tactic can be defined using the special tactic command:

tactic OpName(#p : ...) =
  // tactic expression here
.

This desugars to an instance of the define command, and differs only in that the body of the definiens is here parsed using the grammar of tactic expressions.

Printing objects

To print a previously-defined object from the signature, one can write the following command:

print OpName.

When to use theorems or definitions?

As a rule of thumb, in most cases it is simpler to interactively construct an element of a type using a theorem declaration than it is to define a code for an element, and then prove that it has the intended type. This is why theorems are usually preferred to definitions in |RedPRL|.

However, definitions may be preferable in some cases; consider the definition of an abbreviation for the type family (lam [ty] (-> nat ty)) of sequences. As a theorem, this definition must take a universe level as a parameter

define Sequence(#l : lvl) :
  (-> [ty : (U #l)] (U #l))
by {
  // apply function introduction rule in the tactic language
  lam ty =>
    // explicitly give the body of the function in the object language
    `(-> nat ty)
}.

Later, when using this definition, one would have to explicitly provide the universe level, even though it does not play a part in the actual defined object: for instance, (Sequence #lvl{0}). The parameter was present only in order to express the type of the type family. On the other hand, with a definition, we can write the following:

define Sequence =
  (lam [ty] (-> nat ty))
.

One advantage of theorems over definitions is that |RedPRL| knows their type intrinsically; whereas definitions must be unfolded and proved to be well-typed at each use-site.

Object language

|RedPRL|'s object language and tactic language share a common syntactic framework based on multi-sorted second-order abstract syntax, which provides a uniform treatment of binding with syntactic sorts. |RedPRL| has three main sorts: exp (the sort of expressions), dim (the sort of dimension expressions) and tac (the sort of tactic expressions).

The object language is written in a variant of s-expression notation, with binding operators written systematically in the style of (lam [x] x). An expression in the object language is an untyped program or realizer in the language of Computational Higher Type Theory (CHTT).

These expressions include ordinary programming constructs like lambda abstraction and application, records, projection, etc., as well as cubical programming constructs inspired by cubical sets. Below are summarized common forms overlapping with other calculi.

Ordinary Operation Expression
dependent function type (-> [x y ... : ty] ... ty)
lambda abstraction (lam [x y ...] e)
function application ($ f e1 e2 ...)
dependent record type (record [lbl ... : ty] ..)
tuple (record element) (tuple [lbl e] ...)
record projection (! lbl e)

The cubical extension is characterized by a new sort of expressions, dimension expressions along with many new operations. A dimension expression can be a dimension variable i, representing an interval, or a dimension constant 0 or 1, representing one of its end point.

Cubical Operation Expression
coercion (coe r~>s [i] ty e)
homogeneous composition (hcom r~>s ty cap [i=0 [j] tube0] ...)
path type (path [i] ty e0 e1)
line type (-> [i : dim] ... ty)
path/line abstraction (abs [i j ...] e)
path/line application (@ e r1 r2 ...)
univalence (V a b e)
.. todo::
  Finish summary of object language terms.



Tactic language

.. todo::
  Summarize tactic language