Colloquium Details

Bidirectional Programming Languages

Speaker: Nate Foster, University of Pennsylvania

Location: Warren Weaver Hall 1302

Date: April 8, 2009, 11:30 p.m.

Host: Michael Overton


The need to edit data through a view arises in a host of applications across many different areas of computing. Unfortunately, few systems have support for updatable views, so they are typically implemented using two separate programs -- one to compute the view from the source, 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 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 correspondingly modified 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 language for writing lenses on strings, with syntax 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.

Speaker Bio:

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.


In-person attendance only available to those with active NYU ID cards.

How to Subscribe