When the kernel computes
The kernel reduces a term in exactly three situations. A Step instruction contracts one subterm by a named rule (chapter 16). The weak-head query cc_kernel_whnf and the normal-form query cc_kernel_normalize compute on syntax for inspection and for the driver's search; they certify nothing, and two of the step rules, whnf and normalize, let a derivation take their result as a contraction. And a few instructions look at a weak head to decide a shape, never to decide an equality: HComp and Trans ask whether the family is an instance of a higher declared type.
Chapter 5 describes computation as the source language sees it, with evaluate showing normal forms. This chapter gives the rules the C implements: what each contracts, in which order the rules are tried, and what the result is. The functions named are those of kernel/src; the kernel guide states each formula in full.
import unat;
use unat;
def double(n : UNat) := n + n;
def four := double(2);
def three_path : 3 = 3 := path i => 3;
def const_family(X : U0) := UNat;
def moved : UNat := transport 3 along refl(Unit) in const_family;
def two_or_three(b : Unit or Unit) : UNat :=
match b return UNat { left u => 2; right u => 3; };
// Output: 4
print(evaluate(four));
// Output: 3
print(evaluate(three_path @ 1));
// Output: 3
print(evaluate(moved));
// Output: 3
print(evaluate(two_or_three(right(tt))));
// Output: (λ (ascription : UNat). ascription)([i]. comp(const_family(at(refl(Unit), i:1)), 3))
print(inspect(moved));
Each of these normal forms is reached by the rules below: four by unfolding and applying double and add and computing the recursor; three_path @ 1 by the path rule at an endpoint; moved, a composition over a family that does not vary, by the composition rules; and the match by the sum recursor on a constructor.
The single-step rules
A Step contracts the subterm at its position by one of these rules (contract in kernel/src/instruction_equality.c). The first four and the face rule are purely syntactic: they look at the subterm as written and reduce nothing else. The redex must have the stated shape, or the step is refused.
| Rule | Redex, as written | Contractum |
|---|---|---|
beta | (λ (x : A). b)(a); (λ (x < ω). b) {ℓ} | b[a/x]; b[ℓ/x] with every level of the result in normal form |
delta | a definition reference | the definition's checked body |
iota | (a, b).1, (a, b).2; unitrec(M, b, tt); sumrec(M, l, r, inl(v)), sumrec(M, l, r, inr(v)); an eliminator applied to a constructor, at dimensions or not | a, b; b; l(v), r(v); the clause method applied to the arguments and the induction hypotheses, not β-reduced (below) |
path | (⟨i⟩ b) @ r, tried first at any r; otherwise p @ 0 or p @ 1 whose annotation is Path(i. A, l, r) | b[r/i]; l or r, read from the annotation |
normalize | any term | its normal form |
whnf | any term | its weak-head normal form |
face | comp or hcomp with a tube on the face 1; transp on the face 1 | that tube's term at the end of the direction, u[1/i]; the base |
glue | glue(b', [φ ↦ t]) whose base b' reduces to unglue(b), possibly through nested Glue steps | b, when the two Glue types agree and t and b agree on each clause of φ, each agreement decided by syntax after reducing only as far as that takes |
split | comp or hcomp with a tube on a face of several clauses, or on the face 0 | the same with one tube per clause, each the same term, and no tube on 0 |
Note the order inside the path rule: a path written as an abstraction is substituted into even at an endpoint, and only a path that is not one has its endpoint read from the annotation. Weak-head reduction, below, does the opposite. The iota rule for a declared type returns an application of the clause method, which further beta steps reduce; chapter 14's example shows the two steps in a derivation.
The command-line checker's beta and delta commands issue these steps at the first applicable position of the inspected expression, checked by the kernel:
$ node cli/repl.mjs
> check reductions.cubist
Checked 6 declarations · … kernel steps
> inspect four
reductions__four
Expression: double(2)
Type: UNat
> delta expression
reductions__four
Expression: (λ (n… : UNat). add(n…, n…))(2)
> beta expression
reductions__four
Expression: add(2, 2)
> beta expression
No applicable reduction.
Weak-head normal form
ck_whnf reduces a term until its head is a constructor, a binder, a neutral application or a formal operation that does not compute, by call-by-name: an application reduces its function first, not its argument, and an eliminator reduces its scrutinee, not its branches. Results are memoized by handle. One head step is performed by the worker weak, which either returns a finished head or hands the next term to a driver loop; reducing the head of an eliminated subterm, the function of an application, the pair of a projection or the path of a path application, is a nested call, bounded by the recursion guard ck_enter: 448 nested steps, or 4 MiB of stack, below the outermost. The cases, in the order the code tries them:
- Formal operations.
hcompandtranspgo to the higher-inductive rules;compgoes to the composition rules. Each returns a finished head. - Definitions. A reference unfolds to its checked body; a reference naming no definition is an error.
- Glue. A Glue type or term drops its pieces or tubes on the face
0, and reduces to a piece's type or a tube's term when its face is1. A Glue termglue(b', [φ ↦ t])whose base's weak head isunglue(b)at the same Glue type, up to syntax, reduces tobwhen everytis, by syntax,brestricted to each clause of its face: Glueηwith syntactic side conditions.unglue(g), whose Glue type must be written as such, reduces to the function of the piece's equivalence, its first component, applied togwhen a piece has face1, and otherwise to the base ofg's weak head when that is a Glue term. - Applications.
f(a)reducesf; a lambda is applied by substitution, an eliminator eliminates the weak head ofa, and anything else is neutral.f {ℓ}likewise applies a level lambda by instantiation. A projection reduces its pair and takes the component when the head is a pair. - Recursors.
unitrecreduces its value and takes the point case ontt;sumrecreduces its value and applies the matching case on an injection. - Path applications.
p @ rwithrequal to0or1and a path-type annotation reduces to the recorded endpoint without reducingp. Otherwise it reducesp, and substitutesrinto the body when the head is a path abstraction. An application without an annotation reduces only when its path's weak head is an abstraction; a neutral path there is an error, since its endpoints are unknown. - η-contractions. A lambda whose body applies a term to its own variable, a level lambda likewise, a path abstraction whose body applies a path to its own dimension, and a pair of the two projections of one term, contract to that term when it does not mention the bound name.
In source, the demand mark ! of an evaluation's pattern asks for this weak head, through the query cc_kernel_whnf, η-contractions included, !! for the folded normal form, and !!! for the normal form.
ck_expose is a narrower helper used only by the higher-inductive rules: at most one contraction of a top-face composition, an annotated endpoint, an application of a lambda, or a projection of a pair, without unfolding a definition at the root.
Normal form
ck_normal computes a strong normal form under every binder, with an explicit stack and a memo by handle. Each node is reduced to weak-head form, then its children are normalized and the node rebuilt; if the rebuilt node is a new redex, as when a composition's family became a constructor type, it is reduced again. Two details are particular to cubical terms. A partial term, a composition tube or a Glue piece, is first restricted to the endpoint equations common to every clause of its face, so that what is shown on i = 0 has 0 for i; a composition's own direction never occurs in its tube faces, so this never captures it. And a rebuilt Glue term is checked for Glue η against the normalized restrictions of its unglued base, since restricting can create the redex that makes the pieces agree.
A normal form is what evaluate !!! prints, what witness reads, and what the normalize step takes as a contraction. The weak-head and normal-form caches are cleared by every rollback and commit, since they may point forward to nodes those discard.
ck_normal_folded, the query cc_kernel_normalize_folded, computes the folded normal form with the same stack and a memo of its own. The term asked for is reduced to its weak head and its parts taken in turn, as above. Each part is reduced to its weak head too, by the steps ck_whnf takes, remembering the first definition, applied or projected, that those steps pass through. If the head is data, a constructor applied, a pair, an injection, a point, a glued element, or a variable applied, the part is computed; otherwise the definition stays as written, its arguments in folded normal form, so a function, a path, a type, or an eliminator or composition stuck on a variable is not unfolded. A stuck elimination reached through no definition, an eliminator, recursor, abort or unglue that its last step rebuilt in place, with only its stuck part changed, an eliminator applied left as it was, and the function it is applied to or projected from, if that changed, rebuilt in place by one step of its own, is taken as that step's term, since the head holds its stuck value reduced and the term holds it as written; any other head is taken as computed, a transport's formal composition, a composition with its tubes on empty faces dropped, or an eliminator another step exposed, as f(x) does when f is an eliminator by η, or a match that computes f, and f(x) applied or projected, so that the term asked for stays unfolded. Only η contracts a node rebuilt from folded parts, since reducing it again would unfold them. Steps that compute a head for one of these steps are not watched: (λ y. f(y))(x) is f by η there, so no application of f is folded. No weak-head cache is read to find the definition, and the term asked for neither reads nor fills the folded memo, so the answer does not depend on what was computed before; the memo is cleared with the others. Like the normal form, it certifies nothing, and no step takes it. It is what evaluate !! prints and what an exact expected value is compared by.
Elimination of declared types
An eliminator Elim(M, ms) of a declared type, applied to a scrutinee s, computes in two cases (ck_eliminate in kernel/src/eliminators.c). The iota step takes s as written; weak-head reduction first reduces s to its weak head.
- A constructor,
c(t₁, …, tₐ, q₁, …, q_b) @ r₁ … @ r_d: data arguments, recursive arguments, and interval coordinates for a path constructor. For each recursive argumentq, of typeΠ (ys : Cs). BwithBa cube over the type, the induction hypothesis isλ ys. lift(E, q(ys)), where lifting through the type is the eliminator applied, and through a path typePath(i. B', b₀, b₁)is⟨h⟩ lift(E, v @ h)for a fresh dimensionh, so a path-valued positionqcontributes⟨h⟩ E(q @ h). The result is the clause method applied tot₁, …, tₐ, q₁, …, q_band the hypotheses, as an application spine whose lambdas are not contracted, then applied to each coordinaterwith the displayed path type as annotation. Theiotastep returns this application; weak-head reduction continues reducing it. - A formal composition
hcomp^j I [ψ ↦ w] w₀, under weak-head reduction only: with a fresh dimensionk, lethfill(k) = hcomp^j I [ψ ↦ w(j ∧ k), (k = 0) ↦ w₀] w₀; the result iscomp^k M(hfill(k)) [ψ ↦ E(w(k))] E(w₀), the eliminator applied to each wall and to the base, composed in the motive over the filler.
Anything else, a variable or a neutral term, leaves the application as it is. The clause types that EliminatorClause checks (chapter 16) are computed by the same display: each position shown by its hypothesis, each earlier constructor by its clause.
Filling
The kernel has no primitive filler. Given a composition problem in direction i over A(i) with tubes [φ ↦ u(i)] and base a₀, the filler at an interval expression r is a composition in a fresh direction j with one more wall (ck_fill):
fill^i A [φ ↦ u] a₀ r = comp^j A(r ∧ j) [φ ↦ u(r ∧ j), (r = 0) ↦ a₀] a₀
At r = 0 the added wall has face 1 and the composition is a₀; at r = 1 it is comp^j A(j) [φ ↦ u(j)] a₀, the composition itself. The Σ, Π and higher-inductive rules below use it.
Composition at each type former
To reduce comp^i A [φ ↦ u] a₀ (ck_reduce_composition in kernel/src/composition_compute.c), the kernel first drops the tubes on the face 0, and if any tube has the face 1 it returns the weak head of that tube's term at i = 1, whatever the family is. Otherwise it reduces the family to its weak head and dispatches on it; a neutral family gives a neutral composition. Below, v(i) abbreviates a filler and A(1) the family at i = 1.
| Family | Reduction of comp^i A [φ ↦ u] a₀ |
|---|---|
Unit | tt when the weak heads of a₀ and of every tube's term are tt; otherwise neutral. |
Σ (x : F(i)). G(i, x) | Compose the first components, c₁ = comp^i F [φ ↦ u.1] a₀.1, fill them, v(i) = fill^i F [φ ↦ u.1] a₀.1 i, compose the second components in the family at the filler, c₂ = comp^i G(i, v(i)) [φ ↦ u.2] a₀.2, and return (c₁, c₂) at the pair type at i = 1. |
Π (y : F(i)). G(i, y) | For a fresh variable x : F(1), fill backward with no tubes, v(i) = fill^i F(1 − i) [] x (1 − i), so that v(1) = x, and return λ (x : F(1)). comp^i G(i, v(i)) [φ ↦ u(v(i))] (a₀(v(0))). |
Π (x < ω). G(i, x) | Levels do not vary along the interval: for a fresh level variable y, λ (y < ω). comp^i G(i, y) [φ ↦ u {y}] (a₀ {y}). |
Path(j. P(i, j), l(i), r(i)) | For a fresh dimension k, apply every tube and the base at k, add the walls (k = 0) ↦ l(i) and (k = 1) ↦ r(i), and return ⟨k⟩ comp^i P(i, k) [φ ↦ u @ k, (k = 0) ↦ l(i), (k = 1) ↦ r(i)] (a₀ @ k). |
L(i) + R(i) | Reduce a₀ and every tube's term to weak heads. When all are inl, or all inr, push the composition inside: inl(comp^i L [φ ↦ v] v₀) with the injected values; otherwise neutral. |
a data declared type S(ps(i)) | One with no path constructor and no truncation. Reduce a₀ and every tube's term to weak heads. When all are the same constructor applied to arguments, pack the constructor's argument types into a telescope Σ (x₁ : A₁(i)). … Unit, each argument spine into a tuple, compose the tuples, and apply the constructor at S(ps(1)) to the components of the result; otherwise neutral. Transport in such a type is the composition with the tube φ ↦ a₀. |
a higher declared type S(ps(i)) | Decompose into the formal operations (below): hcomp^i S(ps(1)) [φ ↦ squeeze(u)] (transp^i S(ps(i)) 0 a₀), where squeeze(u) = transp^j S(ps(i ∨ j)) (i = 1) u moves each wall to the end of the direction. |
Glue [ψ ↦ (T, w)] A | The Glue rule (below). |
U(ℓ) | The universe rule (below). |
A rule never takes a tube's constructor from the base: when a wall is neutral, the composition stays neutral. moved in the example above is comp^i const_family(refl(Unit) @ i) [] 3, which print(inspect(moved)) shows as [i]. comp(…) under the ascription; its family reduces to the declared type UNat, a data type, so the composition of the single constructor spine 3 with no tubes is 3.
Glue and the universe
Composition in a Glue type Glue [ψ(i) ↦ (T(i), w(i))] A(i) (ck_glue_composition in kernel/src/glue_compute.c) follows CCHM section 6.2, built only from compositions, fillers and the supplied equivalences; no inverse is chosen and no new rule is assumed.
- Project the base and the tubes to
Awithunglue, and compose there:a₁' = comp^i A [φ ↦ unglue(u)] unglue(a₀). - For each piece and each clause
Cof its face ati = 1, a pick(T|C, w|C), build a partial element of the fiberΣ (x : T(1)|C). Path(A(1), a₁', (w(1)|C).1(x)): on each clauseDof∀i. ψfor every piece, the pair of the composition in that piece's type and the path that the equivalence preserves composition (CCHM's lemma 6); on each clause of the composition's own face, the pair ofu(1)and the constant path. The equivalence's contractibility proof ata₁'extends this partial element to a fiber element(t, α)onC. - Correct
a₁'along a fresh dimension, with each pick's pathαas a wall on its clause and the constantunglue(u(1))on the composition's faces, toa₁. - Return
glue(a₁, [C ↦ t])at the Glue type ati = 1.
Composition in a universe, comp^i U(ℓ) [φ ↦ E(i)] A, follows CCHM section 7.1: it is the Glue type Glue [φ ↦ (E(1), comp^i Equiv(E(1), E(1 − i)) [] idEquiv(E(1)))] A, whose equivalences are the identity equivalence of E(1) transported along the reversed line of types. This is how a path of types transports: transport along a path built with Glue (chapter 11) composes in the universe and then unglues.
Higher inductive types
A declared type with a path constructor or a truncation is a higher type, and its formal operations hcomp and transp are canonical values that compute only in these cases (ck_hit_reduce in kernel/src/hit_composition.c):
hcomp^i I [φ ↦ u] a₀drops its tubes on the face0and reduces tou[1/i]when a tube has the face1; with no tube left it stays as it is, a value that does not reduce toa₀. An eliminator applied to it computes by the composition case above.transp^i I(i) 1 a₀, on the face1, isa₀.transp^i I(i) φ (hcomp^j I(0) [ψ ↦ w] w₀)distributes:hcomp^k I(1) [ψ ↦ transp^i I(i) φ w(k)] (transp^i I(i) φ w₀), withjrenamed to a freshk.transp^i I(i) φ (c(a₁, …, aₙ) @ r₁ … @ r_d), on a constructor: pack the arguments into a tuplet₀in the constructor's telescope ati = 0, compose it with the constant tube,t₁ = comp^i T(i) [φ ↦ t₀] t₀, and apply the constructor atI(1)to the components oft₁and to the coordinates. For a point constructor this is the result. For a path constructor the boundary must be corrected: transporting the arguments changes the endpoints on each facer = 0,r = 1, so the result is wrapped in anhcompalong a fresh dimensionhwhose walls, on each such face, are the boundary piece at the filler of the arguments, squeezed to the end ofiand reversed inh, and whose wall onφisa₀. Ath = 0the wall meets the transported constructor's endpoint; ath = 1it is the transport of the original endpoint, so transport commutes with each face.
Together with the decomposition of comp into transp and hcomp in the table above, these rules give every higher inductive type of the library, the circle, truncations, quotients and pushouts, its computation: a path constructor at an endpoint reduces to its boundary by the path rule, since the elaborator annotates the application with the constructor's path type, and an eliminator computes on constructors and on formal compositions.