FlashMeta: A Framework for Inductive Program Synthesis
Inductive synthesis, or programming-by-examples (PBE) is gaining prominence with disruptive applications for automating repetitive tasks in end-user programming. However, designing, developing, and maintaining an effective industrial-quality inductive synthesizer is an intellectual and engineering challenge, requiring 1-2 man-years of effort.
Our novel observation is that many PBE algorithms are a natural fall-out of one generic meta-algorithm and the domain-specific properties of the operators in the underlying domain-specific language (DSL). The meta-algorithm propagates example-based constraints on an expression to its subexpressions by leveraging associated witness functions, which essentially capture the inverse semantics of the underlying operator. This observation enables a novel program synthesis methodology called data-driven domain-specific deduction (D4), where domain-specific insight, provided by the DSL designer, is separated from the synthesis algorithm.
Our FlashMeta framework implements this methodology, allowing synthesizer developers to generate an efficient synthesizer from the mere DSL definition (if properties of the DSL operators have been modeled). In our case studies, we found that 10+ existing industrial-quality mass-market applications based on PBE can be cast as instances of D4. Our evaluation includes reimplementation of some prior works, which in FlashMeta become more efficient, maintainable, and extensible. As a result, FlashMeta-based PBE tools are deployed in several industrial products, including Microsoft PowerShell 3.0 for Windows 10, Azure Operational Management Suite, and Microsoft Cortana digital assistant.
Wed 28 OctDisplayed time zone: Eastern Time (US & Canada) change
10:30 - 12:00
2. Domain Specific LanguagesOOPSLA at Grand Station 2
Chair(s): Eelco Visser Delft University of Technology
|Synthesis of Layout Engines from Relational Constraints|
Thibaud Hottelier Graphistry, Inc, Rastislav Bodík University of Washington, USALink to publication Media Attached
|A Sound and Optimal Incremental Build System with Dynamic Dependencies|
Sebastian Erdweg TU Darmstadt, Germany, Moritz Lichter TU Darmstadt, Germany, Manuel Weiel TU Darmstadt, GermanyLink to publication Media Attached
|FlashMeta: A Framework for Inductive Program Synthesis|
Alex Polozov University of Washington, USA, Sumit Gulwani Microsoft Research, USALink to publication DOI Media Attached
|Scrap your Boilerplate with Object Algebras|
Haoyuan Zhang University of Hong Kong, China, Zewei Chu University of Hong Kong, China, Bruno C. d. S. Oliveira University of Hong Kong, China, Tijs van der Storm CWILink to publication Media Attached