Component-Based Synthesis for Complex APIs
Y. Feng, R. Martins, Y. Wang, I. Dillig, T.W. Reps
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.
(Click here to access the paper:
PDF.)