Boosting component-based synthesis with API usage knowledge
Authors: 
Jiaxin Liu, Wei Dong, Binbin LiuAuthors Info & Claims
Abstract
Component-based synthesis is one of the hottest research areas in automated software engineering. It aims to generate programs from a collection of components like Java library. However, the program space constituted by all the components in the library is fairly large, which leads to a vast number of candidate programs generated for a long time. The intractability of the program space affects the synthesis efficiency of the program and the size of the program generated. In this paper, we propose Itas, a framework of iterative program synthesis via API usage knowledge from the Internet, which can significantly improve the efficiency of program synthesis. Itas aims to constrain the program space by combining two main ideas. First, narrow down the program space from the outside via the guidance of API usage knowledge. Second, expand the program space from the inside via iterative strategy based on knowledge. For evaluation, we collect a set of programming tasks and compare our approach with a program synthesis tool on synthesizing these tasks. The experiment results show that Itas can significantly improve the efficiency of program synthesis, which can reduce the synthesis time by 97.1% than the original synthesizer.
References
[1]
Miltiadis Allamanis, Earl T. Barr, Premkumar T. Devanbu, and Charles A. Sutton. 2018. A Survey of Machine Learning for Big Code and Naturalness. ACM Comput. Surv. 51, 4 (2018), 81:1--81:37.
[2]
Rajeev Alur, Dana Fisman, Rishabh Singh, and Armando Solar-Lezama. 2017. SyGuS-Comp 2017: Results and Analysis. In Proceedings Sixth Workshop on Synthesis, SYNT@CAV 2017, Heidelberg, Germany, 22nd July 2017 (EPTCS, Vol. 260), Dana Fisman and Swen Jacobs (Eds.). 97--115.
[3]
Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. 2017. DeepCoder: Learning to Write Programs. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net. https://openreview.net/forum?id=ByldLrqlx
[4]
Joel Brandt, Philip Guo, Joel Lewenstein, Mira Dontcheva, and Scott Klemmer. 2009. Two Studies of Opportunistic Programming: Interleaving Web Foraging, Learning, and Writing Code. 1589--1598.
[5]
Yu Feng, Ruben Martins, Jacob Van Geffen, Isil Dillig, and Swarat Chaudhuri. 2017. Component-based synthesis of table consolidation and transformation tasks from examples. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, Barcelona, Spain, June 18-23, 2017, Albert Cohen and Martin T. Vechev (Eds.). ACM, 422--436.
[6]
Yu Feng, Ruben Martins, Yuepeng Wang, Isil Dillig, and Thomas Reps. 2017. Component-based synthesis for complex APIs. 599--612.
[7]
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, Portland, OR, USA, June 15-17, 2015, David Grove and Steve Blackburn (Eds.). ACM, 229--239.
[8]
Pranav Garg, Daniel Neider, P. Madhusudan, and Dan Roth. 2016. Learning invariants using decision trees and implication counterexamples. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2016, St. Petersburg, FL, USA, January 20 - 22, 2016, Rastislav Bodík and Rupak Majumdar (Eds.). ACM, 499--512.
[9]
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. 2017. Program Synthesis. Foundations and Trends in Programming Languages 4, 1-2 (2017), 1--119.
[10]
Kangjing Huang, Xiaokang Qiu, Qi Tian, and Yanjun Wang. 2018. Reconciling Enumerative and Symbolic Search in Syntax-Guided Synthesis. CoRR abs/1802.04428 (2018). arXiv:1802.04428 http://arxiv.org/abs/1802.04428
[11]
Xiaochen Li, He Jiang, Yasutaka Kamei, and Xin Chen. 2018. Bridging Semantic Gaps between Natural Languages and APIs with Word Embedding. CoRR abs/1810.09723 (2018). arXiv:1810.09723 http://arxiv.org/abs/1810.09723
[12]
Wang Ling, Phil Blunsom, Edward Grefenstette, Karl Moritz Hermann, Tomás Kociský, Fumin Wang, and Andrew W. Senior. 2016. Latent Predictor Networks for Code Generation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers. The Association for Computer Linguistics.
[13]
David Mandelin, Lin Xu, Rastislav Bodik, and Doug Kimelman. 2005. Jungloid Mining: Helping To Navigate the API Jungle. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) 40, 48--61.
[14]
Daniel Perelman, Sumit Gulwani, Dan Grossman, and Peter Provost. 2014. Test-driven synthesis. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '14, Edinburgh, United Kingdom - June 09 - 11, 2014, Michael F. P. O'Boyle and Keshav Pingali (Eds.). ACM, 408--418.
[15]
Amir Pnueli and Roni Rosner. 1989. On the Synthesis of a Reactive Module. In Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, Austin, Texas, USA, January 11-13, 1989. 179--190.
[16]
Mukund Raghothaman, Yi Wei, and Youssef Hamadi. 2016. SWIM: synthesizing what i mean: code search and idiomatic snippet synthesis. In Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, Austin, TX, USA, May 14-22, 2016, Laura K. Dillon, Willem Visser, and Laurie Williams (Eds.). ACM, 357--367.
[17]
Shambwaditya Saha, Pranav Garg, and P. Madhusudan. 2015. Alchemist: Learning Guarded Affine Functions. In Computer Aided Verification - 27th International Conference, CAV 2015, San Francisco, CA, USA, July 18-24, 2015, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 9206), Daniel Kroening and Corina S. Pasareanu (Eds.). Springer, 440--446.
[18]
Kensen Shi, Jacob Steinhardt, and Percy Liang. 2019. FrAngel: component-based synthesis with control structures. PACMPL 3, POPL (2019), 73:1--73:29.
[19]
Abhishek Udupa, Arun Raghavan, Jyotirmoy V. Deshmukh, Sela Mador-Haim, Milo M. K. Martin, and Rajeev Alur. 2013. TRANSIT: specifying protocols with concolic snippets. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '13, Seattle, WA, USA, June 16-19, 2013, Hans-Juergen Boehm and Cormac Flanagan (Eds.). ACM, 287--296.
[20]
Yuepeng Wang, Yu Feng, Ruben Martins, Arati Kaushik, Isil Dillig, and Steven P. Reiss. 2016. Hunter: next-generation code reuse for Java. In Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2016, Seattle, WA, USA, November 13-18, 2016, Thomas Zimmermann, Jane Cleland-Huang, and Zhendong Su (Eds.). ACM, 1028--1032.
[21]
Pengcheng Yin and Graham Neubig. 2017. A Syntactic Neural Model for General-Purpose Code Generation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, ACL 2017, Vancouver, Canada, July 30 - August 4, Volume 1: Long Papers, Regina Barzilay and Min-Yen Kan (Eds.). Association for Computational Linguistics, 440--450.
Index Terms
- Boosting component-based synthesis with API usage knowledge
Recommendations
Component-based synthesis for complex APIs
POPL '17: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming LanguagesComponent-based approaches to program synthesis assemble programs from a database of existing components, such as methods provided by an API. In this paper, we present a novel type-directed algorithm for component-based synthesis. The key novelty of ...
FrAngel: component-based synthesis with control structures
In component-based program synthesis, the synthesizer generates a program given a library of components (functions). Existing component-based synthesizers have difficulty synthesizing loops and other control structures, and they often require formal ...
Specification-guided component-based synthesis from effectful libraries
Component-based synthesis seeks to build programs using the APIs provided by a set of libraries. Oftentimes, these APIs have effects, which make it challenging to reason about the correctness of potential synthesis candidates. This is because changes to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2020
195 pages
ISBN:9781450381284
DOI:10.1145/3417113
- General Chair:
- John Grundy,
- Program Chairs:
- Claire Le Goues,
- David Lo
Copyright © 2020 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
In-Cooperation
- IEEE CS
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 January 2021
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National key R&D program of China
- National Natural Science Foundation of China
Conference
ASE '20: 35th IEEE/ACM International Conference on Automated Software Engineering
September 21 - 25, 2020
Virtual Event, Australia
Acceptance Rates
Overall Acceptance Rate 82 of 337 submissions, 24%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 96Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)1
Reflects downloads up to 09 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in