FrAngel: component-based synthesis with control structures

By Kensen Shi, Jacob Steinhardt, Percy Liang. 2018

61 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Code Generation & Program Synthesis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Code Generation & Program Synthesis

Citations in the corpus

SPoC: Search-based Pseudocode to Code (2019, background): “For other domains, while input-output examples are precise in evaluating functional correctness, they provide mostly global signals and inform very little about the intermediate computation, thereby requiring other forms of speciﬁcation along with input-output examples (e.g., [9, 31]).”