Blog › ICP guides

Agda developer on retainer: dependently typed programming, TERMINATING pragma elimination, sized types, cubical Agda, and formal verification on monthly retainer

October 10, 2026 · ~20 min read

An Agda verification library for a network packet serialization protocol had accumulated four {-# TERMINATING #-} pragmas over six months of development. Each pragma was added after the Agda termination checker rejected a recursive function with the error Termination checking failed for the following functions; the pragma suppressed the error and allowed the build to proceed. The Agda developer on retainer diagnosed all four pragmas and found a common root cause: the packet payloads were represented as Vec n A (size-indexed vectors), but each function was pattern-matching on the vector’s content and recursing on an intermediate List-like structure derived from the payload, not on the Vec n size index directly. Agda’s termination checker requires that at least one argument to a recursive function is structurally smaller on every recursive call; the intermediate extracted structure was not recognizable as a structural subterm of the original Vec n A argument. The developer restructured all four functions to recurse on the size index n: the Vec (suc n) A pattern binds the head element and the tail Vec n A, and the recursive call on the tail is unambiguously structurally decreasing on the first argument. {-# TERMINATING #-} pragmas: 4 → 0. Round-trip serialization proofs for 12 packet types: 12 of 12 verified by the Agda kernel.

The work log entry read “eliminated 4 TERMINATING pragmas, restructured Vec recursion, 14h.” It names the count and the duration, leaving the client unable to explain to the safety review why functions marked with {-# TERMINATING #-} were less trustworthy than functions without the pragma, or why the restructuring justified 14 hours of engineering work. The diagnosis required understanding that {-# TERMINATING #-} is not a verified annotation — it is an escape hatch that tells Agda to accept the function as terminating without verification, bypassing the guarantee that Agda’s verified functions actually terminate. A function decorated with {-# TERMINATING #-} could diverge on certain inputs; any downstream proof that uses the function’s result inherits the unverified assumption that it terminates. The four restructured functions are now verified total by the Agda termination checker: the checker can trace the structural decrease on n in each recursive call, and the 12 round-trip serialization proofs that depend on them are now trusted by the Agda kernel without axiom assumptions. The 14 hours of recursion structure analysis, intermediate structure tracing, and size-indexed type propagation are not visible in the diff beyond the four restructured function bodies and the removed pragmas.

Agda fundamentals: dependent types, indexed families, and pattern matching

Agda is a proof assistant and total functional programming language based on Martin-Löf type theory with inductive families and universe polymorphism. Agda’s type system is fully dependent: types can contain values, and functions can return types. data Vec (A : Set) : ℕ → Set where [] : Vec A 0; _::_ : A → Vec A n → Vec A (suc n) defines a vector indexed by its length — Vec A 0 is the type of empty vectors; Vec A (suc n) is the type of non-empty vectors with n+1 elements. The length is encoded in the type: a function head : Vec A (suc n) → A is total because Vec A (suc n) cannot be the empty vector (which has type Vec A 0). data Fin : ℕ → Set where zero : Fin (suc n); suc : Fin n → Fin (suc n) defines bounded natural numbers: a value of type Fin n is a natural number strictly less than n; lookup : Fin n → Vec A n → A is total because the index is by construction in-bounds. The universe hierarchy: Set (also Set₀) is the type of ordinary types; Set₁ is the type of Set; universe polymorphism: {l : Level} (A : Set l) quantifies over universe levels, enabling polymorphic library code.

Agda uses dependent pattern matching: patterns can bind type indices as variables. head : Vec A (suc n) → A; head (x :: _) = x has one case because the type Vec A (suc n) has only one constructor (_::_); the empty case [] has type Vec A 0, which is incompatible with Vec A (suc n) and is automatically handled by the dependent pattern match. The Agda coverage checker verifies that all cases are covered; functions with missing cases are rejected. where clauses introduce local definitions and lemmas: a function can use where to define helper functions that are visible only within the enclosing definition. postulate declares an axiom without proof, analogous to Admitted in Coq; postulate funext : {A B : Set} {f g : A → B} → (∀ x → f x ≡ g x) → f ≡ g postulates function extensionality. The abstract keyword hides the implementation details of a definition from other modules: abstract sorted-insert = ... makes the definition opaque outside the module, preventing clients from case-splitting on the implementation. BUILTIN pragmas connect Agda data types to compiler primitives: {-# BUILTIN NATURAL ℕ #-} enables numeric literals; {-# BUILTIN EQUALITY _≡_ #-} connects Agda’s propositional equality to the kernel’s definitional equality.

Agda’s termination checker uses structural recursion as its primary criterion: a recursive function must have at least one argument that is strictly structurally smaller on every recursive call. Structural subterms: if xs : Vec A (suc n) and x :: ys = xs, then ys : Vec A n is a structural subterm of xs; the recursive call on ys is structurally decreasing on xs. The termination checker also recognizes lexicographic decrease: if the primary argument is not decreasing, a secondary argument that is decreasing under the same primary value is also accepted. The {-# TERMINATING #-} pragma bypasses all termination checking and accepts the function as total without verification. The {-# NON_TERMINATING #-} pragma marks a function as explicitly non-terminating, preventing it from being used in proofs. A function without either pragma that the termination checker cannot verify is rejected with Termination checking failed. A retainer engagement eliminating {-# TERMINATING #-} pragmas involves first classifying each: is the recursion genuinely structural on some argument (and the checker failed to recognize it due to an intermediate structure)? Or does the function require sized types or a well-founded recursion argument? Each class requires a different restructuring strategy, and the analysis of which class applies typically runs 3–6 hours per pragma before any code is changed.

The Agda standard library (agda-stdlib) provides verified implementations of common data structures and algorithms. Key modules for retainer work: Data.Vec (Vec n A operations: map, zipWith, foldr, lookup, head, tail, _++_ with length arithmetic in the type); Data.Fin (Fin n operations: raise, inject+, toNat, fromNat<); Data.List (List operations with propositional proofs about them); Relation.Binary.PropositionalEquality (propositional equality: _≡_, refl, cong, sym, trans, subst); Data.Nat.Properties (arithmetic lemmas about ℕ: +-comm, +-assoc, *-distribˡ-+); Function.Equality (setoid morphisms); Data.Maybe (Maybe A and its monad instance). The module system: open import Data.Vec using (Vec; lookup; _++_) imports specific names; open import Data.Vec renaming (lookup to vecLookup) renames on import. Anonymous modules: module _ (A : Set) where introduces a parameter that all subsequent definitions inherit. The module system’s parameterization is how Agda library code achieves the equivalent of ML functors.

Sized types, coinduction, --safe flag, and cubical Agda

Sized types extend Agda’s termination checking to functions that are not structurally recursive on their primary argument. A size is a type-level measure of the recursion depth: data Tree (A : Set) : {i : Size} → Set where leaf : Tree A; node : {i : Size} → A → Tree A {i} → Tree A {i} → Tree A {↑ i} indexes the tree by a size that increases with the height of the constructor. A recursive function f : {i : Size} → Tree A {i} → B can recurse on a subtree of size i while the outer tree has size ↑ i; Agda’s sized-type checker verifies that every recursive call uses a strictly smaller size. The --sized-types flag enables sized type checking; sized types are an extension beyond the core Agda type theory. A retainer engagement adding sized types to functions that the standard termination checker rejects involves first understanding why structural recursion fails (the recursion is on a value computed from the input, not on the input itself), then designing the size parameter to capture the remaining recursion depth. The size parameter design — which argument it is applied to, how it threads through helper functions, how it interacts with data type indices — typically runs 8–18 hours for a cluster of related functions.

Coinductive data types in Agda represent potentially-infinite structures: streams, process algebras, reactive systems. record Stream (A : Set) : Set where coinductive; field head : A; tail : Stream A defines a stream using a coinductive record; field definitions use copattern matching. zeros : Stream ℕ; zeros .head = 0; zeros .tail = zeros defines the infinite stream of zeros by copattern: .head and .tail are projections that are defined separately. The Agda productivity checker verifies that coinductive definitions are guarded: every definition of a coinductive field must be a constructor or a record constructor application at the top level, ensuring the computation is productive (does not loop before producing a value). {-# NON_TERMINATING #-} is sometimes used as a workaround when the productivity checker cannot verify guardedness; a retainer engagement eliminating these pragmas involves restructuring the definition to make the guard explicit — often by introducing an intermediate coinductive helper or by using sized types to measure productivity. Thunk (from Data.Colist or manually) delays evaluation: record Thunk (A : Set) : Set where constructor λ; field force : A suspends a computation until .force is called, enabling productive definitions that compute their next value on demand.

The --safe command-line flag compiles Agda with a restricted set of trusted axioms, rejecting postulates that have not been proved and flagging BUILTIN pragmas that could potentially introduce unsoundness. Running with --safe is the gold standard for Agda verification work intended to be trusted: a module that compiles with --safe has its correctness properties verified entirely within the trusted Agda kernel, without unverified assumptions. A retainer engagement migrating a codebase from non-safe to --safe compilation involves auditing every postulate declaration (does it state a provable fact, or is it an unsound axiom?), every BUILTIN pragma (does it connect a data type to a compiler primitive in a way that preserves the type-theoretic invariants?), every {-# TERMINATING #-} and {-# NON_TERMINATING #-} pragma, and every foreign function interface declaration. Each unproved postulate must either be proved using Agda tactics or replaced with a structurally different design that does not require the axiom. A codebase with seven postulates commonly requires 12–30 hours to achieve --safe compilation; the resulting codebase provides a strictly stronger correctness guarantee and the achievement is visible in the build flags, not in the individual proof terms.

Cubical Agda is an extension of Agda implementing cubical type theory, which provides a constructive interpretation of the Univalence Axiom from Homotopy Type Theory (HoTT). In standard Agda, propositional equality is an inductive family _≡_ : A → A → Set with a single constructor refl : x ≡ x; equalities between distinct terms must be proved by rewriting. In cubical Agda, paths are the primitive notion: Path A x y is the type of paths from x to y in space A, and refl is the constant path. The interval type I has endpoints i0 : I and i1 : I; a path p : Path A x y is a function I → A with p i0 = x and p i1 = y. Function extensionality is provable in cubical Agda (it follows from the path definition of equality): funExt : ({x : A} → f x ≡ g x) → f ≡ g is a theorem, not a postulate. Univalence is also provable: equivalent types are equal. The Cubical.Foundations standard library provides path-based equality reasoning; the --cubical flag enables the extension. A retainer engagement migrating a library from postulate-based function extensionality to cubical Agda involves converting all postulate funext = ... uses to the built-in cubical funExt, which typically improves both the soundness and the proof ergonomics of the codebase.

How HourTab tracks Agda developer retainer hours

Agda retainer work shares the invisible-work problem with all proof assistant retainers, amplified by the fact that Agda’s most common retainer tasks — pragma elimination, indexed type design, --safe migration — involve structural changes to the type signatures and recursion architecture that produce small diffs. Removing four {-# TERMINATING #-} pragmas is a four-line diff that changes the library from “assumed total by developer assertion” to “verified total by the Agda kernel.” Adding a size index to a data type is a one-argument addition that enables the termination checker to verify a cluster of related functions automatically. Replacing a postulate with a proved lemma is a diff whose size is the proof term — typically 5–40 lines — but whose value is eliminating an unverified assumption from the trusted computing base. The recursion structure analysis, the intermediate structure tracing, the size-index design, the proof construction — none of these have artifacts proportional to their complexity in the committed diff.

HourTab gives Agda developers a public retainer-hours URL they send to clients — typically formal verification teams, programming language research groups, protocol specification organizations, or mathematics formalization projects — at the start of an engagement. For Agda retainers, each work log entry should name the mechanism ({-# TERMINATING #-} pragma elimination; Vec n / size-indexed type recursion restructuring; indexed invariant type design; Fin n bounded index migration; --safe flag migration and postulate elimination; sized type Size argument design; coinductive copattern definition; abstract information hiding design; cubical Agda path equality migration; Agda standard library integration), the specific function name and the termination checker error message, the restructuring strategy and why, and the before/after observable metric. Agda retainers are often compared to Lean 4 developer retainers and Coq developer retainers for proof assistant work, and to Idris developer retainers for dependent types engagements. The distinction from Idris is that Agda’s type theory is intentionally more minimal — there is no built-in universe hierarchy for Prop/Set/Type; instead, Agda uses Set l with explicit universe level polymorphism — and Agda’s primary use case is programming language research and mathematics formalization rather than production software verification. HourTab’s work log bridges the gap: the entry names the pragma, the termination checker diagnosis, the restructuring decision, and the before/after production metric, so the client understands what the retainer accomplished without needing to know Martin-Löf type theory.

FAQ: Agda developer retainers