These are some of the notes I took in a writing class at Stanford. They are mainly written for my future reference, but it would be awesome if you also find it helpful. Please feel free to leave comments on the doc if you find errors or have suggestions. :) ♥
Link to Google Doc: https://docs.google.com/document/d/1V65BhNXAGZayEixHHpGD3EU1h8X4iyVfC4etA6Ex1F0/edit?usp=sharing
Preview:
It was rather surprising that such a simple approach can go this far, and this case study should be shared in the community. – Reviewer 1
You can find relevant materials here:
AlphaRegex: Automatic Synthesizer for Regular Expressions from Examples
For those who do not have background in computer science, I wrote brief descriptions for a few terms to help you understand the contents.
Regular expressions?
A regular expression is a way to express a text pattern.
For instance, *.txt represents all text files. A wildcard notation * is used for any sequence of characters; hence, any files with the extension .txt regardless of their names are selected by the regular expression above. You may use it to find all text files in certain directories.
Due to the expressiveness of regular expressions, they are widely used for various text manipulation tasks such as text extraction, classification, etc.
Introductory automata assignments?
Regular expressions are taught in many computer science courses such as automata theory.
In practice, all available characters more or less are used to construct regular expressions. However, in automata classes, students who learn regular expressions for the first time usually only deal with the binary alphabet (i.e. 0 and 1) for simplicity.
Program synthesis?
Program synthesis is the task of automatically generating a program that meets user intent.
More details available here.
This is a sample question in assignments for introductory automata courses.
Find a regular expression for the following language.
L = {w ∈ {0, 1}* | Strings have exactly one pair of consecutive 0s}
For students, they may not understand the meaning of the problem, do not know where to start, or give up after a few trials, not to mention they may come up with wrong answers.
Even for instructors, it takes a while to solve the problem. Moreover, they may wonder whether their regular expression is an optimal solution.
Use of examples
Case 1. When students do not understand the problem, instructors often use examples to clarify the meaning of the problem:
Student: I don’t understand what ‘one pair of consecutive 0s’ in the question means.
Instructor: It means ‘00‘ appears only one time in each string represented by the regular expression. For instance, correct strings would be ‘00‘, ‘1001′, ’010010′ and so on, whereas ’01’, ’11’, and ‘000’ would be wrong examples of the strings.
Case 2. Students often use examples and counterexamples to check whether their answers are correct.
In lieu of having instructors demonstrating the meaning of problems to each student or wondering if their answers are optimal ones, let’s come up with:
A method for synthesizing regular expressions
from a set of simple, basic examples given by users.
In a nutshell, while regular expressions are widely used for lots of text applications, it is still hard for first-timers to construct them. Our method automatically finds an optimal regular expression from a set of examples they provide.
Syntax
e → a ∈ Σ | ε | ∅ | e + e | e • e | e*
Regular expression problems
Students are given with a description of a regular language L. We assume that the description of the language is given by a pair (P, N) of example strings.
Positive examples: P ⊆ Σ*
Negative examples: N ⊆ Σ*
Positive examples are correct strings that must be included in the language, and negative examples are wrong strings that must be excluded from the language.
A regular expression problem: (P, N)
Basic search algorithm
Our algorithm checks all regular expressions in the order of their simplicity until it finds a solution.
Starting from the initial (i.e. simplest) regular expression, it iteratively constructs regular expressions. Because this approach results in a huge search space, we need to effectively prune out the search tree to find a solution in a reasonable time.
Pruning the search space
(Please check the paper for more details!)
In most cases, there are far fewer instructors than students. Working as a teaching assistant for Basics of Computer Systems at University of British Columbia, I remember that my colleagues and I spent great amount of time in grading assignments submitted by hundreds of students and had hard time giving each student qualitative feedback every week. I believe program synthesis can play a great role in that it can automatically generate and solve problems (even with difficulty customized to each student) as well as provide detailed, tailored feedback to students.
Herewith, I leave my super subjective notes and comments on each material to remember and easily refer to them at any point in the future. Hence, this page is constantly updated as I continue exploring the field of programming languages, especially program synthesis in the context of computer-aided education!
DISCLAIMER: This post does not claim to be comprehensive or exhaustive :)
A great starting point to get a sense of what computer-aided education is.
Example-Based Learning in Computer-Aided STEM Education
CACM 2014, Sumit Gulwani
More emphasis on computing education research (CER)
The Importance of Computing Education Research
CoRR 2016, Steve Cooper, Jeff Forbes, Armando Fox, Susanne E. Hambrusch, Andrew Ko, Beth Simon
Automated Feedback Generation
Automated Feedback Generation for Introductory Programming Assignments
PLDI 2013, Rishabh Singh, Sumit Gulwani, Armando Solar-Lezama
Automated (Partial) Grading
Thanks to Loris D’Antoni , I was able to get more information about automated grading on basic problems of concepts in the theory of computation as well as Automata Tutor, the actual implementation of the work with web-based interfaces for end-users. After I received a reply from him this afternoon, I spent the rest of the day reading his follow-up papers, and I must say, I truly enjoyed the time. I am really grateful to his work and appreciate his endeavor to make the service online. You can find the original paper on the work as well as follow-up papers listed below at his website.
Automated Grading of DFA constructions
IJCAI 2013, Rajeev Alur, Loris D’Antoni, Sumit Gulwani, Dileep Kini, Mahesh Viswanathan
How Can Automatic Feedback Help Students Construct Automata?
TOCHI 2015, L. D’Antoni, D. Kini, R. Alur, S. Gulwani, M. Viswanathan, B. Hartmann
Automata Tutor and What We Learned from Building an Online Teaching Tool
Bulletin of EATCS, L. D’Antoni, M. Weaver, A. Weinert, R. Alur
Intelligent Tutoring Systems (ITS) 2016
The Intelligent Tutoring Systems (ITS) 2016 conference is the 13th in an ongoing series of top-flight international conferences on the use of advanced computer technologies and interdisciplinary research for enabling, supporting and enhancing human learning.
The theme of the conference is “Adaptive Learning in real world contexts“. It wishes to stress the need for devising learning systems that can adapt adequately to users, furnishing them the knowledge they are seeking in real world contexts, i.e. systems that are effectively usable in everyday learning situations such as courses in schools or training programs in companies, but also in informal situations such as Web or App provided help in using new technologies. The above theme encourages conference participants to think about this educational need in our increasingly complex everyday world.
Topics of interest to the conference include, but are not limited to:
Innovation and Technology in Computer Science Education (ITiCSE 2016)
ITiCSE 2016, the 21th Annual Conference on Innovation and Technology in Computer Science Education, will normally address aspects of computing education, that is, the education of students who are studying computing.
Within the domain of computing and computing engineering education, papers might cover:
Computer-Supported Cooperative Work and Social Computing (CSCW 2017)
The 20th ACM Conference on Computer-Supported Cooperative Work and Social Computing (CSCW 2017) is the premier venue for presenting research in the design and use of technologies that affect groups, organizations, communities, and networks. Bringing together top researchers and practitioners from academia and industry, CSCW explores the technical, social, material, and theoretical challenges of designing technology to support collaborative work and life activities.
World Conference on Computers in Education (WCCE 2017)
The World Conference on Computers in Education (WCCE 2017) is organized by the International Federation for Information Processing and hosted by the Irish Computer Society. The conference theme, “Tomorrow’s Learning: Involving Everyone”, reflects the long-standing commitment to both learning and technology that has concerned members of the Technical Committee 3 (TC3) and its working groups of the International Federation for Information Processing (IFIP).
The conference will focus on the latest uses of technologies, on computing and technology learning resources, highlighted educational practice, thought-leadership for the future and cutting edge educational research. This event will bring together professionals and novices, experienced teachers and learners, to dream about and discuss future learning environments.
Artificial Intelligence in Education (AIED 2017)
The 18th International Conference on Artificial Intelligence in Education (AIED 2017) is the next in a longstanding series of biennial international conferences for high quality research in intelligent systems and cognitive science for educational computing applications. Empirical and theoretical papers are solicited for submission.
My penchant for program synthesis stems largely from, I believe, its enormous applicability to other fields such as biology, database, data mining, human-computer interaction, machine learning, security, software engineering, and so much more.
Herewith, I leave my super subjective notes and comments on each material to remember and easily refer to them at any point in the future. Hence, this page is constantly updated as I continue exploring the field of programming languages, especially program synthesis!
DISCLAIMER: This post does not claim to be comprehensive or exhaustive :)
Program Synthesis, Microsoft Research
Program synthesis is the task of automatically discovering an executable piece of code given user intent expressed using various forms of constraints such as input-output examples, demonstrations, natural language, etc. Program synthesis has direct applications for various classes of users in the technology pyramid: end users, students and teachers, software developers, and algorithm designers.
Program Synthesis, Wikipedia
Program synthesis is a special form of automatic programming that is most often paired with a technique for formal verification. The goal is to construct automatically a program that provably satisfies a given high-level specification. In contrast to other automatic programming techniques, the specifications are usually non-algorithmic statements of an appropriate logical calculus.
A great starting point to get a sense of what program synthesis is.
Dimensions in Program Synthesis
PPDP 2010, Sumit Gulwani
More detailed introduction to inductive programming.
Inductive Programming Meets the Real World
CACM 2015, Sumit Gulwani, Jose Hernandez-Orallo, Emanuel Kitzelmann, Stephen Muggleton, Ute Schmid, Ben Zorn
Programming by Examples (and its applications in data wrangling)
Marktoberdorf Lecture Notes, Sumit Gulwani
A good summary of PBE-based technologies (in MS software) and industrial point of view.
Program Synthesis in the Industrial World: Inductive, Incremental, Interactive
SYNT 2016, Oleksandr Polozov, Sumit Gulwani, and the rest of the PROSE team
Some publications of technologies incorporated in MS software
FlashMeta: A Framework for Inductive Program Synthesis
OOPSLA 2015, Alex Polozov, Sumit Gulwani
FlashExtract: A Framework for Data Extraction by Examples
PLDI 2014, Vu Le, Sumit Gulwani
Automating String Processing in Spreadsheets using Input-Output Examples
POPL 2011, Sumit Gulwani
Manipulating recursive functions, data structures, etc.
Synthesizing Transformations on Hierarchically Structured Data
PLDI 2016, Navid Yaghmazadeh, Chris Klinger, Isil Dillig, Swarat Chaudhuri
Synthesizing Data Structure Transformations from Input-Output Examples
PLDI 2015, John Feser, Swarat Chaudhuri, Isil Dillig
Biology
Saurabh Srivastava
Founder and CEO of 20n
Database
Alvin Cheung
Assistant Professor in the Department of Computer Science & Engineering at the University of Washington
Data Mining
Using Program Synthesis for Social Recommendations
CIKM 2012, Alvin Cheung, Armando Solar-Lezama, Samuel Madden
Machine Learning
Unsupervised Learning by Program Synthesis
NIPS 2015, Kevin Ellis, Armando Solar-Lezama, Joshua B. Tenenbaum
sk_p: a neural program corrector for MOOCs
CoRR 2016, Yewen Pu, Karthik Narasimhan, Armando Solar-Lezama, Regina Barzilay
Latte: A Language, Compiler, and Runtime for Elegant and Efficient Deep Neural Networks
PLDI 2016, Leonard Truong, Rajkishore Barik, Ehsan Totoni, Hai Liu, Chick Markley, Armando Fox, Tatiana Shpeisman
Software Engineering
Synthesizing Framework Models for Symbolic Execution
ICSE 2016, Jinseong Jeon, Xiaokang Qiu, Jonathan Fetter-Degges, Jeffrey S. Foster, Armando Solar-Lezama
