Efficient Bottom-Up Synthesis for Programs with Local Variables
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration
Program synthesis is challenging largely because of the difficulty of search in a large space of programs. Human programmers routinely tackle the task of writing complex programs by writing sub-programs and then analyzin…
Program SynthesisCrossBeam: Learning to Search in Bottom-Up Program Synthesis
Many approaches to program synthesis perform a search within an enormous space of programs to find one that satisfies a given specification. Prior works have used neural models to guide combinatorial search algorithms, b…
Program SynthesisStructured PredictionProgram Synthesis with Best-First Bottom-Up Search
Cost-guided bottom-up search (BUS) algorithms use a cost function to guide the search to solve program synthesis tasks. In this paper, we show that current state-of-the-art cost-guided BUS algorithms suffer from a common…
Program SynthesisGrounding Bound Founded Answer Set Programs
To appear in Theory and Practice of Logic Programming (TPLP) Bound Founded Answer Set Programming (BFASP) is an extension of Answer Set Programming (ASP) that extends stable model semantics to numeric variables. While …
AbstractBeam: Enhancing Bottom-Up Program Synthesis using Library Learning
LambdaBeam is a state-of-the-art, execution-guided algorithm for program synthesis that utilizes higher-order functions, lambda functions, and iterative loops within a Domain-Specific Language (DSL). LambdaBeam generates…
Program Synthesis