Cubist

LANGUAGE REFERENCE · CHAPTER 17

Kernel computation: reduction, elimination and composition

What the kernel computes when asked: the single-step rules, weak-head and normal forms, dependent elimination of declared types, and composition, transport and filling at every type former.

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.

RuleRedex, as writtenContractum
beta(λ (x : A). b)(a); (λ (x < ω). b) {ℓ}b[a/x]; b[ℓ/x] with every level of the result in normal form
deltaa definition referencethe 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 nota, 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
normalizeany termits normal form
whnfany termits weak-head normal form
facecomp or hcomp with a tube on the face 1; transp on the face 1that tube's term at the end of the direction, u[1/i]; the base
glueglue(b', [φ ↦ t]) whose base b' reduces to unglue(b), possibly through nested Glue stepsb, 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
splitcomp or hcomp with a tube on a face of several clauses, or on the face 0the 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:

  1. Formal operations. hcomp and transp go to the higher-inductive rules; comp goes to the composition rules. Each returns a finished head.
  2. Definitions. A reference unfolds to its checked body; a reference naming no definition is an error.
  3. 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 is 1. A Glue term glue(b', [φ ↦ t]) whose base's weak head is unglue(b) at the same Glue type, up to syntax, reduces to b when every t is, by syntax, b restricted 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 to g when a piece has face 1, and otherwise to the base of g's weak head when that is a Glue term.
  4. Applications. f(a) reduces f; a lambda is applied by substitution, an eliminator eliminates the weak head of a, 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.
  5. Recursors. unitrec reduces its value and takes the point case on tt; sumrec reduces its value and applies the matching case on an injection.
  6. Path applications. p @ r with r equal to 0 or 1 and a path-type annotation reduces to the recorded endpoint without reducing p. Otherwise it reduces p, and substitutes r into 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.
  7. η-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.

  1. 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 argument q, of type Π (ys : Cs). B with B a 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 type Path(i. B', b₀, b₁) is ⟨h⟩ lift(E, v @ h) for a fresh dimension h, so a path-valued position q contributes ⟨h⟩ E(q @ h). The result is the clause method applied to t₁, …, tₐ, q₁, …, q_b and the hypotheses, as an application spine whose lambdas are not contracted, then applied to each coordinate r with the displayed path type as annotation. The iota step returns this application; weak-head reduction continues reducing it.
  2. A formal composition hcomp^j I [ψ ↦ w] w₀, under weak-head reduction only: with a fresh dimension k, let hfill(k) = hcomp^j I [ψ ↦ w(j ∧ k), (k = 0) ↦ w₀] w₀; the result is comp^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.

FamilyReduction of comp^i A [φ ↦ u] a₀
Unittt 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)] AThe 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.

  1. Project the base and the tubes to A with unglue, and compose there: a₁' = comp^i A [φ ↦ unglue(u)] unglue(a₀).
  2. For each piece and each clause C of its face at i = 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 clause D of ∀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 of u(1) and the constant path. The equivalence's contractibility proof at a₁' extends this partial element to a fiber element (t, α) on C.
  3. Correct a₁' along a fresh dimension, with each pick's path α as a wall on its clause and the constant unglue(u(1)) on the composition's faces, to a₁.
  4. Return glue(a₁, [C ↦ t]) at the Glue type at i = 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 face 0 and reduces to u[1/i] when a tube has the face 1; with no tube left it stays as it is, a value that does not reduce to a₀. An eliminator applied to it computes by the composition case above.
  • transp^i I(i) 1 a₀, on the face 1, is a₀.
  • 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₀), with j renamed to a fresh k.
  • transp^i I(i) φ (c(a₁, …, aₙ) @ r₁ … @ r_d), on a constructor: pack the arguments into a tuple t₀ in the constructor's telescope at i = 0, compose it with the constant tube, t₁ = comp^i T(i) [φ ↦ t₀] t₀, and apply the constructor at I(1) to the components of t₁ 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 face r = 0, r = 1, so the result is wrapped in an hcomp along a fresh dimension h whose walls, on each such face, are the boundary piece at the filler of the arguments, squeezed to the end of i and reversed in h, and whose wall on φ is a₀. At h = 0 the wall meets the transported constructor's endpoint; at h = 1 it 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.