# Coq

> Source: https://aiwiki.ai/wiki/coq
> Updated: 2026-11-18
> Fact-checked: 2026-11-18
> Categories: Developer Tools, Mathematics, Programming Languages
> License: CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) - attribute to "AI Wiki (aiwiki.ai)"
> Cite as: AI Wiki. "Coq." aiwiki.ai, 18 Nov 2026. https://aiwiki.ai/wiki/coq
> From AI Wiki (https://aiwiki.ai), the free encyclopedia of artificial intelligence. Reuse freely with attribution.

**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](https://aiwiki.ai/wiki/machine_learning) research on automated theorem proving, from the CoqGym dataset in 2019 to agents built on [large language models](https://aiwiki.ai/wiki/large_language_model) 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].

<figure class="w-56">
<img src="/images/media-2026-11-18-coq-8225ac3f03ed-tile.png" alt="Rocq logo: a dark purple stylised bird head beside the word ROCQ in orange capital letters" width="744" height="254" />
<figcaption>The logo of the Rocq Prover, the name under which Coq has been distributed since version 9.0. Rocq, via <a href="https://commons.wikimedia.org/wiki/File:Rocq_logo.svg">Wikimedia Commons</a>, Public domain.</figcaption>
</figure>

## 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] |

<figure class="embedvideo">
<iframe src="https://www.youtube-nocookie.com/embed/aQ1q2B0GBlU" title="Proof Assistant Assistants: From teaching Rocq to LLM-assisted proofs"></iframe>
<figcaption>"Proof Assistant Assistants: From teaching Rocq to LLM-assisted proofs", video from Institut Henri Poincaré, published January 17, 2026. <a href="https://www.youtube.com/watch?v=aQ1q2B0GBlU">Watch on YouTube</a>.</figcaption>
</figure>

## 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](https://aiwiki.ai/wiki/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](https://aiwiki.ai/wiki/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](https://aiwiki.ai/wiki/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](https://aiwiki.ai/wiki/icml) 2019, packaged 71K proofs from 123 projects as a learning environment and introduced ASTactic, a [deep learning](https://aiwiki.ai/wiki/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](https://aiwiki.ai/wiki/k_nearest_neighbors) solver proved 1.72 times as many theorems as an offline equivalent, and that a [graph neural network](https://aiwiki.ai/wiki/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](https://aiwiki.ai/wiki/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](https://aiwiki.ai/wiki/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](https://aiwiki.ai/wiki/ai_agents) 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](https://aiwiki.ai/wiki/retrieval_augmented_generation) 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].

## See also

- [Lean](https://aiwiki.ai/wiki/lean)
- [Automated theorem proving](https://aiwiki.ai/wiki/automated_theorem_proving)
- [Mathlib](https://aiwiki.ai/wiki/mathlib)
- [PutnamBench](https://aiwiki.ai/wiki/putnambench)
- [Inria](https://aiwiki.ai/wiki/inria)
- [Lambda calculus](https://aiwiki.ai/wiki/lambda_calculus)

## References

1. Rocq Prover. "About The Rocq Prover". rocq-prover.org, accessed 2026-11-18. https://rocq-prover.org/about
2. Rocq Prover. "Rocq Prover and Rocq Platform releases". rocq-prover.org, accessed 2026-11-18. https://rocq-prover.org/releases
3. Rocq Prover. "Early history of Coq". The Rocq Prover 9.0.0 documentation, 2025. https://rocq-prover.org/doc/V9.0.0/refman/history.html
4. Rocq Prover. "Rocq Prover 9.0.0 Release Notes". rocq-prover.org, 2025-03-12. https://rocq-prover.org/releases/9.0.0
5. Rocq Prover. "Typing rules". The Rocq Prover 9.0.0 documentation, 2025. https://rocq-prover.org/doc/V9.0.0/refman/language/cic.html
6. Rocq Prover. "Program extraction". The Rocq Prover 9.0.0 documentation, 2025. https://rocq-prover.org/doc/V9.0.0/refman/addendum/extraction.html
7. Leroy, Xavier. "Formal verification of a realistic compiler". Communications of the ACM 52(7), 2009. https://xavierleroy.org/publi/compcert-CACM.pdf
8. CompCert. "CompCert - Main page". compcert.org, accessed 2026-11-18. https://compcert.org/
9. Knies, Rob. "Theorem Proof Gains Acclaim". Microsoft Research Blog, 2012-10-11. https://www.microsoft.com/en-us/research/blog/theorem-proof-gains-acclaim/
10. coq-community. "fourcolor: Formal proof of the Four Color Theorem". GitHub, accessed 2026-11-18. https://github.com/coq-community/fourcolor
11. 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. https://doi.org/10.1007/978-3-642-39634-2_14
12. mit-plv. "Fiat-Crypto: Synthesizing Correct-by-Construction Code for Cryptographic Primitives". GitHub, accessed 2026-11-18. https://github.com/mit-plv/fiat-crypto
13. Software Foundations. "Software Foundations". University of Pennsylvania, accessed 2026-11-18. https://softwarefoundations.cis.upenn.edu/
14. Yang, Kaiyu; Deng, Jia. "Learning to Prove Theorems via Interacting with Proof Assistants". ICML 2019, arXiv:1905.09381. https://arxiv.org/abs/1905.09381
15. Sanchez-Stern, Alex; Alhessi, Yousef; Saul, Lawrence; Lerner, Sorin. "Generating Correctness Proofs with Neural Networks". MAPL 2020, arXiv:1907.07794. https://arxiv.org/abs/1907.07794
16. Czajka, Łukasz. "CoqHammer". GitHub, accessed 2026-11-18. https://github.com/lukaszcz/coqhammer
17. Czajka, Łukasz; Kaliszyk, Cezary. "Goal Translation for a Hammer for Coq (Extended Abstract)". HaTT 2016, EPTCS 210, arXiv:1606.05946. https://arxiv.org/abs/1606.05946
18. Blaauwbroek, Lasse; Urban, Josef; Geuvers, Herman. "Tactic Learning and Proving for the Coq Proof Assistant". LPAR 2020, EPiC Series in Computing 73, arXiv:2003.09140. https://arxiv.org/abs/2003.09140
19. Blaauwbroek, 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. https://arxiv.org/abs/2401.02949
20. Thakur, Amitayush; Tsoukalas, George; Wen, Yeming; Xin, Jimmy; Chaudhuri, Swarat. "An In-Context Learning Agent for Formal Theorem-Proving". arXiv:2310.04353, 2023. https://arxiv.org/abs/2310.04353
21. Tsoukalas, 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. https://arxiv.org/abs/2407.11214
22. Kozyrev, Andrei; Solovev, Gleb; Khramov, Nikita; Podkopaev, Anton. "CoqPilot, a plugin for LLM-based generation of proofs". ASE 2024 Tool Demonstrations, arXiv:2410.19605. https://arxiv.org/abs/2410.19605
23. Thompson, 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. https://arxiv.org/abs/2412.14063
24. Kasibatla, 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. https://arxiv.org/abs/2410.19940
25. Kozyrev, Andrei; Khramov, Nikita; Solovev, Gleb; Podkopaev, Anton. "RocqStar: Leveraging Similarity-driven Retrieval and Agentic Systems for Rocq generation". arXiv:2505.22846, 2025. https://arxiv.org/abs/2505.22846
26. Tu, Haoxin; Zhao, Huan; Song, Yahui; Zafar, Mehtab; Meng, Ruijie; Roychoudhury, Abhik. "Agentic Verification of Software Systems". FSE 2026, arXiv:2511.17330. https://arxiv.org/abs/2511.17330
27. Sun, Yican; Shi, Chengwei; Lyu, Hangzhou; Xiong, Yingfei. "On Reasoning-Centric LLM-based Automated Theorem Proving". arXiv:2604.19558, 2026. https://arxiv.org/abs/2604.19558
28. Coquand, Thierry; Huet, Gérard. "The calculus of constructions". Information and Computation 76(2-3), 1988. https://doi.org/10.1016/0890-5401(88)90005-3
29. math-comp. "odd-order: The formal proof of the Odd Order Theorem". GitHub, accessed 2026-11-18. https://github.com/math-comp/odd-order
30. rocq-prover. "Rocq 9.3.0". GitHub release, 2026-09-19. https://github.com/rocq-prover/rocq/releases/tag/V9.3.0

