|
|
Le cours a lieu en salle 1014, le jeudi de 16h15 à 19h15.
Il est nécessaire d'apporter un ordinateur portable sur lequel Coq est installé pour les travaux pratiques (version 8.5 ou plus de préférence). Il est souhaité 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 prinicipal 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 apperç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 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...
Project handout, commented Coq files due the day of written exam.
- Programmation
- un langage fonctionnel (Ocaml)
- 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:
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. -
B. C. Pierce, C. Casinghino, M. Gaboardi, M. Greenberg, C. Hriţcu, V. Sjöberg, B. Yorgey. Software Foundations.
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).
-
-
Annales examens:
Exercices:
Bruno Barras, Chargé de Recherche INRIA Saclay - Île-de-France
Matthieu Sozeau, Chargé de Recherche INRIA Paris
|