Augmented Example-based Synthesis using Relational Perturbation Properties
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 JanDisplayed time zone: Saskatchewan, Central America change
10:30 - 11:35
|Synthesis of Coordination Programs from Linear Temporal Specifications|
Suguman Bansal Rice University, USA, Kedar Namjoshi Bell Labs, Nokia, Yaniv Sa'ar Nokia Bell Labs, Kfar Saba, IsraelLink to publication DOI Media Attached File Attached
|Augmented Example-based Synthesis using Relational Perturbation Properties|
Shengwei An Purdue University, Rishabh Singh Google Brain, Sasa Misailovic University of Illinois at Urbana-Champaign, Roopsha Samanta Purdue UniversityLink to publication DOI Media Attached File Attached
|Provenance-Guided Synthesis of Datalog Programs|
Mukund Raghothaman University of Southern California, Jonathan Mendelson University of Pennsylvania, David Zhao The University of Sydney, Mayur Naik University of Pennsylvania, Bernhard Scholz University of Sydney, AustraliaLink to publication DOI Media Attached File Attached