Write a Blog >>
Thu 23 Jan 2020 10:51 - 11:13 at Ile de France III (IDF III) - Synthesis Chair(s): Mohsen Lesani

Example-based specifications for program synthesis are inherently ambiguous and may cause synthesizers to generate programs that do not exhibit intended behavior on unseen inputs. Existing synthesis techniques attempt to address this problem by either placing a domain specific, syntactic bias on the hypothesis space or heavily relying on user feedback to help resolve ambiguity.

We present a new framework to address the ambiguity/generalizability problem in example-based synthesis. The key feature of our framework is that it places a semantic bias on the hypothesis space using “relational perturbation properties” that relate the perturbation/change in a program output to the perturbation/change in a program input. An example of such a property is permutation invariance: the program output does not change when the elements of the program input (array) are permuted. The framework is portable across multiple domains and synthesizers and is based on two core steps: (1) automatically augment the set of user-provided examples by “applying” relational perturbation properties and (2) use a generic example-based synthesizer to generate a program consistent with the augmented set of examples. Our framework can be instantiated with three different user interfaces, with varying degrees of user engagement to help infer relevant relational perturbation properties. This includes an interface in which the user only provides examples and our framework automatically infers relevant properties. We implement our framework in a tool SketchAX specialized to the Sketch synthesizer and demonstrate that SketchAX is effective in significantly boosting the performance of Sketch for all three user interfaces.

Augmented Example-based Synthesis using Relational Perturbation Properties (Samanta_POPL2020.pdf)7.33MiB

Thu 23 Jan

POPL-2020-Research-Papers
10:30 - 11:35: Research Papers - Synthesis at Ile de France III (IDF III)
Chair(s): Mohsen LesaniUniversity of California, Riverside
POPL-2020-Research-Papers10:30 - 10:51
Talk
Suguman BansalRice University, USA, Kedar NamjoshiBell Labs, Nokia, Yaniv Sa'arNokia Bell Labs, Kfar Saba, Israel
Link to publication DOI Media Attached File Attached
POPL-2020-Research-Papers10:51 - 11:13
Talk
Shengwei AnPurdue University, Rishabh SinghGoogle Brain, Sasa MisailovicUniversity of Illinois at Urbana-Champaign, Roopsha SamantaPurdue University
Link to publication DOI Media Attached File Attached
POPL-2020-Research-Papers11:13 - 11:35
Talk
Mukund RaghothamanUniversity of Southern California, Jonathan MendelsonUniversity of Pennsylvania, David ZhaoThe University of Sydney, Mayur NaikUniversity of Pennsylvania, Bernhard ScholzUniversity of Sydney, Australia
Link to publication DOI Media Attached File Attached