Cubist

LANGUAGE REFERENCE · CHAPTER 2

A first proof and files

First proofs about pairs, alternatives and numbers, then how a source file is laid out: imports, names, comments and declarations.

A first proof

A statement is a type, and a proof of it is a value of that type (chapter 1). The first statements to prove are about any two statements A and B. If both hold, then both hold in the other order: A and B -> B and A.

def and_swap(A, B : U0) : A and B -> B and A {
  intro both;               // both : A and B
  exact (both.2, both.1);   // a B, then an A
}

A and B are parameters of type U0: any two small types, read as statements. The stated type is an implication, so a proof of it is a function. Given evidence that A and B holds, a pair, it returns evidence that B and A holds, another pair.

The proof is a block. At every point in a block there is a goal, the type still to be proved, and a context, the names available and their types. At the start, the goal is the stated type, A and B -> B and A, and the context holds the parameters, A, B : U0.

  • intro both; takes the input of the implication, as in chapter 1. The context gains both : A and B, and the goal becomes B and A.
  • both.1 and both.2 are the two components of the pair both: both.1 : A and both.2 : B. So (both.2, both.1) is a pair of a B and an A, a value of exactly the goal type. exact gives it, and that finishes the proof.

In the proof workspace, click the line number of a statement to see its goal and context; Open in workspace opens any example of this reference there. The REPL at the bottom of this page checks Cubist one entry at a time. typeof shows the type of a term, and evaluate computes its value. Here the REPL has the example above loaded:

> import unat;
Imported unat.
> use unat;
Selected unat.
> typeof and_swap;
forall A : U0. forall B : U0. A and B -> B and A
> evaluate !!and_swap;
fun (A, B : U0, both : A and B) => (both.2, both.1)
> evaluate and_swap(UNat, Unit, (3, tt));
(tt, 3)

The proof is a function of three arguments: the two statements, and the evidence for the first. The block built it, and evaluate !! shows it as a term: !! asks for the normal form, which computes inside functions too, as plain evaluate computes data and shows a function only as <fun>. Applied to the types UNat and Unit and the pair (3, tt), it swaps the pair. Fork into REPL copies the session into the REPL bar, to continue it there.

The components can also be named. obtain (a, b) := both; splits the pair into a : A and b : B:

def and_swap_again(A, B : U0) : A and B -> B and A {
  intro both;
  obtain (a, b) := both;   // a : A and b : B
  exact (b, a);
}

The checker accepts a proof only when every value has the type it is given. Here the components are in the wrong order. The first component of a B and A must be a B, and both.1 is an A:

def wrong_order(A, B : U0) : A and B -> B and A {
  intro both;
  exact (both.1, both.2);  // Error: Type mismatch: found A, expected B.
}

Using an alternative: match

Evidence of A or B is either a value of A or a value of B, and it records which (chapter 1). To use it, prove the goal in each case. If A or B holds, then so does B or A:

def or_swap(A, B : U0) : A or B -> B or A {
  intro either;                       // either : A or B
  match either {
    left(a) => { exact right(a); }    // a : A
    right(b) => { exact left(b); }    // b : B
  }
}

match either { … } splits the proof in two, one clause for each way either can have been built. In the clause left(a), it is left(a) for some a : A, and the proof gives right(a): a on the A side of B or A. In the clause right(b), it gives left(b). Each clause is a block of its own, with the component in its context and the goal, B or A. match finishes the proof once both clauses do, so it is the last statement of its block.

> import unat;
Imported unat.
> use unat;
Selected unat.
> evaluate or_swap(UNat, Unit, left(3));
right(3)
> evaluate or_swap(UNat, Unit, right(tt));
left(tt)

Putting a on the wrong side is a type error, since left of B or A takes a B:

def same_side(A, B : U0) : A or B -> B or A {
  intro either;
  match either {
    left(a) => { exact left(a); }  // Error: Type mismatch: found A, expected B.
    right(b) => { exact left(b); }
  }
}

An or is evidence of one side in particular, so a proof that uses it must handle both sides. There is no way to ask which side holds without a match, the statement here or the expression.

A proof about numbers

Every natural number has a greater one. As a type, the statement is forall n : UNat. exists m : UNat. lt(n, m): for every n there is an m with n < m. First define lt, and try it on two numbers:

import unat;
use unat;

// n < m: m is n plus a positive number, succ(k) for some k.
def lt(n, m : UNat) : U0 {
  exact exists k : UNat. succ(k) + n = m;
}

// 2 < 7: take k = 4, since succ(4) + 2 = 7.
def two_lt_seven : lt(2, 7) {
  exact (4, refl(7));
}

lt is a function that returns a type, so its value is a type in U0: lt(n, m) is the statement that n is less than m. A value of it is evidence: a number k together with a proof that succ(k) + n = m. This lt is written out to show exists at work. unat has its own <, computed rather than existential; a note at the end of this section shows how to use it.

two_lt_seven proves lt(2, 7), which unfolds to exists k : UNat. succ(k) + 2 = 7. The pair (4, refl(7)) takes k = 4, and refl(7) is accepted as evidence because succ(4) + 2 computes to 7. Any other k fails, because succ(k) + 2 would compute to a different number.

In the REPL, with the example above loaded, evaluate needs no expected value, unlike the directive:

> typeof lt;
UNat -> UNat -> U0
> evaluate !!lt;
fun (n, m : UNat) => exists k : UNat. succ(induction k return UNat { zero => n; succ h => succ(h); }) = m
> typeof two_lt_seven;
lt(2, 7)
> evaluate !!two_lt_seven;
(4, refl(7))

lt takes two numbers and returns a type in U0. Evaluating it unfolds every definition, + included. unat defines + by recursion on its first argument: 0 + b is b, and succ(a) + b is succ(a + b). So succ(k) + n computes one step, to succ(k + n). Then k + n is stuck, because k is a variable, not a numeral. The recursive definition waits for a constructor; the REPL shows it as the eliminator it elaborates to, induction k return UNat { zero => n; succ h => succ(h); }, where h is the sum for the predecessor. With a numeral in place of k, it runs to the end: succ(4) + 2 computes to 7. The chapter on structural recursion shows the definition of addition.

The same idea works for every n: succ(n) is greater than n, with k = 0. That gives the statement:

import unat;
use unat;

def lt(n, m : UNat) : U0 {
  exact exists k : UNat. succ(k) + n = m;
}

// succ(n) is greater than n: take k = 0.
def lt_succ(n : UNat) : lt(n, succ(n)) {
  exact (0, refl(succ(n)));
}

// Every number has a greater one.
def exists_greater_number : forall n : UNat. exists m : UNat. lt(n, m) {
  intro n;                       // n : UNat
  exact (succ(n), lt_succ(n));   // the witness, and the evidence
}

lt_succ proves lt(n, succ(n)), which unfolds to exists k : UNat. succ(k) + n = succ(n). The pair (0, refl(succ(n))) takes k = 0, and refl(succ(n)) is accepted as evidence because succ(0) + n computes to succ(0 + n) and then to succ(n).

exists_greater_number is proved in a block, as and_swap is. Its statement has no parameters, so at the start the context is empty and the goal is the whole statement.

  • intro n; takes the input of the forall and adds it to the context, as in chapter 1. The context holds n : UNat, and the goal becomes exists m : UNat. lt(n, m).
  • exact (succ(n), lt_succ(n)); gives a value of exactly the goal type: the witness succ(n), and the evidence lt_succ(n) : lt(n, succ(n)). It finishes the proof.

The elaborator section below shows every step of this proof.

A proof is a value like any other. Evaluating one with !! shows the term its block built:

> evaluate !!lt_succ;
fun (n : UNat) => (0, refl(succ(n)))
> evaluate !!exists_greater_number;
fun (n : UNat) => (succ(n), 0, refl(succ(n)))
> evaluate !!exists_greater_number(5);
(6, 0, refl(6))

exists_greater_number is a function: given n, it returns the witness succ(n) and the evidence (0, refl(succ(n))). The REPL writes the nested pair (succ(n), (0, refl(succ(n)))) as (succ(n), 0, refl(succ(n))): a tuple of three is a pair whose second component is a pair. Applied to 5, it gives the witness 6, with k = 0 and refl(6) as evidence that succ(0) + 5 = 6.

The same proof as a term

A proof block is a readable way to build a term. A proof of a forall statement is a function: given n, it returns the witness and the evidence. It can be written directly:

import unat;
use unat;

def lt(n, m : UNat) := exists k : UNat. succ(k) + n = m;

def exists_greater_number : forall n : UNat. exists m : UNat. lt(n, m) :=
  fun (n : UNat) => (succ(n), (0, refl(succ(n))));

Both forms produce the same kind of kernel term. The chapter on proof blocks describes every statement a block can contain.

A wrong proof is rejected with a message, and nothing is added. Here the witness is n itself, which is not greater than n: the evidence lt_succ(n) is about succ(n).

import unat;
use unat;

def lt(n, m : UNat) := exists k : UNat. succ(k) + n = m;

def lt_succ(n : UNat) : lt(n, succ(n)) {
  exact (0, refl(succ(n)));
}

def not_greater : forall n : UNat. exists m : UNat. lt(n, m) {
  intro n;
  exact (n, lt_succ(n));  // Error: Type mismatch: found lt(n, succ(n)), expected lt(n, n).
}

The elaborator

Cubist has two parts. The elaborator, written in JavaScript, reads the source and builds kernel terms: fully explicit terms, in which every function has typed parameters, every notation is expanded, and every proof statement has become part of a term. The kernel, written in C, then checks each term. Proof assistants call this first step elaboration rather than compilation. The elaborator adds detail to what you wrote, working out from the types what the source leaves implicit, and its output is never trusted: the kernel checks it again.

For the first proof, elaboration does four things:

  • Parameters become functions. def lt(n, m : UNat) : U0 { … } has the type UNat -> UNat -> U0, and its value is fun (n, m : UNat) => ….
  • Notation expands. + becomes add from unat, exists a dependent pair type, = a path type, and numerals the kernel’s 0 and succ.
  • Proof statements build the term. Each statement faces a goal and builds part of the term. intro n; builds fun (n : UNat) => ?, and exact fills the hole ? with its value.
  • The kernel receives a graph of native nodes. Each node has an opcode, such as CC_LAM for a function or CC_PI for a function type. Two nodes come from the elaborator rather than the source: exact checks its value at the goal T by applying fun (ascription : T) => ascription to it, and refl(x) is the path that stays at x, CC_PLAM.

The kernel then checks the term one node at a time, applying one typing rule to each. Entering a binder checks that its domain is a type and extends the context with the bound name. An application checks its argument against the domain of the function’s type. Wherever a type must match another, the kernel compares the two by conversion, unfolding definitions such as lt as needed.

Open Elaboration below the first proof to see each of its declarations elaborated step by step. Its Kernel row shows the kernel’s check as a forward derivation, recorded by the kernel as it ran. Each step applies one rule, such as CtxExt to extend the context or PiIntro to build a function, to earlier steps, and a comment above it gives the judgement it derives. Steps the elaborator added, such as the ascription, are marked. For more info on the kernel and its opcodes, see the kernel reference, still to be written.

import unat;
use unat;

def lt(n, m : UNat) : U0 {
  exact exists k : UNat. succ(k) + n = m;
}

def lt_succ(n : UNat) : lt(n, succ(n)) {
  exact (0, refl(succ(n)));
}

def exists_greater_number : forall n : UNat. exists m : UNat. lt(n, m) {
  intro n;
  exact (succ(n), lt_succ(n));
}

What checking means

A declaration is accepted only when the kernel accepts its term at its stated type. Only the kernel has to be correct, and it is small: it checks the finished term, not the way the elaborator found it. So a bug in a convenience, such as notation, a tactic or simplification, cannot produce an incorrect proof, because whatever the elaborator builds must still pass the kernel. At worst, such a bug makes a correct proof fail to check, and a declaration that does not check cannot be used.

Each declaration is checked on its own. A rejected declaration is not added, so a later declaration that uses it fails too, with a message naming the missing dependency:

import unat;

def wrong : UNat {
  exact UNat;  // Error: Type mismatch: found U0, expected UNat.
}

def uses_wrong := wrong;  // Error: Untranslated dependency: wrong

Here wrong fails because UNat is a type, not a number, and uses_wrong fails because wrong does not exist. The chapter on checking and inspection shows where to run the checker and how to read its results.

Files and imports

A source file has the extension .cubist. It starts with imports, followed by declarations and directives in any order:

import unat;
import hlevels;
use unat;

// Declarations and directives follow the imports.
def seven := 7;

An import names a module without quotes or a file extension. import unat; loads unat.cubist, the natural numbers, which a file imports to use numerals, +, *, < or <=: nothing is imported without being asked for. The command-line checker looks first in the directory of the file being checked, then in the library: the rebuilt library under library/, then the archived first library. The imported module is checked too, along with everything it imports.

An import makes every checked declaration of the module available, and so do the modules it imports in turn. It also brings the simplification rules and sets that those modules register. Importing a module does not make a theorem depend on that module’s assumptions. Each theorem’s assumptions are computed from its own checked term.

Imports must come first. An import after a declaration is a syntax error:

def zero_again := 0;

import unat;  // Error: Imports must come before declarations.

Names and comments

A name starts with a letter or an underscore, followed by letters, digits and underscores. Names are case-sensitive: value and Value are different names.

import unat;
use unat;

def value := 0;

def Value := 1;

Comments run from // to the end of the line. There are no block comments and no string literals. Source is plain ASCII: write ->, forall and exists, not arrows or quantifier symbols. The inspector can display mathematical symbols, but the source cannot contain them:

def arrow(A : U0) : A → A {  // Error: Unexpected character →
  intro a;
  exact a;
}

A name cannot start with a digit:

def 2nd = 0;  // Error: Expected a name.

Descriptions

// comments directly above a declaration become its description in the inspector, including when the declaration is imported. Consecutive comment lines join into one paragraph, and an empty // line starts another. A blank line separates a section comment from the declaration that follows it. A comment at the end of a line does not describe the next declaration. Descriptions are plain text and do not affect checking.

import unat;

// Section: small functions.

// The identity on numbers.
//
// A second paragraph of the same description.
def same_number(n : UNat) := n;

Here the first comment is a section comment, because a blank line follows it. The next three lines are the description of same_number.

Declarations

A declaration names a checked term. Its value follows :=, and = always means equality. There are three main forms:

FormMeaning
def name(params) := term;The term form. The result type is inferred from the term. The parameters are optional.
def name(params) : T := term;The typed term form. The term is checked against the stated type T.
def name(params) : T { … }The block form. The block is checked against the stated result type T. Use it for proofs and for constructions whose type should be stated.
def identity_term(A : U0, x : A) := x;

def same(A : U0, x : A) : A {
  exact x;
}

def second_of_two(A : U0, x, y : A) : A {
  exact y;
}

A term declaration ends with ;. A block declaration ends with }. A short term with a stated type uses the typed term form, which means the same as a block with exact:

import unat;
use unat;

def four : UNat := 4;

def four_again : UNat {
  exact 4;
}

Writing = for := is an error. In def four : UNat = 4; the checker reads UNat = 4 as the type, an equation, so it says what to write instead:

// Error: Write := to give a value: def name : T := term; here `=` read as an equality type
def four : UNat = 4;
def seven = 7;  // Error: Write := to give a value: def name := term;

A missing semicolon is reported at the next token:

def one := 1
def two := 2;  // Error: Expected ';', found 'def'.

Other declaration forms

FormMeaning
inductive Name … { … }A type defined by its constructors. See inductive declarations and functions on inductive types.
computable def name …A definition that must use no assumption. See computability.
def Name := axiom F;An assumption: a name with a type and no proof. See axioms.
evaluate term expecting value;A directive that checks what a closed term computes to. See evaluate.
simp_rule name priority N;
simp_set name := [rule, …];
Directives that register checked equalities for simplification. See registering rules.

Axioms

A definition whose whole value is axiom F assumes a statement instead of proving it. F is a type, or a family of types: a definition whose parameters, universes or values, end in a type. A type is assumed as it is. A family’s body is assumed for all values of its parameters, so the axiom’s type is the body quantified over them, not the family’s own type. The library’s classical_axioms assumes excluded middle so, as def LEM := axiom ExcludedMiddle; (excluded middle and choice).

import unat;

def Unknown := axiom UNat;

def DoubleNegationShift(U < UU0) := forall A : U. forall B : A -> U.
  (forall a : A. (B(a) -> Void) -> Void) -> ((forall a : A. B(a)) -> Void) -> Void;

def Shift := axiom DoubleNegationShift;

def shifted(B : UNat -> U0, nn : forall n : UNat. (B(n) -> Void) -> Void) :
  ((forall n : UNat. B(n)) -> Void) -> Void := Shift(U0, UNat, B, nn);

Here Shift has the type forall U < UU0. forall A : U. forall B : A -> U. …. It is one entry of the kernel’s context, which every use shares at its universe, and the kernel checks each proof that uses it with it as a hypothesis: no new rule is trusted. An axiom has no computation rule. A result that uses one lists it among its assumptions, by its module and name, as module::Shift; an axiom of the library, as read from library/ with every module it imports, is listed by its bare name, as the library’s excluded middle and choice are listed as LEM and Choice, and a module of a library module’s name from elsewhere, or edited, or one that imports such a module, is listed as any other. A computable declaration, an evaluate directive and a declared type cannot use one.

An axiom is the whole value of a top-level definition without parameters, which names it. axiom is a reserved word, and anywhere else an error:

def Pointed(A : U0) := axiom A;  // Error: An axiom is the whole value of a top-level definition without parameters: def Name := axiom Statement;

Parameters

A parameter list is a comma-separated sequence of typed binders. Consecutive parameters with the same type may share it: (A, B : U0, x, y : A) means (A : U0, B : U0, x : A, y : A). A later parameter’s type can mention earlier parameters, as x : A does.

import unat;
use unat;

def flip_arguments(A, B, C : U0, f : A -> B -> C) : B -> A -> C {
  intro b, a;
  exact f(a, b);
}

def pick_second(A, B : U0, x, y : A, b : B) := y;

def picked := pick_second(UNat, UNat, 1, 2, 3);

A declaration with parameters is a function of them. There are no implicit arguments, so pick_second takes both types, here UNat twice; an argument that the others determine can be a hole, _ (holes). Arguments can also be supplied a few at a time:

import unat;
use unat;

def first(A, B : U0, a : A, b : B) := a;

def first_number := first(UNat, UNat, 5);

def five := first_number(7);

first_number has type UNat -> UNat: it waits for the last argument. Supplying more arguments than a function takes is an error:

import unat;
use unat;

def pick_first(A, B : U0, a : A, b : B) := a;

def too_many := pick_first(UNat, UNat, 1, 2, 3);  // Error: pick_first takes 4 arguments; this is one more.

Every parameter needs a type. After x, the parser expects a colon, or a comma and another name sharing the type. A universe variable has < in place of the colon, as in U < UU0 (chapter 6):

def untyped_parameter(x) := x;  // Error: Expected ':' or '<', found ')'

Parameters or a quantified type

A statement can put its inputs in the parameters or in the result type. These two declarations have the same type, forall A : U0. A -> A:

def in_parameters(A : U0, a : A) : A {
  exact a;
}

def in_type : forall A : U0. A -> A {
  intro A, a;
  exact a;
}

Parameters are shorter. A quantified result type is better when the statement is a named proposition that other declarations reuse.

Order, scope and recursion

Declarations become available in source order. A declaration can use only the declarations above it and the imported ones. There are no forward declarations:

import unat;
use unat;

def uses_later := later;  // Error: Untranslated name: later

def later := 0;

A recursive definition can call itself on a recursive constructor argument in a match. See structural recursion for functions on natural numbers and lists, and proofs by matching for induction. Other self-calls are rejected:

import unat;

def loop(n : UNat) : UNat {
  exact loop(n);  // Error: loop is being defined: it can call itself only on an argument of a constructor
}

Each name can be declared once in a module:

import unat;
use unat;

def twice_named := 0;

def twice_named := 1;  // Error: Duplicate declaration twice_named: a declaration in this module already owns that name.

Inside a declaration, parameters and local names shadow outer ones. Pick fresh local names when a clash would be confusing to the reader.

A module's declaration is also module::name, written with no space around ::, and nothing shadows it: no parameter, local name or dimension is named with ::. A type, a constructor, a theory and a notation are named so too, as unat::UNat, unat::zero and, in use unat::unat; or unat::unat.(2 + 3), the notation unat. It is read wherever a name refers to a declaration: in a term, a match's or an induction's constructors, a theory's parent, a rule's name, a hint and a selection, and a model's field, as main::m.c; in its own declaration too, where a type's constructors name the type or a definition calls itself. Where a name is introduced, by a declaration, a binder or a parameter, it is refused:

import unat;
use unat;

// The parameter succ shadows unat's constructor; unat::succ is the constructor.
def shift(succ : UNat -> UNat, n : UNat) : UNat := unat::succ(succ(n));

evaluate shift(fun (m : UNat) => m, 1) expecting 2;

The module is the one the name is written in, or one imported, and it declares the name:

import unat;

def missing := unat::nothing;  // Error: unat declares no nothing, so unat::nothing names nothing.

def unloaded := hlevels::IsProp;  // Error: hlevels::IsProp names a declaration of hlevels, which is not imported here: import hlevels;

A declaration’s identity joins its module’s name and its own with two underscores, as the command line’s inspect shows it: unat__add. Two modules’ spellings can meet in one identity, as a::b__c and a__b::c do in a__b__c. A check that loads both refuses the later declaration, whatever either declares, so that neither name ever reads the other’s value.