Programming by Examples

Programming by Examples (PBE) involves synthesizing intended programs in an underlying domain-specific language (DSL) from example-based specifications. PBE is set to revolutionize the programming experience for both developers and end users. It can provide a 10-100x productivity increase for developers in some task domains, and can enable computer users, 99% of whom are non-programmers, to create small scripts to automate repetitive tasks. Two killer applications for this technology include data wrangling (an activity where data scientists today spend 80% time) and code refactoring (an activity where developers spend up to 40% time in a typical application migration scenario).

We will discuss some principles behind designing useful DSLs for program synthesis. A key technical challenge in PBE is to search for programs in the underlying DSL that are consistent with the examples provided by the user. We will discuss a divide-and-conquer based search paradigm that inductively reduces the problem of synthesizing a program with a certain top-level operator to simpler synthesis problems over its sub-programs by leveraging the operator's inverse semantics. Another challenge in PBE is to resolve the ambiguity in the example-based specification. We will discuss two complementary approaches: (a) ranking techniques that can pick an intended program from among those that satisfy the specification, and (b) active-learning based user interaction models. The various concepts will be illustrated using Flash Fill, FlashExtract, and FlashRelate---PBE technologies for data manipulation domains. The Microsoft PROSE SDK allows easy construction of such technologies. We will do a hands-on exercise that will involve building a synthesizer for a small part of the Flash Fill DSL using the PROSE framework.

We will also discuss some related topics including: (a) programming by natural language, and (b) applications in intelligent tutoring systems including feedback generation and problem generation.

Bio

Sumit Gulwani is a Research manager at Microsoft, leading the PROSE research and engineering team that develops APIs for program synthesis and incorporates them into real products. He is the inventor of the Flash Fill feature in Microsoft Excel used by hundreds of millions of people. He has published 110+ papers in top-tier conferences/journals across multiple computer science areas, and delivered 40+ keynotes/invited talks at various forums. He was awarded the ACM SIGPLAN Robin Milner Young Researcher Award in 2014 for his pioneering contributions to end-user programming and intelligent tutoring systems. He obtained his PhD in Computer Science from UC-Berkeley in 2005, and was awarded the ACM SIGPLAN Outstanding Doctoral Dissertation Award. He obtained his BTech in Computer Science and Engineering from IIT Kanpur in 2000, and was awarded the President’s Gold Medal.