Coq (logiciel)

Coq est un assistant de preuve utilisant le langage Gallina, développé par l'équipe PI.R2 de l’Inria au sein du laboratoire PPS du CNRS et en partenariat avec l'École polytechnique, le CNAM, l'université Paris Diderot et l'université Paris-Sud (et antérieurement l'École normale supérieure de Lyon).

Coq

CoqIde : l'environnement de développement de Coq.

Informations

Développé par	INRIA, Université Paris Diderot, École polytechnique, Université Paris-Sud, École normale supérieure de Lyon
Première version	1984
Dernière version	8.20.0 (3 septembre 2024)
Dépôt	Coq sur GitHub
État du projet	En développement actif
Écrit en	OCaml et C
Système d'exploitation	Multiplateforme
Langues	Anglais
Type	Assistant de preuve
Politique de distribution	Gratuit et open source
Licence	GNU LGPL 2.1
Site web	coq.inria.fr

Le nom du logiciel (initialement CoC) est particulièrement adéquat car : il est français ; il est fondé sur le calcul des constructions (CoC abrégé en anglais) introduit par Thierry Coquand. Dans la même veine, son langage est Gallina et Coq possède un wiki dédié, baptisé Cocorico!.

En 2013, Coq a été récompensé du Programming Languages Software Award par l'ACM SIGPLAN. Coq a reçu en 2022 le premier prix science ouverte du logiciel libre de la recherche dans la catégorie « scientifique et technique ».

Historique du projet

Au début des années 1980, Gérard Huet lance un projet de fabrication d’un démonstrateur interactif de théorème. Il s'agit d'un assistant de preuve. Thierry Coquand et Gérard Huet conçoivent la logique de Coq et le calcul des constructions. Christine Paulin-Mohring étend cette logique avec une nouvelle construction, les types inductifs et un mécanisme d’extraction qui permet d’obtenir automatiquement un programme zéro défaut à partir d’une preuve.

Caractéristiques du logiciel

Coq est fondé sur le calcul des constructions, une théorie des types d'ordre supérieur, et son langage de spécification est une forme de lambda-calcul typé. Le calcul des constructions utilisé dans Coq comprend directement les constructions inductives, d'où son nom de calcul des constructions inductives (CIC).

Coq a été récemment doté de fonctionnalités d'automatisation croissantes. Citons notamment la tactique lia qui décide l'arithmétique de Presburger, les tactiques field et ring pour manipuler des expressions polynomiales et rationnelles.

Plus particulièrement, Coq permet :

• de manipuler des assertions du calcul ;
• de vérifier mécaniquement des preuves de ces assertions ;
• d'aider à la recherche de preuves formelles ;
• de synthétiser des programmes certifiés à partir de preuves constructives de leurs spécifications.

C'est un logiciel libre distribué selon les termes de la licence GNU LGPL.

Parmi les grands succès de Coq, on peut citer :

• le théorème des quatre couleurs, dont une démonstration complètement mécanisée a été terminée en 2004 par Georges Gonthier et Benjamin Werner ;
• le théorème de Feit-Thompson, dont une preuve a été terminée par Georges Gonthier et son équipe en septembre 2012 après six ans d'efforts ;
• CompCert, un compilateur optimisant pour le langage C qui est en grande partie programmé et prouvé en Coq ;
• la démonstration inédite, par une équipe réunie autour de Tristan Stérin, que le castor affairé à 5 états s'exécute en 47 176 870 étapes.

Éléments du langage

Coq utilise la correspondance de Curry-Howard. La preuve d'une proposition est vue comme un programme dont le type est cette proposition. Pour définir un programme ou une preuve, il faut :

• soit l'écrire dans le langage Gallina, proche du langage de programmation fonctionnelle OCaml ;
• soit déclarer son type (ou la proposition que l'on veut démontrer). Le langage Ltac permet alors de définir cette preuve/programme par chaînage arrière, de façon interactive. Cette méthode est privilégiée pour les preuves mathématiques car Coq est alors capable de deviner certaines étapes intermédiaires. Des procédures entièrement automatiques existent pour certains fragments de logique ou d'arithmétique.

Diverses fonctionnalités permettent par ailleurs de définir un programme en Gallina en y laissant des trous correspondant à des preuves à fournir, et ensuite compléter ces trous à l'aide du prouveur interactif.

Il est aussi possible d'utiliser SSReflect à la place de Ltac. Autrefois développé séparément, il est maintenant inclus par défaut dans Coq.

Exemples de programmes

• La fonction factorielle (avec Gallina) :

Require Import Nat.

Fixpoint factorielle n :=
  match n with
  | 0 => 1
  | S p => n * factorielle p
  end.

• La fonction factorielle (avec Ltac) :

Require Import Nat.

Definition factorielle (n : nat) : nat.
  (* On fait une définition par récurrence *)
  induction n.
  - (* Si l'argument est 0, on retourne 1 *)
    exact 1.
  - (* Si l'argument de la forme (S n), on retourne un produit *)
    apply Nat.mul.
    + (* 1er facteur du produit : le successeur de n *)
      exact (S n).
    + (* 2nd facteur du produit : valeur de factorielle en n *)
      exact IHn.
  (* On indique que la définition est terminée et que l'on souhaite pouvoir calculer cette fonction. *)
Defined.

Exemple de démonstration (avec Ltac)

• Tout entier naturel est soit pair, soit impair, par récurrence, avec la tactique lia.

Require Import Lia.

Lemma odd_or_ind : forall (n : nat),
    (exists (p : nat), n = 2 * p) \/ (exists (p : nat), n = 1 + 2 * p).
Proof.
  intro n.
  induction n.
  - (* Cas 0 *) left. now exists 0.
  - (* Cas (n + 1) *)
    destruct IHn as [[p Hpair] | [p Himpair]].
    + (* n est pair *)
      right. exists p. auto.
    + (* n est impair *)
      left. exists (S p). lia.
  (* On indique que la preuve est terminée et qu'elle ne sera pas utilisée comme un programme. *)
Qed.

Voir aussi

• Démonstration automatique de théorèmes
• Lean, un assistant de preuve basé sur une théorie des types très voisine de celle de Coq
• Isabelle
• Mizar
• PhoX
• PVS

Liens externes

• (en) Le site du projet Coq
• (en) Le Wiki de Coq
• (en) Compte-rendu de l'équipe-projet PI.R2 qui développe Coq
• (fr) Livre sur coq de Yves Bertot et Pierre Castéran