Program Synthesis Using Stochastic Techniques

Program synthesis involves discovering a program from an underlying space of programs that satisfies a given specification using some search technique.3 It has many applications including algorithm discovery, optimized implementations, programming assistance,5 and synthesis of small scripts to automate repetitive tasks for end users.4 Its success relies heavily on efficient search algorithms to navigate the underlying huge state space of programs. The authors of the following paper have developed a stochastic search technique and applied it to program optimization. The impressive results of their implementation STOKE on hard program optimization benchmarks illustrate the promising potential of stochastic search to hard program synthesis problems.