Boomerang: resourceful lenses for string data
Boomerang: resourceful lenses for string data
复制标题
DOI：
10.1145/1328438.1328487
复制
发表时间：
2008-01
期刊：
影响因子：
--
通讯作者：
A. Bohannon;Nate Foster;B. Pierce;Alexandre Pilkiewicz;Alan Schmitt
中科院分区：
文献类型：
--
作者：
A. Bohannon;Nate Foster;B. Pierce;Alexandre Pilkiewicz;Alan Schmitt
镜头是一个双向程序。当从左到右读取时，它表示将输入映射到输出的普通函数。当从右到左读取时，它表示一个“更新转换器”，它接受输入和更新的输出，并产生反映更新的新输入。这个想法的许多变体已经在文献中进行了探索，但没有一个完全处理有序数据。例如，如果更新更改了输出中列表的顺序，则输出列表中的项和生成它们的输入块可能会不对齐，从而导致数据丢失或损坏。我们在字符串（原始有序数据类型）的双向转换上下文中解决这个问题。我们首先提出了一个双向字符串透镜组合子集合，它基于常规换能器上常见的操作（联合、连接、Kleene-star）和基于正则表达式的类型系统。然后，我们设计了新的字典透镜语义空间，丰富了Foster等人（2007）的透镜，支持两个额外的组合子来标记“可重新排序的块”及其键。为了演示这些原语的有效性，我们描述了Boomerang的设计和实现，Boomerang是一种成熟的双向编程语言，其核心是字典透镜。我们已经使用Boomerang为复杂的现实世界数据格式（包括SwissProt基因组数据库）构建了转换器。我们通过定义准遗忘透镜的精细语义空间，形式化了机智的基本属性——正确使用键来关联输入和输出中的块。先前研究的透镜的一些性质在这个空间中被证明具有紧凑的特征。
A lens is a bidirectional program. When read from left toright, 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 theoutput, 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 anew semantic space of dictionary lenses, enriching the lenses of Foster et al. (2007) with support for two additional combinators for marking ''reorderable chunks'' andtheir 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 format sincluding 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.