Cubist

LANGUAGE REFERENCE · CHAPTER 9

Equational reasoning and simplification

Chains of equalities, rewriting with checked lemmas, and simplification.

Picking a tool

Proving an equality with only sym, trans and cong is exact but hard to read: every intermediate endpoint is implicit. The statements in this chapter build the same checked paths from more readable source. Each produces an ordinary proof term that the kernel checks, and in the inspector each links to the term it built.

SituationUse
The two sides compute to the same thingrfl;
You want to show each intermediate expressioncalc { … }
One known equation should replace one specific subtermrw [p];
A few lemmas should be applied everywhere until nothing changessimp only [lemmas];
A hypothesis matches the goal after the same simplificationsimpa only [lemmas] using h;

rfl; was introduced in chapter 1; this chapter adds the others. rfl, calc and rw act on homogeneous equality goals: x = y with both sides in one fixed type. simp also rewrites goals that are types. None of them rewrites a PathP over a varying family; for such goals, see dependent paths.

Reflexivity: rfl

rfl; closes the goal x = y when x and y are definitionally equal. It is exact refl(x); without repeating x.

import unat;
use unat;

def two_plus_two : 2 + 2 = 4 {
  rfl;
}

def successor_first(n, m : UNat) : succ(n) + m = succ(n + m) {
  rfl;
}

succ(n) + m computes to succ(n + m), because addition recurses on its first argument. n + 0 does not compute for a variable n, so rfl cannot prove n + 0 = n; that needs induction, as in the library lemma unat_add_zero.

import unat;
use unat;

def plus_zero(n : UNat) : n + 0 = n {
  rfl;  // Error: Type mismatch: found n + 0 = n + 0, expected n + 0 = n.
}
import unat;

def not_an_equality : UNat {
  rfl;  // Error: rfl requires a homogeneous equality goal.
}

Chains: calc

A calc block proves a = d as a chain a = b, b = c, c = d, writing every intermediate expression and the proof of each step. The steps are composed with trans:

import unat;
use unat;

def add_zero_twice(n : UNat) : (n + 0) + 0 = n {
  calc {
    (n + 0) + 0 = n + 0 by unat_add_zero(n + 0);
    _ = n by unat_add_zero(n);
  }
}

def through_hypotheses(a, b, c : UNat, p : a = b, q : b = c) : a + 0 = c {
  calc {
    a + 0 = a by unat_add_zero(a);
    _ = b by p;
    _ = c by q;
  }
}

Each step has the form left = right by proof;. The proof is either a term, followed by ;, or a nested block by { … }, with no semicolon. Inside calc, _ as a left endpoint means the right endpoint of the preceding step. The first left endpoint must match the goal’s left side, and the last right endpoint the goal’s right side, up to conversion. The steps are composed with trans in order.

A nested block starts with that step’s equality as its goal, so it can use any statement:

import unat;
use unat;

def calc_with_blocks(B : U0, f : UNat -> B, n : UNat) :
  f((n + 0) + 0) = f(n) {
  calc {
    f((n + 0) + 0) = f(n + 0) by {
      rw [unat_add_zero(n + 0)];
    }
    _ = f(n) by {
      rw [unat_add_zero(n)];
    }
  }
}

calc closes the block. It supports only equality chains; mixed chains such as a < b = c <= d are not available. Each of these is rejected:

import unat;
use unat;

def broken_chain(n : UNat) : (n + 0) + 0 = n {
  calc {
    (n + 0) + 0 = n + 0 by unat_add_zero(n + 0);
    // Error: calc step left endpoint does not match the preceding endpoint.
    n + 1 = n by unat_add_zero(n);
  }
}
import unat;
use unat;

def stops_early(n : UNat) : (n + 0) + 0 = n {
  calc {
    // Error: calc final endpoint does not match the goal.
    (n + 0) + 0 = n + 0 by unat_add_zero(n + 0);
  }
}
import unat;
use unat;

def wrong_step_proof(n : UNat) : (n + 0) + 0 = n {
  calc {
    // Error: Type mismatch: found n + 0 = n, expected n + 0 + 0 = n.
    (n + 0) + 0 = n by unat_add_zero(n);
  }
}
import unat;

def not_an_equality : UNat {
  calc {  // Error: calc requires a homogeneous equality goal.
    0 = 0 by refl(0);
  }
}

Rewriting: rw

Given a proof of a = b, rw replaces an occurrence of a in an equality goal by b, and continues with the new goal:

import unat;
use unat;

def rewrite_then_finish(n, m : UNat, h : n = m) : n + 0 = m {
  rw [unat_add_zero(n)];   // goal is now n = m
  exact h;
}

def rewrite_second(n : UNat) : (n + 0) + (n + 0) = (n + 0) + n {
  rw [unat_add_zero(n)] at lhs occurrence 2;
}

def rewrite_backwards(n : UNat) : n = n + 0 {
  rw [<- unat_add_zero(n)] at lhs;
}

def rewrite_several(a, b : UNat) : (a + 0) + (b + 0) = a + b {
  rw [unat_add_zero(a), unat_add_zero(b)];
}

rw [p]; takes a proof p : a = b and replaces one occurrence of a in the goal by b. Internally it builds cong of a one-hole context around the occurrence and composes it with the goal. <- p uses p right to left, replacing b by a. Several rules rw [p, q, <- r]; are applied one after another, in order.

  • Rules are fully instantiated. Write unat_add_zero(n), not unat_add_zero. rw does not search for arguments; simp only does.
  • Which occurrence. Occurrences are counted in preorder, parent before children and left to right. Without at, the count runs across the left endpoint and then the right. at lhs or at rhs restricts it to one side, and occurrence N picks the Nth match; the default is the first. In rewrite_second, the first n + 0 is occurrence 1 and the second is occurrence 2.
  • After rewriting. If the rewritten goal holds by conversion, rw ends the block; no rfl; is needed. Otherwise a following statement must prove the rewritten goal.
  • Where it looks. Rewriting looks only through applications, such as f(…) and a + …. It never looks under fun or a quantifier, or inside transport, comp and other cubical forms: a subterm there is not counted as an occurrence. A match in a dependent argument, where replacing it would change the result type, is skipped. When a skipped match was the only one, the error says so. For such positions, use an explicit cong(fun (x : A) => …, p).
import unat;
use unat;

def no_third(n : UNat) : (n + 0) + (n + 0) = (n + 0) + n {
  // Error: Rewrite occurrence 3 was not found (2 eligible matches).
  rw [unat_add_zero(n)] at lhs occurrence 3;
}
import unat;
use unat;

def unfinished(n, m : UNat) : n + 0 = m {
  // Error: rw left an unresolved equality goal; add a following proof statement.
  //   Remaining goal: n = m. 1 rewrite changed the left side, using unat_add_zero(n).
  rw [unat_add_zero(n)];
}
import unat;
use unat;

def uninstantiated(n : UNat) : n + 0 = n {
  rw [unat_add_zero];  // Error: rw requires a homogeneous equality proof.
}
import unat;
use unat;

def dependent_argument(C : UNat -> U0, f : forall n : UNat. C(n), n : UNat) : f(n + 0) = f(n + 0) {
  rw [unat_add_zero(n)] at lhs;  // Error: Rewrite match occurs in an unsupported dependent position.
}
import unat;
use unat;

def type_goal(P : UNat -> U0, n : UNat, h : P(n)) : P(n + 0) {
  rw [unat_add_zero(n)];  // Error: rw requires a homogeneous equality goal.
  exact h;
}

The last goal is a type, not an equality. simp rewrites such goals.

Simplification: simp only

The simplifier rewrites with a set of equality lemmas, repeatedly and everywhere it can, until no rule applies. Unlike rw, it accepts lemmas with quantified parameters and works out their arguments by matching. It is predictable rather than clever: it uses only the rules you select or register, never searches arbitrary theorems, and never succeeds by looping or exhausting a budget.

import unat;
use unat;

def add_zero_twice_simp(n : UNat) : (n + 0) + 0 = n {
  simp only [unat_add_zero];
}

def residual_goal(n, m : UNat, h : n = m) : (n + 0) + 0 = m {
  simp only [unat_add_zero];   // goal is now n = m
  exact h;
}

def with_hypothesis(a, b : UNat, h : a = b) : a + 0 = b {
  simp only [unat_add_zero, h];
}

unat_add_zero has type forall x : UNat. (x + 0) = x. The simplifier finds each subterm of the shape ? + 0, fills x from it, and checks the instantiated rule. As with rw, if the simplified goal holds by conversion the block is closed; otherwise a following statement must prove it.

A rule may be:

  • a quantified lemma name such as unat_add_zero;
  • an instantiated proof such as unat_add_zero(n), or a local hypothesis such as h : a = b;
  • a named simplification set;
  • any of these reversed with <-.

Every quantified parameter must be determined by the matched side. Matching is rigid and first-order: a pattern matches a subterm with the same function heads, and it does not unfold definitions to find a match. Below, extra matches any x, but nothing fixes y. Supply the argument yourself, as in simp only [extra(n, 0)].

import unat;
use unat;

def extra(x, y : UNat) : x = x + (0 * y) {
  exact sym(unat_add_zero(x));
}

def undetermined(n : UNat) : n = n + 0 {
  // Error: A simplification rule parameter is not determined by the matched side; supply arguments.
  simp only [extra];
}
import unat;
use unat;

def unfinished(n, m : UNat) : n + 0 = m {
  // Error: simp only left an unresolved equality goal; add a following proof statement.
  //   Remaining goal: n = m. 1 rewrite changed the left side, using unat_add_zero.
  simp only [unat_add_zero];
}

An unfinished rw, simp, simpa or calc says where it stopped: the remaining goal, which side its rewrites changed and the rules that fired, or for calc the endpoints that do not meet. A long goal is cut short with “…”.

import unat;

def no_rules(n : UNat) : n + 0 = n {
  simp only;  // Error: simp only requires an explicit rule list.
}

Traversal order and budgets

The traversal is deterministic, so the same rules always give the same result:

  1. Children are simplified before their parents, and the left endpoint before the right.
  2. At each subterm, rules are tried in the listed order and the first that matches fires.
  3. The pass repeats until no rule applies.

Traversal reaches the same positions as rw. A match in a dependent argument is skipped, so it never stops simplification elsewhere or a goal that already holds. If the goal is left unsolved, the error says that such matches were skipped.

Commutativity-style rules such as forall x y, x + y = y + x rewrite their own output back into their input. The simplifier detects the repeated state and fails, naming the rules that brought the goal back. Instantiate such rules at specific arguments instead, as in unat_add_comm(a, b).

import unat;
use unat;

def commuted(a, b : UNat) : a + b = b + a {
  // Error: Simplification cycle detected in the selected rules. unat_add_comm returned
  //   the goal to where it was 2 rewrites earlier.
  simp only [unat_add_comm];
}

There are also fixed bounds. One simplification makes at most 64 rewrites and 64 premise searches, each traversal visits at most 512 subterms and tries at most 8,192 match candidates, and generated terms have a size bound.

Each search also spends counted fuel: rw’s search for one rule, one simplification, or the two of simpa. It counts subterms visited, candidate rules tried, rewrites, premise searches, term nodes walked and kernel queries. The defaults are several times what any checked proof in this reference, the rebuilt library or the archive spends. A declaration also has fuel of its own for all the kernel queries it asks. That covers elaborating the rules you list, the statements after a search and the steps of a calc.

Fuel counts work, never time, so a proof checks or fails the same way on every machine and in every session. Two other limits fail separately and say so. The kernel bounds its own steps per operation (“Kernel checking/reduction budget exhausted.”), and a checker may set a time limit per declaration (“Declaration time limit exceeded.”). These two are safety limits, outside that guarantee. The kernel's bound is far above what checked proofs use, but the kernel reuses work it has already done within a declaration, so a step near the bound could pass in one session and fail in another. A proof that reaches it should be split into smaller steps.

Exceeding a bound or the fuel is a failure that names it and shows the goal where the search stopped. Here the reversed rule turns every number x into x + 0, forever:

import unat;
use unat;

def growing(n, m : UNat, h : n = m) : n = m + 0 {
  simp only [<- unat_add_zero];  // Error: Simplification rewrite budget exceeded.
  exact h;
}

Generic lemmas

rw and simp accept a lemma with a universe variable without its universe argument. The universe is found by matching, where the rewritten side contains it as a plain variable, as in Id(U, A). When the lemma does not mention its universe, any universe will do. Otherwise, supply the universe yourself, as in simp only [lemma(U2)].

def Id(U < UU0, A : U) := A;
def id_unfold(U < UU0, A : U) : Id(U, A) = A := refl(A);
def unfolded(A : U3) : Id(U3, Id(U3, A)) = A {
  simp only [id_unfold];
}

Using a hypothesis: simpa

A hypothesis often proves the goal once both are simplified the same way. simpa does both simplifications and closes the goal with the hypothesis:

import unat;
use unat;

def simpa_example(n, m : UNat, h : n + 0 = m) : n = m + 0 {
  simpa only [unat_add_zero] using h;
}

simpa [rules] using proof; simplifies both the goal and the type of proof with the same rules. Here both become n = m. It checks that the simplified types match, then reconstructs the original goal from the checked rewrite paths. This saves stating the simplified form of a hypothesis. simpa always closes the block.

import unat;
use unat;

def different_after_simplifying(n, m : UNat, h : n = m + 1) : n + 0 = m {
  // Error: Type mismatch: found n = m + 1, expected n = m.
  simpa only [unat_add_zero] using h;
}

Simplifying types

When the goal is a type rather than an equality, simp rewrites the type itself. Each rewrite gives a checked path between types, and the proof of the simplified type is transported back along it:

import unat;
use unat;

def family_simp(P : UNat -> U0, n : UNat, h : P(n)) : P(n + 0) {
  simp only [unat_add_zero];   // goal is now P(n)
  exact h;
}

def family_simpa(P : UNat -> U0, n : UNat, h : P(n)) : P(n + 0) {
  simpa only [unat_add_zero] using h;
}

def move_type(A, B : U0, p : A = B, a : A) : B {
  simpa only [p] using a;
}

In move_type, the rule is a path p : A = B between types, and simpa transports a along it. The simplifier only follows actual paths of types. It will not turn a logical equivalence or a pair of maps between propositions into a rewrite.

Registering rules and sets

A module can register lemmas as default rules, which a plain simp uses, and name sets of rules for simp only:

import unat;
use unat;

simp_rule unat_add_zero priority 10;
simp_set nat_units := [unat_add_zero];

def default_rules(n, m : UNat) : (n + 0) + (m + 0) = n + m {
  simp;
}

def named_set(n : UNat) : (n + 0) + 0 = n {
  simp only [nat_units];
}

def simplified_copy(n, m : UNat, h : n + 0 = m + 0) : n = m {
  simp [nat_units] at h as h2;   // h2 : n = m
  exact h2;
}

simp_rule name; and simp_rule name priority N; are top-level directives, placed between declarations. They register an already checked equality as a default rule. The priority is an integer from 0 to 1000, with 0 as the default. simp_set name := [a, b]; names a collection of rules. Neither directive creates a new proof rule or an assumption: the registered lemma is rechecked every time it is used.

Registrations and sets are inherited through imports. When modules register the same lemma, it appears once. Defaults are tried in descending priority, then in a fixed order by checked identity. If two imports define different sets with the same name, that name is ambiguous until the current module declares its own set with that name.

FormRules used
simp;All default rules in scope
simp [a, s];Default rules plus the listed rules and sets
simp only [a, s];Exactly the listed rules and sets; defaults are ignored
simp without [a];Default rules except a. Cannot be combined with only.
simp [s] at h as h2;The rules of simp [s], applied to the type of the local hypothesis h. Binds the result as h2 and keeps h. A proof statement must follow.
simpa … using proof;Any of the rule selections above, applied to the goal and to proof

Plain simp depends on which rules happen to be registered, so it can change behavior when an import changes. Prefer simp only in library proofs. The inspector can freeze a working simp into a simp only list of the rules that actually fired; see checking and inspection.

import unat;

// Error: simp_rule priority must be an integer from 0 to 1000.
simp_rule unat_add_zero priority 2000;
import unat;

simp_rule unat_add_zero;
// Error: Simplification rule unat_add_zero is already registered in this module.
simp_rule unat_add_zero priority 5;
import unat;

def only_and_without(n : UNat) : n + 0 = n {
  simp only [unat_add_zero] without [unat_add_zero];  // Error: simp only cannot exclude rules.
}
import unat;

def not_local(n : UNat) : n = n {
  // Error: simp at requires a local hypothesis: unat_add_zero.
  simp [unat_add_zero] at unat_add_zero as h2;
  rfl;
}
import unat;
use unat;

def copy_only(n, m : UNat, h : n + 0 = m) : n = m {
  // Error: A simplified hypothesis copy must be followed by a proof statement.
  simp only [unat_add_zero] at h as h2;
}

Conditional rules

A rule may have hypotheses that matching does not determine. Here zero_if rewrites n + 0 to 0, but only given h : n = 0:

import unat;
use unat;

def zero_if(n : UNat, h : n = 0) : n + 0 = 0 {
  calc {
    n + 0 = n by unat_add_zero(n);
    _ = 0 by h;
  }
}

simp_rule zero_if priority 20;

def conditional(n : UNat, h : n = 0) : n + 0 = 0 {
  simp with [h];
}

After matching fixes n, the simplifier needs a proof of the premise n = 0. It looks for one in this order:

  1. a local hypothesis listed in with [h, …], which must be a name from the current context;
  2. refl, when the premise holds by conversion;
  3. for an equality premise, simplifying it with the other selected rules. This search goes at most two levels deep. A rule cannot be used to prove its own premise. Each distinct premise is searched once per simp, and at most 64 premises are searched; after that, conditional rules whose premise is not already known do not fire.

Every premise proof found this way is checked by the kernel and passed to the rule. If none is found, the rule does not fire, and the error names the blocked parameter and suggests simp with [name]. Only equality premises are solved. Other kinds of hypothesis must be supplied through with.

import unat;
use unat;

def zero_if(n : UNat, h : n = 0) : n + 0 = 0 {
  calc {
    n + 0 = n by unat_add_zero(n);
    _ = 0 by h;
  }
}

simp_rule zero_if priority 20;

def premise_not_given(n : UNat, h : n = 0) : n + 0 = 0 {
  // Error: simp only left an unresolved equality goal; add a following proof statement.
  //   Rule zero_if has an unproved premise at parameter 2; supply a local witness with simp with [name].
  simp;
}
import unat;
use unat;

def global_witness(n : UNat) : n + 0 = n {
  simp with [unat_add_zero];  // Error: Simplification premise witness must be local: unat_add_zero.
}