Title: Program Synthesis from Visual Specification,
Abstract: Program synthesis is the process of automatically translating a specification
into computer code. Traditional synthesis settings require a formal, precise
specification. Motivated by computer education applications where a student
learns to code simple turtle-style drawing programs, we study a novel synthesis
setting where only a noisy user-intention drawing is specified. This allows
students to sketch their intended output, optionally together with their own
incomplete program, to automatically produce a completed program. We formulate
this synthesis problem as search in the space of programs, with the score of a
state being the Hausdorff distance between the program output and the user
drawing. We compare several search algorithms on a corpus consisting of real
user drawings and the corresponding programs, and demonstrate that our
algorithms can synthesize programs optimally satisfying the specification.