Accessible programming using program synthesis

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.Cataloged from PDF version of thesis.Includes bibliographical references (pages 143-153).New computing platforms have greatly increased the demand for programmers, but learning to program remains a big challenge. Program synthesis techniques have the potential to revolutionize programming by making it more accessible. In this dissertation, I present three systems, AutoProf, FlashFill, and Storyboard Programming Tool (SPT), that work towards making programming more accessible to a large class of people, namely students and end-users. The AutoProf (Automated Program Feedback) system provides automated feedback to students on introductory programming assignments. It has been successfully piloted on thousands of student submissions from an edX course and is currently being integrated on the MITx and edX platforms. The FlashFill system helps spreadsheet end-users perform semantic string transformations, number transformations, and table lookup transformations using few input-output examples. A part of the FlashFill system is shipping in Microsoft Excel 2013 and was quoted as one of the top features in Excel by many press articles. Finally, the Storyboard Programming Tool helps students write data structure manipulations using visual examples similar to the ones used in textbooks and classrooms. It has been used to synthesize many textbook manipulations over linked list, binary search trees, and graphs. These systems are enabled by new Program Synthesis techniques. Unlike traditional program synthesis approaches where the primary goal was to derive provably correct programs from a complete specification, these synthesis techniques are designed around natural specification mechanisms and intuitive interaction models. Each system relies on a different synthesis technique, but the techniques can be structured and understood in terms of four major components: -- Specification Mechanism: The way users specify the functional behavior of their intended tasks to the system. Our synthesis techniques support more natural and intuitive forms of specification such as input-output examples, reference implementation, intermediate states etc. -- Hypothesis Space: The hypothesis space defines the space of possible programs the system searches over to synthesize the desired program. The hypothesis space can be fixed or parametrized (user-defined) with additional user inputs. The fixed hypothesis spaces are defined using domain-specific languages (DSL) that exploit the domain knowledge to efficiently structure the hypothesis space, which enables the systems to represent a huge set of expressions in these languages succinctly. The parametric hypothesis spaces are defined using intuitive user inputs that allows users to easily define and control the space of possible programs. -- Synthesis Algorithm: We develop new constraint-based and version-space algebra based synthesis algorithms to efficiently learn programs from a large hypothesis space that conform to the specification. -- User Interaction Model: Finally, the user interaction model determines how users refine their intent and provide additional insights to the system for converging to the desired task. We describe the three systems based on the four components, and present experimental evaluation to show the effectiveness of these systems in practice. We also present related work and some future directions to build upon these techniques to make programming accessible to an even larger class of people.by Rishabh Singh.Ph. D