Skip to Main content Skip to Navigation
New interface
Journal articles

Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem

Abstract : We propose a novel approach to the view update problem for tree-structured data: a domain- specific programming language in which all expressions denote bi-directional transformations on trees. In one direction, these transformations—dubbed lenses—map a “concrete” tree into a simplified “abstract view”; in the other, they map a modified abstract view, together with the original concrete tree, to a correspondingly modified concrete tree. Our design emphasizes both robustness and ease of use, guaranteeing strong well-behavedness and totality properties for well- typed lenses. We begin by identifying a natural mathematical space of well-behaved bi-directional transformations over arbitrary structures, studying definedness and continuity in this setting. We then instantiate this semantic framework in the form of a collection of lens combinators that can be assembled to describe bi-directional transformations on trees. These combinators include familiar constructs from functional programming (composition, mapping, projection, conditionals, recursion) together with some novel primitives for manipulating trees (splitting, pruning, copying, merging, etc.). We illustrate the expressiveness of these combinators by developing a number of bi-directional list-processing transformations as derived forms. An extended example shows how our combinators can be used to define a lens that translates between a native HTML representation of browser bookmarks and a generic abstract bookmark format.
Document type :
Journal articles
Complete list of metadata
Contributor : Alan Schmitt Connect in order to contact the contributor
Submitted on : Wednesday, May 19, 2010 - 4:27:13 PM
Last modification on : Friday, November 18, 2022 - 9:24:08 AM
Long-term archiving on: : Thursday, September 16, 2010 - 3:05:32 PM


Files produced by the author(s)



J. Nathan Foster, Michael B. Greenwald, Jonathan T. Moore, Benjamin C. Pierce, Alan Schmitt. Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 2007, ACM Transactions on Programming Languages and Systems, 29 (3), pp.17. ⟨10.1145/1232420.1232424⟩. ⟨inria-00484971⟩



Record views


Files downloads