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 each program from scratch but does not take advantage of the frequent recurrence of program blocks or subprograms commonly found in specific domains, such as loops for list traversal. To address this limitation, we introduce AbstractBeam: a novel program synthesis framework designed to enhance LambdaBeam by leveraging Library Learning. AbstractBeam identifies and integrates recurring program structures into the DSL, optimizing the synthesis process. Our experimental evaluations demonstrate that AbstractBeam statistically significantly (p < 0.05) outperforms LambdaBeam in the integer list manipulation domain. Beyond solving more tasks, AbstractBeam's program synthesis is also more efficient, requiring less time and fewer candidate programs to generate a solution. Furthermore, our findings indicate that Library Learning effectively enhances program synthesis in domains that are not explicitly designed to showcase its advantages, thereby highlighting the broader applicability of Library Learning.
Code (0)
등록된 구현이 없습니다.
Tasks
Program SynthesisMethods 이 논문이 사용한 방법론
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 PredictionTF-Coder: Program Synthesis for Tensor Manipulations
The success and popularity of deep learning is on the rise, partially due to powerful deep learning frameworks such as TensorFlow and PyTorch that make it easier to develop deep learning models. However, these libraries …
Deep LearningEnumerative SearchProgram SynthesisProgram 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 SynthesisEfficient 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 v…