New tool to compute with inductive in Coq

De nouveaux outils pour calculer avec des inductifs en Coq

Pierre Boutillier (1, 2)

1 PI.R2 - Design, study and implementation of languages for proofs and programs
2 PPS - Preuves, Programmes et Systèmes

The dependently typed lambda-calculus with algebraic datastructures is a programming language with very few primitives but a huge expressivity. The Coq proof assistant is built over one variant of this language, the CIC. Its semantics is extremely clear but it is verbose. Therefore, users do not write programs directly in CIC. Instead, Coq provides tools to elaborate programs incrementally using higher level constructions. Especially, mixing algebraic and dependent types increases the power and the difficulty of case analysis. Each case has a different type depending of the type of the constructor. Some cases are even impossible because of typing. These type casts and impossibility witnesses are explicit in CIC terms but they can be built mechanically. This thesis gives an algorithm to achieve this automation. As far as feedback from the system is concerned, interaction with human asks for a way to compute Coq programs without making their syntactical length explode. This thesis propose a new abstract machine designed for this purpose. Fixpoints provide a convenient way to deal with recursive datastructures. Nevertheless, ensuring their computation does not diverge on any entry is a challenging issue. It is tackled by the last chapter of this thesis.

En ajoutant au lambda-calcul des structures de données algébriques, des types dépendants et un système de modules, on obtient un langage de programmation avec peu de primitives mais une très grande expressivité. L'assistant de preuve Coq s'appuie sur un tel langage (le CIC) à la sémantique particulièrement claire. L'utilisateur n'écrit pas directement de programme en CIC car cela est ardu et fastidieux. Coq propose un environnement de programmation qui facilite la tâche en permettant d'écrire des programmes incrémentalement grâce à des constructions de haut niveau plus concises. Typiquement, les types dépendants imposent des contraintes fortes sur les données. Une analyse de cas peut n'avoir à traiter qu'un sous-ensemble des constructeurs d'un type algébrique, les autres étant impossibles par typage. Le type attendu dans chacun des cas varie en fonction du constructeur considéré. L'impossibilité de cas et les transformations de type doivent être explicitement écrites dans les termes de Coq. Pourtant, ce traitement est mécanisable et cette thèse décrit un algorithme pour réaliser cette automatisation. Par ailleurs, il est nécessaire à l'interaction avec l'utilisateur de calculer des programmes du CIC sans faire exploser la taille syntaxique de la forme réduite. Cette thèse présente une machine abstraite conçu dans ce but. Enfin, les points fixes permettent une manipulation aisée des structure de données récursives. En contrepartie, il faut s'assurer que leur exécution termine systématiquement. Cette question sensible fait l'objet du dernier chapitre de cette thèse.

Mots clés: Coq (software); Proof assistant; Induction (logic); Pattern-matching

Mots clés: Coq (logiciel); Assistants de preuve; Langages de programmation -- Sémantique; Induction (logique); filtrage

Domaines: Langage de programmation [cs.PL]

Pierre Boutillier. De nouveaux outils pour calculer avec des inductifs en Coq. Langage de programmation [cs.PL]. Université Paris-Diderot - Paris VII, 2014. Français. ⟨NNT : ⟩. ⟨tel-01054723⟩