检索结果-内蒙古大学图书馆

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2019年第ICFP期3卷 1-28页

作者： Miltner, Anders Maina, Solomon Fisher, Kathleen Pierce, Benjamin C. Walker, David Zdancewic, Steve Princeton Univ Princeton NJ 08544 USA Univ Penn Philadelphia PA 19104 USA Tufts Univ Medford MA 02155 USA

Lenses are programs that can be run both "front to back" and "back to front:' allowing updates to either their source or their target data to be transferred in both directions. Since their introduction by Foster et al., lenses have been extensively studied, extended, and applied. Recent work has also demonstrated how techniques from type-directed program synthesis can be used to efficiently synthesize a simple class of lenses so-called bijective lenses over string data-given a pair of types (regular expressions) and a small number of examples. We extend this synthesis algorithm to a much broader class of lenses, called simple symmetric lenses, including all bijective lenses, all of the popular category of "asymmetric" lenses, and a rich subset of the more powerful "symmetric lenses" proposed by Hofmann et al. Intuitively, simple symmetric lenses allow some information to be present on one side but not the other and vice versa. They are of independent theoretical interest, being the largest class of symmetric lenses that do not rely on persistent internal state. Synthesizing simple symmetric lenses is substantially more challenging than synthesizing bijective lenses: Since some of the information on each side can be "disconnected" from the other side, there will, in general, be many lenses that agree with a given example. To guide the search process, we use stochastic regular expressions and ideas from information theory to estimate the amount of information propagated by a candidate lens, generally preferring lenses that propagate more information, as well as user annotations marking parts of the source and target data structures as either irrelevant or essential. We describe an implementation of simple symmetric lenses and our synthesis procedure as extensions to the Boomerang language. We evaluate its performance on 48 benchmark examples drawn from Flash Fill, Augeas, the bidirectional programming literature, and electronic file format synchronization tasks. Our i

关键词： bidirectional programming Program Synthesis Type-Directed Synthesis Type Systems Information Theory

来源：评论

学校读者我要写书评

暂无评论

Fusing Direct Manipulations into Functional Programs

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2024年第POPL期8卷 1211-1238页

作者： Zhang, Xing Xie, Ruifeng Guo, Guanchen He, Xiao Zan, Tao Hu, Zhenjiang Peking Univ Beijing Peoples R China Univ Sci & Technol Beijing Beijing Peoples R China Longyan Univ Longyan Fujian Peoples R China

bidirectional live programming systems (BLP) enable developers to modify a program by directly manipulating the program output, so that the updated program can produce the manipulated output. One state-of-the-art approach to BLP systems is operation-based, which captures the developer's intention of program modifications by taking how the developer manipulates the output into account. The program modifications are usually hard coded for each direct manipulation in these BLP systems, which are difficult to extend. Moreover, to reflect the manipulations to the source program, these BLP systems trace the modified output to appropriate code fragments and perform corresponding code transformations. Accordingly, they require direct manipulation users be aware of the source code and how it is changed, making "direct" manipulation (on output) be "indirect". In this paper, we resolve this problem by presenting a novel operation-based framework for bidirectional live programming, which can automatically fuse direct manipulations into the source code, thus supporting code-insensitive direct manipulations. Firstly, we design a simple but expressive delta language DM capable of expressing common direct manipulations for output values. Secondly, we present a fusion algorithm that propagates direct manipulations into the source functional programs and applies them to the constants whenever possible;otherwise, the algorithm embeds manipulations into the "proper positions" of programs. We prove the correctness of the fusion algorithm that the updated program executes to get the manipulated output. To demonstrate the expressiveness of DM and the effectiveness of our fusion algorithm, we have implemented FuseDM, a prototype SVG editor that supports GUI-based operations for direct manipulation, and successfully designed 14 benchmark examples starting from blank code using FuseDM.

关键词： bidirectional programming Direct Manipulation FuseDM

来源：评论

学校读者我要写书评

暂无评论

Synthesizing Quotient Lenses

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2018年第ICFP期2卷 1–29页

作者： Maina, Solomon Miltner, Anders Fisher, Kathleen Pierce, Benjamin C. Walker, David Zdancewic, Steve Univ Penn Philadelphia PA 19104 USA Princeton Univ Princeton NJ 08544 USA Tufts Univ Medford MA 02155 USA

Quotient lenses are bidirectional transformations whose correctness laws are loosened" by specified equivalence relations, allowing inessential details in concrete data formats to be suppressed. For example, a programmer could use a quotient lens to define a transformation that ignores the order of fields in XML data, so that two XML files with the same fields but in different orders would be considered the same, allowing a single, simple program to handle them both. Building on a recently published algorithm for synthesizing plain bijective lenses from high-level specifications, we show how to synthesize bijective quotient lenses in three steps. First, we introduce quotient regular expressions (QREs), annotated regular expressions that conveniently mark inessential aspects of string data formats;each QRE specifies, simultaneously, a regular language and an equivalence relation on it. Second, we introduce QRE lenses, i.e., lenses mapping between QREs. Our key technical result is a proof that every QRE lens can be transformed into a functionally equivalent lens that canonizes source and target data just at the "edges" and that uses a bijective lens to map between the respective canonical elements;no internal canonization occurs in a lens in this normal form. Third, we leverage this normalization theorem to synthesize QRE lenses from a pair of QREs and example input-output pairs, reusing earlier work on synthesizing plain bijective lenses. We have implemented QREs and QRE lens synthesis as an extension to the bidirectional programming language Boomerang. We evaluate the effectiveness of our approach by synthesizing QRE lenses between various real-world data formats in the Optician benchmark suite.

关键词： bidirectional programming Program Synthesis Type-Directed Synthesis Type Systems

来源：评论

学校读者我要写书评

暂无评论

bidirectional Evaluation with Direct Manipulation

引用

PROCEEDINGS OF THE ACM ON programming LANGUAGES-PACMPL 2018年第OOPSLA期2卷 1–28页

作者： Mayer, Mikael Kuncak, Viktor Chugh, Ravi Univ Chicago Chicago IL 60637 USA Ecole Polytech Fed Lausanne Lausanne Switzerland

We present an evaluation update (or simply, update) algorithm for a full-featured functional programming language, which synthesizes program changes based on output changes. Intuitively, the update algorithm retraces the steps of the original evaluation, rewriting the program as needed to reconcile differences between the original and updated output values. Our approach, furthermore, allows expert users to define custom lenses that augment the update algorithm with more advanced or domain-specific program updates. To demonstrate the utility of evaluation update, we implement the algorithm in SKETCH -N -SKETCH, a novel direct manipulation programming system for generating HTML documents. In SKETCH -N -SKETCH, the user writes an ML-style functional program to generate MIMI. output. When the user directly manipulates the output using a graphical user interface, the update algorithm reconciles the changes. We evaluate bidirectional evaluation in SKETCH-N-SKETCH by authoring ten examples comprising approximately 1400 lines of code in total. These examples demonstrate how a variety of HTML documents and applications can be developed and edited interactively in SKETCH -N -SKETCH, mitigating the tedious edit-run-view cycle in traditional programming environments.

关键词： bidirectional programming Direct Manipulation Sketch-n-Sketch

来源：评论

学校读者我要写书评

暂无评论

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

引用

ACM TRANSACTIONS ON programming LANGUAGES AND SYSTEMS 2007年第3期29卷 3.1-3.65页

作者： Foster, J. Nathan Greenwald, Michael B. Moore, Jonathan T. Pierce, Benjamin C. Schmitt, Alan Univ Penn Philadelphia PA 19104 USA

We propose a novel approach to the view-update problem for tree-structured data: a domain-specific programming language in which all expressions denote bidirectional 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 space of well-behaved bidirectional 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 bidirectional 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 bidirectional 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.

关键词： bidirectional programming Harmony XML lenses view update problem

来源：评论

学校读者我要写书评

暂无评论

Edit Lenses 12

Edit Lenses

引用

39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of programming Languages

作者： Hofmann, Martin Pierce, Benjamin Wagner, Daniel Univ Munich D-80539 Munich Germany Univ Penn Philadelphia PA 19104 USA

ISBN: (纸本)9781450310833

A lens is a bidirectional transformation between a pair of connected data structures, capable of translating an edit on one structure into an appropriate edit on the other. Many varieties of lenses have been studied, but none, to date, has offered a satisfactory treatment of how edits are represented. Many foundational accounts [5, 7] only consider edits of the form "overwrite the whole structure," leading to poor behavior in many situations by failing to track the associations between corresponding parts of the structures when elements are inserted and deleted in ordered lists, for example. Other theories of lenses do maintain these associations, either by annotating the structures themselves with change information [6, 15] or using auxiliary data structures [2, 4], but every extant theory assumes that the entire original source structure is part of the information passed to the lens. We offer a general theory of edit lenses, which work with descriptions of changes to structures, rather than with the structures hemselves. We identify a simple notion of "editable structure"-a set of states plus a monoid of edits with a partial monoid action on the states-and construct a semantic space of lenses between such structures, with natural laws governing their behavior. We show how a range of constructions from earlier papers on "state-based" lenses can be carried out in this space, including composition, products, sums, list operations, etc. Further, we show how to construct edit lenses for arbitrary containers in the sense of Abbott, Altenkirch, and Ghani [1]. Finally, we show that edit lenses refine a well-known formulation of state-based lenses [7], in the sense that every state-based lens gives rise to an edit lens over structures with a simple overwrite-only edit language, and conversely every edit lens on such structures gives rise to a state-based lens.

关键词： Design Languages Theory algebra bidirectional programming edit lens symmetric

来源：评论

学校读者我要写书评

暂无评论

Incremental Updates for Efficient bidirectional Transformations 11

Incremental Updates for Efficient Bidirectional Transformati...

引用

16th ACM SIGPLAN International Conference on Functional programming (ICFP 11)

作者： Wang, Meng Gibbons, Jeremy Wu, Nicolas Chalmers Univ Technol S-41296 Gothenburg Sweden

ISBN: (纸本)9781450308656

A bidirectional transformation is a pair of mappings between source and view data objects, one in each direction. When the view is modified, the source is updated accordingly. The key to handling large data objects that are subject to relatively small modifications is to process the updates incrementally. Incrementality has been explored in the semi-structured settings of relational databases and graph transformations;this flexibility in structure makes it relatively easy to divide the data into separate parts that can be transformed and updated independently. The same is not true if the data is to be encoded with more general-purpose algebraic datatypes, with transformations defined as functions: dividing data into well-typed separate parts is tricky, and recursions typically create inter-dependencies. In this paper, we study transformations that support incremental updates, and devise a constructive process to achieve this incrementality.

关键词： Functional programming bidirectional programming Incremental Computing Program Transformation View-update Problem

来源：评论

学校读者我要写书评

暂无评论

BiFluX: A bidirectional Functional Update Language for XML 14

BiFluX: A Bidirectional Functional Update Language for XML

引用

16th International Symposium on Principles and Practice of Declarative programming (PPDP)

作者： Pacheco, Hugo Zan, Tao Hu, Zhenjiang Cornell Univ Ithaca NY 14853 USA Grad Univ Adv Studies Hayama Kanagawa Japan Natl Inst Informat Tokyo Japan

ISBN: (纸本)9781450329477

Different XML formats are widely used for data exchange and processing, being often necessary to mutually convert between them. Standard XML transformation languages, like XSLT or XQuery, are unsatisfactory for this purpose since they require writing a separate transformation for each direction. Existing bidirectional transformation languages mean to cover this gap, by allowing programmers to write a single program that denotes both transformations. However, they often 1) induce a more cumbersome programming style than their traditionally unidirectional relatives, to establish the link between source and target formats, and 2) offer limited configurability, by making implicit assumptions about how modifications to both formats should be translated that may not be easy to predict. This paper proposes a bidirectional XML update language called BIFLUX (bidirectional FunctionaL Updates for XML), inspired by the FLUX XML update language. Our language adopts a novel bidirectional programming by update paradigm, where a program succinctly and precisely describes how to update a source document with a target document, in an intuitive way, such that there is a unique " inverse" source query for each update program. BIFLUX extends FLUX with bidirectional actions that describe the connection between source and target formats. We introduce a core BIFLUX language, with a clear and well-behaved bidirectional semantics and a decidable static type system based on regular expression types.

关键词： XML bidirectional programming update languages

来源：评论

学校读者我要写书评

暂无评论

Synthesizing Lenses

Synthesizing Lenses

引用

作者： Miltner, Anders Princeton University

学位级别：博士

Lenses are bidirectional functions that satisfy a set of "round-tripping laws." Lenses arise in a number of domains, and can implement serializer/deserializer pairs, parser/pretty printer pairs, and incremental data structure transformers. Domain-specific languages like Boomerang, Augeas, GRoundTram, BiFluX, BiYacc, Brul, BiGUL, and HOBiT allow programmers to write both transformations with a single program, and guarantee the transformations satisfy the round-tripping laws. However, writing in domain-specific lens languages can be hard, requiring the user to reason about fiddly details of the transformations, often within the context of a complex type system. In this work we introduce Optician, which provides an alternative method of developing lenses – synthesis. We develop a synthesis engine for Boomerang, a lens language for string transformations. Pairs of regular expressions serve as types for Boomerang lenses, which transform strings between the languages of those regular expressions. Instead of manually writing Boomerang lenses, programmers merely need to provide the type of the desired lens and a set of input/output examples describing the lens's behavior. Optician will then synthesize a lens between the provided types that exhibits the demonstrated behavior. We demonstrate how to synthesize three classes of lenses: bijective lenses, quotient lenses, and symmetric lenses. Bijective lenses encode bijections, quotient lenses encode bijections modulo an equivalence relation, and symmetric lenses encode bidirectional transformations that may discard information when going from one format to another. We define a synthesizer that involves two cooperating procedures. One procedure proposes a candidate space of lenses, the second procedure searches through that space. To synthesize quotient lenses, regular expressions are augmented with equivalence information, and the synthesizer generates lenses that translate between the rep

关键词： bidirectional programming Program Synthesis

来源：评论

学校读者我要写书评

暂无评论

Linguistic foundations for bidirectional transformations: invited tutorial 12

Linguistic foundations for bidirectional transformations: in...

引用

Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems

作者： Benjamin C. Pierce University of Pennsylvania Philadelphia PA USA

ISBN: (纸本)9781450312486

Computing is full of situations where two different structures must be "connected" in such a way that updates to each can be propagated to the other. This is a generalization of the classical view update problem, which has been studied for decades in the database community [11, 2, 22]; more recently, related problems have attracted considerable interest in other areas, including programming languages [42, 28, 34, 39, 4, 7, 33, 16, 1, 37, 35, 47, 49] software model transformation [43, 50, 44, 45, 12, 13, 14, 24, 25, 10, 51], user interfaces [38] and system configuration [36]. See [18, 17, 10, 30] for recent *** the fruits of this cross-pollination has been the development of a linguistic perspective on the problem. Rather than taking some view definition language as fixed (e.g., choosing some subset of relational algebra) and looking for tractable ways of "inverting" view definitions to propagate updates from view to source [9], we can directly design new bidirectional programming languages in which every expression defines a pair of functions mapping updates on one structure to updates on the other. Such structures are often called lenses [18].The foundational theory of lenses has been studied extensively [20, 47, 26, 32, 48, 40, 15, 31, 46, 41, 21, 27], and lens-based language designs have been developed in several domains, including strings [5, 19, 3, 36], trees [18, 28, 39, 35, 29], relations [6], graphs [23], and software models [43, 50, 44, 12, 13, 14, 24, 25, 8]. These languages share some common elements with modern functional languages---in particular, they come with very expressive type systems. In other respects, they are rather novel and *** tutorial surveys recent developments in the theory of lenses and the practice of bidirectional programming languages.

关键词： bidirectional programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：