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.
Conference DayWed 28 OctDisplayed time zone: Eastern Time (US & Canada) change
10:30 - 12:00
|Synthesis of Layout Engines from Relational Constraints|
OOPSLALink to publication Media Attached
|A Sound and Optimal Incremental Build System with Dynamic Dependencies|
Sebastian ErdwegTU Darmstadt, Germany, Moritz LichterTU Darmstadt, Germany, Manuel WeielTU Darmstadt, GermanyLink to publication Media Attached
|FlashMeta: A Framework for Inductive Program Synthesis|
OOPSLALink to publication DOI Media Attached
|Scrap your Boilerplate with Object Algebras|
Haoyuan ZhangUniversity of Hong Kong, China, Zewei ChuUniversity of Hong Kong, China, Bruno C. d. S. OliveiraUniversity of Hong Kong, China, Tijs van der StormCWILink to publication Media Attached