Trace-Guided Inductive Synthesis of Recursive Functional Programs
Yongwei Yuan, Arjun Radhakrishna, Roopsha Samanta
Abstract
We propose a novel trace-guided approach to tackle the challenges of ambiguity and generalization in synthesis of recursive functional programs from input-output examples. Our approach augments the search space of programs with recursion traces consisting of recursive subcalls of the programs. Our method is based on a new version space algebra (VSA) for succinct representation and efficient manipulation of pairs of recursion traces and programs that are consistent with each other. We have implemented this approach in a tool called SyRup and evaluated it on benchmarks from prior work. Our evaluation demonstrates that SyRup not only requires fewer examples to achieve a certain success rate than existing synthesizers, but is also less sensitive to the quality of the examples.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
7 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Relational Synthesis of Recursive Programs via Constraint Annotated Tree Automata cites Bottom-up synthesis of recursive functional programs using angelic execution
- Relational Synthesis of Recursive Programs via Constraint Annotated Tree Automata cites Cyclic program synthesis
- Relational Synthesis of Recursive Programs via Constraint Annotated Tree Automata cites Recursion synthesis with unrealizability witnesses
- Programming By Scaffolded Demonstration with Perpend cites Bottom-up synthesis of recursive functional programs using angelic execution
- Programming By Scaffolded Demonstration with Perpend cites Recursive Program Synthesis using Paramorphisms
- Bottom-up synthesis of recursive functional programs using angelic execution cites Combining the top-down propagation and bottom-up enumeration for inductive program synthesis
- Bottom-up synthesis of recursive functional programs using angelic execution cites Cyclic program synthesis
- Recursive Program Synthesis using Paramorphisms cites Bottom-up synthesis of recursive functional programs using angelic execution
- Recursive Program Synthesis using Paramorphisms cites Cyclic program synthesis
- From Batch to Stream: Automatic Generation of Online Algorithms cites Bottom-up synthesis of recursive functional programs using angelic execution
Cited by top-tier papers7
- Recursive Program Synthesis using ParamorphismsQiantan Hong, Alex AikenPLDI 2024 · 7 citations
- Control-Flow Deobfuscation using Trace-Informed Compositional Program SynthesisBenjamin Mariano, Ziteng Wang, Shankara Pailoor, Christian S. Collberg et al.OOPSLA 2024 · 5 citations
- From Batch to Stream: Automatic Generation of Online AlgorithmsZiteng Wang, Shankara Pailoor, Aaryan Prakash, Yuepeng Wang et al.PLDI 2024 · 4 citations
- Relational Synthesis of Recursive Programs via Constraint Annotated Tree AutomataAnders Miltner, Ziteng Wang, Swarat Chaudhuri, Isil DilligCAV 2024 · 2 citations
- Programming By Scaffolded Demonstration with PerpendAngela Bi, Eric Rawn, Justin Lubin, Sarah E. ChasinsCHI 2026 · 2 citations
Builds on8
- Bottom-up synthesis of recursive functional programs using angelic executionAnders Miltner, Adrian Trejo Nuñez, Ana Brendel, Swarat Chaudhuri et al.POPL 2022 · 38 citations
- Combining the top-down propagation and bottom-up enumeration for inductive program synthesisWoosuk LeePOPL 2021 · 34 citations
- Just-in-time learning for bottom-up enumerative synthesisShraddha Barke, Hila Peleg, Nadia PolikarpovaOOPSLA 2020 · 33 citations
- Cyclic program synthesisShachar Itzhaky, Hila Peleg, Nadia Polikarpova, Reuben N. S. Rowe et al.PLDI 2021 · 26 citations
- Recursion synthesis with unrealizability witnessesAzadeh Farzan, Danya Lette, Victor NicoletPLDI 2022 · 19 citations
Related papers
- Inductive Synthesis of Structurally Recursive Functional Programs from Non-recursive ExpressionsWoosuk Lee, Hangyeol ChoPOPL 2023 · 19 citations
- Inductive Program Synthesis via Iterative Forward-Backward Abstract InterpretationYongho Yoon, Woosuk Lee, Kwangkeun YiPLDI 2023 · 15 citations
- Inductive Program Synthesis Guided by Observational Program SimilarityJohn K. Feser, Isil Dillig, Armando Solar-LezamaOOPSLA 2023 · 6 citations
- Tunneling through the Hill: Multi-way Intersection for Version-Space Algebras in Program SynthesisGuanlin Chen, Ruyi Ji, Shuhao Zhang, Yingfei XiongOOPSLA 2025
- Neural Program Synthesis with QueryDi Huang, Rui Zhang, Xing Hu, Xishan Zhang et al.ICLR 2022 · 2 citations
