Coq
Coq is an interactive proof assistant that began at Inria in France in 1984 and has been distributed as the Rocq Prover since version 9.0, released on 2025-03-12, which completed the renaming of the project [1][2][4]. Users write definitions, programs and theorems in a specification language called Gallina, build proofs interactively, and have every proof checked by a small certification kernel; verified functions can then be extracted to OCaml, Haskell or Scheme [1][6]. The system's logic is a version of the Calculus of Inductive Constructions, a dependently typed lambda calculus that serves as both a programming language and a logic [1][5]. Coq was used for the CompCert verified C compiler and for the machine-checked proofs of the four color theorem and the Feit-Thompson odd order theorem [7][9][10], and it has been used as an environment for machine learning research on automated theorem proving, from the CoqGym dataset in 2019 to agents built on large language models in 2025 and 2026 [14][25][26].
Rocq is written in OCaml and released under the GNU Lesser General Public License version 2.1 [1]. Its development is managed by the Rocq Team, and the project's own site says more than 200 people have contributed to it [1].
History
Calculus of Constructions (1984 to 1989)
The project started as an implementation of the Calculus of Constructions, a type theory introduced by Thierry Coquand. According to the "Early history of Coq" chapter of the reference manual, a first implementation was begun in 1984 by Gérard Huet and Coquand at INRIA-Rocquencourt; version 1.10 was frozen on 22 December 1984, and Coquand defended his thesis, which used that version, on 31 January 1985 [3]. Coquand and Huet published the calculus in Information and Computation in 1988 [28]. The early versions were written in CAML, a functional language of the ML family designed at INRIA [3].
The Calculus of Inductive Constructions and the name Coq
In 1989 Coquand and Christine Paulin extended the formalism with primitive inductive definitions [3]. The reference manual records that at the end of 1989 work began on version 5.1, which was "renamed as the system Coq for the Calculus of Inductive Constructions" [3]. The project's About page dates Paulin's extension of the system to the Calculus of Inductive Constructions to 1991 [1]. In 1990 Coquand left for Chalmers University in Göteborg and Paulin-Mohring joined the LIP laboratory at ENS Lyon; the Formel project at INRIA split into the Cristal team (functional programming in Caml) and the Coq team, led jointly by Huet at INRIA-Rocquencourt and Paulin-Mohring in Lyon [3]. Versions 5.6 (1991) and 5.8 (May 1993) were major distributed releases [3]. Version 6.1 was ported to Objective Caml by Bruno Barras, and version 7, a reimplementation begun in September 1999 by Jean-Christophe Filliâtre with a new type-checking kernel, was first distributed in March 2001 [3].
Timeline
| Date | Event |
|---|---|
| 1984 | Huet and Coquand begin implementing the Calculus of Constructions [3] |
| 1984-12-22 | Version 1.10 frozen [3] |
| 1985-01-31 | Coquand defends his thesis [3] |
| 1988 | "The calculus of constructions" published in Information and Computation [28] |
| 1989 | Inductive definitions added; version 5.1 named Coq [3] |
| 1991 | Version 5.6 released [3] |
| 2001-03 | Version 7.0 released [3] |
| 2005 | Formal proof of the four color theorem completed [9] |
| 2012-09-20 | Formal proof of the odd order theorem completed [9] |
| 2013 | ACM Software System Award [1] |
| 2022 | French Open Science Free Software Award [1] |
| 2025-01-16 | Coq 8.20.1 released [2] |
| 2025-01-24 | Rocq Prover 9.0+rc1 released [2] |
| 2025-03-12 | Rocq Prover 9.0.0 released, completing the rename [2][4] |
| 2025-09-15 | Rocq Prover 9.1.0 released [2] |
| 2026-03-27 | Rocq Prover 9.2.0 released [2] |
| 2026-09-19 | Rocq 9.3.0 released [30] |
Renaming to the Rocq Prover
The project's About page explains that the name "Coq" referred to the Calculus of Constructions, to Thierry Coquand, and to the French rooster [1]. The new name honors Inria Rocquencourt, where the system was developed, and alludes to the Roc, a mythical bird; the core team chose it after a poll of users [1].
The release notes for Rocq Prover 9.0.0 state that it "marks the completion of the renaming from The Coq Proof Assistant to The Rocq Prover" [4]. That release introduced a single command-line tool, rocq, and shipped compatibility Coq binaries and packages so that existing projects could keep building [4]. The accompanying Rocq Standard Library 9.0.0 changed the library's require prefix from Coq to Stdlib [2]. Coq 8.20.1, released on 2025-01-16, is the last prover version under the Coq name on the project's release list [2].
The newest prover release as of November 2026 is Rocq 9.3.0, published on the project's GitHub repository on 2026-09-19 [30]; the release list on rocq-prover.org still showed Rocq Prover 9.2.0 (2026-03-27) as its newest prover entry, along with Rocq Platform 2026.07.0 (2026-07-30), a distribution for Rocq 9.1 [2]. Many libraries still carry the old name in their titles while supporting the new versions: the coq-community four color theorem project, for example, describes itself as a proof "in Coq" and lists compatibility with Rocq 9.0 or later [10].
Design
Logic
The reference manual states that "The underlying formal language of the Rocq Prover is a Calculus of Inductive Constructions (CIC)" [5]. In this calculus every term has a type, and types are themselves terms; the manual notes that the constructions express "both logical and programming notions, according to the Curry-Howard correspondence between proofs and programs, and between propositions and types" [5]. A proposition is a type, and a proof of it is a term of that type, so checking a proof amounts to type checking a term (see lambda calculus for the background of this correspondence). The About page describes the language as the "Polymorphic, Cumulative Calculus of Inductive Constructions," combining higher-order logic with a typed functional programming language [1].
The calculus has a hierarchy of sorts: SProp, Prop, Set and a family of universes Type(i) [5]. Universes are cumulative, so a term in universe $i$ is also a term in universe $i+1$, and Prop is included in Set; SProp is not related to the other sorts by cumulativity [5]. Inductive definitions declare both constructors and the inductive or coinductive types they build [5].
Proofs and the kernel
Users develop proofs interactively, mostly by entering tactics, high-level proof steps that the system applies to the current goal, and the finished proofs are checked by a small certification kernel [1][14]. Machine-learning work relies on this check: the authors of Cobblestone note that its proofs are guaranteed to be sound even though the large language models that propose them are not, and AutoRocq's final output is a proof derivation checked by the Rocq prover [24][26].
Program extraction
Extraction turns Gallina functions and the computational content of proofs into ordinary functional programs. The manual describes the extraction commands as "used to build certified and relatively efficient functional programs," with OCaml, Haskell and Scheme as output languages [6]. Logical parts and types are erased, and a logical axiom "has no computational content and hence will not appear in extracted terms" [6]. Values whose type lives in Set are extractable, while values of types in Prop are not [5].
Notable developments
CompCert
CompCert, developed by Xavier Leroy and colleagues at Inria, is an optimizing C compiler whose correctness is proved in Coq. Leroy's 2009 article in Communications of the ACM describes using "the Coq proof assistant both for programming the compiler and for proving its correctness," with a proof of semantic preservation: the generated machine code behaves as the semantics of the source program prescribes [7]. The current CompCert C covers "almost all of the C language (ISO C 2011)" and generates code for ARM, PowerPC, RISC-V and x86 [8]. The developers received the 2021 ACM Software System Award for CompCert, and in March 2026 the project reported that the compiler had been qualified for the Multi-Function Computer New Generation (MFC_NG) of ATR 42/72 aircraft, the first time certification credit under DO-178C, DO-333 and DO-330 could be claimed for critical avionics software from compiler usage [8]. CompCert 3.18, released in August 2026, is compatible with Rocq 9.2 [8]. CompCert's proof obligations were later used as a test set for machine-learning provers such as Proverbot9001 and COPRA [15][20].
Four color theorem
Georges Gonthier and Benjamin Werner completed a formal proof of the four color theorem in 2005 [9]. The proof is maintained by the coq-community project as "a formal proof of the Four Color Theorem in Coq," together with supporting theories of classical real numbers, plane topology and combinatorial hypermaps; it depends on the Mathematical Components (MathComp) ssreflect library [10].
Feit-Thompson odd order theorem
The odd order theorem, proved by Walter Feit and John Griggs Thompson in 1963, states that every finite group of odd order is solvable [9]. Gonthier's Mathematical Components team at the Microsoft Research-Inria Joint Centre finished a Coq proof on 2012-09-20 after a project of more than six years [9]. In an email quoted by Microsoft Research, Laurent Théry summarized the size of the development as 170,000 lines, 15,000 definitions and 4,300 theorems [9]. The result was published as "A Machine-Checked Proof of the Odd Order Theorem" at the Interactive Theorem Proving conference in 2013 [11], and the code is maintained in the math-comp organization on top of the Mathematical Components library [29].
Verified cryptography and teaching
Fiat Cryptography synthesizes correct-by-construction code for cryptographic primitives, and its current version requires Coq 9.0 or later with Rocq standard library 9.1 or later [12]. Its generated C code is tested against the BoringSSL test suite, and its Zig output is used in the Zig standard library [12]. The approach was described by Andres Erbsen, Jade Philipoom, Jason Gross, Robert Sloan and Adam Chlipala at the IEEE Symposium on Security and Privacy in 2019 [12].
Software Foundations, a series of seven textbooks on the mathematical foundations of reliable software, is written as a machine-checked "proof script" for the Rocq proof assistant, so that its exercises can be checked by the system [13].
Use in AI and machine-learning research
Research on learned provers for Coq has largely framed proof synthesis as a way to lower the cost of formal software verification, and its benchmarks are often drawn from verified software projects such as CompCert [15][20][23]. Several systems were evaluated on Coq alongside other proof assistants such as Lean and Isabelle [20][21].
Datasets and learned tactic predictors
| System | Year | Approach | Reported result |
|---|---|---|---|
| CoqHammer | 2016 | Translates goals for external automated provers (Vampire, CVC4, E, Z3) and reconstructs proofs with the sauto tactic [16][17] | Combined with Tactician, proved 56.7% of standard library lemmas [18] |
| CoqGym / ASTactic | 2019 | Dataset of 71K human-written proofs from 123 Coq projects; tactic generator over abstract syntax trees [14] | Proved theorems not previously provable by automated methods [14] |
| Proverbot9001 | 2019 | Learned proof search, evaluated on CompCert [15] | 27.5% of test theorems with solver-based tooling [15] |
| Tactician | 2020 | Learns from tactic scripts as the user works [18] | 39.3% of standard library lemmas fully automatically [18] |
| Graph2Tac | 2024 | Graph neural network with online learning of new definitions, in Tactician [19] | Graph2Tac and Tactician's online k-NN solver each beat CoqHammer, Proverbot9001 and a transformer baseline by at least 1.48x [19] |
CoqGym, published by Kaiyu Yang and Jia Deng at ICML 2019, packaged 71K proofs from 123 projects as a learning environment and introduced ASTactic, a deep learning model that generates tactics as programs [14]. Proverbot9001 (Alex Sanchez-Stern and colleagues) reported a proof completion rate four times that of earlier machine-learning models for Coq when run without additional solvers [15]. Tactician, by Lasse Blaauwbroek, Josef Urban and Herman Geuvers, predicted the correct tactic 23.4% of the time on the Coq standard library [18]. Its later Graph2Tac work reported that an online k-nearest neighbors solver proved 1.72 times as many theorems as an offline equivalent, and that a graph neural network learning hierarchical representations of new definitions gave a 1.5x improvement over an offline baseline [19].
Large language model provers and agents
| System | Year | Approach | Reported result |
|---|---|---|---|
| COPRA | 2023 | GPT-4 proposes tactics inside a backtracking search, prompted in context [20] | Outperformed few-shot GPT-4 on Coq tasks from CompCert [20] |
| CoqPilot | 2024 | VS Code extension that fills admit holes with LLM and non-LLM candidates [22] | Benchmarking framework for Coq generation methods [22] |
| Rango | 2024 | Fine-tuned LLM with retrieval of premises and similar proofs; CoqStoq dataset [23] | 32.0% of benchmark theorems, 29% more than Tactician [23] |
| Cobblestone | 2024 | LLM proofs used to split goals into parts; iterates on unproven parts [24] | Up to 58% of theorems with an oracle; $1.25 and 14.7 minutes per run on average [24] |
| RocqStar | 2025 | Similarity-driven premise retrieval and a multi-stage agent [25] | Multi-agent debate in planning raised success by 20% [25] |
| AutoRocq | 2025 | Agent that refines proofs in a loop with the Rocq prover [26] | Evaluated on SV-COMP benchmarks and Linux kernel modules [26] |
| ReCent-Prover | 2026 | Reflection on generated tactics and plan-conditioned retrieval [27] | 22.58% relative improvement on CoqStoq [27] |
COPRA, by Amitayush Thakur, Swarat Chaudhuri and colleagues, repeatedly queries GPT-4 for tactics inside a stateful search and feeds execution results and retrieved lemmas back into the prompt; it was evaluated on miniF2F in Lean and on a set of CompCert tasks in Coq [20]. PutnamBench, a NeurIPS 2024 benchmark by an overlapping set of authors, contains 1,692 formalizations of 640 Putnam competition theorems; every problem is formalized in Lean 4 and Isabelle, and a substantial subset also in Coq [21].
Rango, presented at ICSE 2025, introduced CoqStoq, a dataset of 2,226 open-source Coq projects and 196,929 theorems collected from GitHub, and retrieves relevant proofs and premises at every proof step for its fine-tuned model; adding similar proofs to the context increased the number of theorems proven by 47% [23]. Cobblestone, which was accepted to ICSE 2026, uses partial progress from unsound LLM proofs to build proofs that are still checked by Coq [24]. CoqPilot, whose code is hosted by JetBrains Research, and RocqStar share their authors; RocqStar reported up to a 28% relative increase in generator performance from a self-attentive embedder used for premise selection [22][25]. AutoRocq, whose camera-ready version appeared at FSE 2026, is described by its authors as an AI agent that collaborates with the Rocq prover rather than relying on extensive training on proof examples, and they propose pairing it with AI coding agents in a generate-and-validate loop [26]. ReCent-Prover, posted in April 2026, has the LLM critique its own tactic proposals and condition retrieval on generated proof plans [27].
Recognition
The initial Coq development team received the ACM Software System Award in 2013, which the project describes as "the highest distinction for research software," and the ACM SIGPLAN Programming Languages Software Award in the same year [1]. In 2022 the Coq Proof Assistant received the Open Science Free Software Award from the French ministry of higher education and research [1].
Continue reading
- InriaInria (in English, the National Institute for Research in Digital Science and Technology) is a French public research institute for computer science, applied mathematics and digital technologyMentioned 8 times above
- Lean (Theorem Prover)Lean is an open source interactive theorem prover and dependently typed functional programming language created by Leonardo de Moura, first launched at Microsoft Research Redmond in 2013.Mentioned 3 times above
- Lambda CalculusLambda calculus (often written λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.Mentioned twice above
- Automated Theorem ProvingAutomated theorem proving (ATP) is the use of computer programs to find or check mathematical proofs, expressing both the statement and the proof in a formal_logic so that correctness can be decided…Listed in See also
- PutnamBenchPutnamBench is a benchmark for evaluating automated theorem proving systems, especially neural and large-language-model-based provers, on competition mathematics.Listed in See also
- MathlibMathlib (formally mathlib4, the active Lean 4 incarnation) is the community-maintained, open-source unified library of formalized mathematics for the lean theorem prover, and it is the largest single library…Listed in See also
More to read
References
- ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12 ^13 ^14Rocq Prover. "About The Rocq Prover". rocq-prover.org, accessed 2026-11-18. rocq-prover.org/about
- ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9Rocq Prover. "Rocq Prover and Rocq Platform releases". rocq-prover.org, accessed 2026-11-18. rocq-prover.org/releases
- ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12 ^13Rocq Prover. "Early history of Coq". The Rocq Prover 9.0.0 documentation, 2025. rocq-prover.org/...history
- ^1 ^2 ^3 ^4Rocq Prover. "Rocq Prover 9.0.0 Release Notes". rocq-prover.org, 2025-03-12. rocq-prover.org/...9.0.0
- ^1 ^2 ^3 ^4 ^5 ^6 ^7Rocq Prover. "Typing rules". The Rocq Prover 9.0.0 documentation, 2025. rocq-prover.org/...cic
- ^1 ^2 ^3Rocq Prover. "Program extraction". The Rocq Prover 9.0.0 documentation, 2025. rocq-prover.org/...extraction
- ^1 ^2Leroy, Xavier. "Formal verification of a realistic compiler". Communications of the ACM 52(7), 2009. xavierleroy.org/...compcert-CACM.pdf
- ^1 ^2 ^3CompCert. "CompCert - Main page". compcert.org, accessed 2026-11-18. compcert.org
- ^1 ^2 ^3 ^4 ^5 ^6 ^7Knies, Rob. "Theorem Proof Gains Acclaim". Microsoft Research Blog, 2012-10-11. microsoft.com/...theorem-proof-gains-acclaim
- ^1 ^2 ^3coq-community. "fourcolor: Formal proof of the Four Color Theorem". GitHub, accessed 2026-11-18. github.com/...fourcolor
- ^Gonthier, Georges; Asperti, Andrea; Avigad, Jeremy; Bertot, Yves; Cohen, Cyril; Garillot, François; Le Roux, Stéphane; Mahboubi, Assia; et al. "A Machine-Checked Proof of the Odd Order Theorem". Interactive Theorem Proving (ITP 2013), Lecture Notes in Computer Science, Springer, 2013. doi.org/...978-3-642-39634-2_14
- ^1 ^2 ^3mit-plv. "Fiat-Crypto: Synthesizing Correct-by-Construction Code for Cryptographic Primitives". GitHub, accessed 2026-11-18. github.com/...fiat-crypto
- ^Software Foundations. "Software Foundations". University of Pennsylvania, accessed 2026-11-18. softwarefoundations.cis.upenn.edu
- ^1 ^2 ^3 ^4 ^5Yang, Kaiyu; Deng, Jia. "Learning to Prove Theorems via Interacting with Proof Assistants". ICML 2019, arXiv:1905.09381. arxiv.org/...1905.09381
- ^1 ^2 ^3 ^4 ^5Sanchez-Stern, Alex; Alhessi, Yousef; Saul, Lawrence; Lerner, Sorin. "Generating Correctness Proofs with Neural Networks". MAPL 2020, arXiv:1907.07794. arxiv.org/...1907.07794
- ^Czajka, Łukasz. "CoqHammer". GitHub, accessed 2026-11-18. github.com/...coqhammer
- ^Czajka, Łukasz; Kaliszyk, Cezary. "Goal Translation for a Hammer for Coq (Extended Abstract)". HaTT 2016, EPTCS 210, arXiv:1606.05946. arxiv.org/...1606.05946
- ^1 ^2 ^3 ^4Blaauwbroek, Lasse; Urban, Josef; Geuvers, Herman. "Tactic Learning and Proving for the Coq Proof Assistant". LPAR 2020, EPiC Series in Computing 73, arXiv:2003.09140. arxiv.org/...2003.09140
- ^1 ^2 ^3Blaauwbroek, Lasse; Olšák, Miroslav; Rute, Jason; Schaposnik Massolo, Fidel Ivan; Piepenbrock, Jelle; Pestun, Vasily. "Graph2Tac: Online Representation Learning of Formal Math Concepts". arXiv:2401.02949, 2024. arxiv.org/...2401.02949
- ^1 ^2 ^3 ^4 ^5 ^6Thakur, Amitayush; Tsoukalas, George; Wen, Yeming; Xin, Jimmy; Chaudhuri, Swarat. "An In-Context Learning Agent for Formal Theorem-Proving". arXiv:2310.04353, 2023. arxiv.org/...2310.04353
- ^1 ^2Tsoukalas, George; Lee, Jasper; Jennings, John; Xin, Jimmy; Ding, Michelle; Jennings, Michael; Thakur, Amitayush; Chaudhuri, Swarat. "PutnamBench: Evaluating Neural Theorem-Provers on the Putnam Mathematical Competition". NeurIPS 2024 Datasets and Benchmarks Track, arXiv:2407.11214. arxiv.org/...2407.11214
- ^1 ^2 ^3Kozyrev, Andrei; Solovev, Gleb; Khramov, Nikita; Podkopaev, Anton. "CoqPilot, a plugin for LLM-based generation of proofs". ASE 2024 Tool Demonstrations, arXiv:2410.19605. arxiv.org/...2410.19605
- ^1 ^2 ^3 ^4Thompson, Kyle; Saavedra, Nuno; Carrott, Pedro; Fisher, Kevin; Sanchez-Stern, Alex; Brun, Yuriy; Ferreira, João F.; Lerner, Sorin; First, Emily. "Rango: Adaptive Retrieval-Augmented Proving for Automated Software Verification". ICSE 2025, arXiv:2412.14063. arxiv.org/...2412.14063
- ^1 ^2 ^3 ^4Kasibatla, Saketh Ram; Agarwal, Arpan; Brun, Yuriy; Lerner, Sorin; Ringer, Talia; First, Emily. "Cobblestone: A Divide-and-Conquer Approach for Automating Formal Verification". ICSE 2026, arXiv:2410.19940. arxiv.org/...2410.19940
- ^1 ^2 ^3 ^4Kozyrev, Andrei; Khramov, Nikita; Solovev, Gleb; Podkopaev, Anton. "RocqStar: Leveraging Similarity-driven Retrieval and Agentic Systems for Rocq generation". arXiv:2505.22846, 2025. arxiv.org/...2505.22846
- ^1 ^2 ^3 ^4 ^5Tu, Haoxin; Zhao, Huan; Song, Yahui; Zafar, Mehtab; Meng, Ruijie; Roychoudhury, Abhik. "Agentic Verification of Software Systems". FSE 2026, arXiv:2511.17330. arxiv.org/...2511.17330
- ^1 ^2 ^3Sun, Yican; Shi, Chengwei; Lyu, Hangzhou; Xiong, Yingfei. "On Reasoning-Centric LLM-based Automated Theorem Proving". arXiv:2604.19558, 2026. arxiv.org/...2604.19558
- ^1 ^2Coquand, Thierry; Huet, Gérard. "The calculus of constructions". Information and Computation 76(2-3), 1988. doi.org/...0890-5401(88)90005-3
- ^math-comp. "odd-order: The formal proof of the Odd Order Theorem". GitHub, accessed 2026-11-18. github.com/...odd-order
- ^1 ^2rocq-prover. "Rocq 9.3.0". GitHub release, 2026-09-19. github.com/...V9.3.0
Improve this article
Add missing citations, update stale details, or write a clearer explanation. Anyone can edit: changes go live when you publish, and every edit is checked by an editor.
2 revisions · v2 · 3,239 words · full history
Fact-checks are independent of edits: a reviewer re-verifies the article against its sources and stamps the date. How we verify
Research and drafting on this wiki are AI-assisted, under named human editorial standards. How AI is used here
Reviewer note: Independent fact-check before publication on November 18, 2026: 96 claims checked against 31 cited and independent sources; 1 material and 4 minor corrections applied before publication.
Cite this page: AI Wiki. "Coq." aiwiki.ai, updated 18 Nov 2026, fact-checked 18 Nov 2026. CC BY 4.0. https://aiwiki.ai/wiki/coq
