  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 Prog that is correct for S. The synthesizer repeatedly checks
if there exists a counter-example input c such that the execution of 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.
  The STUN approach extends CEGIS with the idea that given a program Prog that
is correct for a subset of inputs, the synthesizer can try to find a program
Prog' that is correct for the rest of the inputs. If Prog and Prog' can be
unified into a program in the program space, then a solution has been found. We
present a generic synthesis procedure based on the STUN approach and specialize
it for three different domains by providing the appropriate unification
operators. We implemented these specializations in prototype tools, and we show
that our tools often per- forms significantly better on standard benchmarks
than a tool based on a pure CEGIS approach.

Programming Languages