Boomerang: Resourceful Lenses for String Data

Abstract : A lens is a bidirectional program. When read from left to right, it denotes an ordinary function that maps inputs to outputs. When read from right to left, it denotes an “update translator” that takes an input together with an updated output and produces a new input that reflects the update. Many variants of this idea have been explored in the literature, but none deal fully with ordered data. If, for example, an update changes the order of a list in the output, the items in the output list and the chunks of the input that generated them can be misaligned, leading to lost or corrupted data. We attack this problem in the context of bidirectional transformations over strings, the primordial ordered data type. We first propose a collection of bidirectional string lens combinators, based on familiar operations on regular transducers (union, concatenation, Kleene-star) and with a type system based on regular expressions. We then design a new semantic space of dictionary lenses, enriching the lenses of Foster et al. (2007b) with support for two additional combinators for marking “reorderable chunks” and their keys. To demonstrate the effectiveness of these primitives, we describe the design and implementation of Boomerang, a full-blown bidirectional programming language with dictionary lenses at its core. We have used Boomerang to build transformers for complex real-world data formats including the SwissProt genomic database. We formalize the essential property of resourcefulness—the correct use of keys to associate chunks in the input and output—by defining a refined semantic space of quasi-oblivious lenses. Several previously studied properties of lenses turn out to have compact characterizations in this space.
Type de document :
Communication dans un congrès
ACM SIGPLAN--SIGACT Symposium on Principles of Programming Languages (POPL'08), Jan 2008, San Francisco, California, United States. pp.407--419, 2008, 〈10.1145/1328897.1328487〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00496456
Contributeur : Alan Schmitt <>
Soumis le : mercredi 30 juin 2010 - 15:58:29
Dernière modification le : jeudi 10 mai 2018 - 01:17:48
Document(s) archivé(s) le : lundi 4 octobre 2010 - 13:03:59

Fichier

Bohannon2008Boomerang-Resource...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Aaron Bohannon, J. Foster, Benjamin Pierce, Alexandre Pilkiewicz, Alan Schmitt. Boomerang: Resourceful Lenses for String Data. ACM SIGPLAN--SIGACT Symposium on Principles of Programming Languages (POPL'08), Jan 2008, San Francisco, California, United States. pp.407--419, 2008, 〈10.1145/1328897.1328487〉. 〈inria-00496456〉

Partager

Métriques

Consultations de la notice

364

Téléchargements de fichiers

131