{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T14:47:17Z","timestamp":1764859637329,"version":"3.41.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2022YFB450190"],"award-info":[{"award-number":["2022YFB450190"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62161146003"],"award-info":[{"award-number":["62161146003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1943623 and 1911149"],"award-info":[{"award-number":["1943623 and 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":[[2024,6,20]]},"abstract":"<jats:p>\n            Intermediate data structures are a common cause of inefficiency in functional programming.\n            <jats:italic toggle=\"yes\">Fusion<\/jats:italic>\n            attempts to eliminate intermediate data structures by combining adjacent data traversals into one; existing fusion techniques, however, are based on predefined rewrite rules and hence are limited in expressiveness.\n          <\/jats:p>\n          <jats:p>\n            In this work we explore a different approach to eliminating intermediate data structures, based on inductive program synthesis. We dub this approach\n            <jats:italic toggle=\"yes\">superfusion<\/jats:italic>\n            (by analogy with\n            <jats:italic toggle=\"yes\">superoptimization<\/jats:italic>\n            , which uses inductive synthesis for program optimization). Starting from a reference program annotated with data structures to be eliminated, superfusion first generates a\n            <jats:italic toggle=\"yes\">sketch<\/jats:italic>\n            where program fragments operating on those data structures are replaced with holes; it then fills the holes with constant-time expressions such that the resulting program is equivalent to the reference. The main technical challenge here is scalability because optimized programs are often complex, making the search space intractably large for naive enumeration. To address this challenge, our key insight is to first synthesize a\n            <jats:italic toggle=\"yes\">ghost function<\/jats:italic>\n            that describes the relationship between the original intermediate data structure and its compressed version; this function, although not used in the final program, serves to decompose the joint sketch filling problem into independent simpler problems for each hole.\n          <\/jats:p>\n          <jats:p>\n            We implement superfusion in a tool called\n            <jats:sc>SuFu<\/jats:sc>\n            and evaluate it on a dataset of 290 tasks collected from prior work on deductive fusion and program restructuring. The results show that SuFu solves 264 out of 290 tasks, exceeding the capabilities of rewriting-based fusion systems and achieving comparable performance with specialized approaches to program restructuring on their respective domains.\n          <\/jats:p>","DOI":"10.1145\/3656415","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"939-964","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Superfusion: Eliminating Intermediate Data Structures via Inductive Synthesis"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0150-8629","authenticated-orcid":false,"given":"Ruyi","family":"Ji","sequence":"first","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-6392-3096","authenticated-orcid":false,"given":"Yuwei","family":"Zhao","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"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, San Diego, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8991-747X","authenticated-orcid":false,"given":"Yingfei","family":"Xiong","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9034-205X","authenticated-orcid":false,"given":"Zhenjiang","family":"Hu","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1087939"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.260.9"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54577-5_18"},{"key":"e_1_3_1_5_1","volume-title":"In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017","author":"Balog Matej","year":"2017","unstructured":"Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. 2017. DeepCoder: Learning to Write Programs. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. https:\/\/openreview.net\/forum?id=ByldLrqlx"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/32.2.122"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/248932"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38856-9_8"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837666"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/141471.141494"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291199"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/121973.773545"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523726"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062355"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81685-8_39"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454089"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062382"},{"key":"e_1_3_1_19_1","unstructured":"Maarten M. Fokkinga. 1992. Law and order in algorithmics. Univ. Twente."},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/165180.165214"},{"key":"e_1_3_1_21_1","first-page":"25","volume-title":"In Selected papers from the 3rd Scottish Functional Programming Workshop (SFP01), University of Stirling, Bridge of Allan, Scotland, August 22nd to 24th, 2001 (Trends in Functional Programming, Vol. 3)","author":"Hamilton Geoff W.","year":"2001","unstructured":"Geoff W. Hamilton. 2001. Extending Higher-Order Deforestation: Transforming Programs to Eliminate Even More Trees. In Selected papers from the 3rd Scottish Functional Programming Workshop (SFP01), University of Stirling, Bridge of Allan, Scotland, August 22nd to 24th, 2001 (Trends in Functional Programming, Vol. 3), Kevin Hammond and Sharon Curtis (Eds.). Intellect, 25\u201336."},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3002812"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24276-2_2"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81685-8_37"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/232627.232637"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/258948.258964"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22308-2_13"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786805.2803189"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485544"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","unstructured":"Ruyi Ji Yuwei Zhao Nadia Polikarpova Yingfei Xiong and Zhenjiang Hu. 2024a. Artifact for PLDI'24: Superfusion:Eliminating Intermediate Data Structures via Inductive Synthesis. https:\/\/doi.org\/10.5281\/zenodo.10951760 10.5281\/zenodo.10951760","DOI":"10.5281\/zenodo.10951760"},{"key":"e_1_3_1_31_1","unstructured":"Ruyi Ji Yuwei Zhao Yingfei Xiong Di Wang Lu Zhang and Zhenjiang Hu. 2024b. Decomposition-Based Synthesis for Applying Divide-and-Conquer-Like Algorithmic Paradigms. ACM Transactions on Programming Languages and Systems (2024)."},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498722"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314602"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2013.6679396"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.9"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571209"},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3408991"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/36177.36194"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/3540543961_7"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498682"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250752"},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632870"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594339"},{"key":"e_1_3_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872362.2872387"},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498709"},{"key":"e_1_3_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048076"},{"key":"e_1_3_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379022.1375602"},{"key":"e_1_3_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133900"},{"key":"e_1_3_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451150"},{"key":"e_1_3_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814278"},{"key":"e_1_3_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54013-4_22"},{"key":"e_1_3_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10672-9_3"},{"key":"e_1_3_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_3_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314592"},{"key":"e_1_3_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/224164.224221"},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509578.2509586"},{"key":"e_1_3_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594340"},{"key":"e_1_3_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19027-9_23"},{"key":"e_1_3_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441617"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656415","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656415","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:41:45Z","timestamp":1751661705000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656415"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":58,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656415"],"URL":"https:\/\/doi.org\/10.1145\/3656415","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}