{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T14:45:31Z","timestamp":1776955531498,"version":"3.51.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1911149"],"award-info":[{"award-number":["1911149"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,1,9]]},"abstract":"<jats:p>\n            <jats:italic>Library learning<\/jats:italic>\n            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.\n          <\/jats:p>\n          <jats:p>\n            We propose\n            <jats:italic>library learning modulo theory<\/jats:italic>\n            (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\n            <jats:italic>e-graph anti-unification<\/jats:italic>\n            technique to find common patterns in the corpus more directly and efficiently.\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3571207","type":"journal-article","created":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T21:58:14Z","timestamp":1673474294000},"page":"396-424","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["babble: Learning Better Abstractions with E-Graphs and Anti-unification"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6163-1821","authenticated-orcid":false,"given":"David","family":"Cao","sequence":"first","affiliation":[{"name":"University of California at San Diego, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7432-8488","authenticated-orcid":false,"given":"Rose","family":"Kunkel","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8633-8413","authenticated-orcid":false,"given":"Chandrakana","family":"Nandi","sequence":"additional","affiliation":[{"name":"Certora, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8066-4218","authenticated-orcid":false,"given":"Max","family":"Willsey","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4731-0124","authenticated-orcid":false,"given":"Zachary","family":"Tatlock","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5571-173X","authenticated-orcid":false,"given":"Nadia","family":"Polikarpova","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Matt Bowers. 2022. Compression Benchmark. https:\/\/github.com\/mlb2251\/compression_benchmark \t\t\t\t  Matt Bowers. 2022. Compression Benchmark. https:\/\/github.com\/mlb2251\/compression_benchmark"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571234"},{"key":"e_1_2_1_3_1","volume-title":"Zakharov","author":"Bulychev Peter E.","year":"2010","unstructured":"Peter E. Bulychev , Egor V. Kostylev , and Vladimir A . Zakharov . 2010 . Anti-unification Algorithms and Their Applications in Program Analysis. In Perspectives of Systems Informatics, Amir Pnueli, Irina Virbitskaite, and Andrei Voronkov (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg. 413\u2013423. isbn:978-3-642-11486-1 Peter E. Bulychev, Egor V. Kostylev, and Vladimir A. Zakharov. 2010. Anti-unification Algorithms and Their Applications in Program Analysis. In Perspectives of Systems Informatics, Amir Pnueli, Irina Virbitskaite, and Andrei Voronkov (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 413\u2013423. isbn:978-3-642-11486-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7120897"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13507"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI \u201913)","author":"Dechter Eyal","unstructured":"Eyal Dechter , Jon Malmaud , Ryan P. Adams , and Joshua B. Tenenbaum . 2013. Bootstrap Learning via Modular Concept Discovery . In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI \u201913) . AAAI Press, 1302\u20131309. isbn:9781577356332 Eyal Dechter, Jon Malmaud, Ryan P. Adams, and Joshua B. Tenenbaum. 2013. Bootstrap Learning via Modular Concept Discovery. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI \u201913). AAAI Press, 1302\u20131309. isbn:9781577356332"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523711"},{"key":"e_1_2_1_8_1","volume-title":"Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI","author":"Dumancic Sebastijan","year":"2021","unstructured":"Sebastijan Dumancic , Tias Guns , and Andrew Cropper . 2021. Knowledge Refactoring for Inductive Program Synthesis . In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021 , Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021. AAAI Press , 7271\u20137278. https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/16893 Sebastijan Dumancic, Tias Guns, and Andrew Cropper. 2021. Knowledge Refactoring for Inductive Program Synthesis. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021. AAAI Press, 7271\u20137278. https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/16893"},{"key":"e_1_2_1_9_1","volume-title":"Tenenbaum","author":"Ellis Kevin","year":"2017","unstructured":"Kevin Ellis , Daniel Ritchie , Armando Solar-Lezama , and Joshua B . Tenenbaum . 2017 . Learning to Infer Graphics Programs from Hand-Drawn Images . https:\/\/doi.org\/10.48550\/ARXIV.1707.09627 10.48550\/ARXIV.1707.09627 Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Joshua B. Tenenbaum. 2017. Learning to Infer Graphics Programs from Hand-Drawn Images. https:\/\/doi.org\/10.48550\/ARXIV.1707.09627"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454080"},{"key":"#cr-split#-e_1_2_1_11_1.1","unstructured":"Srinivasan Iyer Alvin Cheung and Luke Zettlemoyer. 2019. Learning Programmatic Idioms for Scalable Semantic Parsing. https:\/\/doi.org\/10.48550\/ARXIV.1904.09086 10.48550\/ARXIV.1904.09086"},{"key":"#cr-split#-e_1_2_1_11_1.2","unstructured":"Srinivasan Iyer Alvin Cheung and Luke Zettlemoyer. 2019. Learning Programmatic Idioms for Scalable Semantic Parsing. https:\/\/doi.org\/10.48550\/ARXIV.1904.09086"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459821"},{"key":"e_1_2_1_13_1","volume-title":"Weld","author":"Lau Tessa","year":"2001","unstructured":"Tessa Lau , Steven A. Wolfman , Pedro Domingos , and Daniel S . Weld . 2001 . Programming By Demonstration Using Version Space Algebra . Tessa Lau, Steven A. Wolfman, Pedro Domingos, and Daniel S. Weld. 2001. Programming By Demonstration Using Version Space Algebra."},{"key":"#cr-split#-e_1_2_1_14_1.1","unstructured":"Miguel L\u00e1zaro-Gredilla Dianhuan Lin J. Swaroop Guntupalli and Dileep George. 2018. Beyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programs. https:\/\/doi.org\/10.48550\/ARXIV.1812.02788 10.48550\/ARXIV.1812.02788"},{"key":"#cr-split#-e_1_2_1_14_1.2","doi-asserted-by":"crossref","unstructured":"Miguel L\u00e1zaro-Gredilla Dianhuan Lin J. Swaroop Guntupalli and Dileep George. 2018. Beyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programs. https:\/\/doi.org\/10.48550\/ARXIV.1812.02788","DOI":"10.1126\/scirobotics.aav3150"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2013.6606596"},{"key":"e_1_2_1_16_1","volume-title":"Version Spaces: A Candidate Elimination Approach to Rule Learning. In IJCAI.","author":"Mitchell Tom Michael","year":"1977","unstructured":"Tom Michael Mitchell . 1977 . Version Spaces: A Candidate Elimination Approach to Rule Learning. In IJCAI. Tom Michael Mitchell. 1977. Version Spaces: A Candidate Elimination Approach to Rule Learning. In IJCAI."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236794"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386012"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485496"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737959"},{"key":"e_1_2_1_21_1","volume-title":"Lattice Theoretic Properties of Subsumption","author":"Plotkin Gordon","unstructured":"Gordon Plotkin . 1970. Lattice Theoretic Properties of Subsumption . Edinburgh University , Department of Machine Intelligence and Perception. https:\/\/books.google.com\/books?id=2p09cgAACAAJ Gordon Plotkin. 1970. Lattice Theoretic Properties of Subsumption. Edinburgh University, Department of Machine Intelligence and Perception. https:\/\/books.google.com\/books?id=2p09cgAACAAJ"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Mohammad Raza Natasa Milic-Frayling and Sumit Gulwani. 2014. Programming by Example using Least General Generalizations. AAAI - Association for the Advancement of Artificial Intelligence. https:\/\/www.microsoft.com\/en-us\/research\/publication\/programming-by-example-using-least-general-generalizations\/ \t\t\t\t  Mohammad Raza Natasa Milic-Frayling and Sumit Gulwani. 2014. Programming by Example using Least General Generalizations. AAAI - Association for the Advancement of Artificial Intelligence. https:\/\/www.microsoft.com\/en-us\/research\/publication\/programming-by-example-using-least-general-generalizations\/","DOI":"10.1609\/aaai.v28i1.8744"},{"key":"e_1_2_1_23_1","unstructured":"John C. Reynolds. 1969. Transformational systems and the algebraic structure of atomic formulas. \t\t\t\t  John C. Reynolds. 1969. Transformational systems and the algebraic structure of atomic formulas."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO53902.2022.9741256"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2017.44"},{"key":"#cr-split#-e_1_2_1_26_1.1","unstructured":"Gopal Sharma Rishabh Goyal Difan Liu Evangelos Kalogerakis and Subhransu Maji. 2017. CSGNet: Neural Shape Parser for Constructive Solid Geometry. https:\/\/doi.org\/10.48550\/ARXIV.1712.08290 10.48550\/ARXIV.1712.08290"},{"key":"#cr-split#-e_1_2_1_26_1.2","doi-asserted-by":"crossref","unstructured":"Gopal Sharma Rishabh Goyal Difan Liu Evangelos Kalogerakis and Subhransu Maji. 2017. CSGNet: Neural Shape Parser for Constructive Solid Geometry. https:\/\/doi.org\/10.48550\/ARXIV.1712.08290","DOI":"10.1109\/CVPR.2018.00578"},{"key":"e_1_2_1_27_1","volume-title":"Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alch\u00e9-Buc","author":"Shin Eui Chul","year":"2019","unstructured":"Eui Chul Shin , Miltiadis Allamanis , Marc Brockschmidt , and Alex Polozov . 2019. Program Synthesis and Semantic Parsing with Learned Code Idioms . In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alch\u00e9-Buc , E. Fox, and R. Garnett (Eds.). 32, Curran Associates, Inc. . https:\/\/proceedings.neurips.cc\/paper\/ 2019 \/file\/cff34ad343b069ea6920464ad17d4bcf-Paper.pdf Eui Chul Shin, Miltiadis Allamanis, Marc Brockschmidt, and Alex Polozov. 2019. Program Synthesis and Semantic Parsing with Learned Code Idioms. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.). 32, Curran Associates, Inc.. https:\/\/proceedings.neurips.cc\/paper\/2019\/file\/cff34ad343b069ea6920464ad17d4bcf-Paper.pdf"},{"key":"e_1_2_1_28_1","volume-title":"Theory Exploration Powered by Deductive Synthesis","author":"Singher Eytan","unstructured":"Eytan Singher and Shachar Itzhaky . 2021. Theory Exploration Powered by Deductive Synthesis . In Computer Aided Verification, Alexandra Silva and K. Rustan M. Leino (Eds.). Springer International Publishing , Cham . 125\u2013148. isbn:978-3-030-81688-9 Eytan Singher and Shachar Itzhaky. 2021. Theory Exploration Powered by Deductive Synthesis. In Computer Aided Verification, Alexandra Silva and K. Rustan M. Leino (Eds.). Springer International Publishing, Cham. 125\u2013148. isbn:978-3-030-81688-9"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 2005 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD \u201905)","author":"Stiff G.","unstructured":"G. Stiff and F. Vahid . 2005. New Decompilation Techniques for Binary-Level Co-Processor Generation . In Proceedings of the 2005 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD \u201905) . IEEE Computer Society, USA. 547\u2013554. isbn:078039254X G. Stiff and F. Vahid. 2005. New Decompilation Techniques for Binary-Level Co-Processor Generation. In Proceedings of the 2005 IEEE\/ACM International Conference on Computer-Aided Design (ICCAD \u201905). IEEE Computer Society, USA. 547\u2013554. isbn:078039254X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/384281.808217"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1594834.1480915"},{"key":"#cr-split#-e_1_2_1_32_1.1","unstructured":"Yonglong Tian Andrew Luo Xingyuan Sun Kevin Ellis William T. Freeman Joshua B. Tenenbaum and Jiajun Wu. 2019. Learning to Infer and Execute 3D Shape Programs. https:\/\/doi.org\/10.48550\/ARXIV.1901.02875 10.48550\/ARXIV.1901.02875"},{"key":"#cr-split#-e_1_2_1_32_1.2","unstructured":"Yonglong Tian Andrew Luo Xingyuan Sun Kevin Ellis William T. Freeman Joshua B. Tenenbaum and Jiajun Wu. 2019. Learning to Infer and Execute 3D Shape Programs. https:\/\/doi.org\/10.48550\/ARXIV.1901.02875"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446707"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the Annual Meeting of the Cognitive Science Society. 43","author":"Wang Haoliang","unstructured":"Haoliang Wang , Nadia Polikarpova , and Judith E. Fan . 2021. Learning part-based abstractions for visual object concepts . In Proceedings of the Annual Meeting of the Cognitive Science Society. 43 , https:\/\/escholarship.org\/uc\/item\/9009w415 Haoliang Wang, Nadia Polikarpova, and Judith E. Fan. 2021. Learning part-based abstractions for visual object concepts. In Proceedings of the Annual Meeting of the Cognitive Science Society. 43, https:\/\/escholarship.org\/uc\/item\/9009w415"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407799"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"#cr-split#-e_1_2_1_37_1.1","unstructured":"Catherine Wong Kevin Ellis Joshua B. Tenenbaum and Jacob Andreas. 2021. Leveraging Language to Learn Program Abstractions and Search Heuristics. https:\/\/doi.org\/10.48550\/ARXIV.2106.11053 10.48550\/ARXIV.2106.11053"},{"key":"#cr-split#-e_1_2_1_37_1.2","unstructured":"Catherine Wong Kevin Ellis Joshua B. Tenenbaum and Jacob Andreas. 2021. Leveraging Language to Learn Program Abstractions and Search Heuristics. https:\/\/doi.org\/10.48550\/ARXIV.2106.11053"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Annual Meeting of the Cognitive Science Society.","author":"Wong Catherine","unstructured":"Catherine Wong , William P. McCarthy , Gabriel Grand , Yoni Friedman , Joshua B. Tenenbaum , Jacob Andreas , Robert D. Hawkins , and Judith E. Fan . 2022. Identifying concept libraries from language about object structure . In Proceedings of the Annual Meeting of the Cognitive Science Society. Catherine Wong, William P. McCarthy, Gabriel Grand, Yoni Friedman, Joshua B. Tenenbaum, Jacob Andreas, Robert D. Hawkins, and Judith E. Fan. 2022. Identifying concept libraries from language about object structure. In Proceedings of the Annual Meeting of the Cognitive Science Society."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356518"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of Machine Learning and Systems, A. Smola, A. Dimakis, and I. Stoica (Eds.). 3, 255\u2013268","author":"Yang Yichen","year":"2021","unstructured":"Yichen Yang , Phitchaya Phothilimthana , Yisu Wang , Max Willsey , Sudip Roy , and Jacques Pienaar . 2021 . Equality Saturation for Tensor Graph Superoptimization . In Proceedings of Machine Learning and Systems, A. Smola, A. Dimakis, and I. Stoica (Eds.). 3, 255\u2013268 . https:\/\/proceedings.mlsys.org\/paper\/2021\/file\/65ded5353c5ee48d0b7d48c591b8f430-Paper.pdf Yichen Yang, Phitchaya Phothilimthana, Yisu Wang, Max Willsey, Sudip Roy, and Jacques Pienaar. 2021. Equality Saturation for Tensor Graph Superoptimization. In Proceedings of Machine Learning and Systems, A. Smola, A. Dimakis, and I. Stoica (Eds.). 3, 255\u2013268. https:\/\/proceedings.mlsys.org\/paper\/2021\/file\/65ded5353c5ee48d0b7d48c591b8f430-Paper.pdf"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571207","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3571207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:21Z","timestamp":1750183701000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,9]]},"references-count":45,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2023,1,9]]}},"alternative-id":["10.1145\/3571207"],"URL":"https:\/\/doi.org\/10.1145\/3571207","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,9]]},"assertion":[{"value":"2023-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}