Synthesis Through Unification

Abstract

Given a specification and a set of candidate programs (program space), the program synthesis problem is to find a candidate program that satisfies the specification. We present the synthesis through unification (STUN) approach, which is an extension of the counter-example guided inductive synthesis (CEGIS) approach. In CEGIS, the synthesizer maintains a subset S of inputs and a candidate program \(\mathtt {Prog}\) that is correct for S. The synthesizer repeatedly checks if there exists a counterexample input c such that the execution of \(\mathtt {Prog}\) is incorrect on c. If so, the synthesizer enlarges S to include c, and picks a program from the program space that is correct for the new set S.