SPLASH 2023
Sun 22 - Fri 27 October 2023 Cascais, Portugal
Wed 25 Oct 2023 11:54 - 12:12 at Room II - program synthesis 1 Chair(s): Michael Coblenz

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 Oct

Displayed time zone: Lisbon change

11:00 - 12:30
program synthesis 1OOPSLA at Room II
Chair(s): Michael Coblenz University of California, San Diego
11:00
18m
Talk
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
18m
Talk
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
18m
Talk
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
18m
Talk
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
18m
Talk
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