Mechanisation of computation for identity types in Martin-Löf type theory
Thibaut Benjamin (University of Cambridge)
November 25, 2024
Martin-Löf type theory is a powerful theory that is at the foundation of modern proof assistants such as Coq, Lean, Agda. It provides a unifying framework to formalise mathematics and software. Although this framework is powerful enough to formalise and verify very complex software (like for instance the CompCert C compiler, formally verified in Coq), its practical use is constrained by the large proof effort it requires, rendering the adoption of such tools slower. Various techniques are considered to simplify and streamline the use of proof-assistants. For instance, identity types, that represent equalities have a very rich and complex structure, and it is common to ignore that structure by adding a principle called Uniqueness of Identity Proofs (UIP). This axiom states that any two identity proofs are equal thus enforcing in a way proof irrelevance for equality. Another example is the so-called univalent axiom (originally coming from a connection with homotopy theory) that for computer scientists mean that the formalisation can be done in a way that is independent of the choice of datatypes, as long as those datatypes encode the same information. This is not only a powerful reasoning principle that allows one to reason on simple but inefficient datatypes and transport the results to finicky but efficient ones, it also reflects the very common computer science practice of hiding the implementation of datatypes under an API to make the programs more modular. Unfortunately, UIP and the univalence axiom are incompatible. In this talk, I will present a workflow that I am designing to handle and automate complex computation on identity types, in an effort to reduce the need for UIP and render practical the use of the univalence axiom. I will in particular show the implementation of this workflow as a Coq plugin, that uses a secondary tool called CaTT, which is specifically designed to handle the algebraic structure of identity types, called higher groupoid.