What is Coq?

Handling proofs and programs

Coq implements a program specification and mathematical higher-level language called Gallina that is based on an expressive formal language called the Calculus of Inductive Constructions that itself combines both a higher-order logic and a richly-typed functional programming language. Through a vernacular language of commands, Coq allows:

  • to define functions or predicates, that can be evaluated efficiently;
  • to state mathematical theorems and software specifications;
  • to interactively develop formal proofs of these theorems;
  • to machine-check these proofs by a relatively small certification "kernel";
  • to extract certified programs to languages like OCaml, Haskell or Scheme.

As a proof development system, Coq provides interactive proof methods, decision and semi-decision algorithms, and a tactic language for letting the user define its own proof methods. Connection with external computer algebra system or theorem provers is available.

As a platform for the formalization of mathematics or the development of programs, Coq provides support for high-level notations, implicit contents and various other useful kinds of macros.

The Coq bundle

Coq comes with libraries for efficient arithmetics in N, Z and Q, libraries about lists, finite sets and finite maps, libraries on abstract sets, relations, classical analysis, etc.

Coq is released with:

  • a graphical user interface based on gtk (CoqIDE) (see the chapter of the reference manual about CoqIDE),
  • documentation tools (coqdoc and coq-tex) and a statistics tool (coqwc),
  • dependency and makefile generation tools for Coq (coq_makefile and coqdep),
  • a stand-alone proof verifier (coqchk).

Coq is the result of more than 30 years of research. It started in 1984 from an implementation of the Calculus of Constructions at INRIA-Rocquencourt by Thierry Coquand and GĂ©rard Huet. In 1991, Christine Paulin extended it to the Calculus of Inductive Constructions. All in all, more than 200 people have contributed to the development of Coq. The Coq Team is responsible for the development of Coq and integration of contributions. See credits for a detailed list of contributors over the years, the history and recent changes chapters in the Coq Reference Manual for detailed information about changes in the system or the synthetic who did what table for an overview of the systems contributors.

Coq is written in OCaml. It is distributed under the GNU Lesser General Public Licence Version 2.1 (LGPL).