Component-based synthesis for complex APIs

By Yu Feng, Ruben Martins, Yuepeng Wang, Işıl Dillig, Thomas W. Reps. 2017

163 citations recorded by the source corpus.

Component-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 our approach is the use of a compact Petri-net representation to model relationships between methods in an API. Given a target method signature S, our approach performs reachability analysis on the underlying Petri-net model to identify sequences of method calls that could be used to synthesize an implementation of S. The programs synthesized by our algorithm are guaranteed to type check and pass all test cases provided by the user. We have implemented this approach in a tool called SyPet, and used it to successfully synthesize real-world programming tasks extracted from on-line forums and existing code repositories. We also compare SyPet with two state-of-the-art synthesis tools, namely InSynth and CodeHint, and demonstrate that SyPet can synthesize more programs in less time. Finally, we compare our approach with an alternative solution based on hypergraphs and demonstrate its advantages.

Subfields: Artificial Intelligence, Information Systems, Management Information Systems, Natural Language Processing, Code Generation & Program Synthesis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Percy Liang
2. Mirella Lapata
3. Luke S. Zettlemoyer
4. Mohit Bansal
5. Li Dong
6. Panupong Pasupat
7. Graham Neubig
8. Jonathan Berant

In Information Systems

1. Percy Liang
2. Mirella Lapata
3. Panupong Pasupat
4. C. Jermaine
5. Swarat Chaudhuri
6. Li Dong
7. Armando Solar-Lezama
8. David Melski

In Management Information Systems

1. C. Jermaine
2. Swarat Chaudhuri
3. Jacob Steinhardt

In Natural Language Processing

1. Mirella Lapata
2. Percy Liang
3. Panupong Pasupat
4. Li Dong
5. Jonathan Berant
6. Graham Neubig
7. Luke S. Zettlemoyer
8. Mohit Bansal

In Code Generation & Program Synthesis

1. Swarat Chaudhuri
2. C. Jermaine
3. Percy Liang
4. David Melski
5. Yanxin Lu
6. Armando Solar-Lezama
7. A. Aiken
8. Kensen Shi

Citations in the corpus

• SPoC: Search-based Pseudocode to Code (2019, background): “For other domains, while input-output examples are precise in evaluating functional correctness, they provide mostly global signals and inform very little about the intermediate computation, thereby requiring other forms of specification along with input-output examples (e.g., [9, 31]).”
• Coarse-to-Fine Decoding for Neural Semantic Parsing (2018, methodology): “The idea of using sketches as intermediate representations has also been explored in the field of program synthesis (Solar-Lezama, 2008; Zhang and Sun, 2013; Feng et al., 2017).”
• Semantic code search via equational reasoning (2020, methodology): “Type-directed pure-synthesis approaches include Prospector [42], CodeHint [16], and SyPet [12].”
• Data-Driven Program Completion (2017, methodology): “e problem of program synthesis has been considered for a long time (Alur et al. 2015a; Pnueli and Rosner 1989) and recently it has been successfully applied to domain-speci c tasks (Feng et al. 2016, 2017; Polozov and Gulwani 2015; Yaghmazadeh et al. 2016).”
• FrAngel: component-based synthesis with control structures (2018, methodology): “Loops in particular have been a common source of difficulty in component-based synthesis [Feng et al. 2017b; Gulwani et al. 2011a; Jha et al. 2010; Menon et al. 2013].”