Proof assistants like Coq, Lean, or HOL4 rely heavily on stateful meta-programs called scripts to assemble proofs. Unlike pen-and-paper proofs, proof scripts only describe the steps to take (induct on x, apply a theorem, …), not the states that these steps lead to; as a result, plain proof scripts are essentially incomprehensible without the assistance of an interactive user interface able to run the script and show the corresponding proof states.
Until now, the standard process to communicate a proof without forcing readers to execute its script was to manually copy-paste intermediate proof states into the script, as source code comments — a tedious and error-prone exercise. Additional prose (such as for a book or tutorial) was likewise embedded in comments, preserving executability at the cost of a mediocre text-editing experience.
This paper describes a new approach to the development and dissemination of literate proof scripts, with a focus on the Coq proof assistant. Specifically, we describe two contributions: a compiler that interleaves Coq’s output with the original proof script to produce interactive webpages that are complete, self-contained presentations of Coq proofs; and a new literate programming toolkit that allows authors to switch seamlessly between prose- and code-oriented views of the same sources, by translating back and forth between reStructuredText documents and literate Coq source files. In combination, these tools offer a new way to write, communicate, and preserve proofs, combining the flexibility of procedural proof scripts and the intelligibility of declarative proofs.
I’m a PhD candidate at MIT, working in Adam Chlipala’s lab. My research focuses on proof assistants, extensible compilers, and programming languages; my broader interests include hardware design languages, optimization, databases, and type theory. I work on end-to-end verified compilation pipelines from high-level specifications to assembly language, verified compilers and fast simulation for rule-based hardware design languages with EHRs, and Coq tooling.
And I’m applying for faculty positions this year!
Fri 22 OctDisplayed time zone: Central Time (US & Canada) change
13:50 - 15:10
|Untangling mechanized proofs
Clément Pit-Claudel MIT CSAILLink to publication
|Python 3 Types in the Wild: A Tale of Two Type Systems
Ingkarat Rak-amnouykit Rensselaer Polytechnic Institute, Daniel McCrevan Rensselaer Polytechnic Institute, Ana Milanova Rensselaer Polytechnic Institute, Martin Hirzel IBM Research, Julian Dolby IBM Research, USALink to publication Pre-print
|Discussion, Questions and Answers