FrAngel: component-based synthesis with control structures
FrAngel: component-based synthesis with control structures
复制标题
FrAngel：具有控制结构的基于组件的合成
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Percy Liang
中科院分区：
文献类型：
--
作者：
Kensen Shi;J. Steinhardt;Percy Liang
在基于组件的程序合成中，合成器生成给定组件（函数）库的程序。现有的基于组件的合成器很难合成循环和其他控制结构，并且它们通常需要组件的正式规范，这可能是昂贵的生成。我们提出了FrAngel，一种新的方法，基于组件的合成，可以合成短的Java功能与控制结构时，给定一个所需的签名，一组输入输出的例子，和一个集合的库（没有正式的规范）。FrAngel旨在通过结合两个主要思想来发现具有许多不同行为的程序。首先，它从只通过某些示例的部分成功的程序中挖掘代码片段。由于我们称之为特殊情况相似性的性质，这些提取的片段通常对合成有用。第二，FrAngel使用天使的条件作为占位符的控制结构的条件和乐观地评估所产生的程序草图。天使条件分解合成过程：FrAngel首先找到有希望的部分程序，然后填充它们缺少的条件。我们证明了FrAngel可以在几秒钟内合成各种有趣的程序与控制结构的组合，显着优于现有的最先进的。
In component-based program synthesis, the synthesizer generates a program given a library of components (functions). Existing component-based synthesizers have difficulty synthesizing loops and other control structures, and they often require formal specifications of the components, which can be expensive to generate. We present FrAngel, a new approach to component-based synthesis that can synthesize short Java functions with control structures when given a desired signature, a set of input-output examples, and a collection of libraries (without formal specifications). FrAngel aims to discover programs with many distinct behaviors by combining two main ideas. First, it mines code fragments from partially-successful programs that only pass some of the examples. These extracted fragments are often useful for synthesis due to a property that we call special-case similarity. Second, FrAngel uses angelic conditions as placeholders for control structure conditions and optimistically evaluates the resulting program sketches. Angelic conditions decompose the synthesis process: FrAngel first finds promising partial programs and later fills in their missing conditions. We demonstrate that FrAngel can synthesize a variety of interesting programs with combinations of control structures within seconds, significantly outperforming prior state-of-the-art.