Paper Info
Title
LooPy: interactive program synthesis with control structures
Abstract
AbstractOne vision for program synthesis, and specifically for programming by example (PBE), is an interactive programmer's assistant, integrated into the development environment. To make program synthesis practical for interactive use, prior work on Small-Step Live PBE has proposed to limit the scope of synthesis to small code snippets, and enable the users to provide local specifications for those snippets. This paradigm, however, does not work well in the presence of loops. We present LooPy, a synthesizer integrated into a live programming environment, which extends Small-Step Live PBE to work inside loops and scales it up to synthesize larger code snippets, while remaining fast enough for interactive use. To allow users to effectively provide examples at various loop iterations, even when the loop body is incomplete, LooPy makes use of live execution, a technique that leverages the programmer as an oracle to step over incomplete parts of the loop. To enable synthesis of loop bodies at interactive speeds, LooPy introduces Intermediate State Graph, a new data structure, which compactly represents a large space of code snippets composed of multiple assignment statements and conditionals. We evaluate LooPy empirically using benchmarks from competitive programming and previous synthesizers, and show that it can solve a wide variety of synthesis tasks at interactive speeds. We also perform a small qualitative user study which shows that LooPy's block-level specifications are easy for programmers to provide.
Year
DOI
Venue
2021
10.1145/3485530
Proceedings of the ACM on Programming Languages
Keywords
DocType
Volume
Program synthesis, live programming
Journal
5
Issue
Citations 
PageRank 
OOPSLA
0
0.34
References 
Authors
0
5
Name
Order
Citations
PageRank
Kasra Ferdowsifard100.34
Shraddha Barke211.04
Hila Peleg3475.04
Sorin Lerner498163.89
Nadia Polikarpova516916.60