Trace-Guided Inductive Synthesis of Recursive Functional Programs
summary
A method augments program search with explicit recursion traces and a new version space algebra that represents pairs of traces and programs under angelic semantics, and it ships as the synthesizer SyRup. On 43 benchmarks from prior work SyRup returns programs that generalize with fewer examples and shows far lower sensitivity to example quality than prior tools; the approach builds a compact DAG of trace-program pairs and the implementation empirically improves generalization while keeping synthesis time comparable.
AI-written summary · about
chapters (14)
- 0:00Program synthesis intro
- 0:25Trace-guided inductive synthesis
- 1:11Synthesis problem inputs
- 3:01Recursive synthesis challenges
- 4:22Solution with recursion traces
- 5:03Recursion traces matter
- 7:11Using recursion traces in synthesis
- 8:38Building recursion trace graph
- 9:43Version space algebra
- 10:26Consistent pairs in Syrup
- 11:08Evaluating Syrup generalizability
- 12:32Performance across examples
- 13:16Conclusion and future
- 13:40Q&A
related talks
25mRecursive Program Synthesis using Paramorphisms
33mProgram Synthesis Using Example Propagation
40mSuperfusion: Eliminating Intermediate Data Structures via Inductive Synthesis
29mIntroduction to Recursion Schemes
35mUsing the Design Recipe in Theory of Computation
22mCan Logic Programming Be Liberated from Predicates and Backtracking? (Lightning talk)
16mDigging for Fold: Synthesis-Aided API Discovery for Haskell
47mSemi-Automated Direction-Driven Functional Conversion