Nate Foster

University of Pennsylvania

Bidirectional Programming Languages

The need to edit data through a view arises in a host of applications across many different areas of computing.  Unfortunately, few existing systems have support for updatable views and so, in practice, they are usually implemented using two separate programs -- one to compute views from sources, and another to handle updates.

This rudimentary design is tedious to program, difficult to reason about, and a nightmare to maintain.


In this talk, I will present bidirectional programming languages, which provide an elegant and effective mechanism for describing updatable views.  Unlike programs written in an ordinary language, which only work in one direction, programs in a bidirectional language can be run both forwards and backwards.  When read from left to right, they describe functions that map sources to views.  When read from right to left, they describe functions that map updated views back to updated sources.  Besides eliminating redundancy, these languages can be designed to ensure correctness, guaranteeing by construction that the two transformations work well together.


Starting from the foundations, I will describe a general semantic space of well-behaved bidirectional transformations called lenses.

Then, building on this framework, I will describe a specific language for writing lenses on strings, with a syntax and type system based on the familiar regular operators (union, concatenation, and Kleene star).  Finally, I will describe a collection of extensions addressing the subtle complications that arise when lenses are used to manipulate ordered, ignorable, and confidential data.


Nate Foster will receive his PhD in Computer and Information Science from the University of Pennsylvania in the summer of 2009.

His research centers around problems in programming languages, data management, and security.  Before coming to Penn, he studied at the University of Cambridge (MPhil in History and Philosophy of Science) and Williams College (BA in Computer Science).  He has also worked as an intern at INRIA Rhone-Alpes and IBM Research.  His dissertation was supported by an NSF Graduate Research Fellowship and was recently selected as a winner of Penn's Rubinoff Award.




5130 Upson Hall

Tuesday, April 14, 2009

Refreshments at 3:45pm in the Upson 4th Floor Atrium

Computer Science


Spring 2009