Lambda the Ultimate

inactiveTopic A Language for Bi-Directional Tree Transformations
started 5/8/2003; 4:31:25 AM - last post 5/8/2003; 4:31:25 AM
Ehud Lamm - A Language for Bi-Directional Tree Transformations  blueArrow
5/8/2003; 4:31:25 AM (reads: 1530, responses: 0)
A Language for Bi-Directional Tree Transformations
A Language for Bi-Directional Tree Transformations. Michael B. Greenwald, Jonathan T. Moore, Benjamin C. Pierce, and Alan Schmitt. 2003.

We develop a semantic foundation and a core programming language for bi-directional transformations on tree-stuctured data. In one direction, these transformations, called lenses, map a complex "concrete" tree into a simplified "abstract" one; in the other, they map a modified abstract tree, together with the original concrete tree, to a correspondingly modified concrete tree...

We then instantiate our semantic framework as a small programming language, called Hocus Focus, whose expressions denote well-behaved lenses operating on tree-structured data. The primitives include familiar constructs from functional programming (composition, mapping, projection, recursion) together with some novel primitives for manipulating trees (splitting, pruning, pivoting, etc.)

The work presented in this paper is part of the Harmony universal data synchronization project.

The paper includes an extended example showing how Hocus Focus can be used for synchronizing browser bookmarks.

This is a nice example of DSL design. The approach taken is to define a set of primitives, and provide standard cominators (e.g., composition, conditionals etc.)

This is, of course, a standard approach. It directly lends itself to implementation via language embedding.

A longer version of the paper can be found here.

Posted to DSL by Ehud Lamm on 5/8/03; 4:35:03 AM