Introducing Grammars to Boomerang

Daniel Puller, Adam Magee

Faculty Advisors: Benjamin C. Pierce, J. Nathan Foster

Report | Poster
Official Boomerang Page

Abstract

Most programs work in one direction: given an input, they compute an output. In a bidirectional language, however, programs can be operated in two modes: in the forward direction they map inputs to outputs, and in the reverse direction they map outputs back to inputs. These languages are useful for solving problems in a variety of applications where relationships between data needs to be maintained (e.g. data converters and synchronizers, databases, graphical user interfaces, compilers, system administration, and software engineering.) The goal of this project is to extend Boomerang, a general-purpose bidirectional language (http://www.seas.upenn.edu/~harmony/), to support linear right-recursive grammars. This entails designing a new syntax for describing bidirectional transformations that is both practical and elegant, and successfully integrating it with the Boomerang system. Boomerang is a programming language that produces lenses, which are well-behaved bidirectional transformations on textual data formats. Before this project, it had no support for producing lenses other than using its primitive combinators. Grammars make bidirectional transformations much more succinct, and consequently easier to read and write, make bidirectional programming for new users less painful. Concretely, the project began by building a full-blown standalone compiler, which took a grammar as input and produced a lens. After completing this task, the compiler was redesigned and directly integrated with the Boomerang compiler (specifically its parser, typechecker, and interpreter). We based our syntax on an intuitive representation of lens transformations, with guidance from Benjamin Pierce and Nate Foster.

University of Pennsylvania Senior Project 2009