Recursive Program Synthesis using Paramorphisms
summary
Claims a synthesis method that fixes recursive shape with multi-hole templates and fills holes by stochastic search for nonrecursive straight-line code, using paramorphisms as the recursion scheme. Cost combines program size and edit-distance to examples; the search is embarrassingly parallel and beats deduction and deterministic bottom-up baselines, solving 55 of 59 benchmarks and inventing factorial from only successor and zero with six examples. Implementation scales with parallelism and consistently finds diverse correct algorithms.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 4:20Synthesis challenges
- 6:23Limitations of approaches
- 7:26Performance results
- 8:10Factorial synthesis
- 11:00Language stratification and paramorphisms
- 13:08Recursion schemes basics
- 14:53Template generation
- 15:57Stochastic search
- 16:59Search process example
- 18:23Summary and contributions
- 19:05Q&A: Cost function
- 20:33Q&A: Synthesis methods
- 22:44Q&A: Cost function issues
- 24:09Q&A: Burst comparison
related talks
20mTrace-Guided Inductive Synthesis of Recursive Functional Programs
25mBottom-Up Synthesis of Recursive Functional Programs using Angelic Execution
29mIntroduction to Recursion Schemes
32mHole Refinements for Polymorphic Type-and-Example Driven Synthesis
23mInductive Program Synthesis by Meta-Analysis-Guided Hole Filling
33mProgram Synthesis Using Example Propagation
14mRelational Synthesis for Pattern Matching
26mProgram Synthesis Using Example Propagation