Blogs (1) >>
POPL 2019
Sun 13 - Sat 19 January 2019 Cascais, Portugal
Thu 17 Jan 2019 09:22 - 09:44 at Sala II - Synthesis Chair(s): Robbert Krebbers

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.

POPL 2019 Presentation Slides (POPL_2019_FrAngel_Presentation_cleaned.pdf)271KiB

Thu 17 Jan
Times are displayed in time zone: Greenwich Mean Time : Belfast change

09:00 - 10:06: SynthesisResearch Papers at Sala II
Chair(s): Robbert KrebbersDelft University of Technology
09:00 - 09:22
Structuring the Synthesis of Heap-Manipulating ProgramsDistinguished Paper
Research Papers
Nadia PolikarpovaUniversity of California, San Diego, Ilya SergeyYale-NUS College and National University of Singapore
Link to publication DOI Pre-print Media Attached File Attached
09:22 - 09:44
FrAngel: Component-Based Synthesis with Control Structures
Research Papers
Kensen ShiStanford University, Jacob SteinhardtStanford University, Percy LiangStanford University
Link to publication DOI Pre-print Media Attached File Attached
09:44 - 10:06
Hamsaz: Replication Coordination Analysis and Synthesis
Research Papers
Farzin HoushmandUniversity of California, Riverside, Mohsen LesaniUniversity of California, Riverside
Link to publication DOI Media Attached