Cubist

LANGUAGE REFERENCE · CHAPTER 14

The kernel: judgements, derivations and trust

The C kernel that checks every declaration: its judgements and contexts, the derivation graph, definitions, checkpoints, what is trusted, and how to read a derivation.

What the kernel is

Every declaration of this reference was checked by one program: a kernel written in C11, under kernel/ in the repository, compiled to WebAssembly for the browser and the command line. The elaborator turns Cubist source into kernel terms and chooses how to check them, but it is JavaScript and it is not trusted. It can only propose: it issues instructions, one typing rule at a time, and the kernel checks each one and answers with a judgement, or refuses. A declaration enters the kernel's registry of definitions only through the instruction Define, from a closed judgement derived this way, and only such a definition can be used by a later one.

The kernel is therefore an instruction kernel, in the style of THTH, the forward proof engine it descends from. It never searches: it does not decide for itself whether two types are equal, which definition to unfold, or where to reduce. Those decisions belong to the untrusted driver (web/cubical-instruction-driver.mjs), which names each step. The kernel compares terms by syntax alone, up to bound names, and reduces nothing unless an equality instruction names the position and the rule. The four chapters that follow describe what it stores (chapter 15), what it checks (chapter 16) and what it computes when asked (chapter 17). The source is small enough to read: the public interface is kernel/include/cubical_kernel.h, the instructions are in kernel/src/instructions.c and the files beside it, and the kernel guide in the repository follows the C function by function.

Judgements

A judgement is a fact the kernel has certified. Two kinds carry mathematical meaning:

  • a typing judgement Γ ⊢ t : T: in the context Γ, the term t has the type T;
  • an equality judgement Γ ⊢ a ≡ b : T: a and b are definitionally equal terms of type T.

Four more kinds are judgements in progress, published by instructions that build something in several steps: a composition system (a comp, Glue type or Glue term with some of its tubes or pieces), an open declared-type signature, a declared-type instance whose levels and parameters are still being supplied, and an eliminator whose clauses are still being given. Each records what it still needs; only its own instructions continue it, and a rewriting instruction refuses it. The kernel numbers these kinds 1 to 6, and cc_kernel_judgement reads any of them back: its term, its other side for an equality, its type, and the instruction, premises and operands that derived it.

Equalities are built from reflexivity by targeted steps. Refl gives t ≡ t; Step contracts one redex at a position, a path of child indices from the root of one side of the judgement (its term, the other term of an equality, or its type) to the highlighted subterm, by a named rule; Replace rewrites a highlighted occurrence of a by b given a ≡ b. Convert moves t : A to t : B along A ≡ B, and Lift moves it to a larger universe. Chapter 5 describes definitional equality from the source language's side; here, every use of it is one of these instructions, recorded in the derivation.

Contexts and their entries

A context is a set of entries, each one assumption:

  • a term entry x : A, made by Extend from a judgement Γ ⊢ A : U(ℓ); it records its type, the level ℓ, the judgement that A is a type, and the entries A depends on;
  • a level entry x < ω, made by Level: a universe variable ranging over the natural numbers, which only a level may mention (chapter 6);
  • a dimension entry, one for each interval coordinate 0 to 63, made by Dimension;
  • a face entry, the assumption that one face formula holds, made only by Restrict; it depends on the dimension entries of its equations.

Entries have no names: the kernel knows an entry by its number, and the readable spelling belongs to the elaborator, which keeps its own names for the entries it makes. Each Extend and each Level makes a new entry, so the same type extended twice gives two entries, two distinct variables; the elaborator reuses an entry by passing its number again. In a term, a variable of the context is a reference to its entry (CC_CONTEXT), and a variable that a binder binds is a de Bruijn index (CC_BOUND), so a binder carries no name (chapter 15).

Each judgement keeps only the context it depends on, and a context is closed under its entries' own dependencies. Instructions combine contexts in three ways. Merging takes the union of two premises' contexts, refusing if two distinct dimension entries would carry the same index. Discharging removes the entry a binder binds, refusing if a remaining entry depends on it, or is a dimension entry with the same index; a binder discharges exactly one entry. A binder instruction (Pi, Lambda, Sigma, LevelPi, LevelLambda, Path, PathLambda) discharges its entry and merges back the context that the entry's own type needs; Endpoint, Comp, HComp, Trans and Replace discharge alone. A face entry is discharged only by an instruction that takes a partial element on a face implying it: a composition tube, a Glue piece, a Glue value, or their agreement on an overlap. No binder discharges a dimension that a face entry needs, and Define refuses a context that still holds one.

The derivation graph

Judgements and entries form a graph, as THTH's graph store did. Each judgement records the instruction that derived it, its premise judgements in argument order, the entry it bound or used, its operands (a level, a definition reference, an endpoint, a side and a step rule, or an injection's side), for a step or a replacement the position, and the entries a replacement gives the binders its position crosses, or a signature's parameter entries. The same instruction on the same premises, operands, position and entries returns the same judgement: a stateless instruction is answered from this memo, in one budget step, instead of being derived again. Define and the instructions that admit a signature depend on the definition or signature table, which changes as they run, and are never answered from the memo: each Define makes a new definition, and each SignatureBegin a new signature.

The Elaboration panel under an example of this reference shows the derivation as the kernel built it: one line per step, numbered, with the rule's name and the numbers of its premises, and above it a comment with the judgement or context it derives. Steps the elaborator added for its own bookkeeping are marked. Reading a derivation below walks through one.

Definitions and checkpoints

Define takes a closed typing judgement, one whose context is empty, and refuses an open one. It registers the term and its type as a new definition, which has no name (the elaborator names its index), mints a reference node (CC_DEFREF) whose payload is the definition's index, and publishes the closed judgement that the reference has the type. Lookup recalls that judgement for any reference whose index names a definition. Checked terms keep references folded: the reference is one node, and conversion unfolds it only where a Step with the delta rule, or a weak-head or normal-form query, says so. Raw syntax may contain a reference node with any index, like any other inert node, but it certifies nothing, and reducing one whose index names no definition is an error.

The arena, the definitions and the judgement tables are append-only between checkpoints. cc_kernel_checkpoint marks the current sizes. cc_kernel_rollback discards everything made since the checkpoint, nodes, definitions, judgements, entries and open signatures, and clears the reduction caches. cc_kernel_commit_checkpoint keeps the definitions made since the checkpoint and the syntax they reach, compacts the arena so that the surviving nodes get new handles, translated by cc_kernel_relocated, and likewise truncates the judgement tables, so that a definition's Lookup can be issued again. The elaborator opens a checkpoint for each declaration it checks, commits it when the declaration is accepted and rolls it back otherwise, so a rejected declaration leaves nothing behind.

What is trusted

What must be trusted when a declaration is accepted is the C kernel: the instructions, the syntactic comparison they use, the substitution and restriction that build the terms they publish, and the reduction that Step and the queries perform. Nothing in JavaScript is trusted. The elaborator may be arbitrarily clever in choosing a derivation; if it chooses wrongly, the kernel refuses, and nothing is assumed.

The kernel also answers queries: the normal form, folded normal form or weak head of a term (cc_kernel_normalize, cc_kernel_normalize_folded, cc_kernel_whnf), syntactic equality up to bound names (cc_kernel_alpha_equal), a term with a free dimension renamed (cc_kernel_rename), a term at an endpoint of a dimension, and a binder's body opened with an entry (cc_kernel_instantiate, which refuses an entry the body already mentions). The weak head may be asked of a term read under binders, whose bound variables are then opened for the computation and closed again; the normal forms refuse such a term. A query computes on syntax and certifies nothing, including on terms with free variables; the driver uses its answers to pick the instructions it issues, and the kernel recomputes whatever an instruction relies on. Building syntax (cc_kernel_term, cc_kernel_formula) is likewise no certificate: a node exists, and may be ill-typed, until a judgement mentions it.

The assumptions of a declaration are not kernel state: the kernel checks each declaration against the definitions it uses, and the elaborator reports which registered assumptions those definitions depend on. The kernel's tests, make test, make sanitize and the JavaScript tests that compare it with independent reference computations, are evidence against implementation bugs, not a machine-checked soundness proof; full cubical canonicity for every constructor is not claimed.

Budgets, deadlines and limits

Every operation, an instruction or a query, starts with the step budget set by cc_kernel_set_step_budget. Each weak-head or normalization step, syntactic comparison, substitution into a node and level normal-form node takes one step, and an instruction takes one on entry, so an instruction answered from the memo still costs a step; work nested in an operation shares its budget. An operation that runs out records a BUDGET error and makes no judgement. An optional wall-clock deadline works the same way. cc_kernel_work reads cumulative counters that only grow: instructions started, rejected and their steps; queries, failed queries and their steps; operations exhausted or stopped by the deadline. The command-line checker prints the steps a check took after Checked.

A rejection has a kind: MISMATCH when a type is not the expected one, with the two types kept for diagnostics (cc_kernel_mismatch); BUDGET and DEADLINE; RESOURCE when an allocation, depth or representation limit prevented an answer, which raising the budget does not address; and OTHER for every other refusal. A resource failure never establishes a mismatch. The representation limits are: 64 interval dimensions; syntax depth 512; positions at most 1024 deep; universe levels with a finite part below 65535 and a tier at most 255; and, for declared types, 24 universe parameters, 64 term parameters, 256 constructors, 64 constructor arguments, 16 constructor dimensions and truncation level at most 14. Native recursion is limited to 448 steps and 4 MiB of stack (ck_enter, in chapter 15). Exceeding one rejects, and never accepts anything; the language chapter on limits describes what the elaborator does with such a rejection.

Reading a derivation

Open the Elaboration panel under this example. For each declaration it shows the source, the type, the proof statements with their goals and the term each builds, the finished term, and under Kernel the derivation: the instruction kernel's steps, each one rule applied to earlier steps.

import unat;
use unat;

def swap(A, B : U0, p : A and B) : B and A := (p.2, p.1);

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

def four : double(2) = 4 { rfl; }

The derivation of swap starts with the universe (UIntro), extends the context with A : U0 and B : U0 (CtxExt) and reads them as variables (Vble), forms the two pair types (SigmaForm), extends the context with p, projects it (SigmaSnd, SigmaFst), pairs the projections (SigmaIntro) and abstracts the three variables (PiIntro), each abstraction discharging its entry. The steps marked added by the elaborator build the ascription that checks the body at the stated type: a function from B × A to itself, applied to the pair (PiElim). The rule names are THTH's, shown in the panel; chapter 16 lists each instruction with the name it is shown under.

The derivation of four shows how rfl is accepted. refl(double(2)) is a constant path (PathIntro) whose type is double(2) =[UNat] double(2), not double(2) =[UNat] 4. The elaborator rewrites that type one step at a time, each step a Step instruction shown under its rule's name and the position it contracts: Delta unfolds double in the right endpoint, Beta applies it, Delta and Beta unfold and apply add, and Iota computes the recursor on the numeral, twice, until the endpoint is succ(succ(2)). The ascription function's domain is rewritten to meet it (Eta of succ, then HighSubs), and the final PiElim applies the function to the path. No step compares two types by conversion inside the kernel: each rewrites one position by one rule, and the application type-checks by syntax alone.

The same facts are available outside the browser. The command-line checker's inspect prints the checked term, its type and its assumptions, and print(inspect(…)) shows a term as the kernel checked it, in the inspector's notation for kernel terms: here the ascription that := adds around a definition's body, a function from the stated type applied to the body.

import unat;
use unat;

def swap(A, B : U0, p : A and B) : B and A := (p.2, p.1);

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

def four : double(2) = 4 { rfl; }

// Output: (λ (ascription : (double(2) =[UNat] 4)). ascription)(refl(double(2)))
print(inspect(four));
$ node cli/repl.mjs
> check kernel.cubist
Checked 3 declarations · … kernel steps
> inspect swap
kernel__swap
Expression: swap
Type: Π (A : U0), Π (B : U0), ((A × B) → (B × A))
Assumptions: none
> inspect four
kernel__four
Expression: four
Type: (double(2) =[UNat] 4)
Assumptions: none

inspect shows a definition by its name, since a checked definition is a folded reference; Π, × and =[UNat] are the inspector's notation for the kernel's Pi, Sigma and Path nodes, which forall, and and an equality type elaborate to. The kernel workbench shows the same terms as native nodes, with their handles and operands, and the judgement graph that derived them; chapter 15 explains that listing.