Program Synthesis Co-Design

Program synthesis is the problem of generating a program the user is looking for for them. Since the expressed user intent is often (very) partial, synthesis algorithms must search a space of candidate programs for one that exhibits the desired behavior. A lion’s share of the work on program synthesis focuses on new ways to perform the search, but this does not tell the whole story of how a synthesizer operates. This focus disregards the user now, and moreover, makes turning the resulting synthesis algorithm into a usable tool even harder.

The complex relationship between user intent, specifications, and interaction model means program synthesis research must consider all three as early as possible in the development process. Interaction not only dictates the choice of synthesis algorithm but how it must be modified, and algorithmic limitations need to be accommodated in the interaction.

We demonstrate the process of concurrently building both the synthesizer and its intended user-facing tool as a way to search for a balance of the needs of the interaction model (and, implicitly, the user) and the algorithm, a process we name Synthesis Co-Design. We include in this paper three case studies of interactive synthesis developed with and without co-design, and discuss the lessons learned from those projects.