19.4.06
Talk: The Weird World of Bi-Directional Programming
Benjamin Pierce. 4pm Monday, 17th April 2006.
[Phil's comment: I had to miss the talk, but I discussed the content with Benjamin. Interesting to see how this is coming on, and that different groups have independently developed similar ideas. One of the competing ideas has a weaker well-formedness condition that looks more like an adjoint or Galois connection than like a bijection, that could be interesting. Benjamin says the next step is a type system for their data model. Their data model seems the same as that used by Buneman, Davidson, Fernandez, and Suciu for UnQL, which allows a nice form of fixpoint definition that doesn't work for XML. The fixpoints always converge if labeled children form a set, but not if they form a list or bag.]
Abstract. Programs generally work in just one direction, from input to answer. But sometimes we need a program to work in two directions: after calculating an answer, we want to UPDATE the answer and then somehow calculate backwards to find a correspondingly updated input. Of course, in general, a given update to the answer may not correspond to a unique update on the input, or to any at all; we need an "update translation policy" that tells us which updates can be translated and how to choose among translations when there are many possibilities. The question of how to determine such a policy has been called the VIEW UPDATE PROBLEM in the database literature.
Many approaches to this problem have been devised over the years; most have taken existing database query languages (such as SQL) as their starting points and then proposed ways of describing or inferring update policies. More recently, several groups have begun working to design entirely new languages in which programs are inherently bi-directional -- i.e., in which every program can be read from left to right as a map from inputs to answers and from right to left as (roughly) a map from updated answers to updated inputs. Moreover, bi-directionality in these languages is treated compositionally: each primitive works in both directions, and the two directions of compound programs can be derived from the two directions of their subcomponents.
This talk charts some interesting regions of the world of bidirectional programming and bi-directional language design, using as a touchstone our experiences at the University of Pennsylvania in the context of the Harmony project, where bi-directional languages -- one for transforming trees and another for relational data -- play a crucial role in the architecture of a universal data synchronizer.
[Phil's comment: I had to miss the talk, but I discussed the content with Benjamin. Interesting to see how this is coming on, and that different groups have independently developed similar ideas. One of the competing ideas has a weaker well-formedness condition that looks more like an adjoint or Galois connection than like a bijection, that could be interesting. Benjamin says the next step is a type system for their data model. Their data model seems the same as that used by Buneman, Davidson, Fernandez, and Suciu for UnQL, which allows a nice form of fixpoint definition that doesn't work for XML. The fixpoints always converge if labeled children form a set, but not if they form a list or bag.]
Abstract. Programs generally work in just one direction, from input to answer. But sometimes we need a program to work in two directions: after calculating an answer, we want to UPDATE the answer and then somehow calculate backwards to find a correspondingly updated input. Of course, in general, a given update to the answer may not correspond to a unique update on the input, or to any at all; we need an "update translation policy" that tells us which updates can be translated and how to choose among translations when there are many possibilities. The question of how to determine such a policy has been called the VIEW UPDATE PROBLEM in the database literature.
Many approaches to this problem have been devised over the years; most have taken existing database query languages (such as SQL) as their starting points and then proposed ways of describing or inferring update policies. More recently, several groups have begun working to design entirely new languages in which programs are inherently bi-directional -- i.e., in which every program can be read from left to right as a map from inputs to answers and from right to left as (roughly) a map from updated answers to updated inputs. Moreover, bi-directionality in these languages is treated compositionally: each primitive works in both directions, and the two directions of compound programs can be derived from the two directions of their subcomponents.
This talk charts some interesting regions of the world of bidirectional programming and bi-directional language design, using as a touchstone our experiences at the University of Pennsylvania in the context of the Harmony project, where bi-directional languages -- one for transforming trees and another for relational data -- play a crucial role in the architecture of a universal data synchronizer.
