ProSy: API-Based Synthesis with Probabilistic Model
- PDF / 1,162,288 Bytes
- 24 Pages / 595 x 842 pts (A4) Page_size
- 1 Downloads / 206 Views
ProSy: API-Based Synthesis with Probabilistic Model Bin-Bin Liu1 , Wei Dong2,∗ , Member, CCF, Jia-Xin Liu1 , Ya-Ting Zhang1 , and Dai-Yan Wang1 1 2
College of Computer Science, National University of Defense Technology, Changsha 410072, China Key Laboratory of Software Engineering for Complex Systems, College of Computer Science, National University of Defense Technology, Changsha 410072, China
E-mail: {liubinbin09, wdong, liujiaxin18, zhangyating18, wangdaiyan}@nudt.edu.cn Received April 10, 2020; revised October 22, 2020. Abstract Program synthesis is an exciting topic that desires to generate programs satisfying user intent automatically. But in most cases, only small programs for simple or domain-specific tasks can be synthesized. The major obstacle of synthesis lies in the huge search space. A common practice in addressing this problem is using a domain-specific language, while many approaches still wish to synthesize programs in general programming languages. With the rapid growth of reusable libraries, component-based synthesis provides a promising way, such as synthesizing Java programs which are only composed of APIs (application programming interfaces). However, the efficiency of searching for proper solutions for complex tasks is still a challenge. Given an unfamiliar programming task, programmers would search for API usage knowledge from various coding resources to reduce the search space. Considering this, we propose a novel approach named ProSy to synthesize API-based programs in Java. The key novelty is to retrieve related knowledge from Javadoc and Stack Overflow and then construct a probabilistic reachability graph. It assigns higher probabilities to APIs that are more likely to be used in implementing the given task. In the synthesis process, the program sketch with a higher probability will be considered first; thus, the number of explored reachable paths would be decreased. Some extension and optimization strategies are further studied in the paper. We implement our approach and conduct several experiments on it. We compare ProSy with SyPet and other state-of-the-art API-based synthesis approaches. The experimental results show that ProSy reduces the synthesis time of SyPet by up to 80%. Keywords synthesis
1
application programming interface (API)-based program, Petri net, probabilistic reachability graph, program
Introduction
Program synthesis, the task of automatically generating a program that satisfies user intent, has been regarded as the holy grail of computer science [1] and one of the most central problems in the theory of programming [2] . Many different techniques have been proposed for program synthesis, such as programming by examples [3] , syntax-guided synthesis [4] , componentbased synthesis [5] , program sketching [6] , and neural programming [7, 8] . The key problem to be solved in most of these techniques is how to specify the user intent accurately and then investigate efficient search
techniques in the program space. Due to the huge search space, many approaches define d
Data Loading...
