The traditional formulation of the program synthesis problem is to find a program that meets a logical correctness specification. When synthesis is successful, there is a guarantee that the implementation satisfies the specification. Unfortunately, synthesis engines are typically monolithic algorithms, and obscure the correspondence between the specification, implementation and user intent. In contrast, humans often include comments in their code to guide future developers towards the purpose and design of different parts of the codebase. In this paper, we introduce \emph{subspecifications} as a mechanism to augment the synthesized implementation with explanatory notes of this form. In this model, the user may ask for explanations of different parts of the implementation; the subspecification generated in response is a logical formula that describes the constraints induced on that subexpression by the global specification and surrounding implementation. We develop algorithms to construct and verify subspecifications and investigate their theoretical properties. We perform an experimental evaluation of the subspecification generation procedure, and measure its effectiveness and running time. Finally, we conduct a user study to determine whether subspecifications are useful: we find that subspecifications greatly aid in understanding the global specification, in identifying alternative implementations, and in debugging faulty implementations.
Wed 25 OctDisplayed time zone: Lisbon change
11:00 - 12:30 | |||
11:00 18mTalk | Asparagus: Automated Synthesis of Parametric Gas Upper-Bounds for Smart Contracts OOPSLA Zhuo Cai Hong Kong University of Science and Technology, Soroush Farokhnia Hong Kong University of Science and Technology, Amir Kafshdar Goharshady Hong Kong University of Science and Technology, S. Hitarth Hong Kong University of Science and Technology DOI | ||
11:18 18mTalk | Equality Saturation Theory Exploration à la Carte OOPSLA Anjali Pal University of Washington, Brett Saiki University of Washington, Ryan Tjoa University of Washington, Cynthia Richey University of Washington, Amy Zhu University of Washington, Oliver Flatt University of Washington, Max Willsey UC Berkeley, Zachary Tatlock University of Washington, Chandrakana Nandi Certora DOI Pre-print | ||
11:36 18mTalk | Synthesizing Specifications OOPSLA Kanghee Park University of Wisconsin-Madison, Loris D'Antoni University of Wisconsin-Madison, Thomas Reps University of Wisconsin-Madison DOI | ||
11:54 18mTalk | Explainable Program Synthesis by Localizing Specifications OOPSLA Amirmohammad Nazari University of Southern California, Yifei Huang University of Southern California, Roopsha Samanta Purdue University, Arjun Radhakrishna Microsoft, Mukund Raghothaman University of Southern California DOI | ||
12:12 18mTalk | Pushing the Limit of 1-Minimality of Language-Agnostic Program Reduction OOPSLA Zhenyang Xu University of Waterloo, Yongqiang Tian The Hong Kong University of Science and Technology; University of Waterloo, Mengxiao Zhang University of Waterloo, Gaosen Zhao University of Waterloo, Yu Jiang Tsinghua University, Chengnian Sun University of Waterloo DOI |