babble: Learning Better Abstractions with E-Graphs and Anti-unification
Open Access
- 9 January 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 7 (POPL) , 396-424
Abstract
Library learning compresses a given corpus of programs by extracting common structure from the corpus into reusable library functions. Prior work on library learning suffers from two limitations that prevent it from scaling to larger, more complex inputs. First, it explores too many candidate library functions that are not useful for compression. Second, it is not robust to syntactic variation in the input. We propose library learning modulo theory (LLMT), a new library learning algorithm that additionally takes as input an equational theory for a given problem domain. LLMT uses e-graphs and equality saturation to compactly represent the space of programs equivalent modulo the theory, and uses a novel e-graph anti-unification technique to find common patterns in the corpus more directly and efficiently. We implemented LLMT in a tool named babble. Our evaluation shows that babble achieves better compression orders of magnitude faster than the state of the art. We also provide a qualitative evaluation showing that babble learns reusable functions on inputs previously out of reach for library learning.Keywords
All Related Versions
Funding Information
- National Science Foundation (1911149)
This publication has 21 references indexed in Scilit:
- Synthesizing structured CAD models with equality saturation and inverse transformations2020
- Carpentry compilerACM Transactions on Graphics, 2019
- Beyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programsScience Robotics, 2019
- Functional programming for compiling and decompiling computer-aided designProceedings of the ACM on Programming Languages, 2018
- CSGNet: Neural Shape Parser for Constructive Solid Geometry2018
- Learning Syntactic Program Transformations from Examples2017
- Automatically improving accuracy for floating point expressionsACM SIGPLAN Notices, 2015
- Lase: Locating and applying systematic edits by learning from examples2013
- Equality saturationACM SIGPLAN Notices, 2009
- An improvement of trace scheduling for global microcode compactionACM SIGMICRO Newsletter, 1984