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 provide support for updatable views. In practice, when they are needed, updatable views are usually implemented using two separate programs: one to compute the view from the source and another to handle updates. This rudimentary design is tedious for programmers, difficult to reason about, and a nightmare to maintain. This dissertation describes bidirectional programming languages, which provide an elegant mechanism for describing updatable views. Unlike programs written in an ordinary language, which only work in one direction, programs written in a bidirectional language can be run both forwards and backwards: from left to right, they describe functions that map sources to views, and 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 functions work well together. Starting from the foundations, we identify a general semantic space of well-behaved bidirectional transformations called lenses. Then, building on this foundation, we describe a specific language for defining lenses for strings with syntax based on the regular operators. We also present extensions to the basic framework that address the complications that arise when lenses are used to manipulate sources containing inessential, ordered, and confidential data, and we describe the implementation of these features in the Boomerang language