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.
Type de document :
Article dans une revue
ACM Transactions on Programming Languages and Systems (TOPLAS), ACM, 2007, ACM Transactions on Programming Languages and Systems, 29 (3), pp.17. 〈10.1145/1232420.1232424〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00484971
Contributeur : Alan Schmitt <>
Soumis le : mercredi 19 mai 2010 - 16:27:13
Dernière modification le : jeudi 11 janvier 2018 - 06:22:03
Document(s) archivé(s) le : jeudi 16 septembre 2010 - 15:05:32

Fichier

lenses-toplas-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

249

Téléchargements de fichiers

375