|
Le cours a lieu en salle 1004, le lundi de 12h45 à 15h45 à partir du 5 décembre 2022.
Il est nécessaire d'apporter un ordinateur portable sur lequel Coq est installé pour les travaux pratiques. Nous recommandons l'installation de la Plateforme Coq
Il est souhaité (mais non exigé) un niveau de pratique de Coq minimal. Pour cela, il est conseillé de suivre *une* des méthodes introductives citées plus bas (ou bien le début pour les plus elaborées).
L’objectif principal de ce cours est de développer la maîtrise de l’assistant à la
preuve Coq, ainsi que les connaissances théoriques indispensables à la bonne compréhension
et au bon emploi du formalisme implanté. Cette partie théorique donnera
un aperçu de la problématique de la recherche en Théorie des Types.
Le point essentiel, qui fait la particularité de Coq, est la notion générale de type inductif, qui
est un ingrédient quasiment indispensable dans la plupart des modélisations, que ce soit
dans le cas de structures algébriques abstraites ou de structures de données concrètes.
Le corps principal de ce cours est formé de 5 séances de 3h abordant les sujets suivants:
Rappels et mise à niveau (2 séances): lambda-calcul, types dépendents, isomorphisme de Curry-Howard, Calcul des Constructions.
Introduction au Calcul des Constructions Inductives et au système Coq. Du calcul des constructions pur aux constructions inductives.
Les spécificités du Calcul des Constructions Inductives : égalité de Leibniz, arbres à branchement infini, inductifs mutuels, inductifs imbriqués. Théorie des définitions inductives: contrainte de positivité stricte, restrictions d'élimination, types singletons, définition par point-fixe.
Modélisation de structures mathematiques, de structures de données, constructions monadiques. Utilisation de structures canoniques et de typeclasses. Liens entre une structure abstraite et ses représentations.
Le module se terminera avec 3 séances qui traiteront de points qui pourront être pris dans la liste suivante:
Réalisabilité, extraction de programmes à partir de preuves.
Programmation fonctionnelle : récursion structurelle versus accessibilité, fonctions partielles, définitions co-inductives.
Calcul efficace: réflexion calculatoire, certification d'algorithmes efficaces.
Modèles du Calcul des Constructions. Résultats d'indépendance.
Programmation par types dépendants, filtrage dépendant.
Théorie des types homotopique.
Chaque séance se composera d'une moitié enseignement magistral et d'une moitié de travaux pratiques sur machine.
Examen écrit, durée 3h.
1 Exercice en Coq à préparer individuellement, à partir de la moitié du cours. Cet exercice consistera à implanter des définitions ou prouver des lemmes (remettre le fichier source), et expliquer les choix de modélisation ou difficultés rencontrées (document PDF).
Français de préférence mais le cours pourra être fait en anglais suivant demande.
Polycopié “Assistants de Preuves” (PDF, HTML). Attention, ce polycopié est lié à une version antérieure du cours : il ne couvre ainsi pas la totalité de ce qui sera abordé mais traite aussi de sujets qui ne sont pas au programme de cette année.
Cette section se remplira cours après cours...
- Programmation
- un langage fonctionnel (Ocaml, Haskell, ...)
- Langages
- typage (systèmes de types élémentaires, inférence de
type à la ML)
- Logique
- calcul propositionnel, logique du premier ordre,
systèmes de preuves en déduction naturelle
- Calculabilité
- lambda-calcul pur
(syntaxe, alpha-conversion, beta-réduction, confluence, normalisation)
- Mathématique
- ordres bien fondés
Méthodes d'introduction à Coq:
B. C. Pierce, C. Casinghino, M. Gaboardi, M. Greenberg, C. Hriţcu, V. Sjöberg, B. Yorgey. Software Foundations (Volume 1).
-
Y. Bertot, P. Castéran. Interactive Theorem Proving and Program Development, Coq'Art: The Calculus of Inductive Constructions.
Texts in Theoretical Computer Science. An EATCS Series (2004), Springer.
Une version française est librement disponible ici.
Autres documents liés au cours:
B. Nordström, K. Petersson, J. Smith. Programming in Martin-Löf's Type Theory, Clarendon Press, Oxford (1990).
-
-
Matthieu Sozeau, Chargé de Recherche Inria Rennes-Bretagne Atlantique
Yannick Forster, Post-doctorant Inria Rennes-Bretagne Atlantique
Théo Winterhalter, Chargé de Recherche Inria Saclay
|