The term arena
Every kernel term is a node in one arena, and a term is named by its handle, a positive integer (cc_term); the handle 0 means absent, or an error. A node is immutable and holds its kind, one of the primitives below (cc_term_kind); a payload, one 32-bit number whose meaning depends on the kind: a bound variable's index, a context variable's entry, a dimension binder's dimension, a formula, a definition, signature or constructor index, or a level constant, and 0 for a term or level binder, which carries no name; and up to four children, the handles of its operand terms in slots a, b, c, d. A missing child is 0, and only the slots the table below marks optional may be missing. Nodes are built by cc_kernel_term(kind, payload, a, b, c, d), read back by cc_kernel_node, and the kernel workbench and the command-line checker's assembly print them as the listing at the end of this chapter.
Building a node certifies nothing: it is inert syntax until a judgement mentions it (chapter 14). The arena does refuse a few malformed shapes outright: a retired kind, a missing child in a required slot, a child handle that does not exist, a universe node with a payload (an older encoding), a term or level binder with a payload, a context variable whose entry is not a live term or level entry, and a formula payload that names no registered formula. Three facts about nodes matter when reading the kernel:
- Sharing. With
CC_SHARE_SYNTAX, on by default, identical syntax is one node: building a node with the same kind, payload and children as an existing one returns the existing handle. So two handles are equal exactly when the terms are identical, a stronger relation than equality up to bound names; the kernel's comparison (below) uses it as a fast path only. - Depth. Each node records its depth, one more than its deepest child; a term deeper than 512 is refused as a resource limit. The large traversals, substitution, comparison and normalization, run on explicit stacks rather than by native recursion; weak-head reduction and a few list walks recurse natively. Where reduction, normalization, comparison, level canonicalization or a rewritten position re-enters itself, each step passes the guard
ck_enter, which refuses a step, as a resource limit, past 448 steps (CC_RECURSION_LIMIT) or 4 MiB of stack (CC_STACK_BUDGET) below the outermost one. - Dependency masks and counters. Each node carries two 64-bit masks:
contexts, a filter over the entries its context variables refer to (bite mod 64for entrye), anddims, the interval dimensions it may mention; and two exact counters:loose, one more than the largest bound-variable index free in it, so0exactly when the term is locally closed, andopened, the same for the kernel's own placeholders (below). A clear bit or a zero counter proves absence, so instantiation, abstraction, substitution and comparison skip subterms without visiting them; the dimension mask is refined to exactly the free dimensions the first time a term's free dimensions are computed. Every term a judgement holds is locally closed.
Between checkpoints the arena only grows (chapter 14). Rollback truncates it, and commit compacts it, so a handle made after a checkpoint is valid until the next rollback or commit.
Interval and face formulas
Two kinds of formula appear as payloads: interval expressions such as i, ~i, i & j and i | j (chapter 11), and face formulas, disjunctions of conjunctions of endpoint equations such as (i = 0) ∨ (i = 1 ∧ j = 0). They are registered with cc_kernel_formula, numbered from 1 in order of registration, and stored once each; a formula payload is this number. Both kinds share one representation, a disjunctive normal form: a list of clauses, each a pair of 64-bit sets of dimensions, positive and negative, kept without any clause that contains another (absorption) and compared as sets. The empty list is the constant 0; the single empty clause is the constant 1. The two sorts read the same bits differently:
| Sort | Bit i in positive | Bit i in negative | Both bits in one clause |
|---|---|---|---|
| interval | the coordinate i | the reversed coordinate ~i | allowed: i & ~i is a meet, not 0 |
| face | the equation i = 1 | the equation i = 0 | contradictory: the clause is dropped |
The interval expressions form a free De Morgan algebra, not a Boolean one: i & ~i is not 0, and reversal (cc_reverse) exchanges meets with joins and each coordinate with its reversal. Substituting an interval expression for a coordinate (cc_interval_substitute) replaces i by the expression and ~i by its reversal in every clause. The face operations are built on these: cc_endpoint turns an interval expression r into the face r = 1 (one clause per monomial, each factor equal to 1) or r = 0 (every monomial has a factor equal to 0); cc_face_substitute replaces i = 1 and i = 0 in a face by r = 1 and r = 0; cc_face_forall, the universal quantification ∀i. φ, keeps exactly the clauses of φ that do not mention i (so ∀i. (i = 0) ∨ (i = 1) is 0, not 1); and cc_face_entails decides ψ ⊢ φ as: every clause of ψ contains some clause of φ. A formula may hold at most 4096 clauses, and an operation whose expansion would exceed a work bound is refused as a resource limit, never silently simplified.
Every primitive
The table lists every value of cc_term_kind, by its number in the enumeration (the opcode the workbench shows in brackets), with its children in slot order, its payload, which child slots its payload binds in, and the Cubist construct that elaborates to it. Thirteen numbers are retired: the former primitive natural numbers, W types and pushouts are now declared types, and the named variable CC_VAR gave way to bound and context variables; their kinds are kept only so that the numbers stay stable, and building one is refused. The encoding has an ABI version, 4 (CC_KERNEL_ABI_VERSION), which a client built for another version must not share handles with: version 4 replaced named variables by CC_BOUND and CC_CONTEXT, with binders that carry no name.
| Kind | № | Children (a, b, c, d) | Payload | Binds in | In Cubist |
|---|---|---|---|---|---|
CC_U | 1 | level | — | — | U0, U(ℓ): a universe |
CC_VAR | 2 | retired (the named variable of ABI 3); refused | |||
CC_PI | 3 | domain, body | — | b, index 0 | forall x : A. B, A -> B |
CC_LAM | 4 | domain, body | — | b, index 0 | fun (x : A) => b |
CC_APP | 5 | function, argument | — | — | f(a), a constructor's or eliminator's argument |
CC_SIGMA | 6 | domain, body | — | b, index 0 | exists x : A. B, A and B |
CC_PAIR | 7 | type, first, second | — | — | (a, b), with its Σ type |
CC_FST | 8 | pair | — | — | p.1 |
CC_SND | 9 | pair | — | — | p.2 |
CC_NAT | 10 | retired; refused | |||
CC_ZERO | 11 | retired; refused | |||
CC_SUCC | 12 | retired; refused | |||
CC_NATREC | 13 | retired; refused | |||
CC_UNIT | 14 | — | — | — | Unit |
CC_POINT | 15 | — | — | — | tt |
CC_PATH | 16 | family, left, right | dimension | a | x = y, PathP(fun i => A, x, y) |
CC_PLAM | 17 | family, body | dimension | a, b | path i => t; a constant one is shown as refl |
CC_PAPP | 18 | path, annotation (optional) | interval formula | — | p @ r; the annotation is the path's type |
CC_COMP | 19 | family, tubes (optional), base | dimension | a, tube terms | comp(…), transport, trans |
CC_TUBE | 20 | term, next tube (optional) | face formula | — | a wall face(i, 0, …), one cell of a list |
CC_VOID | 21 | — | — | — | Void |
CC_ABORT | 22 | type, impossible | — | — | the eliminator of Void |
CC_W | 23 | retired; refused | |||
CC_SUP | 24 | retired; refused | |||
CC_WREC | 25 | retired; refused | |||
CC_SUM | 26 | left, right | — | — | A or B |
CC_INL | 27 | sum type, value | — | — | left(a) |
CC_INR | 28 | sum type, value | — | — | right(b) |
CC_SUMREC | 29 | motive, left case, right case, value | — | — | match on A or B |
CC_UNITREC | 30 | motive, point case, value | — | — | match on Unit |
CC_GLUE | 31 | base, system (optional) | — | — | Glue(A, face(…), …) |
CC_GLUE_SYSTEM | 32 | type, equivalence, next (optional) | face formula | — | a piece face(i, 0, T, e) |
CC_GLUE_TERM | 33 | Glue type, base, tubes (optional) | — | — | glue(a, face(…), …) |
CC_UNGLUE | 34 | Glue type, value | — | — | unglue(g) |
CC_DEFREF | 35 | — | definition index | — | the name of a checked definition |
CC_PUSHOUT | 36 | retired; refused | |||
CC_PUSH_LEFT | 37 | retired; refused | |||
CC_PUSH_RIGHT | 38 | retired; refused | |||
CC_PUSH_PATH | 39 | retired; refused | |||
CC_PUSH_ELIM | 40 | retired; refused | |||
CC_HCOMP | 41 | type, tubes (optional), base | dimension | tube terms only | formal composition in a higher inductive type |
CC_TRANS | 42 | family, face tube, base | dimension | a | transport in a higher inductive type |
CC_LBOUND | 43 | — | tier; only 1, the bound ω, occurs | — | the type of a universe variable U < UU0 |
CC_LCONST | 44 | — | tier · 65536 + n | — | a constant level: U3's is 3, UU0's is ω |
CC_LSUCC | 45 | level | count, at least 1 | — | next(U) |
CC_LMAX | 46 | left, right | — | — | max(U, V) |
CC_LPI | 47 | bound, body | — | b, index 0 | the type of a universe-generic declaration |
CC_LLAM | 48 | bound, body | — | b, index 0 | its term |
CC_LAPP | 49 | function, level | — | — | its instance at a level |
CC_SORT | 50 | parameters (list, optional), recorded levels (list, optional) | signature index | — | an instance of a declared type: UNat, Trunc(U0, A) |
CC_CON | 51 | instance | constructor number | — | a constructor: zero, succ |
CC_ELIM | 52 | motive, clauses (list, optional) | signature index | — | induction and match on a declared type |
CC_LIST | 53 | item, next (optional) | — | — | a cell of a parameter, level or clause list |
CC_BOUND | 54 | — | de Bruijn index | — | a variable bound by an enclosing binder, of a term or a universe level |
CC_CONTEXT | 55 | — | entry | — | a variable of the context, of a term or a universe level |
The primitives by group
Universes and levels
A universe CC_U has one child, its level, and no payload. Levels are not terms: a level node occurs only as the child of a universe, as the level argument of CC_LAPP, in the recorded levels of a CC_SORT, and as the operand of the instructions that take a level. A level denotes an ordinal below ω²: CC_LCONST is the constant ω · tier + n, with the tier in the payload's high 16 bits and n in its low 16 bits (so U0's level has payload 0 and UU0's has payload 65536); CC_LSUCC adds its payload, at least 1, to its child; CC_LMAX is the larger of its children; a CC_CONTEXT of a level entry, or a CC_BOUND of a level binder, is a universe variable, ranging over the natural numbers. CC_LBOUND is the binder domain of a level binder, the bound ω with payload 1, and the type of a level entry; CC_LPI and CC_LLAM bind a level variable, index 0, in their body, and CC_LAPP instantiates a level function at a finite level (chapter 6). Every level an instruction publishes is in normal form.
Variables and definitions
A variable is one of two leaves, by its role. CC_BOUND is a variable bound by an enclosing term or level binder, by its de Bruijn index: 0 for the innermost binder, 1 for the next, and so on. CC_CONTEXT is a variable of the context, by its entry's number; the arena refuses one whose entry is not a live term or level entry. Whether a variable is a term or a level is its binder's or its entry's, not the node's. CC_DEFREF is a checked definition, by its index in the kernel's registry; the inspector prints it as the definition's name. It is kept folded by comparison and by the single-step exposure of heads, and unfolded only by a delta step or by the weak-head and normal-form queries (chapter 17).
Functions, pairs, sums, Unit and Void
CC_PI, CC_LAM and CC_SIGMA each hold a domain in slot a and a body in slot b, where they bind index 0; their payload is 0. CC_APP applies a function, and also a constructor CC_CON to its data and recursive arguments and an eliminator CC_ELIM to its scrutinee. CC_PAIR carries its Σ type in slot a, so that a pair's type can be read off it without reconstruction. The recursors CC_SUMREC and CC_UNITREC take a motive, their cases and the value, in that order; CC_ABORT takes the type to produce and the impossible value. Sums, Unit and Void are primitive; natural numbers are not: UNat is a declared type, as the listing below shows.
Paths, tubes and composition
A path type CC_PATH binds its dimension in the family (slot a) only; its endpoints are outside the binder. A path abstraction CC_PLAM binds its dimension in both the family and the body. A path application CC_PAPP applies the path in slot a at the interval formula in its payload; slot b is an optional annotation, the path's type, which the instructions record so that an application at 0 or 1 can be reduced to the recorded endpoint even when the path is a variable. Raw syntax may omit it; comparison ignores it, since the path and the formula determine the application.
A composition CC_COMP holds the family in slot a, a list of tubes in slot b and the base in slot c. A tube CC_TUBE is one cell of that list: the partial term, the next cell or 0, and in its payload the face formula on which the term is given. The composition's dimension is bound in the family and in every tube's term, but not in the tube faces or the base. CC_HCOMP, the formal composition of a higher inductive type, has the same shape with a constant type in slot a, where its dimension is not bound. CC_TRANS, transport in a higher inductive type, binds its dimension in the family only; its slot b is a single tube whose face is the formula on which the family is constant and whose term is a copy of the base, and every reduction reads only that face.
Glue
A Glue type CC_GLUE holds its base type and a list of pieces; a piece CC_GLUE_SYSTEM holds a partial type, an equivalence from it to the base on the piece's face, and the next piece. A Glue element CC_GLUE_TERM holds its Glue type, its base value and a list of tubes, one value per piece in the same order; CC_UNGLUE projects a value of a Glue type to the base, carrying the Glue type with it (chapter 11).
Declared types
A declared type's instance CC_SORT names an admitted signature by index and carries two lists, its term parameters and its recorded universe levels, each a chain of CC_LIST cells or 0 when empty. A universe parameter is recorded unless a term parameter's type determines it, in which case it is erased and read back from that parameter (chapter 8). A constructor CC_CON names its number and the instance; its arguments are applied with CC_APP and its path coordinates with CC_PAPP, so a point of the circle's loop is loop @ i with the constructor as the path. An eliminator CC_ELIM holds the motive and the list of clause methods, one per constructor, the truncation's squash clause included; applied to a scrutinee with CC_APP, it computes on constructors and on formal compositions (chapter 17).
Binder scopes
Only these kinds bind a variable, each in exactly the slots shown; everything else is free.
| Kind | Payload | Slot a | Slot b | Slot c |
|---|---|---|---|---|
CC_PI, CC_LAM, CC_SIGMA, CC_LPI, CC_LLAM | 0 | free (the domain or bound) | bound: index 0 | — |
CC_PATH | dimension | bound (the family) | free (left endpoint) | free (right endpoint) |
CC_PLAM | dimension | bound (the family) | bound (the body) | — |
CC_COMP | dimension | bound (the family) | bound in each tube's term, free in the tube faces | free (the base) |
CC_HCOMP | dimension | free (the type is constant) | bound in each tube's term, free in the tube faces | free (the base) |
CC_TRANS | dimension | bound (the family) | free (the face tube) | free (the base) |
A term or level binder carries no name: it binds index 0 of its body, and CC_BOUND(i) is the variable of the i-th term or level binder around it, 0 the innermost. Term and level binders count in one chain of indices; dimension binders do not count. So λ (A : U0). λ (x : A). x is Lam(U0, Lam(Bound(0), Bound(0))): in the inner domain, Bound(0) is A, and in the inner body it is x. Such binders are never renamed. Dimensions keep their names, the numbers 0 to 63, a namespace of their own, and a dimension binder is renamed to a fresh dimension when it must.
Substitution and restriction
These operations build the terms that instructions publish, all capture-avoiding and all memoized on the immutable syntax.
- Instantiation
t[a/x]of a binder's body replaces its index0bya, asApplydoes to a function type's body and abetastep to a lambda's. The value must be locally closed, which is checked in constant time and refused otherwise, so no binder oftcan capture it and no index is shifted; a dimension binder is renamed to a fresh dimension when the value put under it mentions its dimension. Only subterms with a loose index are visited, so a locally closed part costs nothing however large. - Abstraction is its converse, used by the binder instructions:
Lambda,Piand the others replace each reference to the entry they discharge by the index of the new binder. - Opening and closing. An operation that works under a binder, such as normalization, opens the body by instantiating its index with a placeholder,
CC_OPENED, the kernel's own kind, and closes the result again. A placeholder is never in a judgement, a definition or a query's answer, and building one withcc_kernel_termis refused. - Level instantiation
t[ℓ/x]for a level binder is an instantiation followed by rebuilding every level that a universe or a level application holds in normal form, so that an instance of a universe-generic definition is the term a direct derivation at that level would give. - Dimension substitution
t[r/i]replaces the free coordinateiby an interval expressionr: in a path application's formula by interval substitution, in a tube's or piece's face by face substitution, and under a dimension binder of another dimension that occurs inrafter renaming that binder to a fresh dimension. A binder ofiitself shields its bound slots, and the substitution continues into its free ones. - Restriction
t|φto one consistent face clause substitutes0or1for each dimension the clause constrains, which also rewrites the faces of tubes and pieces insidet; nothing else is done, so a restricted tube whose face becomes1is a redex, not a simplification made here.
Every instruction that states a side condition on a term it did not receive, such as the type of a tube on its face or the endpoint of a path, builds that term by these operations and compares it by syntax; the driver must have derived the same term.
Comparison, levels and cumulativity
The one comparison the instructions use is syntactic equality up to bound names (cc_kernel_alpha_equal as a query; ck_alpha_equal inside). It reduces and unfolds nothing. Two terms are equal when they have the same kind and payload where the payload is not a dimension binder's, equal children in every slot, bound dimensions that correspond pairwise under the dimension binders crossed, formulas that are equal clause sets after the dimension renamings in force, and levels that have the same normal form: under a universe, as a level application's argument, and in the recorded levels of an instance, so that U(max(ℓ + 1, ℓ)) and U(ℓ + 1) are equal types. Two standalone level nodes compared directly, as a query may, must first have the same kind like any two nodes; only then do two constants, successors or maxima compare by normal form. A definition reference compares by its index, folded. Term and level binders bind indices, so their bodies compare as they are, and a bound or context variable compares by its index or entry. A path application's annotation is ignored.
A level's normal form is either finite, a tier-0 constant c together with an offset k ≤ c for each variable it mentions, denoting max(c, x₁ + k₁, …), or a constant of tier 1 or above, which absorbs every variable. Two levels are equal for every assignment of their variables exactly when their normal forms coincide, and one is at most another for every assignment exactly when its constant and each offset are no larger, so equality and order are computed, never searched for. The instructions publish levels in a canonical syntax of this normal form: the maximum, nested to the right in the order of its variables (level entries by number, then a level binder's variables, the outer first), of each x + k, followed by the constant when it exceeds every offset or there is no variable.
Cumulativity is a separate, equally syntactic relation that only the Lift instruction uses: U(ℓ₁) is included in U(ℓ₂) when ℓ₁ ≤ ℓ₂; a Π, Σ or level Π is included in another of the same kind with an equal domain and an included body; and every other type is included only in an equal one. Sums, path types, Glue types and declared types have no inclusion of their own (chapter 6).
Reading an arena listing
The command-line checker's assembly prints a definition's nodes as the arena holds them: the handle, the kind with its opcode in brackets, the payload, the four child handles, and after ; what the payload means. The kernel workbench shows the same nodes with their judgement graph.
import unat;
use unat;
def swap(A, B : U0, p : A and B) : B and A := (p.2, p.1);
def three_path : 3 = 3 := path i => 3;
$ node cli/repl.mjs
> check terms.cubist
Checked 2 declarations · … kernel steps
> assembly swap
; Expression: %…
; Checked type: %…
%… = CC_LAM [4] payload=0 a=%… b=%… c=0 d=0 ; binds index 0 of operand b: A (…)
%… = CC_PI [3] payload=0 a=%… b=%… c=0 d=0 ; binds index 0 of operand b: A (…)
%… = CC_U [1] payload=0 a=%… b=0 c=0 d=0 ; universe; its level is operand a
%… = CC_LAM [4] payload=0 a=%… b=%… c=0 d=0 ; binds index 0 of operand b: B (…)
%… = CC_PI [3] payload=0 a=%… b=%… c=0 d=0 ; binds index 0 of operand b: B (…)
%… = CC_LCONST [44] payload=0 a=0 b=0 c=0 d=0 ; level 0
%… = CC_LAM [4] payload=0 a=%… b=%… c=0 d=0 ; binds index 0 of operand b: p (…)
%… = CC_PI [3] payload=0 a=%… b=%… c=0 d=0 ; binds index 0 of operand b: p (…)
%… = CC_SIGMA [6] payload=0 a=%… b=%… c=0 d=0 ; binds index 0 of operand b: …
%… = CC_APP [5] payload=0 a=%… b=%… c=0 d=0
%… = CC_SIGMA [6] payload=0 a=%… b=%… c=0 d=0 ; binds index 0 of operand b: …
%… = CC_BOUND [54] payload=1 a=0 b=0 c=0 d=0 ; bound variable, index 1
%… = CC_LAM [4] payload=0 a=%… b=%… c=0 d=0 ; binds index 0 of operand b: ascription…
%… = CC_PAIR [7] payload=0 a=%… b=%… c=%… d=0
%… = CC_BOUND [54] payload=3 a=0 b=0 c=0 d=0 ; bound variable, index 3
%… = CC_BOUND [54] payload=0 a=0 b=0 c=0 d=0 ; bound variable, index 0
%… = CC_SND [9] payload=0 a=%… b=0 c=0 d=0
%… = CC_FST [8] payload=0 a=%… b=0 c=0 d=0
> assembly three_path
; Expression: %…
; Checked type: %…
%… = CC_APP [5] payload=0 a=%… b=%… c=0 d=0
%… = CC_PATH [16] payload=0 a=%… b=%… c=%… d=0 ; dimension #0
%… = CC_LAM [4] payload=0 a=%… b=%… c=0 d=0 ; binds index 0 of operand b: ascription…
%… = CC_PLAM [17] payload=0 a=%… b=%… c=0 d=0 ; dimension #0
%… = CC_SORT [50] payload=… a=0 b=0 c=0 d=0 ; signature #…: unat__UNat
%… = CC_APP [5] payload=0 a=%… b=%… c=0 d=0
%… = CC_BOUND [54] payload=0 a=0 b=0 c=0 d=0 ; bound variable, index 0
%… = CC_CON [51] payload=1 a=%… b=0 c=0 d=0 ; constructor 1
%… = CC_APP [5] payload=0 a=%… b=%… c=0 d=0
%… = CC_APP [5] payload=0 a=%… b=%… c=0 d=0
%… = CC_CON [51] payload=0 a=%… b=0 c=0 d=0 ; constructor 0
In swap, the expression is a CC_LAM whose domain is the universe CC_U over the level constant 0, and whose body is the next lambda; its checked type is the matching CC_PI. Every binder has payload 0 and binds index 0 of its body; the listing names it after the source's variable. The two CC_SIGMA nodes are A × B and B × A. In A × B, the domain of p's binder, A is index 1 under the binders of A and B, and B, under the Σ's own binder too, is also index 1: both are one node. In B × A, which lies under p's binder as well, B is index 1 and A, under the Σ's binder, index 3. p.2 and p.1 are CC_SND and CC_FST of p, the innermost variable, index 0, and the CC_PAIR carries B × A as its type. The extra CC_LAM over ascription and the CC_APP that applies it are the ascription the elaborator adds to check a definition's body at its stated type; its body, its own variable, is index 0 too, the same node as p. In three_path, the type is a CC_PATH whose family is the CC_SORT UNat, bound in dimension 0, and whose endpoints are the numeral 3: the constructor succ (CC_CON number 1) applied three times with CC_APP to zero (number 0). The path itself is a CC_PLAM whose body is that numeral, which the inspector shows as refl(3). The two numerals are one node, %…: identical syntax is shared.