{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:07:24Z","timestamp":1767928044675,"version":"3.49.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2022,8,29]],"date-time":"2022-08-29T00:00:00Z","timestamp":1661731200000},"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":["1943623"],"award-info":[{"award-number":["1943623"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"AFRL\/RIKE","award":["FA8750-20-C-0208"],"award-info":[{"award-number":["FA8750-20-C-0208"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,8,29]]},"abstract":"<jats:p>Many problem domains, including program synthesis and rewrite-based optimization, require searching astronomically large spaces of programs. Existing approaches often rely on building specialized data structures\u2014version-space algebras, finite tree automata, or e-graphs\u2014to compactly represent such spaces. At their core, all these data structures exploit independence of subterms; as a result, they cannot efficiently represent more complex program spaces, where the choices of subterms are entangled.<\/jats:p>\n          <jats:p>\n            We introduce\n            <jats:italic>equality-constrained tree automata<\/jats:italic>\n            (ECTAs), a new data structure, designed to compactly represent large spaces of programs with entangled subterms. We present efficient algorithms for extracting programs from ECTAs, implemented in a performant Haskell library, ecta. Using the ecta library, we construct Hectare, a type-driven program synthesizer for Haskell. Hectare significantly outperforms a state-of-the-art synthesizer Hoogle+\u2014providing an average speedup of 8\u00d7\u2014despite its implementation being an order of magnitude smaller.\n          <\/jats:p>","DOI":"10.1145\/3547622","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T19:39:26Z","timestamp":1661974766000},"page":"23-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Searching entangled program spaces"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3948-6904","authenticated-orcid":false,"given":"James","family":"Koppel","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0927-4011","authenticated-orcid":false,"given":"Zheng","family":"Guo","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3979-3397","authenticated-orcid":false,"given":"Edsko","family":"de Vries","sequence":"additional","affiliation":[{"name":"Well-Typed LLP, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7604-8252","authenticated-orcid":false,"given":"Armando","family":"Solar-Lezama","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, 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":[[2022,8,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133906"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/174652.174655"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.28"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(2:1)2013"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49019-1_11"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55210-3_181"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-59340-3_8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1995.1048"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066102"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009851"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485530"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-004-6246-0"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32033-3_26"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299711.3242760"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371080"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-47166-2_21"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428273"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01692511"},{"key":"e_1_2_1_20_1","unstructured":"James Koppel. 2021. Version Space Algebras are Acyclic Tree Automata. https:\/\/doi.org\/10.48550\/arXiv.2107.12568 arxiv:2107.12568. \t\t\t\t  James Koppel. 2021. Version Space Algebras are Acyclic Tree Automata. https:\/\/doi.org\/10.48550\/arXiv.2107.12568 arxiv:2107.12568."},{"key":"e_1_2_1_21_1","unstructured":"James Koppel Zheng Guo Edsko de Vries Armando Solar-Lezama and Nadia Polikarpova. 2022. Searching Entangled Program Spaces (Extended Version). https:\/\/doi.org\/10.48550\/ARXIV.2206.07828 \t\t\t\t  James Koppel Zheng Guo Edsko de Vries Armando Solar-Lezama and Nadia Polikarpova. 2022. Searching Entangled Program Spaces (Extended Version). https:\/\/doi.org\/10.48550\/ARXIV.2206.07828"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12138"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025671410623"},{"key":"e_1_2_1_24_1","unstructured":"Neil Mitchell. 2004. Hoogle. https:\/\/www.haskell.org\/hoogle\/ \t\t\t\t  Neil Mitchell. 2004. Hoogle. https:\/\/www.haskell.org\/hoogle\/"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386012"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485496"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322198"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217859"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/210376.197409"},{"key":"e_1_2_1_30_1","unstructured":"Joshua Pollock and Altan Haan. 2021. E-Graphs Are Minimal Deterministic Finite Tree Automata (DFTAs) \u00b7 Discussion #104 \u00b7 egraphs-good\/egg. https:\/\/github.com\/egraphs-good\/egg\/discussions\/104 \t\t\t\t  Joshua Pollock and Altan Haan. 2021. E-Graphs Are Minimal Deterministic Finite Tree Automata (DFTAs) \u00b7 Discussion #104 \u00b7 egraphs-good\/egg. https:\/\/github.com\/egraphs-good\/egg\/discussions\/104"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858965.2814310"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386001"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16242-8_41"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480915"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62688-3_47"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2009.07.004"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133886"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158151"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"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\/3547622","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3547622","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3547622","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:43:28Z","timestamp":1750272208000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3547622"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,29]]},"references-count":40,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2022,8,29]]}},"alternative-id":["10.1145\/3547622"],"URL":"https:\/\/doi.org\/10.1145\/3547622","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,29]]},"assertion":[{"value":"2022-08-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}