Program Synthesis Without Full Specifications for Novel Applications

Thesis (Ph.D.)--University of Washington, 2015Program synthesis is a family of techniques that generate programs from a description of what the program should do but not how it should do it. By designing a program synthesis algorithm together with the user interaction model we show that by accepting small increases in user effort, it is easier to write the synthesizer and the need for specialization of the synthesizer to a given domain is reduced without losing performance. In this work, we target three tasks to show the breadth of our methodology: code completion, end-user programming-by-example for data transformations, and feedback for introductory programming assignments. For each of these tasks, we develop an interaction model and program synthesis algorithm together to best support the user. In the first, we use partial expressions to allow programmers to express exactly what they don't know and want the completion system to fill in. In the second, we use the sequence of examples to inform building up larger programs iteratively. In the last, we use attempts from other students on the same assignment to mine corrections