Augmented Example-based synthesis using relational perturbation properties

Shengwei An, Rishabh Singh, Sasa Misailovic, Roopsha Samanta

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number56
JournalProceedings of the ACM on Programming Languages
Issue numberPOPL
StatePublished - Jan 2020
Externally publishedYes


  • Ambiguity-Resolution
  • Example-Based Synthesis
  • Program Synthesis

ASJC Scopus subject areas

  • Software
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'Augmented Example-based synthesis using relational perturbation properties'. Together they form a unique fingerprint.

Cite this