Efficient Bottom-Up Synthesis for Programs with Local Variables
This addresses a bottleneck in program synthesis for tasks involving local variables, such as web automation, though it appears incremental as it builds on prior bottom-up synthesis techniques.
The paper tackles the problem of slow synthesis for programs with local variables by proposing a new algorithm that efficiently reduces the search space, resulting in a tool, Arborist, that automates a broader range of web automation tasks more efficiently than state-of-the-art methods.
We propose a new synthesis algorithm that can efficiently search programs with local variables (e.g., those introduced by lambdas). Prior bottom-up synthesis algorithms are not able to evaluate programs with free local variables, and therefore cannot effectively reduce the search space of such programs (e.g., using standard observational equivalence reduction techniques), making synthesis slow. Our algorithm can reduce the space of programs with local variables. The key idea, dubbed lifted interpretation, is to lift up the program interpretation process, from evaluating one program at a time to simultaneously evaluating all programs from a grammar. Lifted interpretation provides a mechanism to systematically enumerate all binding contexts for local variables, thereby enabling us to evaluate and reduce the space of programs with local variables. Our ideas are instantiated in the domain of web automation. The resulting tool, Arborist, can automate a significantly broader range of challenging tasks more efficiently than state-of-the-art techniques including WebRobot and Helena.