Eliminating Dependent Pattern-Matching in Coq

Cyprien Mangin 1
1 PI.R2 - Design, study and implementation of languages for proofs and programs
PPS - Preuves, Programmes et Systèmes, Inria Paris-Rocquencourt, UPD7 - Université Paris Diderot - Paris 7, CNRS - Centre National de la Recherche Scientifique : UMR7126
Abstract : Coq [1] is a proof assistant which relies on the Curry-Howard isomorphism to construct certified proofs. Proving a theorem is the same thing as providing a term which inhabits a type corresponding to this theorem. In order to trust Coq, it is enough to trust its kernel, which is intentionally kept small enough for a motivated reader to understand and, hopefully, trust it. This approach can have some drawbacks, as high-level constructs have to be translated down to simpler constructs, by the user or by some part of code external to the kernel. For example, writing dependent pattern-matching in Coq can be complicated. Simpifying this task is one of the purposes of the Equations [2] plugin. Given a high-level specification of a function, which can use dependent pattern-matching and complex recursion schemes, it will compile it to pure Coq terms. Equations is the result of the work of Matthieu Sozeau[10], largely based on the research of Goguen et al[7]. This internship revolves around Equations as a tool to benchmark, improve and adapt to new settings. This in turn involves the study of dependent pattern-matching. Research problem The initial goal of this internship was to rewrite a part of Equations, in order to better control the use of the axiom K during the compilation phase. This axiom states that to prove a property depending on a proof of equality, it is enough to consider the case where this proof is the reflexivity. Equivalently, it says that any proof of equality is propositionally equal to the reflexivity. While it is useful in some cases, and even provable for a lot of types, it can be harmful when working in some contexts, like Homotopy Type Theory[12] – abbreviated HoTT. Another problem is that, as an axiom, it will block any computation in Coq that involves it.
Type de document :
Mémoires d'étudiants -- Hal-inria+
Programming Languages [cs.PL]. 2015
Liste complète des métadonnées

Contributeur : Matthieu Sozeau <>
Soumis le : mardi 5 janvier 2016 - 13:56:25
Dernière modification le : mardi 11 octobre 2016 - 14:41:07
Document(s) archivé(s) le : jeudi 7 avril 2016 - 15:20:32



  • HAL Id : hal-01250855, version 1




Cyprien Mangin. Eliminating Dependent Pattern-Matching in Coq. Programming Languages [cs.PL]. 2015. <hal-01250855>



Consultations de
la notice


Téléchargements du document