PLDI 2023 (series) / EGRAPHS 2023 (series) / E-Graph Research, Applications, Practices, and Human-factors Symposium /
Optimizing Beta-Reduction in E-Graphs
Sun 18 Jun 2023 16:00 - 16:20 at Magnolia 18 - EGRAPHS: Binding & Extraction
Applications of e-graphs to program synthesis have recently seen a rise in popularity. The efficient equality saturation workload that they enable makes them an ideal tool for program search and optimization. Unfortunately, straightforward approaches to dealing with beta-reduction in a complete manner cause equality saturation to be overrun with additional terms, making the process slow and often intractable. Yet some of us would still like to have complete (or close to complete) beta-reduction in the languages on which we perform equality saturation. We give an overview of approaches to dealing with beta-reduction and propose a fast and simple method that keeps the e-graph size down by culling unnecessary terms.
Slides (Optimizing beta reduction in e-graphs.pdf) | 1.46MiB |
Sun 18 JunDisplayed time zone: Eastern Time (US & Canada) change
Sun 18 Jun
Displayed time zone: Eastern Time (US & Canada) change
16:00 - 17:50 | |||
16:00 20mTalk | Optimizing Beta-Reduction in E-Graphs EGRAPHS Emmanuel Anaya Gonzalez UCSD, Cole Kurashige UCSD, Aditya Giridharan UCSD, Nadia Polikarpova University of California at San Diego File Attached | ||
16:20 20mTalk | Improving Term Extraction with Acyclic Constraints EGRAPHS Deyuan (Mike) He Princeton University, Haichen Dong Princeton University, Sharad Malik Princeton University, Aarti Gupta Princeton University File Attached | ||
16:40 20mTalk | E-graph Extraction Using ZDDs EGRAPHS Eli Rosenthal Google |