Equality Saturation as a Tactic for Proof Assistants
Tue 14 Jun 2022 23:30 - 23:45 at Toucan - Thinking Alike
Rewrites are an essential component of proof assistants. Term rewrite systems are well-studied methods to deal with these kinds of rewrites in a formal setting. A limitation of arbitrary term rewrite systems is the destructive nature of rewrites. In contrast, in Egraphs, applying a rewrite also keeps the previous representative. In a sense, this applies the rewrite in both directions. The main idea of this talk is using equality saturation in proof assistants as a powerful tactic, i.e. a meta-program to partially automate the task of finding proofs. We will discuss the limitations of Egraph-based rewrites and our proposed solutions to these. We do this using the Lean proof assistant and the egg framework, considering examples from group theory.
Tue 14 JunDisplayed time zone: Pacific Time (US & Canada) change
10:30 - 12:00 | |||
10:30 15mTalk | Logging an Egg: Datalog on E-Graphs EGRAPHS Philip Zucker Draper Laboratory Pre-print Media Attached | ||
10:45 15mTalk | Chasing an egg EGRAPHS Yihong Zhang University of Washington Pre-print | ||
11:00 15mTalk | ECTAs: E-Graphs Better (at Encoding) EGRAPHS James Koppel Massachusetts Institute of Technology, USA, Zheng Guo University of California, San Diego, Edsko de Vries Well-Typed LLP, Armando Solar-Lezama Massachusetts Institute of Technology, Nadia Polikarpova University of California at San Diego | ||
11:15 15mTalk | E-Graphs, VSAs, and Tree Automata: a Rosetta StoneVirtual EGRAPHS Yisu Remy Wang University of Washington, James Koppel Massachusetts Institute of Technology, USA, Altan Haan OctoML, Josh Pollock MIT CSAIL Link to publication Pre-print | ||
11:30 15mTalk | Equality Saturation as a Tactic for Proof Assistants EGRAPHS | ||
11:45 15mTalk | Towards Optimising Certified Programs by Proof Rewriting EGRAPHS | ||
22:30 - 00:00 | |||
22:30 15mTalk | Logging an Egg: Datalog on E-Graphs EGRAPHS Philip Zucker Draper Laboratory Pre-print Media Attached | ||
22:45 15mTalk | Chasing an egg EGRAPHS Yihong Zhang University of Washington Pre-print | ||
23:00 15mTalk | ECTAs: E-Graphs Better (at Encoding) EGRAPHS James Koppel Massachusetts Institute of Technology, USA, Zheng Guo University of California, San Diego, Edsko de Vries Well-Typed LLP, Armando Solar-Lezama Massachusetts Institute of Technology, Nadia Polikarpova University of California at San Diego | ||
23:15 15mTalk | E-Graphs, VSAs, and Tree Automata: a Rosetta StoneVirtual EGRAPHS Yisu Remy Wang University of Washington, James Koppel Massachusetts Institute of Technology, USA, Altan Haan OctoML, Josh Pollock MIT CSAIL Link to publication Pre-print | ||
23:30 15mTalk | Equality Saturation as a Tactic for Proof Assistants EGRAPHS | ||
23:45 15mTalk | Towards Optimising Certified Programs by Proof Rewriting EGRAPHS | ||