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 analyzing their intermediate results to compose them in appropriate ways. Motivated by this intuition, we present a new synthesis approach that leverages learning to guide a bottom-up search over programs. In particular, we train a model to prioritize compositions of intermediate values during search conditioned on a given set of input-output examples. This is a powerful combination because of several emergent properties. First, in bottom-up search, intermediate programs can be executed, providing semantic information to the neural network. Second, given the concrete values from those executions, we can exploit rich features based on recent work on property signatures. Finally, bottom-up search allows the system substantial flexibility in what order to generate the solution, allowing the synthesizer to build up a program from multiple smaller sub-programs. Overall, our empirical evaluation finds that the combination of learning and bottom-up search is remarkably effective, even with simple supervised learning approaches. We demonstrate the effectiveness of our technique on two datasets, one from the SyGuS competition and one of our own creation.
翻译:程序合成之所以具有挑战性,主要是因为在很大的程序空间中搜索难度很大。 人类程序设计员通常通过撰写子程序,处理撰写复杂程序的任务,然后分析其中间结果,以适当的方式形成它们。 受这种直觉的启发,我们提出了一个新的综合方法,利用学习来引导自下而上搜索程序。 特别是,我们训练了一个模型,在根据一套特定的输入-产出实例进行搜索时,确定中间值构成的优先次序。 这是一个强大的组合,因为有几个突发特性。 首先,在自下而上的搜索中,可以执行中间程序,向神经网络提供语义信息。 其次,鉴于这些处决的具体价值,我们可以利用基于最近关于属性签名的工作的丰富特征。 最后,自下而上的搜索使系统在产生解决方案时具有相当大的灵活性,使合成器能够从多个较小的子程序中建立程序。 总体而言,我们的经验评估发现,学习和自下而上搜索的组合非常有效,甚至可以用简单的监督学习方法。 我们展示了我们在两个数据集上的方法的有效性, 一个来自SYGu的创建和我们自己的竞争。