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.
The specification for program synthesis can be in the form of a logical declarative relationship between inputs and outputs. Examples or demonstration traces are a popular specification choice for end-user programming.4 In program optimization, when viewed as a synthesis problem, the specification consists of inefficient programs that need to be translated into functionally equivalent but more efficient programs.