Interpretable Program Synthesis
Tianyi Zhang, Zhiyang Chen, Yuanli Zhu, Priyan Vaithilingam, Xinyu Wang, Elena L. Glassman
Abstract
Program synthesis, which generates programs based on user-provided specifications, can be obscure and brittle: users have few ways to understand and recover from synthesis failures. We propose interpretable program synthesis, a novel approach that unveils the synthesis process and enables users to monitor and guide a synthesizer. We designed three representations that explain the underlying synthesis process with different levels of fidelity. We implemented an interpretable synthesizer for regular expressions and conducted a within-subjects study with eighteen participants on three challenging regex tasks. With interpretable synthesis, participants were able to reason about synthesis failures and provide strategic feedback, achieving a significantly higher success rate compared with a state-of-the-art synthesizer. In particular, participants with a high engagement tendency (as measured by NCS-6) preferred a deductive representation that shows the synthesis process in a search tree, while participants with a relatively low engagement tendency preferred an inductive representation that renders representative samples of programs enumerated during synthesis.