EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

babble: Learning Better Abstractions with E-Graphs and Anti-unification

David Cao, Rose Kunkel, Chandrakana Nandi, Max Willsey, Zachary Tatlock, Nadia Polikarpova

Proceedings of the ACM on Programming Languages · 09.01.2023 · 7 (POPL) · 396-424

DOI: 10.1145/3571207 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 11.01.2023. Verfasst von David Cao und 5 weiteren Autor:innen. Die Arbeit wurde bisher 37-mal zitiert (Crossref) und nennt 45 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • National Science Foundation

Zitieren

APA

Cao, D., Kunkel, R., Nandi, C., Willsey, M., Tatlock, Z., & Polikarpova, N. (2023). babble: Learning Better Abstractions with E-Graphs and Anti-unification. Proceedings of the ACM on Programming Languages, 7(POPL), 396-424. https://doi.org/10.1145/3571207

Vancouver

Cao D, Kunkel R, Nandi C, Willsey M, Tatlock Z, Polikarpova N. babble: Learning Better Abstractions with E-Graphs and Anti-unification. Proceedings of the ACM on Programming Languages. 2023;7(POPL):396-424. doi:10.1145/3571207

BibTeX
@article{Cao2023,
  author = {Cao, David and Kunkel, Rose and Nandi, Chandrakana and Willsey, Max and Tatlock, Zachary and Polikarpova, Nadia},
  title = {babble: Learning Better Abstractions with E-Graphs and Anti-unification},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2023},
  volume = {7},
  number = {POPL},
  pages = {396--424},
  doi = {10.1145/3571207}
}
Kostenlos starten →