More Web Proxy on the site http://driver.im/

research-article

Incremental updates for efficient bidirectional transformations

Authors:

Jeremy Gibbons,

Nicolas WuAuthors Info & Claims

ACM SIGPLAN Notices, Volume 46, Issue 9

Pages 392 - 403

https://doi.org/10.1145/2034574.2034825

Published: 19 September 2011 Publication History

Abstract

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 interdependencies. In this paper, we study transformations that support incremental updates, and devise a constructive process to achieve this incrementality.

Supplementary Material

MP4 File (_talk11.mp4)

Download
49.83 MB

References

[1]

U. A. Acar, G. E. Blelloch, and R. Harper. Adaptive functional programming. ACM Transactions on Programming Languages and Systems, 28:990--1034, November 2006.

Digital Library

[2]

F. Bancilhon and N. Spyratos. Update semantics of relational views. ACM Transactions on Database Systems, 6(4):557--575, 1981.

Digital Library

[3]

D. M. Barbosa, J. Cretin, N. Foster, M. Greenberg, and B. C. Pierce. Matching lenses: alignment and view update. In International Conference on Functional Programming (ICFP), pages 193--204, New York, NY, USA, 2010. ACM.

Digital Library

[4]

A. Bohannon, J. N. Foster, B. C. Pierce, A. Pilkiewicz, and A. Schmitt. Boomerang: Resourceful lenses for string data. In Principles of Programming Languages, pages 407--419, New York, NY, USA, Jan. 2008. ACM.

Digital Library

[5]

Y. Cui, J. Widom, and J. L. Wiener. Tracing the lineage of view data in a warehousing environment. ACM Transactions on Database Systems, 25:179--227, June 2000.

Digital Library

[6]

K. Czarnecki, J. N. Foster, Z. Hu, R. Lämmel, A. Schürr, and J. F. Terwilliger. Bidirectional transformations: A cross-discipline perspective. In Theory and Practice of Model Transformations, pages 260--283, Berlin, Heidelberg, 2009. Springer-Verlag.

Digital Library

[7]

U. Dayal and P. A. Bernstein. On the correct translation of update operations on relational views. ACM Transactions on Database Systems, 7(3):381--416, 1982.

Digital Library

[8]

Z. Diskin, Y. Xiong, and K. Czarnecki. From state- to delta-based bidirectional model transformations. In Theory and Practice of Model Transformations, ICMT'10, pages 61--76, Berlin, Heidelberg, 2010. Springer-Verlag.

Digital Library

[9]

L. Fegaras. Propagating updates through XML views using lineage tracing. In International Conference on Data Engineering, pages 309--320, Los Alamitos, CA, USA, 2010. IEEE Computer Society.

[10]

J. N. Foster, M. B. Greenwald, J. T. Moore, B. C. Pierce, and A. Schmitt. Combinators for bidirectional tree transformations: A linguistic approach to the view update problem. ACM Transactions on Programming Languages and Systems, 29(3), May 2007. Preliminary version in POPL '05.

Digital Library

[11]

J. N. Foster, B. C. Pierce, and S. Zdancewic. Updatable security views. In Computer Security Foundations, pages 60--74, Washington, DC, USA, 2009. IEEE Computer Society.

Digital Library

[12]

J. N. Foster, A. Pilkiewicz, and B. C. Pierce. Quotient lenses. In International Conference on Functional Programming (ICFP), pages 383--396, New York, NY, USA, 2008. ACM.

Digital Library

[13]

H. Giese and R. Wagner. From model transformation to incremental bidirectional model synchronization. Software and Systems Modeling, 8:21--43, 2009. 10.1007/s10270-008-0089-9.

[14]

G. Gottlob, P. Paolini, and R. Zicari. Properties and update semantics of consistent views. ACM Transactions on Database Systems, 13(4):486--524, 1988.

Digital Library

[15]

S. Hidaka, Z. Hu, K. Inaba, H. Kato, K. Matsuda, and K. Nakano. Bidirectionalizing graph transformations. In International Conference on Functional Programming (ICFP), ICFP '10, pages 205--216, New York, NY, USA, 2010. ACM.

Digital Library

[16]

R. Hinze and J. Jeuring. Functional Pearl: Weaving a web. Journal of Functional Programming, 11(6):681--689, nov 2001.

Digital Library

[17]

R. Hinze, J. Jeuring, and A. Löh. Type-indexed data types. Science of Computer Programming, 51(1-2):117--151, 2004.

Digital Library

[18]

M. Hofmann, B. Pierce, and D. Wagner. Symmetric lenses. In Principles of Programming Languages (POPL), POPL '11, pages 371--384, New York, NY, USA, 2011. ACM.

Digital Library

[19]

Z. Hu, S.-C. Mu, and M. Takeichi. A programmable editor for developing structured documents based on bidirectional transformations. In Workshop on Partial Evaluation and Program Manipulation (PEPM), pages 178--189, New York, NY, USA, 2004. ACM.

Digital Library

[20]

Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. ACM Transactions on Programming Languages and Systems, 20:546--585, May 1998.

Digital Library

[21]

K. Matsuda, Z. Hu, K. Nakano, M. Hamana, and M. Takeichi. Bidirectionalization transformation based on automatic derivation of view complement functions. In International Conference on Functional Programming (ICFP), pages 47--58, New York, NY, USA, 2007. ACM.

Digital Library

[22]

C. McBride. The derivative of a regular type is its type of one-hole contexts (extended abstract). http://strictlypositive.org/diff.pdf, University of Durham, 2001.

[23]

L. Meertens. Designing constraint maintainers for user interaction. ftp://ftp.kestrel.edu/pub/papers/meertens/dcm.ps, CWI, Amsterdam, 1998.

[24]

S.-C. Mu, Z. Hu, and M. Takeichi. An injective language for reversible computation. In Mathematics of Program Construction, volume 3125 of Lecture Notes in Computer Science, pages 289--313. Springer, 2004.

[25]

H. Pacheco and A. Cunha. Generic point-free lenses. In C. Bolduc, J. Desharnais, and B. Ktari, editors, Mathematics of Program Construction, volume 6120 of Lecture Notes in Computer Science, pages 331--352. Springer Berlin / Heidelberg, 2010.

Digital Library

[26]

S. Peyton Jones, editor. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003.

[27]

P. Stevens. Bidirectional model transformations in QVT: semantic issues and open questions. Software and Systems Modeling, 9:7--20, 2010.

[28]

J. Voigtländer. Bidirectionalization for free! (Pearl). In Principles of Programming Languages (POPL), pages 165--176, New York, NY, USA, 2009. ACM.

Digital Library

[29]

J. Voigtländer, Z. Hu, K. Matsuda, and M. Wang. Combining syntactic and semantic bidirectionalization. In International Conference on Functional Programming (ICFP), pages 181--192, New York, NY, USA, 2010. ACM.

Digital Library

[30]

P. Wadler. Theorems for free! In Functional Programming Languages and Computer Architecture, pages 347--359, New York, NY, USA, 1989. ACM.

Digital Library

[31]

M. Wang, J. Gibbons, K. Matsuda, and Z. Hu. Gradual refinement: Blending pattern matching with data abstraction. In C. Bolduc, J. Desharnais, and B. Ktari, editors, Mathematics of Program Construction, volume 6120 of Lecture Notes in Computer Science, pages 397--426. Springer Berlin / Heidelberg, 2010.

Digital Library

Cited By

Lano KKolahdouz-Rahimi SYassipour-Tehrani S(2018)Declarative Specification of Bidirectional Transformations using Design PatternsIEEE Access10.1109/ACCESS.2018.2889399(1-1)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2889399
Zaytsev VBagge A(2014)Parsing in a Broad SenseModel-Driven Engineering Languages and Systems10.1007/978-3-319-11653-2_4(50-67)Online publication date: 2014
https://doi.org/10.1007/978-3-319-11653-2_4
Foster NMatsuda KVoigtländer J(2010)Three complementary approaches to bidirectional programmingProceedings of the 2010 international spring school conference on Generic and Indexed Programming10.1007/978-3-642-32202-0_1(1-46)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1007/978-3-642-32202-0_1
Show More Cited By

Index Terms

Incremental updates for efficient bidirectional transformations
1. Software and its engineering
  1. Software notations and tools
    1. Context specific languages
      1. Specialized application languages
    2. General programming languages
      1. Language features
        Data types and structures
        Polymorphism
      2. Language types
        Functional languages

Recommendations

Incremental updates for efficient bidirectional transformations
ICFP '11: Proceedings of the 16th ACM SIGPLAN international conference on Functional programming

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 ...
An update calculus for expressing type-safe program updates

The dominant share of software development costs is spent on software maintenance, particularly the process of updating programs in response to changing requirements. Currently, such program changes tend to be performed using text editors, an unreliable ...
Applicative bidirectional programming with lenses
ICFP '15

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 with respect to some laws. One way to reduce the development and maintenance ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 46, Issue 9

ICFP '11

September 2011

456 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2034574

Issue’s Table of Contents

ICFP '11: Proceedings of the 16th ACM SIGPLAN international conference on Functional programming
September 2011
470 pages
ISBN:9781450308656
DOI:10.1145/2034773
General Chairs:
Manuel Chakravarty
University of New South Wales, Australia
,
Zhenjiang Hu
National Institute of Informatics, Japan
,
Program Chair:
Olivier Danvy
Aarhus University, Denmark

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 September 2011

Published in SIGPLAN Volume 46, Issue 9

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
354
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lano KKolahdouz-Rahimi SYassipour-Tehrani S(2018)Declarative Specification of Bidirectional Transformations using Design PatternsIEEE Access10.1109/ACCESS.2018.2889399(1-1)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2889399
Zaytsev VBagge A(2014)Parsing in a Broad SenseModel-Driven Engineering Languages and Systems10.1007/978-3-319-11653-2_4(50-67)Online publication date: 2014
https://doi.org/10.1007/978-3-319-11653-2_4
Foster NMatsuda KVoigtländer J(2010)Three complementary approaches to bidirectional programmingProceedings of the 2010 international spring school conference on Generic and Indexed Programming10.1007/978-3-642-32202-0_1(1-46)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1007/978-3-642-32202-0_1
Fritsche LKosiol JSchürr ATaentzer G(2020)Avoiding unnecessary information loss: correct and efficient model synchronization based on triple graph grammarsInternational Journal on Software Tools for Technology Transfer10.1007/s10009-020-00588-723:3(335-368)Online publication date: 8-Sep-2020
https://doi.org/10.1007/s10009-020-00588-7
Horn RPerera RCheney J(2018)Incremental relational lensesProceedings of the ACM on Programming Languages10.1145/32367692:ICFP(1-30)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3236769
MATSUDA KWANG M(2018)Applicative bidirectional programmingJournal of Functional Programming10.1017/S095679681800009628Online publication date: 21-Jun-2018
https://doi.org/10.1017/S0956796818000096
Ricciotti WStolarek JPerera RCheney J(2017)Imperative functional programs that explain their workProceedings of the ACM on Programming Languages10.1145/31102581:ICFP(1-28)Online publication date: 29-Aug-2017
https://dl.acm.org/doi/10.1145/3110258
Hidaka STisi MCabot JHu Z(2016)Feature-based classification of bidirectional transformation approachesSoftware and Systems Modeling (SoSyM)10.1007/s10270-014-0450-015:3(907-928)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s10270-014-0450-0
Matsuda KWang M(2015)Applicative bidirectional programming with lensesACM SIGPLAN Notices10.1145/2858949.278475050:9(62-74)Online publication date: 29-Aug-2015
https://dl.acm.org/doi/10.1145/2858949.2784750
Matsuda KWang MFisher KReppy J(2015)Applicative bidirectional programming with lensesProceedings of the 20th ACM SIGPLAN International Conference on Functional Programming10.1145/2784731.2784750(62-74)Online publication date: 29-Aug-2015
https://dl.acm.org/doi/10.1145/2784731.2784750
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents