Erik Andersen, Sumit Gulwani, and Zoran Popovic
K-12 mathematics includes many procedures to be learned, such as addition and subtraction, and there are many “buggy” or incorrect procedures that students demonstrate during this learning process. Learning such procedures (both correct and incorrect) from demonstration traces has various applications in computer-aided education. We formalize mathematical procedures as spreadsheet programs, involving loops and conditionals over a given set of base operators, and present a novel algorithm for synthesizing such procedures from demonstrations. Our algorithm is based on dynamic programming and leverages ideas from version-space algebras and template-based program synthesis. Our implementation efficiently synthesized programs to solve 20 common math procedures and reproduce 28 different kinds of bugs that were demonstrated by real students across 9 procedures. Our implementation significantly outperforms SKETCH, a state of the art program synthesizer, on these tasks. We also demonstrate the applicability of our generic program synthesis technology to spreadsheet table transformations, an important domain in end-user programming.
|Publisher||Microsoft Research Technical Report|