Eliminating Dependent Pattern-Matching in Coq
Résumé
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.
Domaines
Langage de programmation [cs.PL]
Loading...