Search

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 31-32)., In this thesis, I approached deep reinforcement learning agents with the novel idea of augmenting the agent with another neural network called an "Oracle" to gain more insights about the game environment. The Oracle is trained through supervised learning and can be used in various ways with the agent such as a reward shaper or in a pipeline with the agent through which it can transform the original input state into a more enhanced input state with more information. Overall results were not positive as creating a good Oracle can be hard. Creating a better Oracle could possibly display promising results., by Zachery A. Miranda., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 31-32)., In this thesis, I approached deep reinforcement learning agents with the novel idea of augmenting the agent with another neural network called an "Oracle" to gain more insights about the game environment. The Oracle is trained through supervised learning and can be used in various ways with the agent such as a reward shaper or in a pipeline with the agent through which it can transform the original input state into a more enhanced input state with more information. Overall results were not positive as creating a good Oracle can be hard. Creating a better Oracle could possibly display promising results., by Zachery A. Miranda., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 31-32)., In this thesis, I approached deep reinforcement learning agents with the novel idea of augmenting the agent with another neural network called an "Oracle" to gain more insights about the game environment. The Oracle is trained through supervised learning and can be used in various ways with the agent such as a reward shaper or in a pipeline with the agent through which it can transform the original input state into a more enhanced input state with more information. Overall results were not positive as creating a good Oracle can be hard. Creating a better Oracle could possibly display promising results., by Zachery A. Miranda., M. Eng.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 153-161)., Traditionally, machine learning (ML) is used to find a function from data to optimize a numerical score. On the other hand, synthesis is traditionally used to find a function (or a program) that can be derived from a grammar and satisfies a logical specification. The boundary between ML and synthesis has been blurred by some recent work [56,90]. However, this interaction between ML and synthesis has not been fully explored. In this thesis, we focus on the problem of finding a function given large amounts of data such that the function satisfies a logical specification and also optimizes a numerical score over the input data. We present a framework to solve this problem in two impactful application domains: formula simplification in constraint solvers and database entity matching (EM). First, we present a system called Swapper based on our framework that can automatically generate code for efficient formula simplifiers specialized to a class of problems. Formula simplification is an important part of modern constraint solvers, and writing efficient simplifiers has largely been an arduous manual task. Evaluation of Swapper on multiple applications of the Sketch constraint solver showed 15-60% improvement over the existing hand-crafted simplifier in Sketch. Second, we present a system called EM-Synth based on our framework that generates as effective and more interpretable EM rules than the state-of-the-art techniques. Database entity matching is a critical part of data integration and cleaning, and it usually involves learning rules or classifiers from labeled examples. Evaluation of EM-Synth on multiple real-world datasets against other interpretable (shallow decision trees, SIFI [116]) and noninterpretable (SVM, deep decision trees) methods showed that EM-Synth generates more concise and interpretable rules without sacrificing too much accuracy., by Rohit Singh., Ph. D.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 31-32)., In this thesis, I approached deep reinforcement learning agents with the novel idea of augmenting the agent with another neural network called an "Oracle" to gain more insights about the game environment. The Oracle is trained through supervised learning and can be used in various ways with the agent such as a reward shaper or in a pipeline with the agent through which it can transform the original input state into a more enhanced input state with more information. Overall results were not positive as creating a good Oracle can be hard. Creating a better Oracle could possibly display promising results., by Zachery A. Miranda., M. Eng.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 153-161)., Traditionally, machine learning (ML) is used to find a function from data to optimize a numerical score. On the other hand, synthesis is traditionally used to find a function (or a program) that can be derived from a grammar and satisfies a logical specification. The boundary between ML and synthesis has been blurred by some recent work [56,90]. However, this interaction between ML and synthesis has not been fully explored. In this thesis, we focus on the problem of finding a function given large amounts of data such that the function satisfies a logical specification and also optimizes a numerical score over the input data. We present a framework to solve this problem in two impactful application domains: formula simplification in constraint solvers and database entity matching (EM). First, we present a system called Swapper based on our framework that can automatically generate code for efficient formula simplifiers specialized to a class of problems. Formula simplification is an important part of modern constraint solvers, and writing efficient simplifiers has largely been an arduous manual task. Evaluation of Swapper on multiple applications of the Sketch constraint solver showed 15-60% improvement over the existing hand-crafted simplifier in Sketch. Second, we present a system called EM-Synth based on our framework that generates as effective and more interpretable EM rules than the state-of-the-art techniques. Database entity matching is a critical part of data integration and cleaning, and it usually involves learning rules or classifiers from labeled examples. Evaluation of EM-Synth on multiple real-world datasets against other interpretable (shallow decision trees, SIFI [116]) and noninterpretable (SVM, deep decision trees) methods showed that EM-Synth generates more concise and interpretable rules without sacrificing too much accuracy., by Rohit Singh., Ph. D.

Thesis: S.M. in Computer Science and Engineering, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2017., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 53-57)., We present a new system for building source-to-source transformations that can run on multiple programming languages, based on a new way of representing programs called incremental parametric syntax. We construct incremental parametric syntaxes for C, Java, JavaScript, Lua, and Python, and demonstrate two multi-language program transformations that can run on all of them. Our evaluation shows that (1) once a transformation is written, relatively little work is required to configure it for a new language (2) transformations built this way output readable code which preserve the structure of the original, according to participants in our human study, and (3) despite dealing with many languages, our transformations can still handle language corner-cases, and pass 90% of compiler test suites. Incremental parametric syntax is based on the datatypes a la carte approach for constructing modular syntax, but extends it with the notion of a sort injection, which allows intermixing language-specific and generic components in a type-safe and modular fashion. Instead of translating each language to a common representation, this allows having a family of representations, each specific to a language, but sharing common components. Our system can construct an incremental parametric syntax semi-automatically from a third-party library for that language, with the user only writing code for the portions they wish to translate into generic components. The resulting incremental parametric syntax is isomorphic to the original representation, allowing transformations to be fully information-preserving. The user can begin by only translating a small fragment of a language into generic components, enough to support a few transformations, and incrementally add more. Our experience shows that constructing an incremental parametric syntax for a new language is easy, typically taking less than a day of work, and that multi-language transformations built against incremental parametric syntaxes c, by James Koppel., S.M. in Computer Science and Engineering

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016., Cataloged from PDF version of thesis., Includes bibliographical references (pages 45-46)., Rule-based biological models help researchers investigate systems such as cellular signalling pathways. Although these models are generally programmed by hand, some research efforts aim to program them automatically using biological facts extracted from papers via natural language processing. However, NLP facts cannot always be directly converted into mechanistic reaction rules for a rule-based model. Thus, there is a need for tools that can convert biological facts into mechanistic rules in a logically sound way. We construct such a tool specifically for Kappa, a model programming language, by implementing Iota, a logic language for Kappa models. Our tool can translate biological facts into Iota predicates, check predicates for satisfiability, and find models that satisfy predicates. We test our system against realistic use cases, and show that it can construct rule-based mechanistic models that are sound with respect to the semantics of the biological facts from which they were constructed., by Chelsea Voss., M. Eng.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016., Cataloged from PDF version of thesis., Includes bibliographical references (pages 131-139)., SPMD-style (single program multiple data) parallel programming, usually done with MPI, are dominant in high-performance computing on distributed memory machines. This thesis outlines a new methodology to aid in the development of SPMD-style high-performance programs. The new methodology is supported by a new language called MSL that combines ideas from generative programming and software synthesis to simplify the development process as well as to allow programmers to package complex implementation strategies behind clean high-level reusable abstractions. We propose in this thesis the key new language features in MSL and new analyses in order to support synthesis and equivalence checking for programs written in SPMD-style, as well as empirical evaluations of our new methodology., by Zhilei Xu., Ph. D.

While sequential programs represent a simple and natural form for expressing functionality, corresponding distributed implementations get considerably more complex. We examine the possibility of using the sequential computation model for programming distributed systems and requirements for making that possible. The benefits of such an approach include easier specification and reasoning about behaviors in the system, as well as a possibility to directly reuse existing techniques for checking correctness and optimization of sequential programs to produce efficient and reliable distributed implementations.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged student-submitted from PDF version of thesis., Includes bibliographical references (pages 103-115)., As a solution to the problem of information leaks, I propose a policy-agnostic programming paradigm that enforces security and privacy policies by construction. I present the implementation of this paradigm in a new language, Jeeves, that automatically enforces information flow policies describing how sensitive values may flow through computations. In Jeeves, the programmer specifies expressive information flow policies separately from other functionality and relies on the language runtime to customize program behavior based on the policies. Jeeves allows programmers to implement information flow policies once instead of as repeated checks and filters across the program. To provide strong guarantees about Jeeves programs, I present a formalization of the dynamic semantics of Jeeves, define non-interference and policy compliance properties, and provide proofs that Jeeves enforces these properties. To demonstrate the practical feasibility of policy-agnostic programming, I present Jacqueline, a web framework built on Jeeves that enforces policies in database-backed web applications. I provide a formalization of Jacqueline as an extension of Jeeves to include relational operators and proofs that this preserves the policy compliance guarantees. Jacqueline enforces information flow policies end-to-end and runs using an unmodified Python interpreter and SQL database. I show, through several case studies, that Jacqueline reduces the amount of policy code required while incurring limited overheads, by Jean Yang., Ph. D.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (page 63)., In this thesis, I expanded the programming model implemented by the Sketch language to supplement its distributed memory parallelism with shared memory parallelism that uses the popular fork-join model. The primary contribution of this thesis is the means by which the code is assured to be free of race conditions. Sketch uses constraint satisfaction analysis to ensure it synthesizes code the functions properly for all inputs, and I demonstrate how assertions can be generated and inserted into the analysis to guarantee freedom from race conditions. This expanded programming model is then evaluated using test cases to ensure correct operation and benchmarks to examine overall performance., by Jeremy Edward Sharpe., M. Eng.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016., Cataloged from PDF version of thesis., Includes bibliographical references (pages 116-121)., In this thesis, we introduce an architecture for programming productivity tools that relies on a database of execution traces. Our database enables a novel user interaction model for a programmer assistant based on short demonstrations of framework usages in applications. By matching the demonstration traces against the complete traces in the database, our system infers the code snippets for the demonstrated feature including the missing set-up steps. We develop techniques for an interactive trace matching process, and evaluate them on a sample of Swing applications. We show that our system synthesizes code for several features of the Eclipse platform from traces of existing Eclipse plug-ins, and that the generated code is comparable in quality to the tutorial code., by Kuat Yessenov., Ph. D.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 61-66)., SMT solvers are at the heart of a number of software engineering tools. These SMT solvers use a SAT solver as the back-end and convert the high-level constraints given by the user down to low-level boolean formulas that can be efficiently mapped to CNF clauses and fed into a SAT solver. Current SMT solvers are designed to be general purpose solvers that are suited to a wide range of problems. However, SAT solvers are very non-deterministic and hence, it is difficult to optimize a general purpose solver across all different problems. In this thesis, we propose a system that can automatically generate parts of SMT solvers in a way that is tailored to particular problem domains. In particular, we target the translation from high-level constraints to CNF clauses which is one of the crucial parts of all SMT solvers. We achieve this goal by using a combination of program synthesis and machine learning techniques. We use a program synthesis tool called Sketch to generate optimal encoding rules for this translation and then use auto-tuning to only select the subset of these encodings that actually improve the performance for a particular class of problems. Using this technique, the thesis shows that we can improve upon the basic encoding strategy used by CVC4 (a state of the art SMT solver). We can automatically generate variants of the solver tailored to different domains of problems represented in the bit-vector benchmark suite from the SMT competition 2015., by Jeevana Priya Inala., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 61-66)., SMT solvers are at the heart of a number of software engineering tools. These SMT solvers use a SAT solver as the back-end and convert the high-level constraints given by the user down to low-level boolean formulas that can be efficiently mapped to CNF clauses and fed into a SAT solver. Current SMT solvers are designed to be general purpose solvers that are suited to a wide range of problems. However, SAT solvers are very non-deterministic and hence, it is difficult to optimize a general purpose solver across all different problems. In this thesis, we propose a system that can automatically generate parts of SMT solvers in a way that is tailored to particular problem domains. In particular, we target the translation from high-level constraints to CNF clauses which is one of the crucial parts of all SMT solvers. We achieve this goal by using a combination of program synthesis and machine learning techniques. We use a program synthesis tool called Sketch to generate optimal encoding rules for this translation and then use auto-tuning to only select the subset of these encodings that actually improve the performance for a particular class of problems. Using this technique, the thesis shows that we can improve upon the basic encoding strategy used by CVC4 (a state of the art SMT solver). We can automatically generate variants of the solver tailored to different domains of problems represented in the bit-vector benchmark suite from the SMT competition 2015., by Jeevana Priya Inala., M. Eng.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged student-submitted from PDF version of thesis., Includes bibliographical references (pages 103-115)., As a solution to the problem of information leaks, I propose a policy-agnostic programming paradigm that enforces security and privacy policies by construction. I present the implementation of this paradigm in a new language, Jeeves, that automatically enforces information flow policies describing how sensitive values may flow through computations. In Jeeves, the programmer specifies expressive information flow policies separately from other functionality and relies on the language runtime to customize program behavior based on the policies. Jeeves allows programmers to implement information flow policies once instead of as repeated checks and filters across the program. To provide strong guarantees about Jeeves programs, I present a formalization of the dynamic semantics of Jeeves, define non-interference and policy compliance properties, and provide proofs that Jeeves enforces these properties. To demonstrate the practical feasibility of policy-agnostic programming, I present Jacqueline, a web framework built on Jeeves that enforces policies in database-backed web applications. I provide a formalization of Jacqueline as an extension of Jeeves to include relational operators and proofs that this preserves the policy compliance guarantees. Jacqueline enforces information flow policies end-to-end and runs using an unmodified Python interpreter and SQL database. I show, through several case studies, that Jacqueline reduces the amount of policy code required while incurring limited overheads, by Jean Yang., Ph. D.

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 inp, by Rishabh Singh., Ph. D.

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 inp, by Rishabh Singh., Ph. D.

Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015., Cataloged from PDF version of thesis., Includes bibliographical references (pages 57-58)., We present a framework for approximate inference that, given a factor graph and a subset of its variables, produces an approximate marginal distribution over these variables with bounds. The factors of the factor graph are abstracted as as piecewise polynomial functions with lower and upper bounds, and a variant of the variable elimination algorithm solves the inference problem over this abstraction. The resulting distributions bound quantifies the error between it and the true distribution. We also give a set of heuristics for improving the bounds by further refining the binary space partition trees., by Yewen Pu., S.M.

Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015., Cataloged from PDF version of thesis., Includes bibliographical references (pages 57-58)., We present a framework for approximate inference that, given a factor graph and a subset of its variables, produces an approximate marginal distribution over these variables with bounds. The factors of the factor graph are abstracted as as piecewise polynomial functions with lower and upper bounds, and a variant of the variable elimination algorithm solves the inference problem over this abstraction. The resulting distributions bound quantifies the error between it and the true distribution. We also give a set of heuristics for improving the bounds by further refining the binary space partition trees., by Yewen Pu., S.M.

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 inp, by Rishabh Singh., Ph. D.

Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015., Cataloged from PDF version of thesis., Includes bibliographical references (pages 57-58)., We present a framework for approximate inference that, given a factor graph and a subset of its variables, produces an approximate marginal distribution over these variables with bounds. The factors of the factor graph are abstracted as as piecewise polynomial functions with lower and upper bounds, and a variant of the variable elimination algorithm solves the inference problem over this abstraction. The resulting distributions bound quantifies the error between it and the true distribution. We also give a set of heuristics for improving the bounds by further refining the binary space partition trees., by Yewen Pu., S.M.

This paper describes a new approach to program optimization that allows general purpose code to benefit from the optimization power of domain-specific compilers. The key to this approach is a synthesis-based technique to raise the level of abstraction of general-purpose code to enable aggressive domain-specific optimizations. We have been implementing this approach in an extensible system called Herd. The system is designed around a collection of parameterized kernel translators. Each kernel translator is associated with a domain-specific compiler, and the role of each kernel translator is to scan the input code in search of code fragments that can be optimized by the domain-specific compiler embedded within each kernel translator. By leveraging general synthesis technology, it is possible to have a generic kernel translator that can be specialized by compiler developers for each domain-specific compiler, making it easy to build new domain knowledge into the overall system. We illustrate this new approach to build optimizing compilers in two different domains, and highlight research challenges that need to be addressed in order to achieve the ultimate vision.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 85-87)., SMT/SAT solvers are used by many tools for program verification and analysis. Most of these tools have an optimization layer which applies transformations (or "rewrite rules") to simplify the internal representation of the problem. These hard coded rules can drastically affect the performance of the solver. They are usually hand-picked by experts and verified using trial and error. These rules are very domain-specific as well (the domain from which the tool receives its inputs) and leverage the recurring patterns in the domain. The goal of this thesis is to automatically synthesize this optimization layer by learning an optimal set of rules from a corpus of problems taken from a given domain. To achieve this goal, we will use two key technologies: Machine Learning and Program Synthesis (Sketch tool). Sketch is a state of the art tool for generating programs automatically from high level specifications. We propose a Machine Learning and Sketch based method to automatically generate "statistically significant" optimization rules (rules that can be applied at significant number of places in benchmarks from a particular domain) and then generate efficient code to apply the rules for that particular domain. In addition to using Sketch as a tool, we will also use it as a target for this technology. Sketch uses SAT/SMT solver in its back-end, and, like any other tool it has its own hand-built optimization layer. In particular, Sketch uses a set of pre- determined optimization rules to modify the internal representation of the formula in a way that results in faster SAT/SMT solving. Sketch is being used for synthesizing programs in various domains like Storyboard Programming[21], SQL queries for databases[5], MPI based Parallel Programming, Autograder for MOOCs[20]; The current optimizer has to work well for each one of these domains and one of our goals is to have a domain specific optimizer that can take advantage of specific features of each domain. Hence, Sketch is an i, by Rohit Singh., S.M.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013., Cataloged from PDF version of thesis., Includes bibliographical references (pages 71-72)., We present a novel approach to solving SAT problems in parallel by partitioning the entire set of problem clauses into smaller pieces that can be solved by individual threads. We examine the complications that arise with this partitioning, including the idea of global variables, broadcasting global conflict clauses, and a protocol to ensure correctness. Along with this algorithm description, we provide the details of a C++ implementation, ParallelSAT, with a few specific optimizations. Finally, we demonstrate that this approach provides a significant speedup on a set of SAT problems related to program analysis., by Max Nelson., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 55-56)., In this thesis, I analyze the performance and usability benefits of broadcast-based inter-core communication on manycore architecture. The problem of high communication cost on manycore architecture was tackled by a new architecture which allows ecient broadcasting by leveraging an on-chip optical network. I designed the new architecture and API for the new broadcasting feature and implemented them on a multicore simulator called Graphite. I also re-implemented common parallel APIs (barrier and work-stealing) which benet from the cheap broadcasting and showed their ease of use and superior performance versus existing parallel programming libraries through conducting famous benchmarks on the Graphite simulator., by Seo Jin Park., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013., Cataloged from PDF version of thesis., Includes bibliographical references (pages 71-72)., We present a novel approach to solving SAT problems in parallel by partitioning the entire set of problem clauses into smaller pieces that can be solved by individual threads. We examine the complications that arise with this partitioning, including the idea of global variables, broadcasting global conflict clauses, and a protocol to ensure correctness. Along with this algorithm description, we provide the details of a C++ implementation, ParallelSAT, with a few specific optimizations. Finally, we demonstrate that this approach provides a significant speedup on a set of SAT problems related to program analysis., by Max Nelson., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 55-56)., In this thesis, I analyze the performance and usability benefits of broadcast-based inter-core communication on manycore architecture. The problem of high communication cost on manycore architecture was tackled by a new architecture which allows ecient broadcasting by leveraging an on-chip optical network. I designed the new architecture and API for the new broadcasting feature and implemented them on a multicore simulator called Graphite. I also re-implemented common parallel APIs (barrier and work-stealing) which benet from the cheap broadcasting and showed their ease of use and superior performance versus existing parallel programming libraries through conducting famous benchmarks on the Graphite simulator., by Seo Jin Park., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013., Cataloged from PDF version of thesis., Includes bibliographical references (pages 49-50)., I evaluate the ATAC broadcast mechanism as the foundation for a new paradigm in the design of highly scalable concurrent data structures. Shared memory communication is replaced, alleviating the contention that prevents data structures from achieving high performance on the next generation of manycore computers. The alternative model utilizes thread local memory and relies on the ATAC broadcast for inter-core communication, thus avoiding the complicated protocols that contemporary data structures use to mitigate contention. I explain the design of the ATAC barrier and run benchmarking to validate its high performance relative to existing barriers. I explore several concurrent hash map designs built using the ATAC paradigm and evaluate their performance, explaining the memory access patterns under which they achieve scalability., by Nicholas A. Pellegrino., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014., Thesis: S.B., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014., Cataloged from PDF version of thesis., Includes bibliographical references (pages 55-57)., As people share more personal data on the web, it is increasingly important to correctly enforce policies on sensitive data. To address this problem, we have developed Jelf, a web framework that allows the programmer to separate the implementation of information flow policies from the rest of the functionality. The framework builds on previous work on the Jeeves programming language [28, 7] for automatically enforcing privacy policies. Our approach is novel in that it provides end-to-end guarantees by mediating interactions between the front-end, application, and database layers. The programmer only needs to specify information flow policies once for automatic enforcement across the web framework. To build Jelf, we have integrated Jeeves with Python and extended the Django web framework. Jelf consists of a Django template layer, a Python Jeeves application layer, and a Jeeves-compatible database layer. Our Python integration does not require changing the Python interpreter: we use have implemented our solution as a dynamic source transformation and a runtime library. The programmer may use Jelf with Python 2.7 and a standard SQL database. We have used Jelf to implement a conference management system. We describe the implementation and performance of this conference management system, as well as our experience using and running Jelf. Jelf policies comprise less than 3% of the code base and are concentrated in one place. We have deployed this system to collect submissions and reviews for an actual workshop., by Travis J. Hance., M. Eng., S.B.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014., Thesis: S.B., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014., Cataloged from PDF version of thesis., Includes bibliographical references (pages 55-57)., As people share more personal data on the web, it is increasingly important to correctly enforce policies on sensitive data. To address this problem, we have developed Jelf, a web framework that allows the programmer to separate the implementation of information flow policies from the rest of the functionality. The framework builds on previous work on the Jeeves programming language [28, 7] for automatically enforcing privacy policies. Our approach is novel in that it provides end-to-end guarantees by mediating interactions between the front-end, application, and database layers. The programmer only needs to specify information flow policies once for automatic enforcement across the web framework. To build Jelf, we have integrated Jeeves with Python and extended the Django web framework. Jelf consists of a Django template layer, a Python Jeeves application layer, and a Jeeves-compatible database layer. Our Python integration does not require changing the Python interpreter: we use have implemented our solution as a dynamic source transformation and a runtime library. The programmer may use Jelf with Python 2.7 and a standard SQL database. We have used Jelf to implement a conference management system. We describe the implementation and performance of this conference management system, as well as our experience using and running Jelf. Jelf policies comprise less than 3% of the code base and are concentrated in one place. We have deployed this system to collect submissions and reviews for an actual workshop., by Travis J. Hance., M. Eng., S.B.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013., Cataloged from PDF version of thesis., Includes bibliographical references (pages 49-50)., I evaluate the ATAC broadcast mechanism as the foundation for a new paradigm in the design of highly scalable concurrent data structures. Shared memory communication is replaced, alleviating the contention that prevents data structures from achieving high performance on the next generation of manycore computers. The alternative model utilizes thread local memory and relies on the ATAC broadcast for inter-core communication, thus avoiding the complicated protocols that contemporary data structures use to mitigate contention. I explain the design of the ATAC barrier and run benchmarking to validate its high performance relative to existing barriers. I explore several concurrent hash map designs built using the ATAC paradigm and evaluate their performance, explaining the memory access patterns under which they achieve scalability., by Nicholas A. Pellegrino., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014., Thesis: S.B., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014., Cataloged from PDF version of thesis., Includes bibliographical references (pages 55-57)., As people share more personal data on the web, it is increasingly important to correctly enforce policies on sensitive data. To address this problem, we have developed Jelf, a web framework that allows the programmer to separate the implementation of information flow policies from the rest of the functionality. The framework builds on previous work on the Jeeves programming language [28, 7] for automatically enforcing privacy policies. Our approach is novel in that it provides end-to-end guarantees by mediating interactions between the front-end, application, and database layers. The programmer only needs to specify information flow policies once for automatic enforcement across the web framework. To build Jelf, we have integrated Jeeves with Python and extended the Django web framework. Jelf consists of a Django template layer, a Python Jeeves application layer, and a Jeeves-compatible database layer. Our Python integration does not require changing the Python interpreter: we use have implemented our solution as a dynamic source transformation and a runtime library. The programmer may use Jelf with Python 2.7 and a standard SQL database. We have used Jelf to implement a conference management system. We describe the implementation and performance of this conference management system, as well as our experience using and running Jelf. Jelf policies comprise less than 3% of the code base and are concentrated in one place. We have deployed this system to collect submissions and reviews for an actual workshop., by Travis J. Hance., M. Eng., S.B.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 55-56)., In this thesis, I analyze the performance and usability benefits of broadcast-based inter-core communication on manycore architecture. The problem of high communication cost on manycore architecture was tackled by a new architecture which allows ecient broadcasting by leveraging an on-chip optical network. I designed the new architecture and API for the new broadcasting feature and implemented them on a multicore simulator called Graphite. I also re-implemented common parallel APIs (barrier and work-stealing) which benet from the cheap broadcasting and showed their ease of use and superior performance versus existing parallel programming libraries through conducting famous benchmarks on the Graphite simulator., by Seo Jin Park., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Cataloged from student-submitted PDF version of thesis., Includes bibliographical references (pages 55-56)., In this thesis, I analyze the performance and usability benefits of broadcast-based inter-core communication on manycore architecture. The problem of high communication cost on manycore architecture was tackled by a new architecture which allows ecient broadcasting by leveraging an on-chip optical network. I designed the new architecture and API for the new broadcasting feature and implemented them on a multicore simulator called Graphite. I also re-implemented common parallel APIs (barrier and work-stealing) which benet from the cheap broadcasting and showed their ease of use and superior performance versus existing parallel programming libraries through conducting famous benchmarks on the Graphite simulator., by Seo Jin Park., M. Eng.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013., Cataloged from PDF version of thesis., Includes bibliographical references (pages 71-72)., We present a novel approach to solving SAT problems in parallel by partitioning the entire set of problem clauses into smaller pieces that can be solved by individual threads. We examine the complications that arise with this partitioning, including the idea of global variables, broadcasting global conflict clauses, and a protocol to ensure correctness. Along with this algorithm description, we provide the details of a C++ implementation, ParallelSAT, with a few specific optimizations. Finally, we demonstrate that this approach provides a significant speedup on a set of SAT problems related to program analysis., by Max Nelson., M. Eng.

Our goal is to present a completed, semantic formalization of the Jeeves privacy language evaluation engine, based on the original Jeeves constraint semantics defined by Yang et al at POPL12, but sufficiently strong to support a first complete implementation thereof. Specifically, we present and implement a syntactically and semantically completed concrete syntax for Jeeves that meets the example criteria given in the paper. We also present and implement the associated translation to J, but here formulated by a completed and decompositional operational semantic formulation. Finally, we present an enhanced and decompositional, non-substitutional operational semantic formulation and implementation of the J evaluation engine (the dynamic semantics) with privacy constraints. In particular, we show how implementing the constraints can be defined as a monad, and evaluation can be defined as monadic operation on the constraint environment. The implementations are all completed in Haskell, utilizing its almost one-to-one capability to transparently reflect the underlying semantic reasoning when formalized this way. In practice, we have applied the "literate" program facility of Haskell to this report, a feature that enables the source LATEX to also serve as the source code for the implementation (skipping the report-parts as comment regions). The implementation is published as a github project.

Our goal is to present a completed, semantic formalization of the Jeeves privacy language evaluation engine, based on the original Jeeves constraint semantics defined by Yang et al at POPL12, but sufficiently strong to support a first complete implementation thereof. Specifically, we present and implement a syntactically and semantically completed concrete syntax for Jeeves that meets the example criteria given in the paper. We also present and implement the associated translation to J, but here formulated by a completed and decompositional operational semantic formulation. Finally, we present an enhanced and decompositional, non-substitutional operational semantic formulation and implementation of the J evaluation engine (the dynamic semantics) with privacy constraints. In particular, we show how implementing the constraints can be defined as a monad, and evaluation can be defined as monadic operation on the constraint environment. The implementations are all completed in Haskell, utilizing its almost one-to-one capability to transparently reflect the underlying semantic reasoning when formalized this way. In practice, we have applied the "literate" program facility of Haskell to this report, a feature that enables the source LATEX to also serve as the source code for the implementation (skipping the report-parts as comment regions). The implementation is published as a github project.

This paper presents a new approach to select events of interest to a user in a social media setting where events are generated by the activities of the user's friends through their mobile devices. We argue that given the unique requirements of the social media setting, the problem is best viewed as an inductive learning problem, where the goal is to first generalize from the users' expressed "likes" and "dislikes" of specific events, then to produce a program that can be manipulated by the system and distributed to the collection devices to collect only data of interest. The key contribution of this paper is a new algorithm that combines existing machine learning techniques with new program synthesis technology to learn users' preferences. We show that when compared with the more standard approaches, our new algorithm provides up to order-of-magnitude reductions in model training time, and significantly higher prediction accuracies for our target application. The approach also improves on standard machine learning techniques in that it produces clear programs that can be manipulated to optimize data collection and filtering.

This paper presents a new approach to select events of interest to a user in a social media setting where events are generated by the activities of the user's friends through their mobile devices. We argue that given the unique requirements of the social media setting, the problem is best viewed as an inductive learning problem, where the goal is to first generalize from the users' expressed "likes" and "dislikes" of specific events, then to produce a program that can be manipulated by the system and distributed to the collection devices to collect only data of interest. The key contribution of this paper is a new algorithm that combines existing machine learning techniques with new program synthesis technology to learn users' preferences. We show that when compared with the more standard approaches, our new algorithm provides up to order-of-magnitude reductions in model training time, and significantly higher prediction accuracies for our target application. The approach also improves on standard machine learning techniques in that it produces clear programs that can be manipulated to optimize data collection and filtering.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Cataloged from PDF version of thesis., Includes bibliographical references (p. 54-57)., Our goal is to provide a framework that allows the programmer to easily shift responsibility for certain aspects of the program execution to the runtime system. We present specification- enhanced execution, a programming and execution model that allows the programmer to describe certain aspects of program execution using high level specifications that the runtime is responsible for executing. With our approach, the programmer provides an implementation that covers certain aspects of program behavior and a set of specifications that cover other aspects of program behavior. We propose a runtime system that uses concolic (combined concrete and symbolic) execution to simultaneously execute all aspects of the program. We describe LogLog, a language we have designed for using this programming and runtime model. We present a case study applying this programing model to real-word data processing programs and demonstrate the feasibility of both the programming and runtime models., by Jean Yang., S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Cataloged from PDF version of thesis., Includes bibliographical references (p. 54-57)., Our goal is to provide a framework that allows the programmer to easily shift responsibility for certain aspects of the program execution to the runtime system. We present specification- enhanced execution, a programming and execution model that allows the programmer to describe certain aspects of program execution using high level specifications that the runtime is responsible for executing. With our approach, the programmer provides an implementation that covers certain aspects of program behavior and a set of specifications that cover other aspects of program behavior. We propose a runtime system that uses concolic (combined concrete and symbolic) execution to simultaneously execute all aspects of the program. We describe LogLog, a language we have designed for using this programming and runtime model. We present a case study applying this programing model to real-word data processing programs and demonstrate the feasibility of both the programming and runtime models., by Jean Yang., S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011., Cataloged from PDF version of thesis., Includes bibliographical references (p. 42-43)., This thesis presents MATCHMAKER, a new synthesis tool that aims to help programmers use software frameworks by synthesizing source code needed to interact with the framework. Software engineers of today are constantly faced with the task of using or extending large software code bases. This proves to be a challenging endeavor, as object-oriented frameworks tend to grow exceedingly intricate. Functionality is spread out among numerous classes and tailoring it for a specific need requires knowledge of exact components to extend and combine. MATCHMAKER is presented to help programmers understand such complex behavior, especially, to help deal with one common task in using frameworks: connecting two classes so that they can interact with each other. Taking as input two classes that the programmer want to connect, MATCHMAKER observes many real runs of the framework, aggregates relevant execution traces in which similar connections are built by client-framework interactions, and synthesizes the necessary source code the user needs to write to make the connection possible. MATCHMAKER relies on the hypothesis that the logical connection between two objects is fulfilled by a chain of pointer references linking them together, and the earliest possible pointer reference chain (called Critical Chain) is critical to the logical connection. MATCHMAKER employs a new program behavior data engine (called DELIGHT) to find the critical chain, uses a special slicing algorithm to dig out the relevant instructions which form the client-framework protocol from the critical chain, and synthesize the client code from the slices. In this thesis we also demonstrate MATCHMAKER's capability on a range of programming tasks using complex software frameworks such as Eclipse, and evaluate MATCHMAKER's usability and its improvement to programming efficiency by comprehensive user study., by Zhilei Xu., S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Cataloged from PDF version of thesis., Includes bibliographical references (p. 54-57)., Our goal is to provide a framework that allows the programmer to easily shift responsibility for certain aspects of the program execution to the runtime system. We present specification- enhanced execution, a programming and execution model that allows the programmer to describe certain aspects of program execution using high level specifications that the runtime is responsible for executing. With our approach, the programmer provides an implementation that covers certain aspects of program behavior and a set of specifications that cover other aspects of program behavior. We propose a runtime system that uses concolic (combined concrete and symbolic) execution to simultaneously execute all aspects of the program. We describe LogLog, a language we have designed for using this programming and runtime model. We present a case study applying this programing model to real-word data processing programs and demonstrate the feasibility of both the programming and runtime models., by Jean Yang., S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011., Cataloged from PDF version of thesis., Includes bibliographical references (p. 42-43)., This thesis presents MATCHMAKER, a new synthesis tool that aims to help programmers use software frameworks by synthesizing source code needed to interact with the framework. Software engineers of today are constantly faced with the task of using or extending large software code bases. This proves to be a challenging endeavor, as object-oriented frameworks tend to grow exceedingly intricate. Functionality is spread out among numerous classes and tailoring it for a specific need requires knowledge of exact components to extend and combine. MATCHMAKER is presented to help programmers understand such complex behavior, especially, to help deal with one common task in using frameworks: connecting two classes so that they can interact with each other. Taking as input two classes that the programmer want to connect, MATCHMAKER observes many real runs of the framework, aggregates relevant execution traces in which similar connections are built by client-framework interactions, and synthesizes the necessary source code the user needs to write to make the connection possible. MATCHMAKER relies on the hypothesis that the logical connection between two objects is fulfilled by a chain of pointer references linking them together, and the earliest possible pointer reference chain (called Critical Chain) is critical to the logical connection. MATCHMAKER employs a new program behavior data engine (called DELIGHT) to find the critical chain, uses a special slicing algorithm to dig out the relevant instructions which form the client-framework protocol from the critical chain, and synthesize the client code from the slices. In this thesis we also demonstrate MATCHMAKER's capability on a range of programming tasks using complex software frameworks such as Eclipse, and evaluate MATCHMAKER's usability and its improvement to programming efficiency by comprehensive user study., by Zhilei Xu., S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Includes bibliographical references (p. 67-69)., We introduce Storyboard Programming, a new programming model that harnesses the programmer's visual intuition about a problem to synthesize a correct implementation. The motivation for our technique comes from the domain of data-structure manipulations. In this domain, programmers often think in terms of abstract graphical visualizations but have a hard time translating that intuition into low-level pointer manipulating code. We aim to bridge this gap and show that it is possible to derive the low-level implementation automatically from the graphical specifications with little additional input from the programmer. The storyboard in our programming model consists of a series of scenarios which show how the data-structure evolves under different conditions. We present two novel algorithms to synthesize the code from the storyboards. The algorithms derive an abstract domain and a set of correctness conditions automatically from the storyboards. The synthesizer uses the abstract domain to perform abstraction guided combinatorial synthesis. The resulting program is guaranteed to satisfy the correctness conditions derived from the storyboard, and to conform to the high-level structure specified by the programmer. We have implemented our framework successfully on top of the SKETCH system. Our implementation is capable of synthesizing several interesting data-structure manipulations such as insertion, deletion, rotation, reversal over linked list and binary search tree data structures., by Rishabh Singh., S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Includes bibliographical references (p. 67-69)., We introduce Storyboard Programming, a new programming model that harnesses the programmer's visual intuition about a problem to synthesize a correct implementation. The motivation for our technique comes from the domain of data-structure manipulations. In this domain, programmers often think in terms of abstract graphical visualizations but have a hard time translating that intuition into low-level pointer manipulating code. We aim to bridge this gap and show that it is possible to derive the low-level implementation automatically from the graphical specifications with little additional input from the programmer. The storyboard in our programming model consists of a series of scenarios which show how the data-structure evolves under different conditions. We present two novel algorithms to synthesize the code from the storyboards. The algorithms derive an abstract domain and a set of correctness conditions automatically from the storyboards. The synthesizer uses the abstract domain to perform abstraction guided combinatorial synthesis. The resulting program is guaranteed to satisfy the correctness conditions derived from the storyboard, and to conform to the high-level structure specified by the programmer. We have implemented our framework successfully on top of the SKETCH system. Our implementation is capable of synthesizing several interesting data-structure manipulations such as insertion, deletion, rotation, reversal over linked list and binary search tree data structures., by Rishabh Singh., S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Includes bibliographical references (p. 67-69)., We introduce Storyboard Programming, a new programming model that harnesses the programmer's visual intuition about a problem to synthesize a correct implementation. The motivation for our technique comes from the domain of data-structure manipulations. In this domain, programmers often think in terms of abstract graphical visualizations but have a hard time translating that intuition into low-level pointer manipulating code. We aim to bridge this gap and show that it is possible to derive the low-level implementation automatically from the graphical specifications with little additional input from the programmer. The storyboard in our programming model consists of a series of scenarios which show how the data-structure evolves under different conditions. We present two novel algorithms to synthesize the code from the storyboards. The algorithms derive an abstract domain and a set of correctness conditions automatically from the storyboards. The synthesizer uses the abstract domain to perform abstraction guided combinatorial synthesis. The resulting program is guaranteed to satisfy the correctness conditions derived from the storyboard, and to conform to the high-level structure specified by the programmer. We have implemented our framework successfully on top of the SKETCH system. Our implementation is capable of synthesizing several interesting data-structure manipulations such as insertion, deletion, rotation, reversal over linked list and binary search tree data structures., by Rishabh Singh., S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Includes bibliographical references (p. 67-69)., We introduce Storyboard Programming, a new programming model that harnesses the programmer's visual intuition about a problem to synthesize a correct implementation. The motivation for our technique comes from the domain of data-structure manipulations. In this domain, programmers often think in terms of abstract graphical visualizations but have a hard time translating that intuition into low-level pointer manipulating code. We aim to bridge this gap and show that it is possible to derive the low-level implementation automatically from the graphical specifications with little additional input from the programmer. The storyboard in our programming model consists of a series of scenarios which show how the data-structure evolves under different conditions. We present two novel algorithms to synthesize the code from the storyboards. The algorithms derive an abstract domain and a set of correctness conditions automatically from the storyboards. The synthesizer uses the abstract domain to perform abstraction guided combinatorial synthesis. The resulting program is guaranteed to satisfy the correctness conditions derived from the storyboard, and to conform to the high-level structure specified by the programmer. We have implemented our framework successfully on top of the SKETCH system. Our implementation is capable of synthesizing several interesting data-structure manipulations such as insertion, deletion, rotation, reversal over linked list and binary search tree data structures., by Rishabh Singh., S.M.