Programming by Demonstration Framework applied to Procedural Math Problems
Erik Andersen, Sumit Gulwani, Zoran Popović · 2014
K-12 mathematics includes many procedures to be learned, such as addition and subtraction, and there are many “buggy ” or incor-rect procedures that students demonstrate during this learning pro-cess. 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 pro-cedures 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 re-produce 28 different kinds of bugs that were demonstrated by real students across 9 procedures. Our implementation significantly out-performs 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 im-portant domain in end-user programming. 1.