一句话：FrAngel 通过挖掘部分成功程序中的代码片段并用 angelic 条件占位控制结构条件，实现带循环等控制结构的组件式合成。
基于组件的程序合成中，合成器需要根据一个组件（函数）库生成程序，但现有方法难以合成循环等控制结构，且往往要求组件具有形式化规格，代价高昂。本文提出 FrAngel：在给定目标签名、一组输入输出示例和组件库（无形式规格）的条件下，合成简短的、含控制结构的 Java 函数。其核心思想有二：一是从仅通过部分示例的“部分成功”程序中挖掘代码片段，作者称这类片段因具备 special-case similarity 性质而对合成很有价值；二是用 angelic 条件作为控制结构条件的占位符，对生成的程序 sketch 进行乐观求值，从而把合成过程分解为先寻找有希望的部分程序、再补全其缺失条件。实验表明，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.
@article{paperbot655,
title = {FrAngel: component-based synthesis with control structures},
author = {Kensen Shi and Jacob Steinhardt and Percy Liang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {3},
number = {POPL},
year = {2019},
doi = {10.1145/3290386}
}