Blog › ICP guides

Coq developer on retainer: tactics, induction, rewrite, Gallina, Ltac, and Coq proof engineering on monthly retainer

December 3, 2026 · ~15 min read

A Coq proof development for a verified natural number library needed to prove commutativity of addition: Theorem add_comm : forall n m : nat, n + m = m + n. The developer opened the proof with Proof. and attempted rewrite Nat.add_comm. as the first tactic, expecting the standard library lemma to close the goal immediately. Coq rejected the tactic: the standard library lemma Nat.add_comm has type forall n m : nat, n + m = m + n — but the developer was trying to use it to prove exactly that same statement, creating a circular dependency that Coq’s type checker rejects. The proof required induction. The developer moved to induction n. which generated two subgoals: the base case 0 + m = m + 0 and the inductive case S n + m = m + S n with inductive hypothesis IH : n + m = m + n. For the base case, reflexivity failed because 0 + m reduces definitionally to m but m + 0 does not — Nat.add is defined by structural recursion on its first argument, so 0 + m = m by computation, but m + 0 = m requires a proof by induction on m. The developer needed rewrite Nat.add_0_r. to apply the library lemma Nat.add_0_r : forall n, n + 0 = n, converting m + 0 to m, then reflexivity closed the base case. For the inductive case, the goal S n + m = m + S n simplified under simpl to S (n + m) = m + S n. The developer applied rewrite IH. to substitute n + m with m + n, producing S (m + n) = m + S n, then needed rewrite Nat.add_succ_r. to apply Nat.add_succ_r : forall n m, n + S m = S (n + m) to convert m + S n to S (m + n), and reflexivity closed the goal. Three tactic failures per proof attempt. The Coq developer on retainer diagnosed the rewrite ordering issue: rewrite Nat.add_comm as the opening tactic was circular; the correct structure required induction n first, then targeted rewrites with Nat.add_0_r and Nat.add_succ_r in the correct subgoals. Tactic failures: 3 per attempt → 0.

The work log entry read “fixed Nat commutativity proof, 7h.” It names the result and duration. It cannot explain why reflexivity fails on 0 + m = m + 0 even though both sides equal m — Coq’s reflexivity succeeds only when the two sides are definitionally equal, meaning equal by computation without unfolding arbitrary lemmas; 0 + m reduces by the definition of Nat.add to m in one step, but m + 0 requires structural induction on m to reduce, so reflexivity cannot close the goal. It cannot explain why the developer chose Nat.add_0_r rather than an inlined subproof — the standard library contains exactly this lemma and using it avoids duplicating proof effort, but finding the right lemma name requires fluency with the Nat module’s naming conventions (add_0_r = add with 0 on the right). It cannot explain the decision to use simpl before rewrite IH in the inductive case — simpl unfolds one step of Nat.add’s recursive definition on the S n term, exposing S (n + m) on the left side, which is necessary before the inductive hypothesis can be applied. The 7 hours of induction strategy analysis, tactic sequencing, and standard library theorem search are invisible in the diff.

Coq tactics: induction, rewrite, simpl, reflexivity, apply, and Ltac

Coq proofs are constructed through tactics that transform proof goals. The proof state is a sequence of goals, each consisting of a local context (assumptions with their types) and a goal type (the proposition to prove). Tactics manipulate this state: they may close the current goal, split it into subgoals, introduce new hypotheses, or rewrite the goal using equalities. Understanding which tactic applies to which goal shape is the core competency of Coq proof engineering. reflexivity closes goals of the form t = t where both sides are definitionally equal — equal by computation. simpl performs computation steps, unfolding definitions and reducing expressions; it never fails but may leave the goal unchanged if nothing reduces. intro x introduces a universally quantified variable or hypothesis, moving it from the goal into the context. induction x performs structural induction on an inductive type; for nat, it produces a base case for O and an inductive case for S n with an inductive hypothesis about n.

rewrite is one of the most frequently used tactics and one of the most commonly misapplied. rewrite H where H : a = b rewrites occurrences of a to b in the current goal. rewrite <- H rewrites in the reverse direction, replacing b with a. The critical constraint is that the left-hand side of the equality must appear in the current goal — if it does not, the tactic fails with “did not find an instance.” The tactic placement error in the Coq commutativity proof above — applying rewrite Nat.add_comm before induction — failed because the goal contained a specific n + m and m + n, not instances of the abstract pattern, and using Nat.add_comm to prove itself is circular. Diagnosing rewrite failures requires identifying what the current goal actually contains versus what the rewrite lemma expects to find. The Check vernacular command shows a lemma’s type; Search (pattern) finds lemmas in the current environment matching a pattern; these are essential tools for finding the right standard library lemma rather than reproving a known result.

Ltac is Coq’s tactic language, used to write reusable tactic scripts and proof automation. Ltac supports sequential tactic composition (tactic1 ; tactic2 applies tactic2 to all subgoals produced by tactic1), alternative selection (tactic1 || tactic2 tries tactic1 first and falls back to tactic2 if it fails), optional tactics (try tactic succeeds even if tactic fails), and iteration (repeat tactic applies tactic until it fails). These combinators enable complex proof automation: a tactic like induction n; simpl; try reflexivity; try rewrite IH; reflexivity encodes the proof strategy as a script. Writing good Ltac requires understanding tactic failure semantics: a tactic fails when it cannot make progress, and Ltac propagates failures through the alternative and try combinators. Complex Ltac scripts can become brittle when proof goals change — a tactic that worked against one goal shape may fail silently against a revised definition. Senior Coq retainers spend significant time maintaining and refactoring Ltac automation as proof bases evolve.

Coq Nat inductive type: Nat.add definition, standard library lemmas, and proof term language

The natural number type nat in Coq is an inductive type with two constructors: O : nat (zero) and S : nat -> nat (successor). Every natural number is either O or S k for some k : nat. Addition is defined in the standard library as a Fixpoint by structural recursion on the first argument: Fixpoint add (n m : nat) : nat := match n with | O => m | S n’ => S (add n’ m) end. This definition means that 0 + m reduces by computation to m in one step (the O branch returns m directly), while m + 0 cannot reduce without knowing the shape of m — if m = O then 0 + 0 = 0 trivially, but for m = S k the recursion produces S (k + 0), which still has + 0 on the right. This asymmetry is why proofs about right-zero (n + 0 = n) require induction on n while proofs about left-zero (0 + n = n) hold definitionally.

The Coq standard library’s Nat module contains a curated collection of lemmas about natural number arithmetic. Key lemmas that appear frequently in retainer work include Nat.add_0_r : forall n, n + 0 = n (right zero, proved by induction on n), Nat.add_0_l : forall n, 0 + n = n (left zero, holds definitionally but provided for symmetry), Nat.add_comm : forall n m, n + m = m + n (commutativity, proved by induction), Nat.add_assoc : forall n m p, n + (m + p) = (n + m) + p (associativity), Nat.add_succ_r : forall n m, n + S m = S (n + m) (successor on the right), and Nat.succ_inj : forall n m, S n = S m -> n = m (successor injectivity). Finding the right lemma name requires knowledge of the naming conventions: left-argument facts end in _l, right-argument facts in _r; comm, assoc, succ abbreviate common patterns. Retainers fluent in the standard library can apply these directly; those who are not spend time with Search commands, adding invisible hours to proof development work.

Gallina is the term language underlying Coq’s type theory. Proof terms in Gallina are expressions of the Calculus of Inductive Constructions (CIC): fun x : T => body for function abstraction, forall x : T, P x for dependent function types (also used as universal quantification in propositions), match e with | C1 x => ... | C2 => ... end for pattern matching over inductive types, and fix f (x : T) : R := body for structurally recursive definitions. In Coq’s Prop universe, propositions are types and proofs are terms: Refl : 0 = 0 is a term that proves the equality. The eq_refl constructor is the only constructor of the equality type, and it proves a = a for any term a. Coq was originally developed at INRIA by the Formel and Coq teams, with early work by Thierry Coquand, Gérard Huet, and Christine Paulin-Mohring; the system is named after the French word for rooster (the mascot of the INRIA team’s home institution). Its closest retainer-ecosystem relatives are Agda (dependently typed, proof-relevant, cubical type theory option) and Idris (dependently typed, focused on practical verified programming), but Coq’s Ltac tactic language, Gallina term language, large standard library, and industrial-strength verified software development track record (CompCert, Fiat Cryptography, VST) make the retainer work distinct in tactic automation design, induction strategy selection, and proof term architecture.

How HourTab tracks Coq developer retainer hours

Coq retainer work carries the invisible-hours problem common to all proof-assistant retainers, amplified by the gap between the apparent simplicity of individual tactics and the combinatorial complexity of tactic sequencing. Teams using Coq for verified software development, certified compiler construction, or formalized mathematics frequently encounter the tactic placement pattern described above: a developer adds what appears to be a correct rewrite step, only to find that the rewrite target is not present in the current goal because the proof has not yet been decomposed by induction into the shape where the target appears. The 3 tactic failures per proof attempt described above is one instance of a broader pattern; the retainer work is the proof state analysis that identifies which goal contains the rewrite target, the induction strategy selection that determines which variable to induct on, the standard library search that finds the right lemma name without reproving it, and the Ltac automation that encodes the proof strategy for future maintenance. Coq retainers produce visible outcomes — tactic failures: 3 per attempt → 0; proof compilation errors: N → 0 — but the hours spent on proof state analysis (what is the current goal? what is in context?), induction strategy (which variable? generalize dependent first?), rewrite direction diagnosis (left-to-right or right-to-left?), and Ltac refactoring (does this tactic script still work after the definition changed?) appear in work logs as “fixed proof” without explaining the Calculus of Inductive Constructions mechanics.

HourTab gives Coq developers a public retainer-hours URL they send to clients — typically academic research groups formalizing mathematics or programming language semantics, companies building verified software (cryptographic implementations, certified compilers, safety-critical systems), and organizations maintaining existing Coq proof developments that accumulate technical debt as definitions evolve. For Coq retainers, each work log entry should name the mechanism (tactic placement repair: rewrite before induction restructured; induction variable selection: generalize dependent before induction for stronger IH; rewrite direction: rewrite <- for reversed equality; Ltac tactic script automation for repetitive proof patterns; standard library theorem search and reuse; universe polymorphism annotation for polymorphic proof terms), the specific theorem, tactic sequence, and before/after failure count, and the proof strategy rationale. Coq retainers are often compared to Agda developer retainers for the shared dependently typed proof assistant positioning, but Coq’s Ltac tactic language, Gallina/CIC foundation, opaque vs transparent proof terms, and CompCert-scale verified software development requirements make the retainer work distinct in tactic automation design, proof term construction, and induction strategy engineering. HourTab’s work log makes the tactic placement analysis, induction strategy selection, and standard library search visible to clients who would otherwise see only the symptom — proof compilation failure — and not understand why the fix required understanding the definitional asymmetry of Nat.add’s recursion direction, and why a single rewrite before induction was the difference between a proof that typechecks and one that fails with “did not find an instance.”

FAQ: Coq developer retainers