Letting users do the undecidable: lessons from program synthesis
COM1 Level 3
MR1, COM1-03-19
Abstract:
Like many other fields of programming languages research, the program synthesis problem is undecidable. In some narrower scopes things get better, and it’s just very hard. 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, making turning the resulting synthesis algorithm into a usable tool even harder.
The world of algorithms for PL's undecidable problems are the furthest thing from what you could put in a user-facing tool: users expect tools to be reliable, quick, and easy to operate. The complex relationship between user intent, specifications, and interaction model means the algorithmic 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 an algorithm - in our case, a program 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 named Synthesis Co-Design, and seek to generalize this to other PL problems.
Bio:
Hila Peleg is an Assistant Professor at the Technion, Haifa, working in the intersection of Programming Languages, Software Engineering, and Human Computer Interaction. Her research interests are in the fields of Programming Languages and Program Synthesis, specifically interaction models that create more versatile program synthesis solutions for programmers. She has completed her PhD with Prof. Eran Yahav in 2019 and worked with Prof. Nadia Polikarpova as a postdoc at UCSD.