“Presyn: Modeling Black-Box Components With Probabilistic Synthesis”, 2020-10-09 (; backlinks; similar):
This paper is concerned with synthesizing programs based on black-box oracles: we are interested in the case where there exists an executable implementation of a component or library, but its internal structure is unknown. We are provided with just an API or function signature, and aim to synthesize a program with equivalent behavior.
To attack this problem, we detail Presyn: a [Markov chain] program synthesizer designed for flexible interoperation with existing programs and compiler toolchains. Presyn uses high-level imperative control-flow structures and a pair of cooperating predictive models to efficiently narrow the space of potential programs. These models can be trained effectively on small corpora of synthesized examples.
We evaluate Presyn against 5 leading program synthesizers on a collection of 112 synthesis benchmarks collated from previous studies and real-world software libraries.
We show that Presyn is able to synthesize a wider range of programs than each of them with less human input. We demonstrate the application of our approach to real-world code and software engineering problems with two case studies: accelerator library porting and detection of duplicated library reimplementations.