CompCert4Lean: Porting a Verified C Compiler to Lean in Six Weeks with Parallel Coding Agents

Summary (Overview)

  • CompCert4Lean is a large-scale port of CompCert 3.17's verified compiler core from Rocq (Coq) to Lean, completed in approximately six weeks by one expert directing parallel LLM coding agents
  • The port covers the full typed CompCert C abstract syntax through x86-64 assembly, discharging all 4,908 recorded proof obligations without project-specific axioms, and produces executable Linux binaries
  • The migration workflow partitions the development along dependencies, audits translated definitions and theorem statements before large-scale proof reconstruction, then reconstructs proofs in parallel against stable interfaces
  • Optimization campaigns show the Lean port enables better agent-driven improvements: GPT-6-astra achieved 11.7% lower runtime on Lean versus 2.3% on Rocq across 29 small-tests programs, while preserving the end-to-end correctness theorem
  • Only 3 of 1,071 human interactions supplied technical direction; 88.8% concerned workflow and coordination

Introduction and Theoretical Foundation

The paper addresses the challenge that while Lean has made substantial progress as a platform for formalized mathematics, a substantial body of mature program-verification infrastructure remains available only in Rocq. CompCert is the prominent example: an optimizing C compiler with a machine-checked proof of semantic preservation from C to assembly, embodying years of proof engineering.

Key motivation: Bringing CompCert to Lean would make existing verification work reusable within the Lean ecosystem, enabling new developments to build on its language semantics, memory model, and correctness theorems without reconstructing those foundations.

The correctness obligation is formally specified as:

∀p: Csyntax.program ,a: Asm.program ,ξ, compile (p)= OK (a)  ⟹   BackwardSim (Cξ(p),Aξ(a)).(1)\begin{array}{c} \forall p: \text { Csyntax.program }, a: \text { Asm.program }, \xi , \\ \text { compile } (p) = \text { OK } (a) \implies \text { BackwardSim } \big (\mathcal {C} _ {\xi} (p), \mathcal {A} _ {\xi} (a) \big). \end{array}\tag{1}

where CξC_{\xi} and Aξ\mathcal{A}_{\xi} are the source C and target assembly operational semantics under the same external-call interface ξ\xi.

Trusted computing base: The Lean kernel and its standard axioms (propext, Classical.choice, Quot.sound) replace the Rocq kernel. The source and target semantics, external-call interface, and unverified code (preprocessor to linker) remain in the trusted base.

Methodology

Migration Workflow (Seven Stages)

  1. Resolve migration gates: Investigate representation and interface choices with broad consequences; risk discovery identified 30 issues informing 5 feasibility gates
  2. Migrate definitions in parallel: Partition dependency graph into 166 units (154 source components, 12 shared providers) with canonical owners
  3. Audit & repair definitions: Independent parallel agents compare translated definitions/statements with Rocq source; first audit found 1,091 statements reduced to True
  4. Reconstruct proofs in parallel: Automated agents work from an inventory of 4,908 obligations with bounded attempts and partial acceptance
  5. Finalize remaining proofs: Human-guided agent sessions handle difficult obligations (471 remained when automatic reconstruction stopped)
  6. Integrate, validate, and optimize: Connect verified core to executable toolchain producing Linux x86-64 binaries

Key Technical Decisions

Infinite trace representation (due to Lean 4.33's coinductive mechanism supporting predicates in Prop, not data in Type):

abbrev TraceInf (Event : Type) := Nat -> Event
def head (stream : TraceInf Event) : Event := stream 0
def tail (stream : TraceInf Event) : TraceInf Event := fun index => stream (index + 1)
def cons (event : Event) (stream : TraceInf Event) : TraceInf Event
| 0 => event
| index + 1 => stream index

Algorithm 1 handles parallel definition migration with iterative correspondence auditing, using integration checks enforcing canonical ownership and restrictions on proof escapes. Algorithm 2 handles automated proof grinding with partial acceptance and bounded retries, grouping up to four related proof obligations per batch.

Empirical Validation / Results

Implementation Size

ComponentLean filesLinesCompleted obligations
Foundations and libraries3464,5571,266
Floating-point development (Flocq)2451,178554
Common semantics and infrastructure1844,081799
Typed-C frontend and proofs1746,383437
Backend transformations and proofs56136,4481,516
x86-64 backend and configuration2147,439324
Pipeline composition and correctness31,87712
Migrated core subtotal173391,9634,908

Correctness Results

All 139 applicable CompCert small-tests pass at both O0 and O2, plus 20 correctness executions across six SPEC CPU2026 programs. Differential testing shows:

  • Identical RTL after all nine stages for 18,807 programs at O2 and 18,808 at O0
  • Bit-identical results on 37.4 million specification-function inputs
  • 37 output discrepancies explained (2 undefined-behavior cases, 35 mixed-compiler ABI cases)

Performance Results

BenchmarkInputsProgram runtime (Lean/CompCert)GCC/CompCertCompilation O0Compilation O2
Small-tests291.0040.7962.162.18
LBM20.9770.6511.961.61
SQLite11.0010.9901.711.84

Optimization Campaign Results

ModelSmall-tests runtime (Rocq/Lean)SPEC runtime (Rocq/Lean)Compilation time (Rocq/Lean)New verified passes (Rocq/Lean)
GPT-6-astra0.977 / 0.8830.978 / 0.9311.054 / 2.0540 / 3
DeepSeek 4.1 Flash0.992 / 0.9500.977 / 0.9111.055 / 1.8660 / 0
Kimi K3.10.994 / 0.9770.981 / 0.9851.051 / 2.0010 / 0

Migration Cost

  • 12,435 distinct sessions, 83.53 billion recorded tokens (93.75% cached input)
  • Review and repair accounted for ~59% of recorded tokens
  • Only 29,565 tokens of human-authored prompts across six weeks

Theoretical and Practical Implications

Theoretical contributions:

  • First compiler implemented and verified in Lean covering full typed CompCert C abstract syntax to x86-64 assembly
  • Demonstration that dependency-based partitioning with semantic review before large-scale proof reconstruction reduces error propagation in parallel migration
  • Evidence that workflow coordination (88.8% of interactions) rather than technical direction enables large-scale migration

Practical implications:

  • The Lean port enables agents to produce 106 candidate variants completing full compiler and proof builds (vs. 40 in Rocq), giving more opportunities to evaluate and refine optimizations
  • New verified passes (path splitting, loop unrolling, instruction scheduling) were developed autonomously by agents in Lean
  • The workflow could make other Rocq-based tools available in Lean with manageable human effort

Conclusion

CompCert4Lean demonstrates that one expert directing parallel LLM agents can migrate a verified compiler from Rocq to Lean in approximately six weeks, with only three messages supplying technical direction. The workflow combines dependency-based parallelism, correspondence audits, and proof reconstruction against stable interfaces.

The optimization campaigns show that all three models achieved larger small-tests runtime reductions in Lean while retaining the end-to-end correctness theorem, suggesting that agent-assisted migration could make other Rocq-based tools available in Lean while opening opportunities to extend their verified infrastructure. The authors note that one campaign per environment cannot separate the effects of model capability, proof automation, repository structure, and search choices—a limitation that invites future investigation.

Related papers