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.

该论文通过引入一种名为Bee Search的新的最佳优先从底向上搜索算法，解决了现有的基于成本指导的底向上搜索算法在信息损失和成本函数排序方面的问题。实证结果表明，Bee Search在更复杂的领域特定语言（DSLs）中优于现有的成本指导的BUS算法，在简单的DSLs中与先前的方法表现相当好。此外，我们的新成本函数在字符串操作任务上优于先前的成本函数。

最佳优先自顶向下的程序合成