How an instruction works
An instruction is one C function, cc_instr_… in kernel/include/cubical_kernel.h. It takes earlier judgements and context entries by their numbers, and operands such as a level, a face formula or a step rule; it checks its side conditions; and it publishes one judgement, or records an error and publishes nothing. Every side condition on a term is checked by syntactic equality up to bound names, on a term the instruction received or built by instantiation, abstraction, substitution or restriction; nothing is reduced or unfolded unless the instruction is Step and names the rule. An instruction does nothing while an error is recorded; cc_kernel_clear_error clears it.
The judgement's context is derived from the premises' contexts by merging, discharging and binding, as chapter 14 describes, and the result is published with the instruction's record for the derivation graph. In the tables below, Γ ⊢ t : T stands for a typing judgement given as a premise, ≡ for an equality judgement, and ≡α for the syntactic check. An instruction's result context is the union of its premises' contexts, less what it discharges, unless the table says otherwise. Every term a judgement holds is locally closed: a binder instruction abstracts the entry it discharges, so that the binder binds index 0 of its body, and B[a/x] below is the instantiation of a binder's body B at a (chapter 15).
Instructions and their names
The Elaboration panel and the workbench show each step under THTH's name for its rule; the table gives both names, with the step rules a Step is shown under in place of Step. The numbers are the instruction opcodes of cc_instruction; eleven are retired.
| Group | Instruction (opcode) | Shown as |
|---|---|---|
| Entries | Extend, Level, Dimension (not instructions; they return entries) | CtxExt, CtxExt, DimExt |
| Variables | Variable (14), Endpoint (38), Restrict (74), Define (27), Lookup (28) | Vble, Endpoint, Restrict, Def, DefLookup |
| Universes | Universe (1), LevelPi (61), LevelLambda (62), LevelApply (63) | UIntro, LevelForm, LevelIntro, LevelElim |
| Functions, pairs | Pi (15), Lambda (16), Apply (17), Sigma (18), Pair (19), First (20), Second (21), Domain (22), Family (23) | PiForm, PiIntro, PiElim, SigmaForm, SigmaIntro, SigmaFst, SigmaSnd, Domain, Family |
| Unit, Void, sums | Unit (6), Point (7), UnitElim (8), Void (9), Abort (10), Sum (11), Inject (12), SumElim (13) | UnitForm, UnitIntro, UnitElim, VoidForm, VoidElim, SumForm, SumIntro, SumElim |
| Paths | Path (24), PathLambda (25), PathApply (26), PathAt (39) | PathForm, PathIntro, PathElim, PathElim |
| Composition | System (40), SystemTube (41), SystemOverlap (43), Comp (42), HComp (51), Trans (52) | CompBase, CompTube, CompOverlap, Comp, HComp, Transp |
| Glue | GlueBase (53), GluePiece (54), GlueOverlap (55), Glue (56), GlueTermBase (57), GlueTermPiece (58), GlueTerm (59), Unglue (60) | GlueBase, GluePiece, GlueOverlap, GlueForm, GlueIntroBase, GlueIntroPiece, GlueIntro, GlueElim |
| Declared types | SignatureBegin (64), SignatureConstructor (65), SignatureClose (66), SortBegin (67), SortLevel (68), SortParameter (69), Construct (70), Eliminator (71), EliminatorClause (72), EliminatorClose (73) | SignatureBegin, SignatureCons, SignatureClose, SortBegin, SortLevel, SortParameter, ConIntro, ElimBegin, ElimClause, ElimClose |
| Equality | Refl (29), Step (30), Replace (31), Eta (32), Side (33), Symmetry (34), Transitivity (35), Convert (36), Lift (37) | DefEqRefl; Beta, Delta, Iota, PathBeta, Normalize, Whnf or Face by its rule; HighSubs, Eta, DefEqExt, DefEqSwp, DefEqTrans, Conv, Lift |
Context entries
Three functions make entries rather than judgements, and return the entry's number.
Extend(type)makes a new term entryx : Afrom a typing judgementΓ ⊢ A : U(ℓ). The entry's scope isΓtogether with itself.Level()makes a new level entryx < ω, whose type is the boundLBound(1).Dimension(index)returns the one dimension entry of an index below64.
Entries have no names, and every Extend or Level makes a new one, even from the same judgement: two entries are two variables. The elaborator keeps its own names for them and reuses an entry by passing its number again. A face entry is made only by Restrict, below.
Variables, endpoints, faces and definitions
| Instruction | Premises and checks | Publishes |
|---|---|---|
Variable(x) | a term entry x : A; a level, dimension or face entry is refused | Γ, x : A ⊢ x : A, in the entry's scope; the term x is the reference CC_CONTEXT to the entry |
Endpoint(j, i, ε) | Γ, i ⊢ t : T, a dimension entry i, ε is 0 or 1; i is discharged, so no other entry may depend on it | Γ ⊢ t[ε/i] : T[ε/i] |
Restrict(j, φ) | Γ ⊢ t : T and a face formula of one consistent clause with at least one equation | Γ, φ ⊢ t|φ : T|φ, with the face entry of φ added; unlike Endpoint it succeeds while entries depend on the face's dimensions, and only a partial element on a face implying φ discharges the face entry |
Define(j) | a closed typing judgement ⊢ t : T (empty context) | ⊢ ref : T, where ref is a new definition reference whose index names (t, T); never answered from the memo, so two Defines of one judgement make two definitions |
Lookup(ref) | a reference node whose index names a definition | ⊢ ref : T |
Universes and universe levels
| Instruction | Premises and checks | Publishes |
|---|---|---|
Universe(ℓ) | a level whose variables are level entries and whose normal form's constant is below 65535 | Γ ⊢ U(ℓ) : U(ℓ + 1), both levels in normal form, in the context of the level entries ℓ mentions |
LevelPi(x, j) | a level entry x and Γ, x < ω ⊢ B : U(ℓ); x is discharged | Γ ⊢ Π (x < ω). B : U(lim), where lim is ω when x occurs in the normal form of ℓ, and that normal form otherwise |
LevelLambda(x, j) | a level entry x and Γ, x < ω ⊢ t : B; x is discharged | Γ ⊢ λ (x < ω). t : Π (x < ω). B |
LevelApply(j, ℓ) | Γ ⊢ f : Π (x < ω). B and a finite level ℓ (tier 0; ω itself is refused) whose variables are level entries | Γ ⊢ f {ℓ} : B[ℓ/x], with ℓ and every level of the result in normal form |
A universe-generic declaration (chapter 6) is a LevelLambda whose type is a LevelPi; using it at U2 is a LevelApply at the level 2. A level variable ranges over the natural numbers only, so LevelApply refuses ω, the level of UU0.
Functions and pairs
| Instruction | Premises and checks | Publishes |
|---|---|---|
Pi(x, j) | a term entry x : A, with A : U(ℓ₁), and Γ, x : A ⊢ B : U(ℓ₂); x is bound | Γ ⊢ Π (x : A). B : U(max(ℓ₁, ℓ₂)) |
Lambda(x, j) | a term entry x : A and Γ, x : A ⊢ b : B; x is bound | Γ ⊢ λ (x : A). b : Π (x : A). B |
Apply(f, a) | Γ₁ ⊢ f : Π (x : A). B and Γ₂ ⊢ a : A' with A' ≡α A | Γ₁ ∪ Γ₂ ⊢ f(a) : B[a/x] |
Sigma(x, j) | as Pi | Γ ⊢ Σ (x : A). B : U(max(ℓ₁, ℓ₂)) |
Pair(T, a, b) | Γ₁ ⊢ Σ (x : A). B : U(ℓ), Γ₂ ⊢ a : A' with A' ≡α A, and Γ₃ ⊢ b : B' with B' ≡α B[a/x] | Γ₁ ∪ Γ₂ ∪ Γ₃ ⊢ (a, b) : Σ (x : A). B, the pair carrying its type |
First(p), Second(p) | Γ ⊢ p : Σ (x : A). B | Γ ⊢ p.1 : A; Γ ⊢ p.2 : B[p.1/x] |
Domain(j) | Γ ⊢ F : U(ℓ), F a Π or Σ type (x : A). B | Γ ⊢ A : U(ℓ) |
Family(j, a) | as Domain, and Γ₂ ⊢ a : A' with A' ≡α A | Γ ∪ Γ₂ ⊢ B[a/x] : U(ℓ) |
Domain and Family recover the parts of a type former as types in its universe, which cumulativity allows; the elaborator uses them to type a binder from a function type it already has. The type of a function is the Π type as written, so Apply compares the argument's type with the domain by syntax: an argument whose type is equal only by computation must first be converted (below).
Unit, Void and sums
| Instruction | Premises and checks | Publishes |
|---|---|---|
Unit(), Point(), Void() | none | ⊢ Unit : U0; ⊢ tt : Unit; ⊢ Void : U0 |
UnitElim(M, b, u) | M : Π (x : Unit). U(ℓ), b : M(tt) up to syntax, u : Unit | unitrec(M, b, u) : M(u) |
Abort(T, e) | T : U(ℓ) and e : Void | abort(T, e) : T |
Sum(A, B) | A : U(ℓ₁) and B : U(ℓ₂) | A + B : U(max(ℓ₁, ℓ₂)) |
Inject(S, v, right) | S = A + B : U(ℓ) and v : A, or v : B when right | inl(v) : A + B or inr(v) : A + B, the injection carrying the sum type |
SumElim(M, l, r, v) | M : Π (z : A + B). U(ℓ), l : Π (x : A). M(inl(x)), r : Π (y : B). M(inr(y)), both up to syntax, and v : A + B | sumrec(M, l, r, v) : M(v) |
A motive is checked as a function type into a universe whose domain is the eliminated type, and a case's type is compared, up to bound names, with the type the motive gives it. The natural numbers are not here: UNat is a declared type, and induction on it is its eliminator.
Paths
| Instruction | Premises and checks | Publishes |
|---|---|---|
Path(i, A, l, r) | a dimension entry i, Γ₁, i ⊢ A : U(ℓ), Γ₂ ⊢ l : A[0/i] and Γ₃ ⊢ r : A[1/i], the endpoint types up to syntax; i is bound in A | Γ₁ ∪ Γ₂ ∪ Γ₃ ⊢ Path(i. A, l, r) : U(ℓ) |
PathLambda(i, j) | a dimension entry i and Γ, i ⊢ b : A; i is bound | Γ ⊢ ⟨i⟩ b : Path(i. A, b[0/i], b[1/i]) |
PathApply(p, j, ε) | Γ ⊢ p : Path(i. A, l, r) and a dimension entry j, or no entry and an endpoint ε | Γ, j ⊢ p @ j : A[j/i], or Γ ⊢ p @ ε : A[ε/i]; the application carries the path's type as its annotation |
PathAt(p, r) | Γ ⊢ p : Path(i. A, l, r) and an interval expression r | Γ, Δ ⊢ p @ r : A[r/i], Δ the dimension entries r uses, annotated as above |
Note what PathApply does not do: p @ 0 is published at the type A[0/i], not l. That p @ 0 equals l is a Step with the path rule, which reads the endpoint from the annotation (chapter 17). The annotation is what makes this possible when p is a variable, and it is why chapter 15 describes it as the instructions' addition to the syntax.
Composition systems
A composition comp^i A [φ ↦ u] a₀ : A[1/i] is built one tube at a time, as a system judgement (kind 3) that holds the composition so far as its term and A[1/i] as its type, together with a pending set of earlier tubes the latest tube overlaps and has not yet been shown to agree with.
| Instruction | Premises and checks | Publishes |
|---|---|---|
System(i, A, a₀) | a dimension entry i, Γ₁ ⊢ A : U(ℓ) and Γ₂ ⊢ a₀ : A' with A' ≡α A[0/i]; a₀ must not use i | the system comp^i A [] a₀, with nothing pending |
SystemTube(s, φ, u, e) | a system with nothing pending; a face formula of at most one clause. On the face 0, any typing judgement u and no equality: the tube is never used. On a clause φ: it is consistent and does not mention i; u mentions none of its dimensions (it is already restricted); u : A|φ; and the equality e is u[0/i] ≡ a₀|φ, both sides up to syntax. Face entries that φ implies are discharged from u's and e's contexts | the system with the tube appended, and pending every earlier tube whose face is compatible with φ; a compatible tube at position 64 or above is a resource refusal |
SystemOverlap(s, n, e) | the system's latest tube overlaps the tube at position n; e is u|ψ ≡ v|ψ on the conjunction ψ of the two faces, up to syntax, with the face entries ψ implies discharged | the system with position n no longer pending; also used for a Glue term's tubes |
Comp(s) | a system with nothing pending; i is discharged | Γ ⊢ comp^i A [φ ↦ u] a₀ : A[1/i] |
HComp(s) | as Comp, and A does not use i and its weak head is an instance of an admitted higher declared type | Γ ⊢ hcomp^i A [φ ↦ u] a₀ : A |
Trans(s, φ) | as Comp, with A's weak head an instance of a higher declared type, and the system's tubes exactly the clauses of φ in order, each tube's term a₀ restricted to its clause, up to syntax | Γ, Δ ⊢ transp^i A φ a₀ : A[1/i], Δ the dimensions φ uses |
The source-level comp(family, base, walls…) (chapter 11) is a System, one SystemTube per wall with the agreement equalities the elaborator derives, the SystemOverlaps where walls meet, and a Comp. A wall written on a face of several clauses is split by the elaborator into one tube per clause. HComp and Trans close the same kind of system into the formal operations of a higher inductive type; an ordinary data type, one with no path constructor and no truncation, has neither, and composes by Comp, which computes on its constructors (chapter 17).
Glue
A Glue type Glue [φ ↦ (T, e)] A and a Glue term are built the same way as a composition, piece by piece, as system judgements.
| Instruction | Premises and checks | Publishes |
|---|---|---|
GlueBase(A) | Γ ⊢ A : U(ℓ) | the system Glue [] A : U(ℓ) |
GluePiece(s, φ, T, e) | a Glue system with nothing pending, a face of at most one clause, T : U(ℓ') and e : E. On a clause: T and e mention none of its dimensions, E ≡α Equiv(T, A|φ), the equivalence type as cc_kernel_equiv_type states it, and the face entries φ implies are discharged | the system with the piece appended, its universe raised to U(max(ℓ, ℓ')), and pending the earlier pieces whose faces overlap, with the same position bound as tubes |
GlueOverlap(s, n, t, e) | the latest piece overlaps piece n; t and e are equalities of the two types and of the two equivalences, each restricted to the overlap, up to syntax | the system with position n no longer pending |
Glue(s) | a Glue system with nothing pending | Γ ⊢ Glue [φ ↦ (T, e)] A : U(ℓ) |
GlueTermBase(G, a) | Γ₁ ⊢ G : U(ℓ), G a Glue type over A, and Γ₂ ⊢ a : A' with A' ≡α A | the system glue(a, []) : G |
GlueTermPiece(s, t, e) | for the next piece (φ, T, e') of G in order: t : T, t mentioning none of the face's dimensions, and the equality e is fst(e')(t) ≡ a|φ; on the face 0, only t's typing. Overlaps are resolved with SystemOverlap | the system with [φ ↦ t] appended |
GlueTerm(s) | a Glue term system with nothing pending and one tube per piece of G | Γ ⊢ glue(a, [φ ↦ t]) : G |
Unglue(g) | Γ ⊢ g : G, G a Glue type over A | Γ ⊢ unglue(g) : A |
Equiv(A, B) is Σ (f : A → B). Π (y : B). IsContr(Fiber(f, y)) with Fiber(f, y) = Σ (x : A). Path(B, y, f(x)) and IsContr(F) = Σ (c : F). Π (p : F). Path(F, c, p): a function whose fibers are contractible, as the library's contractible_maps defines it. No equivalence is primitive; univalence is built from these instructions.
Declared types
An inductive declaration (chapter 8) is admitted as a signature, one constructor at a time, from judgements derived by the ordinary instructions in a context of the signature's own entries. The kernel checks that each constructor type has the normal form the H1 specification requires, as written: data arguments, then recursive positions, then a result that is the sort or an iterated path type over it with boundaries built from earlier constructors and positions.
| Instruction | Premises and checks | Publishes |
|---|---|---|
SignatureBegin(F, modifier, es, s, recorded) | a closed ⊢ F : U(…) where F is Π (xs < ω). Π (ps : Ps). U(ℓ): at most 24 universe parameters, each bounded by ω, then at most 64 term parameters; the entries es that stand for them, one for each in order, a level entry for a universe parameter and a term entry for a term parameter, at its domain with the entries before it put for the binders before it; a term entry s that stands for the sort, at U(ℓ) with all of them put in; all these entries distinct; a truncation modifier, 0 for none or n + 2 for trunc(n), at most 16; and a bitmask of the recorded universe parameters, where every other one must be determined by a term parameter whose type ends in exactly U(x) | a signature judgement (kind 4) whose term is the new signature's sort and whose type is F |
SignatureConstructor(s, T, c) | the signature's latest judgement; Γ ⊢ T : U(ℓ) at the signature's level by normal form, where every entry of Γ is a parameter entry, the sort entry, or an earlier constructor's entry; and a term entry c : T, new to the signature, that stands for this constructor in later constructor types. T mentions no erased universe parameter, and has the normal form: at most 64 data and position arguments, each position's arity at most 64 binders over data types with a cube of at most 16 path layers over the sort, and a result cube of at most 16 layers whose boundaries are constructor expressions | the next signature judgement, with the constructor recorded: its type is stored closed over the signature's telescope, its universe parameters, term parameters, sort and earlier constructors, which Construct instantiates at once |
SignatureClose(s) | the latest judgement of an open signature | the signature's index, from 1, after appending the truncation's squash constructor if any; an admitted signature never changes |
SortBegin(index) | an admitted signature | an instance in progress (kind 5), or the complete instance when the signature has no recorded levels and no parameters |
SortLevel(s, ℓ) | the next recorded universe level, a finite level in normal form with constant below 65535, before any parameter | the next instance judgement |
SortParameter(s, a) | the next term parameter's judgement Γ ⊢ a : A | the next instance judgement; with the last, the complete instance: each erased level is read from the universe at the end of the type of the first parameter that determines it, every parameter's type must then equal the telescope's at those levels and the earlier parameters, so a second reading at another level is refused, and the result is Γ ⊢ S{ls}(as) : U(ℓ[ρ]) |
Construct(I, k) | a complete instance Γ ⊢ I : U(…) and a constructor number | Γ ⊢ Con(k; I) : Tₖ, the constructor's declared type with the instance for the sort, the recorded levels, the parameters, and Con(m; I) for each earlier constructor |
Eliminator(M) | Γ ⊢ M : Π (z : I). U(ℓ) over a complete instance of an admitted signature | an eliminator in progress (kind 6) whose type is the first clause's type, or Π (z : I). M(z) at once when the signature has no constructors |
EliminatorClause(e, m) | a judgement m whose type equals, up to bound names, the type the eliminator in progress shows: ClauseTypeₖ, computed by substitution with no reduction, over the constructor's arguments, each position's displayed induction hypothesis, and a result cube whose boundaries show positions by their hypotheses and earlier constructors by their clauses | the eliminator with the clause added and the next clause's type, or Π (z : I). M(z) after the last |
EliminatorClose(e) | an eliminator with a clause for every constructor, the squash included | Γ ⊢ Elim(M, ms) : Π (z : I). M(z) |
The first three instructions depend on the signature table, which changes as they run, so they are never answered from the derivation memo. The entries a signature is admitted over are read only while it is open: an admitted signature's constructor types mention none of them. The H1 specification states the normal form and the elimination rules in full; induction and match on a declared type elaborate to Eliminator, one EliminatorClause per clause and EliminatorClose, applied to the scrutinee with Apply.
Equality, conversion and rewriting
| Instruction | Premises and checks | Publishes |
|---|---|---|
Refl(j) | Γ ⊢ t : T | Γ ⊢ t ≡ t : T |
Side(e, n) | Γ ⊢ a ≡ b : T and a side 0 or 1 | Γ ⊢ a : T or Γ ⊢ b : T |
Symmetry(e) | Γ ⊢ a ≡ b : T | Γ ⊢ b ≡ a : T |
Transitivity(e₁, e₂) | Γ₁ ⊢ a ≡ b : T and Γ₂ ⊢ b' ≡ c : T' with b' ≡α b and T' ≡α T | Γ₁ ∪ Γ₂ ⊢ a ≡ c : T |
Convert(j, e) | Γ₁ ⊢ t : A and Γ₂ ⊢ A' ≡ B : U(ℓ) with A' ≡α A | Γ₁ ∪ Γ₂ ⊢ t : B |
Lift(j, T) | Γ₁ ⊢ t : A and Γ₂ ⊢ B : U(ℓ) with A cumulatively included in B | Γ₁ ∪ Γ₂ ⊢ t : B |
Eta(j) | Γ ⊢ t : T with T a Π, level Π, Σ, path or Glue type | Γ ⊢ t ≡ t' : T, where t' is λ (z : A). t(z), λ (z < ω). t {z}, (t.1, t.2), ⟨j⟩ t @ j with a fresh dimension, or glue(unglue(t), [φ ↦ t]) with t on every piece |
Step(j, side, position, rule) | a typing or equality judgement, a side (0 the term, 1 an equality's other term, 2 the type), a position of at most 1024 child indices leading to a subterm, and a step rule that contracts that subterm (chapter 17) | the same judgement with the contractum in place of the subterm, in the same context. Under binders, the subterm's bound variables are opened with placeholders for the contraction and closed again |
Replace(j, side, position, e, entries) | a typing or equality judgement, Γ' ⊢ a ≡ b : T', and an entry, or 0, for each term or level binder the position crosses, outermost first: the entry that stands for the binder's variable in e, of the binder's kind, at the binder's domain with the outer binders' entries put in, new to the judgement's context, and given to one binder only; 0 for a binder the subterm does not use. The subterm at the position, with those entries put for its bound variables, is a up to syntax; a path application's annotation may be replaced only by a path type. Walking outward along the dimension binders the position crosses, one whose dimension occurs free in a, b or a given entry's type must correspond to a dimension entry of Γ', which is discharged; a subterm that uses a composition's bound dimension cannot be replaced; and no entry left in Γ' may depend on a given entry | the judgement with b, its given entries turned back into the binders' indices, in place of a, in Γ together with what remains of Γ' once the given entries are discharged; the entries are part of the derivation, so the same replacement with other entries is another one |
A step on a typing judgement's term is subject reduction; on its type, it keeps a type. To derive t ≡ t' : A from t : A, the driver takes Refl and then steps on side 1. Everything chapter 5 calls computation happens through these two instructions, each naming the position and the rule, so a derivation records exactly which redexes were contracted to accept a declaration, and nothing is contracted that the derivation does not show.
import unat;
use unat;
def one_plus_one : 1 + 1 = 2 { rfl; }
The Elaboration panel shows the derivation: the numerals and add are built with ConIntro, PiElim and DefLookup, the path type with DimExt and PathForm, and the constant path with PathIntro. Then Delta, Beta and Iota steps rewrite the path's type, and Eta and HighSubs the ascription's domain, each at a stated position, until the two meet by syntax, and the ascription is applied with PiElim.
Retired instructions
Eleven opcodes remain in cc_instruction so that the numbers stay stable, and have no C entry point: the primitive natural numbers (2 to 5), pushouts (44 to 47) and W types (48 to 50). Each of those types is now a declaration in the library, admitted through the declared-type instructions like any other.