2019/12/29 by Osbert Bastani, Xin Zhang, Bastani, Osbert +4
Computer Science · #FOS: Computer and information sciences #Logic, programming, and type systems #Machine Learning and Algorithms #Programming Languages (cs.PL) #Software Testing and Debugging Techniques #cs.PL
paper · pdf · doi:10.48550/arxiv.1912.12659
openalex publication_date 2019/12/29 · arxiv created 2021/10/11 · arxiv updated 2021/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a novel approach to program synthesis, focusing on synthesizing database queries. At a high level, our proposed algorithm takes as input a sketch with soft constraints encoding user intent, and then iteratively interacts with the user to refine the sketch. At each step, our algorithm proposes a candidate refinement of the sketch, which the user can either accept or reject. By leveraging this rich form of user feedback, our algorithm is able to both resolve ambiguity in user intent and improve scalability. In particular, assuming the user provides accurate inputs and responses, then our algorithm is guaranteed to converge to the true program (i.e., one that the user approves) in polynomial time. We perform a qualitative evaluation of our algorithm, showing how it can be used to synthesize a variety of queries on a database of academic publications.