PLDI 2024
Mon 24 - Fri 28 June 2024 Copenhagen, Denmark
Mon 24 Jun 2024 16:50 - 17:15 at Reykjavik - 4. Verification

Interactive theorem provers, like Isabelle/HOL, Coq and Lean, have expressive languages that allow the formalization of general mathematical objects and proofs. In this context, an important goal is to reduce the time and effort needed to prove theorems. A significant means of achieving this is by improving proof automation. We have implemented an early prototype of proof automation for equational reasoning in Lean by using equality saturation. To achieve this, we need to bridge the gap between Lean’s expression semantics and the syntactically driven e-graphs in equality saturation. This involves handling bound variables, implicit typing, as well as Lean’s definitional equality, which is more general than syntactic equality and involves notions like α-equivalence, β-reduction, and η-reduction. In this extended abstract, we highlight how we attempt to bridge this gap, and which challenges remain to be solved. Notably, while our techniques are partially unsound, the resulting proof automation remains sound by virtue of Lean’s proof checking. This work is actively being developed at github.com/marcusrossel/lean-egg.

Mon 24 Jun

Displayed time zone: Windhoek change

16:00 - 17:40
4. VerificationEGRAPHS at Reykjavik
16:00
25m
Talk
Automated Proof Generation for Associative and Distributive Rewriting with E-Graphs
EGRAPHS
Adrian Lehmann University of Chicago, Ben Caldwell University of Chicago, John Reppy University of Chicago, USA, Robert Rand University of Chicago
Media Attached
16:25
25m
Talk
superVer: Verifying Probabilistic Independence of Systems of Expressions using Equality Saturation
EGRAPHS
Alexander Treff University of Lübeck, Pajam Pauls University of Lübeck, Maximilian Orlt TU Darmstadt, Marc Gourjon Hamburg University of Technology and NXP Semiconductors Germany GmbH
Media Attached
16:50
25m
Talk
Bridging Syntax and Semantics of Lean Expressions in E-Graphs
EGRAPHS
Marcus Rossel Technische Universität Dresden, Andrés Goens University of Amsterdam
Pre-print Media Attached
17:15
25m
Talk
Disequalities in E-Graphs: An Experiment
EGRAPHS
George Zakhour University of St. Gallen, Pascal Weisenburger University of St. Gallen, Guido Salvaneschi University of St. Gallen
Pre-print Media Attached