Blog › ICP guides

Coq developer on retainer: Gallina, Admitted proof elimination, Fixpoint termination, SSReflect, and formal verification on monthly retainer

October 9, 2026 · ~20 min read

A formal specification library for a medical device data protocol had an Admitted placeholder that had been in the main branch for six months. The admitted theorem asserted that the calibration matrix determinant was non-zero for all valid sensor input ranges — an assumption the implementation depended on to avoid division by zero in the calibration inversion step. The claim held in all tested inputs, but it had never been proved; the Admitted keyword told the Coq type checker to accept it without verification. The Coq developer on retainer replaced the placeholder with a complete proof: ring established the algebraic identity reducing the determinant to a sum of bounded non-negative terms; omega proved that the sum was bounded away from zero for all integer inputs in the declared range; Qed closed the proof and made the verification permanent. During the same engagement, the developer found that Fixpoint process_samples (n : nat) (samples : list reading) : list output had a wildcard match branch | _ => process_samples (n - 1) samples. On nat, subtraction saturates at zero: 0 - 1 = 0. When n = 0, the function called process_samples 0 samples again — an infinite loop that Coq had accepted without objection because the structural argument n appeared to decrease syntactically in the match but was not the actual recursion driver. Restructured using the Function plugin with a measure length samples decreasing argument. Admitted proofs in the codebase: 3 → 0. Divergent fixpoints: 2 → 0.

The work log entry read “replaced 3 Admitted proofs, fixed 2 divergent Fixpoint definitions, 18h.” It names the count and the duration, leaving the client unable to explain to the safety review board why a six-month-old unverified assumption was now formally proved, or why a function that had always returned correct results on test inputs could have diverged in production. The first diagnosis required understanding that Admitted in Coq is not a stub placeholder in the ordinary sense — it is an axiom that tells the Coq kernel to accept the theorem as true without verification, making any downstream theorem that depends on it conditionally true under an unverified assumption. The Print Assumptions theorem_name command reveals the full dependency chain; three theorems downstream of the admitted lemma inherited the unverified assumption without the development team realizing it. The second diagnosis required understanding that nat subtraction in Coq does not underflow to a negative number; it saturates at zero, so Fixpoint recursion on a nat - 1 expression is not structurally decreasing when n = 0. Coq accepts this without error because the structural argument n is still decremented syntactically in the match, but the recursion on samples in the body is what actually drives computation, and that argument never decreases. The 18 hours of proof work and recursion analysis are not visible in the diff.

Coq fundamentals: Gallina, inductive types, and the Proof/Qed workflow

Coq is a proof assistant based on the Calculus of Inductive Constructions (CIC), a dependent type theory extending the Calculus of Constructions with inductive types and their elimination principles. The Gallina specification language is the formal language for Coq definitions and theorems; Ltac is the meta-language for tactic scripts that construct Gallina proof terms. The universe hierarchy: Prop (the type of logical propositions, proof-irrelevant, impredicative), Set (the type of computational data types, predicative), and Type (the cumulative universe hierarchy Type(0) : Type(1) : ...). In practice: pure logical propositions go in Prop; data types go in Set or Type. Inductive nat : Set := O : nat | S : nat → nat defines natural numbers; Inductive list (A : Type) : Type := nil : list A | cons : A → list A → list A defines polymorphic lists. Coq generates an elimination principle for each Inductive type: nat_rect, nat_ind, nat_rec encode induction over nat; the induction tactic invokes these automatically.

The Coq proof workflow: Theorem my_lemma : P. opens a proof obligation; Proof. enters interactive tactic mode; tactics transform the goal; Qed. closes the proof and registers the verified theorem. Core tactics: intros introduces hypotheses from the goal (each ∀ quantifier or → antecedent), naming them in the context; apply f applies a lemma or hypothesis to the current goal, unifying the conclusion with the goal and generating subgoals for each premise; exact t closes the goal by providing a proof term t directly; simpl applies computation rules (beta reduction, iota reduction for match, delta unfolding for Definition); reflexivity closes goals of the form a = a; rewrite H rewrites using equality hypothesis H : a = b, replacing a with b (or rewrite ← H in the reverse direction); ring proves polynomial ring equalities; omega (and its successor lia in recent Coq versions) proves linear integer arithmetic; auto applies a database of hints automatically up to a depth limit; eauto extends auto with existential variable unification; tauto proves propositional tautologies; intuition combines tauto with auto for predicate logic; constructor applies the appropriate constructor for the goal’s inductive type; induction n applies structural induction; destruct h destructs an inductive hypothesis into its cases; unfold f unfolds a definition; fold f re-folds a recursive definition.

Fixpoint in Coq defines structurally recursive functions. Coq’s termination checker requires that one argument of the function strictly decreases (by the structural subterm relation) on each recursive call. Fixpoint length {A} (l : list A) : nat := match l with | nil => 0 | _ :: t => 1 + length t end is structurally recursive because t is a structural subterm of l. When structural recursion is not possible — for example, a merge sort that splits the list before recursing — the Function plugin provides a general well-founded recursion mechanism: Function mergesort {A} (l : list A) {measure length l} : list A := ... uses length l as the decreasing measure; Coq generates proof obligations that the measure decreases on each recursive call. Program Fixpoint extends Fixpoint with the Program infrastructure for mixing computation and proof: Program Fixpoint div (a b : nat) {wf lt a} : nat := ... uses the well-founded less-than relation on a as the termination argument. A retainer engagement identifying non-structural Fixpoint definitions that diverge on adversarial inputs involves systematically checking every fixpoint that recurses on a computed value, a decremented counter, or a value derived from list processing, and either restructuring to structural recursion or adding the appropriate well-founded measure.

Admitted and admit tell Coq to accept the current proof goal without verification, adding an axiom to the proof context. Print Assumptions theorem_name lists all axioms (including Admitted placeholders) that a theorem transitively depends on; in a codebase with 3 admitted lemmas, any theorem that depends on any of them inherits the unverified assumption. The Coq standard library provides axioms that are conventionally accepted as sound: Classical.classic : forall P, P \/ ~P (classical logic), FunctionalExtensionality.functional_extensionality (function extensionality), PropExtensionality.propositional_extensionality (propositional extensionality). These are flagged by Print Assumptions but are well-understood and widely used. Admitted placeholders, by contrast, are unverified domain claims. A retainer engagement eliminating Admitted proofs requires first categorizing each: is the claim true? Is there a straightforward proof by ring, omega/lia, or auto? Or does the claim require a non-trivial inductive argument, a case analysis, or a library lemma from Coq’s standard library or Math-Comp? The categorization work — determining proof strategy before any tactic is written — typically runs 2–5 hours per admitted theorem and produces no committed artifact.

SSReflect, Math-Comp, extraction, and Coq modules

SSReflect is an alternative tactic language for Coq, originally developed for the proof of the Four Color Theorem and now the standard language for Math-Comp (Mathematical Components) library work. SSReflect’s core tactic is move=> (introduce hypotheses): move=> h1 h2 introduces two hypotheses. rewrite in SSReflect applies rewrites left-to-right by default: rewrite lemma1 lemma2 chains rewrites; rewrite -lemma1 rewrites right-to-left; rewrite (lemma1 arg) instantiates a polymorphic lemma before rewriting. apply: f applies a lemma in suffix-colon style (Ltac: apply f). case: h destructs hypothesis h; elim: n inducts on n. have : P introduces an intermediate goal; set x := expr names a subexpression. SSReflect uses boolean reflection extensively: decidable propositions are represented as bool-valued functions, and a coercion is_true : bool → Prop lifts them to propositions. The reflect P b inductive relates a proposition P to a boolean b: iffP, idP, andP, orP, negP are the standard reflection lemmata that convert between boolean and propositional reasoning.

Math-Comp (Mathematical Components) is a large Coq library built on SSReflect containing algebraic structures and their verified properties. For retainer work on numerical and cryptographic software, the most commonly used components are: ssrnat (natural number arithmetic with SSReflect-style lemmas: addn, muln, subn, divn, modn, leq, ltn); ssrint (integer arithmetic); seq (polymorphic sequence operations with SSReflect-compatible lemmas: size, nth, rcons, cat, map, filter, allP, hasP); fintype (finite types with finType type class, enabling quantification over all elements); matrix (matrix algebra: matrix m n F for m×n matrices over field F; determinant, invertibility, linear independence); poly (polynomial arithmetic); bigop (generalized sums and products: \sum_(i < n) f i, \prod_(i < n) f i notation). A retainer engagement integrating Math-Comp into a cryptographic library for the first time commonly involves 6–12 hours of dependency configuration (Coq package manager opam pin, _CoqProject flags, import ordering), SSReflect tactic migration from Ltac, and identification of which Math-Comp module contains the needed algebraic lemma before the first theorem can be proved with library support.

Coq’s extraction mechanism compiles verified Coq definitions to OCaml or Haskell, removing proof terms (which are computationally irrelevant) and leaving the computational content. Extraction "output.ml" my_function extracts the definition; Recursive Extraction Library MyModule extracts an entire module. Extraction axioms specify how Coq primitives map to host language types: Extract Inductive bool => "bool" [ "true" "false" ]; Extract Constant plus => "(+)". Managing extraction axioms is a retainer engagement in itself: Coq’s nat extracts to a Peano-encoded OCaml type by default, which is exponentially slower than machine integers for large values; replacing with Extract Inductive nat => "int" [ "0" "(fun n -> n + 1)" ] "(fun f0 fs n -> if n = 0 then f0 () else fs (n-1))" is a standard optimization but requires verifying that the extracted code remains correct under the machine integer semantics. The gap between verified Coq behavior and the extracted OCaml performance characteristics is a common source of retainer hours: proving that an algorithm is correct in Coq and proving that the extracted version is efficient in OCaml are different problems, and retainer engagements often address both.

The Coq module system provides abstraction over types and functions analogous to ML modules. Module Type SIGNATURE declares a module interface with required types, functions, and properties; Module Implementation <: SIGNATURE provides a module that satisfies the interface (the <: check is type-theoretic, not just syntactic). Module Functor (X : SIGNATURE) : RESULT_SIG is a parameterized module. Coq Record defines a dependent record type with named projections: Record point : Set := { x_coord : nat; y_coord : nat; bounded : x_coord < 100 } includes a proof field ensuring the invariant at construction time. Instance provides type class instances for Coq’s type class system: Instance : EqDec nat := .... The Hint database controls auto/eauto proof search: Hint Resolve my_lemma : my_db registers a lemma; auto with my_db uses the custom database. Building a well-curated Hint database for a domain — lemmas that close common subgoals automatically, oriented in the direction that terminates proof search — is a 20–50 hour investment whose product is invisible in individual proofs but eliminates manual tactic work from every future theorem in the domain.

How HourTab tracks Coq developer retainer hours

Coq retainer work produces the classic invisible-work problem in formal verification: the highest-value changes look trivially small in the diff. Replacing Admitted with Qed is a one-word diff that permanently closes a verification gap. Adding a Function plugin measure to a Fixpoint is a two-line diff that eliminates a potential divergence. Adding a proof field to a Record is a one-field addition that encodes an invariant the compiler then enforces at every construction site. The proof strategy selection, the goal decomposition, the database search for the right Math-Comp lemma, the algebraic reasoning that justified ring as sufficient — none of these have artifacts in the diff. A client reading the diff sees Admitted replaced with tactic lines; the client cannot see the six months of unverified assumption that was closed, or the three downstream theorems that now have verified rather than conditional correctness.

HourTab gives Coq developers a public retainer-hours URL they send to clients — typically safety-critical embedded systems groups, cryptographic protocol organizations, high-assurance compiler teams, or formal methods research organizations — at the start of an engagement. For Coq retainers, each work log entry should name the mechanism (Admitted proof elimination; Fixpoint non-structural recursion repair; Function plugin / Program Fixpoint measure design; inductive invariant type design; Coq Record proof field addition; structural induction lemma authorship; omega/lia/ring/auto/eauto/tauto/intuition tactic proof construction; SSReflect/Math-Comp library integration; extraction to OCaml/Haskell; Hint database design), the specific theorem name and statement, the proof state at the Admitted placeholder or recursion error, the proof strategy and why, and the before/after observable metric. Coq retainers are often compared to Lean 4 developer retainers and Agda developer retainers for proof assistant work, and to Idris developer retainers for dependent types engagements. The distinction from Lean 4 is that Coq’s most mature ecosystem is the Math-Comp / SSReflect library for algebraic verification — retainers on cryptographic, mathematical software, or formally verified compiler work typically use Coq specifically for this library ecosystem. HourTab’s work log bridges the gap: the entry names the theorem, the tactic strategy, the Print Assumptions dependency chain, and the before/after production metric, so the client understands what the retainer accomplished without needing to know the Calculus of Inductive Constructions.

FAQ: Coq developer retainers