Combinators for bi-directional tree transformations - A linguistic approach to the view update problem

摘要

We propose a novel approach to the well-known view update problem for the case of 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 identify a natural space of well-behaved bi-directional transformations over arbitrary structures, study definedness and continuity in this setting; and state a precise connection with the classical theory of "update translation under a constant complement" from databases. We then instantiate this semantic framework in the form of a collection of lens combinators that can be assembled to describe 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, merging; etc.). We illustrate the expressiveness of these combinators by developing a number of bi-directional list-processing transformations as derived forms.