_Synthesis__________________ __Of_______________________ ___First-Order_____Dynamic___ _____________Programming___ _______________Algorithms___ Yewen (Evan) Pu Rastislav Bodik Saurabh Srivastava University of California, Berkeley
Do you feel lucky?
A new way to build an island? Conventional Domain Specific Compiler: Require deep domain theories Takes a long time to implement Constraint Based Synthesizer: Write a template for desired algorithm Constraint solver fills in the template
Make Templates not Theories Suppose we want to optimize x+x+x+x With domain-specific rewrite rules: With a template in SKETCH [Solar-Lezama]: spec(x): return x+x+x+x sketch(x): return x << ?? program equivalence found using bounded model checking
A Search for a Correct Program Synthesizer finds in a space of candidate programs a correct one (it matches the specification)
Research Question in This Talk Can we write a synthesizer for an entire problem domain using a single template (sketch)?
The Challenge How do we write a template that covers all of our domain, yet the constraints it induces can be efficiently solved?
Our Approach Define a general template that contains the entire domain Optimize the search by reducing the search space
Dynamic Programming Algorithms A well-defined domain We have no DSL compiler for it (taught as an art) Difficulties: inventing sub-problems inventing recurrences We focus on a first-order sub-class, FORDP, which captures many O(n) DP algorithms
An Easy Problem Fibonacci Sequence: fib(n) = fib(n-1) + fib(n-2)
A Harder Problem Maximal Independent Sum (MIS) Input: Array of positive integers Output: Maximum sum of a non-consecutive selections of its elements.
What does the user do? mis(A): best = 0 forall selections: if non_consec(selection): best = max(best, value(A[selection])) return best
What does the template do? Define a general template that contains the entire domain
A General Template Covers every FORDP algorithm
General Template for update All possible compositions of user provided operators
Space Reduction: Optimality All FORDP recurrences have this syntactic form
Space Reduction: Optimality Recurrence for MIS:
Space Reduction: Symmetry Many operators are commutative Pick a canonical representative syntactically
Space Reduction: Recap All possible compositions Syntactically Reduced
Benchmarks Here are some synthesized recurrences
Experiments Synthesizer solving time, in seconds out of memory
Conclusion It is possible to build a domain-specific synthesizer for FORDPA Synthesizer developer only find a syntactic domain structure The lessons learned in building the synthesizer may be general If so, we can build more islands with constraint-based synthesis