Skip to Main content Skip to Navigation
Master thesis

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.
Document type :
Master thesis
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Matthieu Sozeau Connect in order to contact the contributor
Submitted on : Tuesday, January 5, 2016 - 1:56:25 PM
Last modification on : Friday, January 21, 2022 - 3:21:30 AM
Long-term archiving on: : Thursday, April 7, 2016 - 3:20:32 PM


  • HAL Id : hal-01250855, version 1



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



Record views


Files downloads