[talks] Anders Miltner will present his General exam on January 11, 2017 at 1:30pm in CS 302.

[Nicki Gotsis]

Anders Miltner will present his General exam on January 11, 2017 at 1:30pm in CS 302. 

The members of his committee are David Walker, Zak Kincaid, and Brian Kernighan. 



Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. 


SYNTHESIZING BIJECTIVE STRING TRANSFORMERS ANDERS MILTNER 

Bidirectional transformers are groups of functions that convert between data formats. The most common bidirectional transformers are parsers and pretty printers, where a parser converts data from a string representation into a structured representation, and a pretty printer converts data from a structured representation back into a string representation. Other bidirectional transformers convert between data models and GUIs, database views and the underlying tables, and different string formats. Inversion guarantees are usually expected of bidirectional transformers; converting from one data representation and back should not alter the content of the data, beyond the modification of unimportant details like whitespace. Writing these functions in general purpose programming languages requires writing multiple functions and manual reasoning about the invertibility guarantees. Researchers have designed domain specific languages, like Boomerang and biXid, to express bidirectional transformations with a single term, while providing invertibility guarantees. However, coding in these languages requires learning a new paradigm, which has hindered their adoption. We aim to increase the accessibility of one of these languages, Boomerang, by synthesizing the bijective fragment of its programs. Boomerang is a bidirectional language for converting between string representations. The type of a Boomerang program is a pair of regular expressions that specify the format of the source and target data sources. Our program takes two regular expressions and a set of examples as input, and outputs a Boomerang program typed by the input regular expressions, that satisfies the examples. This is done using a method called “type-directed synthesis”, where the types inform the synthesizer how to efficiently search the space of possible programs. Existing work on type-directed synthesis operates on type systems with relatively few isomorphisms between the types. However, each regular expression is equivalent to an infinite number of regular expressions. Synthesis thus requires searching through the equivalent regular expression types as well as through possible terms of the types. Furthermore, the types for complicated data formats are much larger and more complex than the types used in existing work in type-directed synthesis, causing a combinatorial explosion when searching through terms. These issues are resolved through converting the types to a different language with fewer equivalences and treating the user defined types semi-opaquely. We evaluate our procedure on 25 examples taken from Augeas, a program for encoding bidirectional transformations of Linux configuration files, other papers, and microbenchmarks built to highlight the strengths and weaknesses of the program. Our synthesis algorithm is able to synthesize all of these programs in an average of less than half a second. 


Book : 
Types and Programming Languages 
Benjamin Pierce 
2002 
ISBN 0-262-16209-1 
General PL 

Thesis : 
Bidirectional Programming Languages 
Nate Foster 
2010 
http://www.cs.cornell.edu/~jnfoster/papers/jnfoster-dissertation.pdf 
Lenses 

Papers : 
Combinatorial Sketching for Finite Programs 
Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Vijay Saraswat, Sanjit Seshia 
2006 
https://people.csail.mit.edu/asolar/papers/asplos06-final.pdf 
Sketching, Synthesis 

Stochastic Superoptimization 
Eric Schkufza, Rahul Sharma, Alex Aiken 
2013 
http://theory.stanford.edu/~aiken/publications/papers/asplos13.pdf 
Stoke, Stochastic Synthesis 

Dual Syntax for XML Languages 
Claus Brabrand, Anders Møller, Michael I. Schwartzbach 
2005 
http://cs.au.dk/~amoeller/papers/xsugar/journal.pdf 
Bidirectional Programming 

Application of Theorem Proving to Problem Solving 
Cordell Green 
1969 
http://www.ai.sri.com/pubs/files/tn004-green69.pdf 
Classic Paper, Synthesis 

Ch 4 (Focusing) of Frank Pfenning's ATP notes 
Frank Pfenning 
https://www.cs.cmu.edu/~fp/courses/atp/handouts/ch4-focus.pdf 
Automated Theorem Proving / Classic 

Regular Combinators for String Transformations 
Rajeev Alur, Adam Freilich, Mukund Raghothaman 
2014 
https://www.cis.upenn.edu/~alur/Lics14.pdf 
String Transformations 

A Methodology for LISP Program Construction from Examples 
Phillip D. Summers 
1977 
http://dl.acm.org/citation.cfm?id=322002 
Classic Paper, Synthesis 

Type-directed Completion of Partial Expressions 
Daniel Perelman, Sumit Gulwani, Thomas Ball, Dan Grossman 
2012 
http://research.microsoft.com/en-us/um/people/sumitg/pubs/pldi12.pdf 
Synthesis, IDEs 

Learning Semantic String Transformations from Examples 
Rishabh Singh, Sumit Gulwani 
2012 
http://research.microsoft.com/en-us/um/people/sumitg/pubs/semantic.pdf 
String Transformations Synthesis 

Synthesis through Unification 
Rajeev Alur, Pavol Cerny, Arjun Radhakrishna 
2015 
https://www.seas.upenn.edu/~arjunrad/publications/cav15a.pdf 
Synthesis 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20170105/a7a4dfe9/attachment.html>