{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T16:35:31Z","timestamp":1755794131283,"version":"3.44.0"},"reference-count":29,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2025,8,15]],"date-time":"2025-08-15T00:00:00Z","timestamp":1755216000000},"content-version":"unspecified","delay-in-days":226,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title>\n\t  <jats:p>We present a novel approach to synthesizing recursive functional programs from input\u2013output examples. Synthesizing a recursive function is challenging because recursive subexpressions should be constructed while the target function has not been fully defined yet. We address this challenge by using a new technique we call block-based pruning. A block refers to a recursion- and conditional-free expression (i.e., straight-line code) that yields an output from a particular input. We first synthesize as many blocks as possible for each input\u2013output example, and then we explore the space of recursive programs, pruning candidates that are inconsistent with the blocks. Our method is based on an efficient version space learning, thereby effectively dealing with a possibly enormous number of blocks. In addition, we present a method that uses sampled input\u2013output behaviors of library functions to enable a goal-directed search for a recursive program using the library. We have implemented our approach in a system called <jats:sc>Trio<\/jats:sc> and evaluated it on synthesis tasks from prior work and on new tasks. Our experiments show that <jats:sc>Trio<\/jats:sc> significantly outperforms prior work.<\/jats:p>","DOI":"10.1017\/s0956796825100063","type":"journal-article","created":{"date-parts":[[2025,8,15]],"date-time":"2025-08-15T12:02:49Z","timestamp":1755259369000},"update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Inductive synthesis of structurally recursive functional programs from non-recursive expressions"],"prefix":"10.1017","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5869-9473","authenticated-orcid":false,"given":"HANGYEOL","family":"CHO","sequence":"first","affiliation":[{"name":"Hanyang University"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1884-619X","authenticated-orcid":false,"given":"WOOSUK","family":"LEE","sequence":"additional","affiliation":[{"name":"Hanyang University"}]}],"member":"56","published-online":{"date-parts":[[2025,8,15]]},"reference":[{"key":"S0956796825100063_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2738007"},{"key":"S0956796825100063_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454087"},{"key":"S0956796825100063_ref26","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2017.44"},{"key":"S0956796825100063_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/3571263"},{"key":"S0956796825100063_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02768-1_13"},{"key":"S0956796825100063_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-65633-0_3"},{"key":"S0956796825100063_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_67"},{"key":"S0956796825100063_ref8","doi-asserted-by":"publisher","DOI":"10.1561\/2500000010"},{"key":"S0956796825100063_ref29","doi-asserted-by":"publisher","DOI":"10.1145\/3591255"},{"key":"S0956796825100063_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509555"},{"key":"S0956796825100063_ref22","unstructured":"Osera, P.-M. (2015) Program Synthesis with Types. PhD Dissertation, Computer and Information Science, University of Pennsylvania, Philadelphia, Pennsylvania."},{"key":"S0956796825100063_ref19","doi-asserted-by":"publisher","DOI":"10.1145\/3498682"},{"key":"S0956796825100063_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454080"},{"key":"S0956796825100063_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"S0956796825100063_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814310"},{"key":"S0956796825100063_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837629"},{"key":"S0956796825100063_ref28","first-page":"1","article-title":"Program synthesis using abstraction refinement","volume":"2","author":"Wang","year":"2017","journal-title":"Proc. ACM Program. Lang"},{"key":"S0956796825100063_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/3290327"},{"key":"S0956796825100063_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81685-8_39"},{"key":"S0956796825100063_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/3656381"},{"key":"S0956796825100063_ref12","first-page":"429","article-title":"Inductive synthesis of functional programs: An explanation based generalization approach","volume":"7","author":"Kitzelmann","year":"2006","journal-title":"J. Mach. Learn. Res."},{"key":"S0956796825100063_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908093"},{"key":"S0956796825100063_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594333"},{"key":"S0956796825100063_ref11","unstructured":"Kini, D. & Gulwani, S. (2015) Flashnormalize: Programming by examples for text normalization. In Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI\u201915), Buenos Aires, Argentina. AAAI Press, Palo Alto, CA, USA, pp. 776\u2013783."},{"key":"S0956796825100063_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/3408991"},{"key":"S0956796825100063_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-934613-12-5.50028-8"},{"key":"S0956796825100063_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737977"},{"key":"S0956796825100063_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/3434335"},{"key":"S0956796825100063_ref17","volume-title":"Bachelor\u2019s thesis","author":"Lubin","year":"2020"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796825100063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,15]],"date-time":"2025-08-15T12:02:50Z","timestamp":1755259370000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796825100063\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":29,"alternative-id":["S0956796825100063"],"URL":"https:\/\/doi.org\/10.1017\/s0956796825100063","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}],"article-number":"e17"}}