Program Synthesis with Best-First Bottom-Up Search
Saqib Ameen Levi H. S. Lelis
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
problem: they can lose useful information given by the model and fail to
perform the search in a best-first order according to a cost function. We
introduce a novel best-first bottom-up search algorithm, which we call Bee
Search, that does not suffer 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 in memory 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 uses the information provided by an existing cost
model. Empirical results on string manipulation and bit-vector tasks show that
Bee Search can outperform existing cost-guided BUS approaches when employing
more complex domain-specific languages (DSLs); Bee Search and previous
approaches perform equally well with simpler DSLs. Furthermore, our new cost
function with Bee Search outperforms previous cost functions on string
manipulation tasks.