Cubist

LANGUAGE REFERENCE · CHAPTER 13

Checking and inspection

Where to check a proof, and how to read what the checker found.

The proof workspace

Open the proof workspace, select a topic and a proof, then use Edit and Check proof (Ctrl/Cmd+Enter). A rejected edit leaves the last checked proof available.

  • In Read mode, click a name to inspect its type and source.
  • Click a proof-step line number to see the goal and the context at that step.
  • A theorem’s assumptions are listed with it; see computability.
  • // comments directly above a declaration are shown as its description.

The checked kernel details show the expression, its type and its open context. Folded kernel notation keeps names only where their relationship to the stored term is checked. The representation selector switches between Cubist and raw kernel terms; either can be sent to the kernel workbench to explore reduction and dependencies. Binder grouping and equality notation change only the presentation. Equality notation is on by default: (A =[T] B) shows the identity type with endpoints A and B and carrier T. Turn it off to see Id with the carrier as a subscript. Both views keep their links to checked definitions.

In the source reader, keywords and built-in forms are purple, and named functions are green. UNat and its constructors are ordinary imported names; their inspection links lead to the source declaration. Numerals, tuples and arithmetic are notation: they are amber with a dotted underline. Hover over one to see its expansion; 2 shows succ(succ(0)) and a + b shows add(a, b). The index of a projection, as in p.2, is not a numeral.

Inspecting tactics

  • Click calc, rw, simp, simpa or hlevel to see the checked proof term it built. Each by inside a calc links to the path for that step.
  • A simp also shows its rewrite trace: each rule that fired, the checked path it produced, and any premise proofs found for conditional rules.
  • A multi-binder fun, forall or exists opens the whole checked term. Names bound by ext or simp … at h as h2 link to their types like any other local name.

Replace with simp only turns a checked simp, simpa or simp at into a simp only list of the rules that actually fired, in their original order. Before offering it, the elaborator reruns the simplification with just those rules and requires the same remaining goal and an equivalent proof. After the edit, the source is checked again. The action is withheld when it cannot guarantee the same result: when a used imported rule has no name in scope, when a set name would shadow a rule name, and when premise search would change. A universe-generic declaration is offered it like any other: one check covers every universe.

The command-line checker

node cli/repl.mjs checks source files with the same C kernel as the workspace. It needs the kernel built once with make wasm. Given a command, it runs that command and exits; with none, it reads one command per line. A line that is not a command is a REPL entry. The examples below use this file, saved as sample.cubist:

import unat;
import h1_classical;
use unat;

// Twice a number.
def double(n : UNat) := n + n;

def recover(P : U0, prop_ : IsProp(U0, P), nn : (P -> Void) -> Void) : P {
  exact double_negation(U0, P, prop_, nn);
}

evaluate double(2) expecting 4;

check checks the file and everything it imports. It prints the number of declarations and kernel steps, then each declaration that relies on an assumption with every assumption it relies on, each warning, each evaluate result and each print, a print followed by the assumptions its term relies on, as print typeof at line 4 assumes LEM, and exits with status 0. A file that does not check completely, its own declarations or those of a module it imports, prints each failure on a line of its own, as error E606 at line 2:3 (wrong): Type mismatch: …, an import's as (dep.bad), and exits with a nonzero status. Each code has an entry among the error messages.

$ node cli/repl.mjs check sample.cubist
Checked 2 declarations · … kernel steps
recover assumes LEM
evaluate at line 12: 4

Imports are looked up first in the directory of the checked file, then in the rebuilt library under library/, then in the archived first library. So a local module can shadow a library module of the same name, and a library module shadows an archive module. A module of the library imports only from the library, which is self-contained. A module of the archive imports from the archive, then from the library, where unat lives; an archive module always comes before a library module of the same name. One check holds one module per name: if two of its modules would load a name from different places, the check fails and names both. A bare module name, as in node cli/repl.mjs check euclid, is found in library/ first, then in the archive. A checked file is the module its name gives, as an identifier: my-proof.cubist is my_proof, whose declarations are my_proof::name. The test runner, npm test -- euclid, resolves imports the same way.

Commands

CommandEffect
check MODULE, check FILE.cubistCheck a library module or a file, with its imports
inspect NAMEShow a checked declaration: its context, expression, type and assumptions
let NAME := TERM;, def …Define a name for later entries; see the REPL
typeof TERM;Print the type of a term
evaluate TERM;Print the value of a closed term that uses no assumption, in the scope of the checked module, computed as far as it is shown; evaluate !!TERM; prints its normal form
witness TERM;Print the witness a closed truncation holds, with its type (witness)
import MODULE;Load a module for later entries
use NAME;Read operators and numerals in a notation, such as unat, in later entries
/modules [TEXT]List the modules import can load: the rebuilt library, then the archive of the first library; with TEXT, only those whose names contain it
/clear, /restartClear the terminal, or start a new session that forgets every name defined in it
assembly NAMEShow the native kernel opcode graph of a declaration
beta [expression|type]Perform one beta reduction in the inspected declaration, checked by the kernel
delta [expression|type]Unfold one named definition in the inspected declaration, checked by the kernel
export FILE.jsonSave the inspected declaration’s source and inspection data
help, /help, quitShow the command list, or exit
$ node cli/repl.mjs
> check sample.cubist
Checked 2 declarations · … kernel steps
recover assumes LEM
> inspect double
sample__double
Expression: λ (n : UNat). add(n, n)
Type: (UNat → UNat)
Assumptions: none
> evaluate double(3)
6
> inspect recover
sample__recover
Assumptions: LEM
> evaluate recover
E324: The evaluated term depends on non-computing assumptions: LEM. Path to LEM: recover (sample) → double_negation (h1_classical) → LEM.

Lines starting with > are typed commands; the other lines are output. The inspected name is shown with its module, as sample__double. Use that qualified form when a short name is ambiguous. inspect lists the assumptions a declaration uses, or none. evaluate follows the rules of the evaluate directive: a term that uses an assumption is refused, with the path through which the first one enters.

beta and delta reduce the first applicable occurrence in the inspected expression, or in its type. The kernel checks the result. The workbench can select a particular occurrence instead.

$ node cli/repl.mjs
> check sample.cubist
> inspect double
> beta expression
No applicable reduction.
> delta expression
sample__double
Expression: λ (n : UNat). (λ …)(n, n)

double is a function, so there is nothing to beta-reduce. delta unfolds add to its checked body. export saves the selected declaration’s source and inspection data; it does not save a reduction history, and the CLI cannot yet import the file.

Options

The flags --no-share-syntax, --no-reuse-checks and --no-compact-paths turn off the compiler’s reuse of shared syntax, checked instructions and compact paths. The workspace has the same switches, Reuse normal forms and Reuse checked instructions, on by default. They change how much work checking repeats, never the source language or its assumptions. The CLI guide describes setup and the remaining options.

The REPL

The REPL checks Cubist one entry at a time. An entry is a definition, a typeof or evaluate request, an import, a use, or any declaration of a file. The kernel checks each entry as a small module that imports the entries before it, so later entries see earlier names. Every result is shown with every assumption it relies on: a definition after its type, as excluded assumes LEM, and a type, a printed result or a console’s result after itself, as assumes LEM. A result that relies on none is shown alone. A use selects a notation for every entry after it, as at a file’s top level, and entries after check read in the selections the checked file ends with. An entry that does not check changes nothing.

  • In the browser, the REPL page starts from an empty program. Every page of this reference has a REPL bar at the bottom.
  • In the proof workspace, the console under a proof has the proof’s checked names loaded. After an edit is checked, the console replays its own definitions on the new version.
  • On the command line, node cli/repl.mjs reads entries along with its commands. After check, entries see the checked module’s names.
$ node cli/repl.mjs
> import unat;
Imported unat.
> use unat;
Selected unat.
> let x := 7;
x : UNat
> typeof x;
UNat
> evaluate x;
7
> import unat;
Imported unat.
> evaluate x + 3 * 4;
19
> def x_is_seven : x = 7 {
>   exact refl(7);
> }
x_is_seven : x = 7
> def x_is_eight : x = 8 {
>   exact refl(7);
> }
E606: Type mismatch: found 7 = 7, expected x = 8.
> x + 1
8
> evaluate fun (n : UNat) => n + x;
<fun>
> evaluate !!(fun (n : UNat) => x);
fun (n : UNat) => 7

A result that relies on an assumption is followed by every one it relies on, through the definitions it uses:

$ node cli/repl.mjs
> import classical_axioms;
Imported classical_axioms.
> def excluded : ExcludedMiddle(U0) := LEM(U0);
excluded : ExcludedMiddle(U0)
excluded assumes LEM
> typeof excluded;
ExcludedMiddle(U0)
assumes LEM
> print(typeof(excluded));
ExcludedMiddle(U0)
assumes LEM
> typeof tt;
Unit

let x := 7; defines x and prints its type; def works the same way. An entry continues on the next line while a bracket is open, so a proof block is one entry. A term alone is evaluated, and the final ; of an entry can be left out. An evaluation shows the term's value as far as print(evaluate(…)) does: a function is <fun>, and evaluate !!TERM; shows its normal form. x_is_eight is rejected, so it does not exist for later entries. /help lists the entries and the commands, which start with /: /modules lists the modules import can load, /clear clears the log and /restart starts a new session. The consoles on the website take the same commands.

Printing values, types and terms

Four top-level directives show what the checker makes of a closed term, and define no name. print(evaluate(term)); shows the term’s value, under the rule of evaluate: the term may use no assumption. print(typeof(term)); shows its type. print(inspect(term)); shows the term the kernel checked, in the kernel’s notation, as the inspector does: what notation and omitted arguments elaborate to. The name of a definition shows the definition’s checked body. A directive that fails is an error that makes the module incomplete, as a failed evaluate does.

import unat;
use unat;

def double(n : UNat) := n + n;

// Output: 6
print(evaluate(double(3)));
// Output: UNat -> UNat
print(typeof(double));
// Output: λ (n : UNat). add(n, n)
print(inspect(double));

The value print(evaluate(term)); shows is computed only as far as it is shown, its value form: the term's weak head, and if that is a constructor, a pair or an injection, the value forms of its parts, from the left. Any other weak head is shown by a marker of what it is, and nothing inside it is computed: <fun> for a function, <path> for a path, <level fun> for a function of a universe, <type> for a type, <composition> for a formal composition, as transport in a higher inductive type can leave one, and <neutral> for a term stuck on something that has no value, which a closed term that uses no assumption should never be. So a number with a certificate shows the number and <fun> where a proof is a function. The walk computes parts in the order the printer shows them and no more than it shows, and no deeper than the kernel's own terms, 512 levels; a part past them is shown as …, and the value is not cut at a width. The demand marks ask for something else: print(evaluate(!!term)); shows the normal form, which computes inside functions and proofs too and names a definition whose value is no data, print(evaluate(!!!term)); the full normal form, which unfolds every definition, and print(evaluate(!term)); the weak head as the kernel leaves it, its arguments not computed.

import unat;
use unat;

def double(n : UNat) := n + n;
def pair_ : UNat and (UNat -> UNat) := (double(3), double);

// Output: (6, <fun>)
print(evaluate(pair_));
// Output: (6, double)
print(evaluate(!!pair_));
// Output: (6, fun (n : UNat) => induction n return UNat { zero => n; succ h => succ(h); })
print(evaluate(!!!pair_));
// Output: (double(3), double)
print(evaluate(!pair_));
// Output: <type>
print(evaluate(UNat -> UNat));

The value form is computed by the runtime evaluator where it can be: functions, pairs, sums, Unit, types, unapplied path abstractions and the point constructors of declared types, of quotients and other higher or truncated types too, with their eliminators, run as closures over arguments computed at most once, when first needed, and no kernel term is built. A value form whose walk needs anything else, as a path applied, a path constructor, a composition or Glue, is computed again from the start by the kernel's weak-head queries, and nothing the runtime computed is shown. The two show the same value form, except at their limits: the runtime builds no term, so it computes values whose weak heads the kernel's queries cannot build (K344, K336), and it stops at its own limits of work, allocation and time with E487, E488 or E489, which the kernel does not retry. Neither certifies the value shown. What the kernel checks is the term: its type, that it is closed and that it uses no assumption. A pattern, an expected value and the demand marks are computed by the kernel's queries.

import unat;
use unat;

def count_into(n, total : UNat) : UNat := match n {
  zero => total;
  succ(k) => count_into(k, succ(total));
};

// Output: 510
print(evaluate(count_into(2 * 255, 0)));

Here the kernel's weak-head query substitutes the total into each call, so the last calls it builds are more than 512 levels deep, and it stops with K344, as print(evaluate(!!count_into(2 * 255, 0))); does; with a total of 508 it does not. The runtime keeps the total as a value it computes once, and builds no term.

An // Output: comment above a directive states what it shows. The test suite checks these comments in the examples of this reference and in the test modules of cubist-tests/, where npm run inline-errors writes them. The command-line checker prints each output as print evaluate at line N: text, and the REPL takes the directives as entries. print, typeof, inspect and witness are reserved keywords and cannot name declarations or binders.

print(witness(t)); reads the witness a closed truncation holds, with its type. The truncation's normal form is its point(w), perhaps under formal compositions, and w is shown with the type the kernel gives it. Under a transport along a path of types, the witness is of the type at the path's end. It is no eliminator out of the truncation: like evaluate, it needs a closed term that uses no assumption, and a witness with a certificate, as a number with evidence that it bounds another, carries the certificate the kernel checked. The REPL's witness TERM; does the same.

import h1_truncation;
use unat;

def above_two : Trunc(U0, exists n : UNat. 2 < n) := point((3, tt));

// Output: (3, tt) : exists n : UNat. 2 < n
print(witness(above_two));

Warnings

A declaration that checks can still bind a name it never uses. The checker warns about such a binding when it can simply be removed:

  • as k on a natural-number induction whose return type and successor branch do not use k, and as z on a match, or an induction on another declared type, whose return type does not mention z;
  • a variable of forall or exists that its body does not mention, which can be written with -> or and;
  • a let or obtain whose names nothing after it in its block uses.

It also warns about an evaluation's demand mark that asks for nothing more than its part computes already.

A name the syntax requires is never reported, even when it is unused: a parameter, a fun binder, a constructor argument or coordinate in a clause, an induction hypothesis, or a name given to intro. Nor is a let or obtain before an hlevel or a match in the same block, because those can use hypotheses without naming them. A warning does not affect checking: the declaration is checked and can be used.

import unat;
use unat;

def copy(n : UNat) := induction n as k return UNat {  // Warning: k is unused: the return type does not mention it and the successor clause does not use it.
  zero => 0;
  succ previous => succ(previous);
};

def copy_two : copy(2) = 2 { rfl; }

The workspace lists warnings under the checked declarations; click a line number to show the line. The command-line checker prints each with its code, line, column and declaration:

$ node cli/repl.mjs check unused.cubist
Checked 2 declarations · … kernel steps
warning W703 at line 4:38 (copy): k is unused: the return type does not mention it and the successor clause does not use it. Omit as k: induction n return ….

npm run lint:cubist -- FILE.cubist reports the same warnings without checking, and exits with status 1 when there are any. Without file names it lints the library, which has none.

Formatting and tests

  • npm run format:cubist -- FILE.cubist formats a source file. With --check it reports which files would change, without writing. Without file names it formats the library. The formatter keeps every token and comment and checks that the parsed syntax is unchanged.
  • npm run lint:cubist -- FILE.cubist reports unused bindings that can be removed; without file names it lints the library.
  • npm run linearize:cubist -- --check lists right-nested pairs that can be written as flat tuples; without --check, it rewrites them after checking that the expanded syntax is identical.
  • npm test runs the test suite, which includes checking the library and every example in this reference. npm test -- archive/first-library/FILE.cubist checks one library module and its imports.
  • make serve serves the workspace locally.

Limits

The parser accepts at most 1,000,000 source characters and 160,000 tokens, and nests expressions, blocks and patterns at most 128 deep. The explicit unary numeral reader builds values up to 256. Literal rules, including the default binary nat reader, read longer numeric tokens within the source and kernel limits. A tuple expands to at most 128 nested pairs. Larger numbers can be built by expressions. The kernel also bounds its work per declaration, and each simp has the budgets described in simplification. These are implementation limits, not mathematical assumptions: exceeding one rejects the declaration, and never accepts anything.

import unat;

def too_big := unat.(257);  // Error: Unary numerals are limited to 256. Import nat and use nat for binary naturals.

Chapters 14 to 17 describe the kernel itself: its judgements and what must be trusted when a proof is verified, its terms, its instructions, and its computation rules. The kernel guide in the repository follows the C implementation function by function.