- 55 views
- 110 downloads
Program Synthesis with Best-First Bottom-Up Search
-
- Author / Creator
- Ameen, Saqib
-
Cost-guided bottom-up search (BUS) algorithms use a cost function to guide the search for solving program synthesis tasks. In this thesis, we show that current state-of-the-art cost-guided BUS algorithms suffer from a common problem: they can lose useful information given by the model and fail to perform the search in a best-first order according to the cost function. We introduce a novel best-first bottom-up search algorithm, which we call Bee Search, that does not suffer from information loss and is able to perform cost-guided bottom-up synthesis in a best-first manner. Importantly, Bee Search performs best-first search with respect to the generation of programs, i.e., it does not even create programs that are more expensive than the solution program. It attains best-first ordering with respect to generation by performing a search in an abstract space of program costs. We also introduce a new cost function that better utilizes the information provided by an existing cost model. Empirical results on string manipulation and bit-vector tasks show that Bee Search can outperform the state-of-the-art cost-guided BUS approaches when employing more complex domain-specific languages (DSLs); Bee Search and previous approaches perform equally well with simpler DSLs. Further, our new cost function with Bee Search outperforms previous cost functions on string manipulation tasks.
-
- Subjects / Keywords
-
- Graduation date
- Spring 2023
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.