Program synthesis is the task of synthesizing a program that satisfies a given specification. Programming by examples (PBE) is a subfield of program synthesis, where the specification comes in the form of input-output examples. There are two key distinguishing aspects of PBE that motivate dedicated investment in PBE technology. First, program synthesis is a very hard problem in general—in contrast, the nature of example-based specification in PBE makes PBE more tractable than program synthesis since reasoning about concrete input states is much easier than dealing with properties over symbolic program states. Second, writing logical/relational/complete specifications is hard for those even with a programming background—in contrast, PBE can enable non-programmers to create programs for automating repetitive tasks. Today, billions of users have access to computational devices. However, 99% of these end users do not have programming expertise and they often struggle with repetitive tasks in various domains that could otherwise be automated using small scripts.

Developing a PBE technology requires (a) designing a DSL for the application domain; (b) building a synthesis algorithm for it, and (c) disambiguating among learned programs using ranking or user interaction. This tutorial presents Microsoft PROSE SDK, an algorithmic framework of technologies for PBE that facilitates all stages of this pipeline. Given a domain-specific language (DSL) and some input-output examples for the desired program’s behavior, PROSE algorithms synthesize a ranked set of DSL programs that are consistent with the given examples. PROSE provides reusable components and search tactics to ease PBE development for a variety of domains. Its deductive meta-algorithm, parameterized by a DSL, synthesizes scripts with complex business logic in < 1 sec. Using this methodology, we have successfully applied PBE in mass-market industrial applications, such as FlashFill (synthesis of string transformations, released in Excel) and FlashExtract (synthesis of text extraction scripts, released in Microsoft PowerShell and Azure OMS).

This tutorial is a combination of a presentation and a live coding session. The presentation gradually introduces all concepts of PBE, illustrating them with concurrent implementation of PBE-based applications using Microsoft PROSE SDK.

1. Discussion of PBE and its applications including opportunities in the space of data wrangling and education.

2. Discussion of principles behind designing an appropriate domain-specific language, reuse and customization of DSL components. Illustrated via an iterative and step-by-step construction of the FlashFill and FlashExtract DSLs.

3. Discussion of the deductive algorithmic approach to PBE, DSL customization with logical operator properties, and search tactics. Hands-on illustration on customization for a subset of FlashFill and FlashExtract DSLs in PROSE that leads to an industrial-scale synthesis application.

4. Discussion of ambiguity resolution techniques: use of machine learning for ranking programs, and user interaction models based on active learning. Hands-on illustration of a ranking scheme design for a DSL in PROSE.

5. Discussion of real-world research challenges that arise in applying program synthesis to industrial domains.