{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:56:55Z","timestamp":1776106615417,"version":"3.50.1"},"reference-count":50,"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\/"}],"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            We show that synthesizing recursive functional programs using a class of primitive recursive combinators is both simpler and solves more benchmarks from the literature than previously proposed approaches. Our method synthesizes\n            <jats:italic toggle=\"yes\">paramorphisms,<\/jats:italic>\n            a class of programs that includes the most common recursive programming patterns on algebraic data types. The crux of our approach is to split the synthesis problem into two parts: a multi-hole\n            <jats:italic toggle=\"yes\">template<\/jats:italic>\n            that fixes the recursive structure, and a search for non-recursive program fragments to fill the template holes.\n          <\/jats:p>","DOI":"10.1145\/3656381","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"102-125","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Recursive Program Synthesis using Paramorphisms"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-2907-0609","authenticated-orcid":false,"given":"Qiantan","family":"Hong","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3723-9555","authenticated-orcid":false,"given":"Alex","family":"Aiken","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11729976_15"},{"key":"e_1_3_1_3_1","doi-asserted-by":"crossref","unstructured":"Alexandros Agapitos Michael O\u2019Neill Ahmed Kattan and Simon M Lucas. 2017. Recursion in tree-based genetic programming. Genetic programming and evolvable machines 18 2 (2017) 149-183.","DOI":"10.1007\/s10710-016-9277-5"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_67"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10762-2_38"},{"key":"e_1_3_1_6_1","doi-asserted-by":"crossref","unstructured":"Rajeev Alur Rastislav Bodik Garvit Juniwal Milo MK Martin Mukund Raghothaman Sanjit A Seshia Rishabh Singh Armando Solar-Lezama Emina Torlak and Abhishek Udupa. 2013. Syntax-guided synthesis. IEEE.","DOI":"10.1109\/FMCAD.2013.6679385"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168906"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1389095.1389330"},{"key":"e_1_3_1_9_1","doi-asserted-by":"crossref","unstructured":"Taylor L Booth and Richard A Thompson. 1973. Applying probability measures to abstract languages. IEEE transactions on Computers 100 5 (1973) 442\u2013450.","DOI":"10.1109\/T-C.1973.223746"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837666"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3242587.3242661"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02768-1_13"},{"key":"e_1_3_1_13_1","doi-asserted-by":"crossref","unstructured":"Yu Feng Ruben Martins Osbert Bastani and Isil Dillig. 2018. Program synthesis using conflict-driven learning. ACM SIGPLANNotices 53 4 (2018) 420\u2013435.","DOI":"10.1145\/3296979.3192382"},{"key":"e_1_3_1_14_1","doi-asserted-by":"crossref","unstructured":"Yu Feng Ruben Martins Jacob Van Geffen Isil Dillig and Swarat Chaudhuri. 2017. Component-based synthesis of table consolidation and transformation tasks from examples. ACM SIGPLANNotices 52 6 (2017) 422\u2013436.","DOI":"10.1145\/3140587.3062351"},{"key":"e_1_3_1_15_1","doi-asserted-by":"crossref","unstructured":"John K Feser Swarat Chaudhuri and Isil Dillig. 2015. Synthesizing data structure transformations from input-output examples. ACM SIGPLANNotices 50 6 (2015) 229\u2013239.","DOI":"10.1145\/2813885.2737977"},{"key":"e_1_3_1_16_1","first-page":"63","volume-title":"Studies in Logic and the Foundations of Mathematics.","author":"Girard. Jean-Yves","year":"1971","unstructured":"Jean-Yves Girard. 1971. Une extension de L\u2019interpretation de g\u00f6del a L\u2019analyse, et son application a L\u2019elimination des coupures dans L\u2019analyse et la theorie des types. In Studies in Logic and the Foundations of Mathematics. Vol. 63. Elsevier, 63\u201392."},{"key":"e_1_3_1_17_1","unstructured":"Jean-Yves Girard. 1972. Interpretation fonctionnelle et Elimination des coupures de l\u2019arithmetique d\u2019ordre superieur. Ph. D. Dissertation. Editeur inconnu."},{"key":"e_1_3_1_18_1","doi-asserted-by":"crossref","unstructured":"Sumit Gulwani. 2011. Automating string processing in spreadsheets using input-output examples. ACM Sigplan Notices 46 1 (2011) 317\u2013330.","DOI":"10.1145\/1925844.1926423"},{"key":"e_1_3_1_19_1","doi-asserted-by":"crossref","unstructured":"W Keith Hastings. 1970. Monte Carlo sampling methods using Markov chains and their applications. (1970).","DOI":"10.2307\/2334940"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332165.3347925"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54577-5_14"},{"key":"e_1_3_1_22_1","first-page":"944","article-title":"Cyclic program synthesis","author":"Itzhaky Shachar","year":"2021","unstructured":"Shachar Itzhaky, Hila Peleg, Nadia Polikarpova, Reuben NS Rowe, and Ilya Sergey. 2021. Cyclic program synthesis. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 944\u2013959.","journal-title":"Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation."},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509555"},{"key":"e_1_3_1_24_1","first-page":"696","article-title":"Adaptive restarts for stochastic synthesis","author":"Koenig R","year":"2021","unstructured":"Jason R Koenig, Oded Padon, and Alex Aiken. 2021. Adaptive restarts for stochastic synthesis. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 696\u2013709.","journal-title":"Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation."},{"key":"e_1_3_1_25_1","doi-asserted-by":"crossref","unstructured":"John R Koza. 1994. Genetic programming as a means for programming computers by natural selection. Statistics and computing 4 2 (1994) 87\u2013112.","DOI":"10.1007\/BF00175355"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571263"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3408991"},{"key":"e_1_3_1_28_1","unstructured":"Simon Marlow et al. 2010. Haskell 2010 language report. Available online http:\/\/www.haskell.org\/(May 2011) (2010)."},{"key":"e_1_3_1_29_1","doi-asserted-by":"crossref","unstructured":"Henry Massalin. 1987. Superoptimizer: A look at the smallest program. ACM SIGARCH Computer Architecture News 15 5 (1987) 122\u2013126.","DOI":"10.1145\/36177.36194"},{"key":"e_1_3_1_30_1","doi-asserted-by":"crossref","unstructured":"Lambert Meertens. 1992. Paramorphisms. Formal aspects ofcomputing 4 (1992) 413\u2013424.","DOI":"10.1007\/BF01211391"},{"key":"e_1_3_1_31_1","doi-asserted-by":"crossref","unstructured":"Erik Meijer Maarten Fokkinga and Ross Paterson. 1991. Functional programming with bananas lenses envelopes and barbed wire. In Conference on functional programming languages and computer architecture. Springer 124\u2013144.","DOI":"10.1007\/3540543961_7"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/549659"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498682"},{"key":"e_1_3_1_34_1","doi-asserted-by":"crossref","unstructured":"Alberto Moraglio Fernando EB Otero Colin G Johnson Simon Thompson and Alex A Freitas. 2012. Evolving recursive programs using non-recursive scaffolding. In 2012 IEEE Congress on Evolutionary Computation. IEEE 1\u20138.","DOI":"10.1109\/CEC.2012.6256545"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICEC.1998.699720"},{"key":"e_1_3_1_36_1","doi-asserted-by":"crossref","unstructured":"Peter-Michael Osera and Steve Zdancewic. 2015. Type-and-example-directed program synthesis. ACM SIGPLANNotices 50 6 (2015) 619\u2013630.","DOI":"10.1145\/2813885.2738007"},{"key":"e_1_3_1_37_1","doi-asserted-by":"crossref","unstructured":"Nadia Polikarpova Ivan Kuraj and Armando Solar-Lezama. 2016. Program synthesis from polymorphic refinement types. ACM SIGPLANNotices 51 6 (2016) 522\u2013538.","DOI":"10.1145\/2980983.2908093"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-06859-7_148"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89275-5_5"},{"key":"e_1_3_1_40_1","doi-asserted-by":"crossref","unstructured":"Eric Schkufza Rahul Sharma and Alex Aiken. 2013. Stochastic superoptimization. ACM SIGARCH Computer Architecture News 41 1 (2013) 305\u2013316.","DOI":"10.1145\/2490301.2451150"},{"key":"e_1_3_1_41_1","first-page":"343","article-title":"Transforming spreadsheet data types using examples","author":"Singh Rishabh","year":"2016","unstructured":"Rishabh Singh and Sumit Gulwani. 2016. Transforming spreadsheet data types using examples. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACTSymposium on Principles of Programming Languages. 343\u2013356.","journal-title":"Proceedings of the 43rd Annual ACM SIGPLAN-SIGACTSymposium on Principles of Programming Languages"},{"key":"e_1_3_1_42_1","doi-asserted-by":"crossref","unstructured":"Armando Solar-Lezama. 2013. Program sketching. International Journal on Software Tools for Technology Transfer 15 5 (2013) 475\u2013495.","DOI":"10.1007\/s10009-012-0249-7"},{"key":"e_1_3_1_43_1","doi-asserted-by":"crossref","unstructured":"Jerry Swan Krzyszt of Krawiec and Zoltan A Kocsis. 2019. Stochastic synthesis of recursive functions made easy with bananas lenses envelopes and barbed wire. Genetic Programming and Evolvable Machines 20 3 (2019) 327\u2013350.","DOI":"10.1007\/s10710-019-09347-3"},{"key":"e_1_3_1_44_1","first-page":"135","article-title":"Growing solver-aided languages with Rosette","author":"Torlak Emina","year":"2013","unstructured":"Emina Torlak and Rastislav Bodik. 2013. Growing solver-aided languages with Rosette. In Proceedings of the 2013 ACM international symposium on New ideas, newparadigms, and reflections on programming & software. 135\u2013152.","journal-title":"Proceedings of the 2013 ACM international symposium on New ideas, newparadigms, and reflections on programming & software."},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062365"},{"key":"e_1_3_1_46_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3371117","article-title":"Visualization by example","volume":"4","author":"Wang Chenglong","year":"2019","unstructured":"Chenglong Wang, Yu Feng, Rastislav Bodik, Alvin Cheung, and Isil Dillig. 2019. Visualization by example. Proceedings of the ACM on Programming Languages 4, POPL (2019), 1\u201328.","journal-title":"Proceedings of the ACM on Programming Languages"},{"key":"e_1_3_1_47_1","first-page":"221","volume-title":"Advances in genetic programming.","author":"Leung Wong Man","year":"1996","unstructured":"Man Leung Wong and Kwong Sak Leung. 1996. Evolving recursive functions for the even-parity problem using genetic programming. In Advances in genetic programming. MIT press, 221\u2013240."},{"key":"e_1_3_1_48_1","doi-asserted-by":"crossref","unstructured":"Navid Yaghmazadeh Christian Klinger Isil Dillig and Swarat Chaudhuri. 2016. Synthesizing transformations on hierarchically structured data. ACM SIGPLAN Notices 51 6 (2016) 508\u2013521.","DOI":"10.1145\/2980983.2908088"},{"key":"e_1_3_1_49_1","doi-asserted-by":"crossref","unstructured":"Tina Yu. 2001. Hierarchical processing for evolving recursive and modular programs using higher-order functions and lambda abstraction. Genetic Programming and Evolvable Machines 2 4 (2001) 345\u2013380.","DOI":"10.1023\/A:1012926821302"},{"key":"e_1_3_1_50_1","unstructured":"Tina Yu and Chris Clack. 1998. Recursion lambda abstraction and genetic programming. Morgan Kaufman."},{"key":"e_1_3_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591255"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656381","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656381","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:44:35Z","timestamp":1751661875000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":50,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656381"],"URL":"https:\/\/doi.org\/10.1145\/3656381","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"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"}}]}}