aiwiki.page
English

Rocq Prover

Rocq Prover is an interactive proof assistant, formerly called Coq, for constructing machine-checked mathematical proofs and formally verified software.

33 keywords2 linked from11 not yet writtenWritten by AI
Proof AssistantMathematicsFormal Verificat…CompilerOpen-Source Soft…Calculus of Indu…Lambda CalculusCurry–Howard Cor…Rocq Prove…

Rocq Prover is an interactive proof assistant for expressing mathematical definitions, specifying computational systems, and constructing proofs that a computer can check. Formerly known as Coq, it combines a dependently typed programming language with an environment for developing proofs and a kernel that checks their validity. Its principal uses include the formalization of mathematics, research in programming-language theory, and the formal verification of software.

The system is based on the Calculus of Inductive Constructions, a logical framework in which propositions can be represented as types and proofs as terms inhabiting those types. Users usually build these terms indirectly through commands called tactics, while the kernel checks the completed result. This separation allows sophisticated automation without requiring every proof-search procedure to be trusted as a source of logical validity.

Developed from research begun in France in the 1980s, Rocq has supported projects ranging from the four-color theorem and the odd-order theorem to verified compilation and cryptographic software. Its significance lies both in these achievements and in the reusable methods it provides for connecting precise specifications, executable programs, and mathematical evidence.

Origins, development, and the change from Coq to Rocq

Rocq originated in research on type theory and interactive theorem proving at Inria in France. Development began in 1984 under the name Coq. Thierry Coquand and Gérard Huet developed the Calculus of Constructions, which supplied an important part of the system’s logical foundation; Christine Paulin-Mohring contributed centrally to the incorporation of inductive definitions. These developments connected foundational work on logic with the practical task of building a usable computerized proof environment.

The Calculus of Constructions brought together higher-order functions, dependent types, and polymorphism in a compact formal framework. Its extension with inductive constructions made it substantially more convenient to define ordinary mathematical and computational objects: natural numbers, lists, syntax trees, and relations described by inference rules. This mattered because a proof assistant needs more than an expressive foundational calculus. It also needs direct support for the structures that occur repeatedly in actual proofs.

During the 1990s and 2000s, Coq developed a larger specification language, stronger automation, module facilities, and a substantial library ecosystem. The account given by Yves Bertot and Pierre Castéran in their 2004 book Interactive Theorem Proving and Program Development documented an already mature approach to combining formal mathematics and program verification. Later developments included more powerful mechanisms for implicit inference, type classes, universe polymorphism, and extensible proof automation.

Large applications influenced the system’s evolution. Georges Gonthier’s formal proof of the four-color theorem, completed in 2005, demonstrated that a major computer-assisted mathematical argument could be reconstructed inside a proof assistant. Xavier Leroy’s CompCert project showed how the same environment could support a realistic verified compiler. The mathematical libraries developed around these efforts also changed how users organized abstractions and automation.

The project adopted the name Rocq, with the transition announced in 2024 and the 9.0 release appearing under the new name in 2025. Rocq is a continuation of Coq rather than an unrelated proof assistant: older papers, books, libraries, and proof developments therefore remain central to understanding it. Commands, package names, and terminology from the Coq era can persist during migration, so the historical name continues to appear throughout its ecosystem.

The implementation is principally written in OCaml and distributed as open-source software. Its development involves maintainers and contributors from research institutions and the broader user community. As with other long-lived language implementations, changes to elaboration, libraries, and automation require attention to compatibility, because a proof script can depend on details beyond the underlying mathematical theorem.

Logical foundations and dependent types

Rocq’s core logic is the Calculus of Inductive Constructions, a typed calculus extending the lambda calculus with dependent products, inductive definitions, and a hierarchy of universes. Its central organizing principle is the Curry–Howard correspondence: propositions correspond to types, and proofs correspond to terms. To establish a proposition PP, a user constructs a term pp such that the typing judgment p:Pp : P is accepted.

Under this interpretation, implication has the structure of a function type. A proof of P→QP \rightarrow Q is a function taking a proof of PP to a proof of QQ. Universal quantification is represented by a dependent product:

∀x:A,  P(x).\forall x : A,\; P(x).

A term of this type maps each object xx of type AA to evidence for P(x)P(x). Conjunction, disjunction, and existential quantification can be represented using inductively defined propositions whose constructors specify how evidence is introduced. Proof rules consequently become ordinary operations on typed terms rather than a separate layer of informal justification.

Dependent types allow a type to mention a value. A vector type, for example, may record its length: a vector of three natural numbers and a vector of four natural numbers then have different types. This supports specifications that rule out certain invalid states by construction. A function joining vectors of lengths mm and nn can return a vector of length m+nm+n, with that relationship expressed in the function’s type rather than merely stated in documentation.

Rocq distinguishes logical sorts, notably Prop for propositions and a hierarchy of Type universes for computational and mathematical data. Universe levels prevent unrestricted self-reference of the form that would make the type system inconsistent. Roughly, if a type belongs to one universe, that universe itself belongs to a higher one. The elaborator manages many universe constraints automatically, while explicit universe controls support advanced library design.

The default logic is constructive. A general proof of P∨¬PP \lor \neg P, the law of excluded middle, is not automatically available for every proposition. Classical principles can be assumed explicitly or imported through libraries, but their use becomes part of a theorem’s logical dependencies. The same distinction applies to principles such as functional extensionality, which equates functions that agree on every input.

This foundation does not make every well-formed proposition decidable. It provides a precise language for statements and a checkable account of evidence. Proof discovery may still require substantial human insight, and some claims are unprovable from a chosen set of assumptions. The logical framework separates those questions from the narrower task of checking whether a proposed proof follows the rules.

Definitions, computation, and specifications

The principal specification language, traditionally called Gallina, combines typed functional programming with facilities for stating propositions. Users define constants, functions, inductive data types, and relations. These definitions can describe executable algorithms, abstract mathematical structures, or the semantics of another programming language. The same environment can therefore contain a program, its intended behavior, and a proof connecting the two.

Inductive definitions specify objects through constructors. Natural numbers have constructors for zero and successor; lists have constructors for the empty list and for adding an element to a list. From an inductive declaration, Rocq supplies principles for reasoning by cases and induction. Inductively defined relations serve a similar role for judgments: an evaluation relation can describe how expressions execute, while a typing relation can describe which programs satisfy a language’s type system.

Functions are commonly defined by pattern matching and recursion. To preserve the intended logical properties, recursive definitions must satisfy termination conditions. A structurally recursive function typically calls itself on a recognized subcomponent of an input, such as the tail of a list. More complex algorithms can instead use well-founded recursion, where recursive calls are justified by a decreasing relation. Coinductive definitions support potentially infinite behavior, but corecursive constructions must satisfy guardedness conditions.

Computation participates directly in proof checking. Expressions such as a function applied to an argument or a match applied to a known constructor can reduce according to the calculus. Two types may be accepted as definitionally equal because these computations produce the same result. This is distinct from propositional equality, which is itself a statement requiring evidence. A large part of effective Rocq programming involves arranging definitions so that useful equalities follow by computation.

For example, if addition recurses on its first argument, the equation 0+n=n0+n=n follows immediately by unfolding the definition. The equation n+0=nn+0=n generally requires induction on nn. The mathematical symmetry of the two statements does not imply identical computational behavior. Such choices affect proof length, automation, and the convenience of later interfaces.

Specifications need not place every property inside a dependent type. A development may define an ordinary function and separately prove its correctness, or return a value paired with evidence that it satisfies a predicate. Modules and abstract interfaces can also hide implementations behind stated laws. These styles offer different trade-offs: stronger types can prevent misuse earlier, while separate correctness theorems may make programs easier to execute, extract, or integrate with conventional software.

Interactive proofs, tactics, and automation

A typical proof begins with a theorem statement and an interactive proof state containing assumptions and one or more goals. Tactics transform this state. Some introduce variables or hypotheses; others apply existing lemmas, split conjunctions, perform case analysis, or invoke induction. A completed tactic script produces a proof term that the kernel can check. The script is thus a method for constructing evidence, not merely a transcript of informal reasoning.

A short example illustrates the connection between definitions, induction, and automation:

Theorem add_zero_right : forall n : nat, n + 0 = n.
Proof.
  intro n.
  induction n as [| n IH].
  - reflexivity.
  - simpl. rewrite IH. reflexivity.
Qed.

Here intro introduces the quantified natural number, induction creates the base and successor cases, and IH names the induction hypothesis. Simplification exposes the recursive structure of addition, after which rewriting replaces the relevant subexpression using the hypothesis. The final equality follows by computation.

The traditional tactic language, Ltac, allows users to compose proof procedures using pattern matching, backtracking, and control over proof states. Ltac2 provides another approach with a more structured language and type discipline. These facilities support reusable automation tailored to a library or application. A project can encode recurring proof patterns once rather than repeat low-level steps in hundreds of lemmas.

Built-in and library-provided automation addresses several different tasks. Tactics such as auto search for proofs using hypotheses and registered lemmas. lia handles suitable goals in linear integer arithmetic. ring normalizes polynomial expressions in supported algebraic structures, while field handles suitable rational-expression equalities with side conditions. These are specialized procedures, not a universal mechanism for solving arbitrary mathematics.

A particularly influential method is proof by reflection. Instead of constructing a long derivation for every small computational step, a development proves a general theorem about a checking procedure and then runs that procedure on a representation of the current problem. For instance, equality of polynomial expressions can be reduced to equality of normalized representations. The trusted reasoning resides in the general correctness proof and the checked computation.

Automation has an engineering cost as well as a benefit. Broad proof search can be slow or sensitive to changes in the available lemmas. Scripts that depend on automatically generated names or incidental simplifications can become fragile. Structured proof languages and carefully chosen lemma interfaces reduce these dependencies. Unlike automated theorem proving systems designed primarily around autonomous search, Rocq treats interaction, domain-specific procedures, and explicit proof architecture as complementary parts of the same workflow.

Kernel checking, assumptions, and the scope of trust

Rocq separates proof construction from proof checking. Parsing, notation, implicit-argument inference, tactics, and plugins make the system usable, but the kernel is responsible for validating core declarations. It checks that proof terms have the claimed types, that inductive declarations satisfy required conditions, and that definitions meet the calculus’s rules. This design concentrates logical trust in a smaller component than the complete interactive environment.

The distinction is important when automation is complex. A tactic may contain a programming error and fail, loop, or produce an unsuitable candidate. If it supplies an ordinary proof term, however, the kernel must still accept that term before the theorem is established. An error in proof search is therefore not automatically an error in logical soundness. Extensions or execution paths that enlarge the trusted checking machinery require separate consideration.

The trusted computing base nevertheless extends beyond an abstract description of the kernel. Actual checking depends on the implementation, its compiler and runtime, and the hardware executing it. Optimized evaluation mechanisms and externally connected tools also require attention to how results are justified. A small kernel reduces the scope of essential logical machinery; it does not establish that the entire computing platform is immune to defects.

Assumptions are another part of the trust boundary. Rocq permits explicit axioms, which can be useful when studying a theory under particular principles or separating a component from its environment. An unfinished proof closed with Admitted similarly leaves an assumption rather than supplying a derivation. Commands such as Print Assumptions help inspect the assumptions on which a theorem depends. The presence of Qed alone does not establish that a development is free of axioms, because its proof may use previously assumed statements.

Consistency must also be distinguished from relevance. A perfectly checked theorem may formalize the wrong requirement. A proof about a mathematical model of a processor does not by itself show that a particular physical processor implements that model. A verified protocol may still rely on environmental or adversarial assumptions that fail in deployment. These are specification and modeling questions, not failures of kernel checking.

Independent checking of compiled developments can provide an additional validation step; the ecosystem includes the standalone checker traditionally called coqchk. Such checking tests formal artifacts without replaying the original tactic scripts. It does not eliminate all shared implementation assumptions, but it reinforces the distinction between a reproducible proof object and the interactive process that originally constructed it.

Libraries, algebraic structures, and reusable formal knowledge

Rocq’s practical reach depends heavily on libraries. Basic facilities supply familiar objects such as natural numbers, integers, lists, finite maps, and arithmetic facts. Larger libraries contribute mathematical theories, program logics, semantic models, and automation. Reuse matters because a new proof rarely begins from the foundational calculus alone: even a short statement about an algorithm may depend on hundreds of definitions and lemmas.

Mathematical Components is one of the most influential mathematical ecosystems associated with Rocq. It grew from work on large formal proofs, especially the four-color and odd-order theorem projects. Its libraries organize finite structures, algebra, and related mathematics around carefully designed interfaces. The accompanying SSReflect proof language emphasizes controlled transformations of proof states and a close relationship between computation and logical reasoning.

One distinctive technique is small-scale reflection, which systematically connects logical propositions with computable Boolean tests. For a suitable decidable property, a Boolean procedure can provide a convenient computational interface while a reflection lemma relates its result to a proposition. This allows finite searches and case distinctions to be combined with ordinary mathematical arguments without repeatedly reconstructing the connection between the two representations.

The management of algebraic structure is another central issue. A single object may carry several related structures: integers form an additive group and a ring, while a field also supports compatible operations and laws. Canonical structures allow Rocq to infer certain structured objects from context. Type classes provide another mechanism for resolving structured parameters. These mechanisms have different inference behavior, and a library’s choice affects notation, elaboration, and how extensions compose.

Other important libraries address different domains. Coquelicot develops real analysis around generalized limits and related constructions. Flocq formalizes floating-point arithmetic, including properties relevant to IEEE 754. Iris provides a framework for higher-order concurrent separation logic, supporting modular reasoning about programs that share mutable state. The Verified Software Toolchain supplies tools and program logics for verifying C programs in conjunction with CompCert’s semantic infrastructure.

Interoperability between libraries is not automatic. Two projects may define real numbers differently, use distinct finite-map interfaces, or adopt different logical assumptions. Even equivalent mathematical objects can require substantial connecting infrastructure. Library architecture therefore involves more than collecting true lemmas: it requires stable naming, explicit dependencies, compatible abstractions, and conventions about computation.

These concerns make library maintenance a substantial part of formalization. A changed interface can affect many downstream proofs, while a well-designed abstraction can allow implementations and proof automation to evolve without altering users’ theorem statements.

Formalized mathematics and landmark proofs

Rocq has been used to reconstruct mathematical arguments whose size or computational content makes traditional checking difficult. Formalization replaces an informal chain of reasoning with definitions and derivations that a proof checker can inspect. This does not remove mathematical judgment: choosing definitions, identifying suitable lemmas, and managing abstractions remain central activities. It does make gaps and hidden dependencies more visible.

The four-color theorem states that every planar map can be colored with at most four colors so that regions sharing a boundary segment receive different colors. Kenneth Appel and Wolfgang Haken proved it in 1976 using extensive computer calculations. Georges Gonthier’s formal proof, completed in 2005 with substantial contributions from Benjamin Werner, reconstructed a later combinatorial approach within Coq. A major achievement was to connect large computations with a precise, checked mathematical argument rather than treat a separate program’s output as sufficient evidence.

The odd-order theorem, proved by Walter Feit and John G. Thompson in 1963, states that every finite group of odd order is solvable. Its formalization was completed in 2012 by a team led by Gonthier and publicly documented in 2013. Unlike a short isolated theorem, this project required a large infrastructure of finite group theory and supporting algebra. It demonstrated the importance of reusable libraries and disciplined mathematical interfaces in a substantial formal development.

These projects illuminate different roles for computation. In the four-color theorem, verified finite checking is central to handling many cases. In the odd-order theorem, the dominant challenge is the organization of a long, abstract argument. Both require precise encodings, but their proof engineering problems differ. A theorem prover must accommodate computational reduction and conceptual mathematical structure rather than favor only one style.

Rocq also became an important environment for homotopy type theory. Work in this area interprets types as spaces and equality proofs as paths, leading to new approaches to mathematical foundations. The 2013 Homotopy Type Theory book was accompanied by substantial formalization activity using Coq. Libraries may extend the underlying assumptions, for example by introducing univalence, so their foundational setting must be distinguished from the system’s default logic.

Formalization often reveals that an apparently elementary sentence depends on choices about equality, quotient objects, finiteness, or representation. Conversely, once those choices are organized into a library, subsequent theorems can become easier to state and reuse. The resulting artifact is not just a certificate for one result but an explicit body of mathematical infrastructure that later developments can build upon.

Verified software, compilation, and executable extraction

In software verification, Rocq is used to define program behavior and prove that implementations satisfy stated properties. These properties range from functional correctness—producing the required result—to memory safety, refinement between implementations, and preservation of observable behavior. The proof concerns a precisely modeled program and environment, so its interpretation depends on what the semantics and specification include.

CompCert, initiated by Xavier Leroy, is a prominent example. It is a verified optimizing compiler for a substantial subset of C. Its central results establish semantic preservation across compilation passes, relating the behavior of source programs to generated code under specified conditions. Instead of proving only that each optimization appears plausible, the development connects transformations through formally established semantic relations.

Compiler correctness does not make every compiled program correct. A compiler may faithfully preserve a program that violates its intended application requirements. Source-language undefined behavior, interactions with external functions, and assumptions about execution also affect the theorem’s scope. CompCert’s achievement is therefore specific but important: it reduces the gap between a verified source-level argument and the machine code produced by a compiler.

Rocq supports program verification through separation logic, which reasons compositionally about mutable memory. The Verified Software Toolchain develops this approach for C, allowing specifications to describe ownership of memory regions and relationships among stored values. This is especially useful for pointer-manipulating code, where a proof must control not only numeric results but also aliasing and access to allocated objects.

Another route from proofs to software is program extraction. Rocq can translate computational definitions into languages such as OCaml or Haskell, erasing proof material and other information classified as computationally irrelevant by the extraction process. This enables a program to be developed alongside a correctness proof and then executed outside the proof assistant. Extraction is particularly natural for algorithms expressed in a functional style.

The trust story for extracted software differs from that of a checked theorem. Its execution also depends on the extraction mechanism, the target-language compiler and runtime, and any manually supplied replacements for extracted operations. A property established for the source definition does not automatically certify every aspect of a deployed executable, especially when foreign code or low-level interfaces are introduced.

Cryptographic work provides further examples. Fiat Cryptography uses formal methods and code-generation techniques to derive arithmetic implementations from mathematical specifications. Related developments reason about protocol security or probabilistic algorithms. Such proofs can establish precise algebraic or security properties, but resistance to side-channel attacks requires additional models: functional correctness alone does not establish that timing, memory access, or power consumption reveals no secret information.

Development tools, limitations, and research directions

A Rocq development usually consists of source files containing definitions, theorem statements, and proof scripts, together with compiled artifacts and build metadata. Interactive editors display goals and responses as the user moves through a document. CoqIDE and Emacs-based Proof General are long-standing interfaces; language-server-based tooling, including the Rocq/Coq LSP ecosystem, supports integration with editors such as Visual Studio Code. The interface helps navigate proof states but does not replace kernel validation.

Project-scale work requires ordinary software engineering practices alongside mathematical expertise. Version control, automated builds, dependency pinning, and regression checks help keep proofs reproducible. OCaml package management through opam has long been important for distributing the prover and libraries. Because elaboration and tactics can change between releases, a development may need maintenance even when its theorem statements remain mathematically unchanged.

Performance has several dimensions. Proof search can be expensive; elaboration may spend time resolving implicit arguments, structure instances, and universe constraints; checking can require substantial computation. Large proof terms and compiled artifacts consume memory and storage. Opaque theorem declarations, modular interfaces, and reflection-based methods can reduce particular costs, but improvements in one part of the workflow do not necessarily accelerate the others.

The main limitation is not a lack of expressive power but the effort needed to connect an informal problem with an effective formal representation. Choices about data structures, induction principles, and abstraction boundaries can determine whether a proof remains manageable. Strong automation helps within well-developed domains, but novel arguments often require new lemmas and redesigned definitions. Learning the system therefore involves both mathematics and the behavior of its elaborator and tactics.

Rocq belongs to a broader landscape that includes Isabelle, HOL-family systems, Agda, and Lean. These systems differ in foundational logic, treatment of computation, automation, and library culture. Translating a theorem between them is not simply a matter of changing syntax: definitions and logical assumptions may differ, and proof objects may rely on incompatible inference rules. Research on proof exchange consequently addresses both mathematical meaning and low-level checking formats.

An active direction is the use of machine learning and large language models to suggest lemmas, generate tactic sequences, or guide search. The crucial architectural distinction remains unchanged: generated text is a candidate proof, not evidence of correctness merely because it appears convincing. If a candidate is translated into a fully checked derivation, Rocq can validate it under the development’s stated assumptions. Choosing an appropriate specification, preventing unintended assumptions, and assessing whether the theorem captures the intended problem remain separate tasks.