{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T15:40:33Z","timestamp":1782834033975,"version":"3.54.5"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T00:00:00Z","timestamp":1704153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-2123654 and CCF-2236233"],"award-info":[{"award-number":["CCF-2123654 and CCF-2236233"]}],"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":[[2024,1,2]]},"abstract":"<jats:p>\n            We propose a new synthesis algorithm that can\n            <jats:italic toggle=\"yes\">efficiently<\/jats:italic>\n            search programs with\n            <jats:italic toggle=\"yes\">local<\/jats:italic>\n            variables (e.g., those introduced by lambdas). Prior bottom-up synthesis algorithms are not able to evaluate programs with\n            <jats:italic toggle=\"yes\">free local variables<\/jats:italic>\n            , and therefore cannot effectively reduce the search space of such programs (e.g., using standard observational equivalence reduction techniques), making synthesis slow. Our algorithm can reduce the space of programs with local variables. The key idea, dubbed\n            <jats:italic toggle=\"yes\">lifted interpretation<\/jats:italic>\n            , is to lift up the program interpretation process, from evaluating one program at a time to simultaneously evaluating all programs from a grammar. Lifted interpretation provides a mechanism to systematically enumerate all binding contexts for local variables, thereby enabling us to evaluate and reduce the space of programs with local variables. Our ideas are instantiated in the domain of web automation. The resulting tool,\n            <jats:sc>Arborist<\/jats:sc>\n            , can automate a significantly broader range of challenging tasks more efficiently than state-of-the-art techniques including\n            <jats:sc>WebRobot<\/jats:sc>\n            and Helena.\n          <\/jats:p>","DOI":"10.1145\/3632894","type":"journal-article","created":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T20:48:51Z","timestamp":1704487731000},"page":"1540-1568","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Efficient Bottom-Up Synthesis for Programs with Local Variables"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-6860-039X","authenticated-orcid":false,"given":"Xiang","family":"Li","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6404-1098","authenticated-orcid":false,"given":"Xiangyu","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2757-2768","authenticated-orcid":false,"given":"Rui","family":"Dong","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-5928-4396","authenticated-orcid":false,"given":"Yihong","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1836-0202","authenticated-orcid":false,"given":"Xinyu","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_67"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984020"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740908.2742849"},{"key":"e_1_3_1_5_1","unstructured":"Sarah Elizabeth Chasins. 2019. Democratizing Web Automation: Programming for Social Scientists and Other Domain Experts. Ph.D. Dissertation. UC Berkeley."},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3242587.3242661"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454047"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385988"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586183.3606720"},{"key":"e_1_3_1_10_1","unstructured":"Hubert Comon Max Dauchet R\u00e9mi Gilleron Florent Jacquemard Denis Lugiez Christof L\u00f6ding Sophie Tison and Marc Tommasi. 2008. Tree automata techniques and applications."},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523711"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737977"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454046"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993505"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409732"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10003-2_79"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3464432.3464437"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547622"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/VL\/HCC51201.2021.9576476"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025671410623"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434335"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1357054.1357323"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","unstructured":"Xiang Li Xiangyu Zhou Rui Dong Yihong Zhang and Xinyu Wang. 2023a. Efficient Bottom-Up Synthesis for Programs with Local Variables (Artifact). https:\/\/zenodo.org\/records\/10023528 (2023). https:\/\/doi.org\/10.5281\/zenodo.10023528 10.5281\/zenodo.10023528","DOI":"10.5281\/zenodo.10023528"},{"key":"e_1_3_1_25_1","unstructured":"Xiang Li Xiangyu Zhou Rui Dong Yihong Zhang and Xinyu Wang. 2023b. Efficient Bottom-Up Synthesis for Programs with Local Variables (Extended Version). https:\/\/arxiv.org\/abs\/2311.03705 (2023)."},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/168080.168086"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502650.1502667"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240624.1240767"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498682"},{"key":"e_1_3_1_30_1","unstructured":"Dan Hua Mo. 1990. Learning Text Editing Procedures from Examples. (1990)."},{"key":"e_1_3_1_31_1","unstructured":"OpenAI. 2022. Introducing ChatGPT. https:\/\/openai.com\/blog\/chatgpt."},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428227"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872362.2872387"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3526113.3545691"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586183.3606822"},{"key":"e_1_3_1_36_1","volume-title":"arXiv preprint","author":"Si Chenglei","year":"2022","unstructured":"Chenglei Si, Zhe Gan, Zhengyuan Yang, Shuohang Wang, Jianfeng Wang, Jordan Boyd-Graber, and Lijuan Wang. 2022. Prompting gpt-3 to be reliable. arXiv preprint arXiv:2210.09150 (2022)."},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908102"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594340"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462174"},{"key":"e_1_3_1_40_1","unstructured":"UiPath. 2022. UiPath Webinar Slides. https:\/\/start.uipath.com\/rs\/995-XLT-886\/images\/StudioX_Webinar.pdf."},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96145-3_22"},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158151"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133886"},{"key":"e_1_3_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276525"},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_3_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177735"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632894","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632894","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632894","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:04:43Z","timestamp":1751659483000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632894"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,2]]},"references-count":45,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,2]]}},"alternative-id":["10.1145\/3632894"],"URL":"https:\/\/doi.org\/10.1145\/3632894","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,2]]},"assertion":[{"value":"2024-01-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}