research-article

Recursion synthesis with unrealizability witnesses

Authors:

Victor NicoletAuthors Info & Claims

PLDI 2022: Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation

Pages 244 - 259

https://doi.org/10.1145/3519939.3523726

Published: 09 June 2022 Publication History

Abstract

We propose SE2GIS, a novel inductive recursion synthesis approach with the ability to both synthesize code and declare a problem unsolvable. SE2GIS combines a symbolic variant of counterexample-guided inductive synthesis (CEGIS) with a new dual inductive procedure, which focuses on proving a synthesis problem unsolvable rather than finding a solution for it. A vital component of this procedure is a new algorithm that produces a witness, a set of concrete assignments to relevant variables, as a proof that the synthesis instance is not solvable. Witnesses in the dual inductive procedure play the same role that solutions do in classic CEGIS; that is, they ensure progress. Given a reference function, invariants on the input recursive data types, and a target family of recursive functions, SE2GIS synthesizes an implementation in this family that is equivalent to the reference implementation, or declares the problem unsolvable and produces a witness for it. We demonstrate that SE2GIS is effective in both cases; that is, for interesting data types with complex invariants, it can synthesize non-trivial recursive functions or output witnesses that contain useful feedback for the user.

References

[1]

Aws Albarghouthi, Sumit Gulwani, and Zachary Kincaid. 2013. Recursive Program Synthesis. In Computer Aided Verification, Natasha Sharygina and Helmut Veith (Eds.) (Lecture Notes in Computer Science, Vol. 8044). 934–950. https://doi.org/10.1007/978-3-642-39799-8_67

[2]

Rajeev Alur, Rastislav Bodik, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. 2013. Syntax-Guided Synthesis. In 2013 Formal Methods in Computer-Aided Design. 1–8. https://doi.org/10.1109/FMCAD.2013.6679385

[3]

Haniel Barbosa, Pascal Fontaine, and Andrew Reynolds. 2017. Congruence Closure with Free Variables. In Tools and Algorithms for the Construction and Analysis of Systems, Axel Legay and Tiziana Margaria (Eds.) (Lecture Notes in Computer Science). 214–230. https://doi.org/10.1007/978-3-662-54580-5_13

Digital Library

[4]

Clark Barrett, Christopher L. Conway, Morgan Deters, Liana Hadarean, Dejan Jovanović, Tim King, Andrew Reynolds, and Cesare Tinelli. 2011. CVC4. In Computer Aided Verification, Ganesh Gopalakrishnan and Shaz Qadeer (Eds.) (Lecture Notes in Computer Science). 171–177. https://doi.org/10.1007/978-3-642-22110-1_14

[5]

Clark Barrett, Pascal Fontaine, and Aaron Stump. 2017. The SMT-LIB Standard. 104.

[6]

Nikolaj Bjorner and Mikolas Janota. 2016. Playing with Quantified Satisfaction. LPAR-20. 15–1. https://doi.org/10.29007/vv21

[7]

Benjamin Caulfield, Markus N. Rabe, Sanjit A. Seshia, and Stavros Tripakis. 2016. What’s Decidable about Syntax-Guided Synthesis? arxiv:1510.08393.

[8]

Koen Claessen, Moa Johansson, Dan Rosén, and Nicholas Smallbone. 2013. Automating Inductive Proofs Using Theory Exploration. In Automated Deduction – CADE-24, Maria Paola Bonacina (Ed.) (Lecture Notes in Computer Science, Vol. 7898). 392–406. https://doi.org/10.1007/978-3-642-38574-2_27

Digital Library

[9]

Leonardo de Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In Tools and Algorithms for the Construction and Analysis of Systems, C. R. Ramakrishnan and Jakob Rehof (Eds.) (Lecture Notes in Computer Science). 337–340. https://doi.org/10.1007/978-3-540-78800-3_24

[10]

Azadeh Farzan and Victor Nicolet. 2021. Counterexample-Guided Partial Bounding for Recursive Function Synthesis. In Computer Aided Verification (Lecture Notes in Computer Science, Vol. 1). 23.

Digital Library

[11]

John K. Feser, Swarat Chaudhuri, and Isil Dillig. 2015. Synthesizing Data Structure Transformations from Input-Output Examples. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’15). 229–239. https://doi.org/10.1145/2737924.2737977

Digital Library

[12]

Jonathan Frankle, Peter-Michael Osera, David Walker, and Steve Zdancewic. 2016. Example-Directed Synthesis: A Type-Theoretic Interpretation. 51, 1 (2016), 802–815. issn:0362-1340 https://doi.org/10.1145/2914770.2837629

Digital Library

[13]

Yeting Ge and Leonardo Moura. 2009. Complete Instantiation for Quantified Formulas in Satisfiabiliby Modulo Theories. In Proceedings of the 21st International Conference on Computer Aided Verification (CAV ’09). 306–320. https://doi.org/10.1007/978-3-642-02658-4_25

Digital Library

[14]

Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. 2017. Program Synthesis (Foundations and Trends in Programming Languages).

[15]

Qinheping Hu, Jason Breck, John Cyphert, Loris D’Antoni, and Thomas Reps. 2019. Proving Unrealizability for Syntax-Guided Synthesis. In Computer Aided Verification, Isil Dillig and Serdar Tasiran (Eds.) (Lecture Notes in Computer Science). 335–352. https://doi.org/10.1007/978-3-030-25540-4_18

[16]

Qinheping Hu, John Cyphert, Loris D’Antoni, and Thomas Reps. 2020. Exact and Approximate Methods for Proving Unrealizability of Syntax-Guided Synthesis Problems. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. 1128–1142. https://doi.org/10.1145/3385412.3385979

Digital Library

[17]

Susumu Katayama. 2012. An Analytical Inductive Functional Programming System That Avoids Unintended Programs. In Proceedings of the ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation (PEPM ’12). 43–52. https://doi.org/10.1145/2103746.2103758

Digital Library

[18]

Emanuel Kitzelmann and Ute Schmid. 2006. Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach. 7, 7 (2006), 26.

[19]

Etienne Kneuss, Ivan Kuraj, Viktor Kuncak, and Philippe Suter. 2013. Synthesis modulo Recursive Functions. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications. 407–426. https://doi.org/10.1145/2509136.2509555

Digital Library

[20]

Tristan Knoth, Di Wang, Nadia Polikarpova, and Jan Hoffmann. 2019. Resource-Guided Program Synthesis. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. 253–268. https://doi.org/10.1145/3314221.3314602

Digital Library

[21]

Anvesh Komuravelli, Arie Gurfinkel, and Sagar Chaki. 2016. SMT-based Model Checking for Recursive Programs. 48, 3 (2016), 175–205. issn:1572-8102 https://doi.org/10.1007/s10703-016-0249-4

Digital Library

[22]

Paul Krogmeier and P. Madhusudan. 2021. Learning Formulas in Finite Variable Logics. arxiv:2111.03534.

[23]

Paul Krogmeier, Umang Mathur, Adithya Murali, P. Madhusudan, and Mahesh Viswanathan. 2020. Decidable Synthesis of Programs with Uninterpreted Functions. In Computer Aided Verification, Shuvendu K. Lahiri and Chao Wang (Eds.) (Lecture Notes in Computer Science). 634–657. https://doi.org/10.1007/978-3-030-53291-8_32

Digital Library

[24]

Xavier Leroy, Damien Doligez, Alain Frisch, Jacques Garrigue, Didier Rémy, and Jérôme Vouillon. 2020. The OCaml System Release 4.11: Documentation and User’s Manual.

[25]

Justin Lubin, Nick Collins, Cyrus Omar, and Ravi Chugh. 2020. Program Sketching with Live Bidirectional Evaluation. 4 (2020), 109:1–109:29. https://doi.org/10.1145/3408991

Digital Library

[26]

P. Madhusudan, Umang Mathur, Shambwaditya Saha, and Mahesh Viswanathan. 2018. A Decidable Fragment of Second Order Logic With Applications to Synthesis. https://doi.org/10.4230/LIPIcs.CSL.2018.31 arxiv:1712.05513.

[27]

Anders Miltner, Adrian Trejo Nuñez, Ana Brendel, Swarat Chaudhuri, and Isil Dillig. 2022. Bottom-up Synthesis of Recursive Functional Programs Using Angelic Execution. In Proceedings of the 49th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1, 31.

Digital Library

[28]

Anders Miltner, Saswat Padhi, Todd Millstein, and David Walker. 2020. Data-Driven Inference of Representation Invariants. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. 1–15. https://doi.org/10.1145/3385412.3385967

Digital Library

[29]

Victor Nicolet and Danya Lette. 2022. Synduce.

[30]

Victor Nicolet, Danya Lette, and Azadeh Farzan. 2022. Recursion Synthesis with Unrealizability Witnesses (Extended Version).

[31]

C.-H. Luke Ong and Steven J. Ramsay. 2011. Verifying Higher-Order Functional Programs with Pattern-Matching Algebraic Data Types. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’11). 587–598. https://doi.org/10.1145/1926385.1926453

Digital Library

[32]

Peter-Michael Osera and Steve Zdancewic. 2015. Type-and-Example-Directed Program Synthesis. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’15). 619–630. https://doi.org/10.1145/2737924.2738007

Digital Library

[33]

Saswat Padhi, Rahul Sharma, and Todd Millstein. 2016. Data-Driven Precondition Inference with Learned Features. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’16). 42–56. https://doi.org/10.1145/2908080.2908099

Digital Library

[34]

Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezama. 2016. Program Synthesis from Polymorphic Refinement Types. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’16). 522–538. https://doi.org/10.1145/2908080.2908093

Digital Library

[35]

Mukund Raghothaman, Andrew Reynolds, and Abhishek Udupa. 2019. The SyGuS Language Standard Version 2.0. 22.

[36]

Eytan Singher and Shachar Itzhaky. 2021. Theory Exploration Powered by Deductive Synthesis. In Computer Aided Verification, Alexandra Silva and K. Rustan M. Leino (Eds.) (Lecture Notes in Computer Science, Vol. 12760). 125–148. https://doi.org/10.1007/978-3-030-81688-9_6

Digital Library

[37]

Armando Solar-Lezama. 2013. Program Sketching. 15, 5 (2013), 475–495. issn:1433-2787 https://doi.org/10.1007/s10009-012-0249-7

Digital Library

[38]

Phillip D. Summers. 1977. A Methodology for LISP Program Construction from Examples. 24, 1 (1977), 161–175. issn:0004-5411 https://doi.org/10.1145/321992.322002

Digital Library

[39]

Weikun Yang, Grigory Fedyukovich, and Aarti Gupta. 2019. Lemma Synthesis for Automating Induction over Algebraic Data Types. In Principles and Practice of Constraint Programming, Thomas Schiex and Simon de Givry (Eds.) (Lecture Notes in Computer Science). 600–617. https://doi.org/10.1007/978-3-030-30048-7_35

Digital Library

Cited By

Liu JMurphy CGrover AJohnson KReps TD’Antoni L(2024)Synthesizing Formal Semantics from Executable InterpretersProceedings of the ACM on Programming Languages10.1145/36897248:OOPSLA2(362-388)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689724
Nagy SKim JReps TD’Antoni L(2024)Automating Unrealizability Logic: Hoare-Style Proof Synthesis for Infinite Sets of ProgramsProceedings of the ACM on Programming Languages10.1145/36897158:OOPSLA2(113-139)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689715
Kurashige CJi RGiridharan ABarbone MNoor DItzhaky SJhala RPolikarpova N(2024)CCLemma: E-Graph Guided Lemma Discovery for Inductive Equational ProofsProceedings of the ACM on Programming Languages10.1145/36746538:ICFP(818-844)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674653
Show More Cited By

Index Terms

Recursion synthesis with unrealizability witnesses
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
      1. Automatic programming
  2. Software organization and properties
    1. Software functional properties
      1. Formal methods
        Software verification
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Program schemes
    2. Program reasoning

Recommendations

Can reactive synthesis and syntax-guided synthesis be friends?
PLDI 2022: Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation

While reactive synthesis and syntax-guided synthesis (SyGuS) have seen enormous progress in recent years, combining the two approaches has remained a challenge. In this work, we present the synthesis of reactive programs from Temporal Stream Logic ...
Exact and approximate methods for proving unrealizability of syntax-guided synthesis problems
PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation

We consider the problem of automatically establishing that a given syntax-guided-synthesis (SyGuS) problem is unrealizable (i.e., has no solution). We formulate the problem of proving that a SyGuS problem is unrealizable over a finite set of examples as ...
Semantics-guided synthesis

This paper develops a new framework for program synthesis, called semantics-guided synthesis (SemGuS), that allows a user to provide both the syntax and the semantics for the constructs in the language. SemGuS accepts a recursively defined big-step ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2022: Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 2022

1038 pages

ISBN:9781450392655

DOI:10.1145/3519939

General Chair:
Ranjit Jhala
University of California at San Diego, USA
,
Program Chair:
Işil Dillig
University of Texas at Austin, USA

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Conference

PLDI '22

Sponsor:

SIGPLAN

PLDI '22: 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 13 - 17, 2022

CA, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
197
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu JMurphy CGrover AJohnson KReps TD’Antoni L(2024)Synthesizing Formal Semantics from Executable InterpretersProceedings of the ACM on Programming Languages10.1145/36897248:OOPSLA2(362-388)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689724
Nagy SKim JReps TD’Antoni L(2024)Automating Unrealizability Logic: Hoare-Style Proof Synthesis for Infinite Sets of ProgramsProceedings of the ACM on Programming Languages10.1145/36897158:OOPSLA2(113-139)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689715
Kurashige CJi RGiridharan ABarbone MNoor DItzhaky SJhala RPolikarpova N(2024)CCLemma: E-Graph Guided Lemma Discovery for Inductive Equational ProofsProceedings of the ACM on Programming Languages10.1145/36746538:ICFP(818-844)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674653
Mulleners NJeuring JHeeren B(2024)Example-Based Reasoning about the Realizability of Polymorphic ProgramsProceedings of the ACM on Programming Languages10.1145/36746368:ICFP(317-337)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674636
Lubin JFerguson JYe KYim JChasins S(2024)Equivalence by Canonicalization for Synthesis-Backed RefactoringProceedings of the ACM on Programming Languages10.1145/36564538:PLDI(1879-1904)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656453
Ji RZhao YPolikarpova NXiong YHu Z(2024)Superfusion: Eliminating Intermediate Data Structures via Inductive SynthesisProceedings of the ACM on Programming Languages10.1145/36564158:PLDI(939-964)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656415
Ji RZhao YXiong YWang DZhang LHu Z(2024)Decomposition-based Synthesis for Applying Divide-and-Conquer-like Algorithmic ParadigmsACM Transactions on Programming Languages and Systems10.1145/364844046:2(1-59)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3648440
Patton NRahmani KMissula MBiswas JDillig I(2024)Programming-by-Demonstration for Long-Horizon Robot TasksProceedings of the ACM on Programming Languages10.1145/36328608:POPL(512-545)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632860
Miltner AWang ZChaudhuri SDillig I(2024)Relational Synthesis of Recursive Programs via Constraint Annotated Tree AutomataComputer Aided Verification10.1007/978-3-031-65633-0_3(41-63)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-65633-0_3
Sun YPeng XXiong Y(2023)Synthesizing Efficient Memoization AlgorithmsProceedings of the ACM on Programming Languages10.1145/36228007:OOPSLA2(89-115)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622800
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents