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

research-article

Matching lenses: alignment and view update

Authors:

Davi M.J. Barbosa,

Michael Greenberg,

Benjamin C. PierceAuthors Info & Claims

ICFP '10: Proceedings of the 15th ACM SIGPLAN international conference on Functional programming

Pages 193 - 204

https://doi.org/10.1145/1863543.1863572

Published: 27 September 2010 Publication History

Abstract

Bidirectional programming languages are a practical approach to the view update problem. Programs in these languages, called lenses, define both a view and an update policy - i.e., every program can be read as a function mapping sources to views as well as one mapping updated views back to updated sources.

One thorny issue that has not received sufficient attention in the design of bidirectional languages is alignment. In general, to correctly propagate an update to a view, a lens needs to match up the pieces of the view with the corresponding pieces of the underlying source, even after data has been inserted, deleted, or reordered. However, existing bidirectional languages either support only simple strategies that fail on many examples of practical interest, or else propose specific strategies that are baked deeply into the underlying theory.

We propose a general framework of matching lenses that parameterizes lenses over arbitrary heuristics for calculating alignments. We enrich the types of lenses with "chunks" identifying reorderable pieces of the source and view that should be re-aligned after an update, and we formulate behavioral laws that capture essential constraints on the handling of chunks. We develop a core language of matching lenses for strings, together with a set of "alignment combinators" that implement a variety of alignment strategies.

Supplementary Material

JPG File (icfp-tues-1425-cretin.jpg)

Download
11.76 KB

MOV File (icfp-tues-1425-cretin.mov)

Download
95.40 MB

References

[1]

}}François Bancilhon and Nicolas Spyratos. Update semantics of relational views. ACM Transactions on Database Systems, 6(4):557--575, December 1981.

Digital Library

[2]

}}Jean Berstel, Dominique Perrin, and Christophe Reutenauer. Codes and Automata. Cambridge University Press, 2009.

[3]

}}Aaron Bohannon, J. Nathan Foster, Benjamin C. Pierce, Alexandre Pilkiewicz, and Alan Schmitt. Boomerang: Resourceful lenses for string data. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), San Francisco, CA, pages 407--419, January 2008.

Digital Library

[4]

}}Aaron Bohannon, Jeffrey A. Vaughan, and Benjamin C. Pierce. Relational lenses: A language for updateable views. In ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), Chicago, TL, 2006. Extended version available as University of Pennsylvania technical report MS-CIS-05-27.

Digital Library

[5]

}}Krzysztof Czarnecki, J. Nathan Foster, Zhenjiang Hu, Ralf Lämmel, Andy Schürr, and James F. Terwilliger. Bidirectional transformations: A cross-discipline perspective. In ICMT '09: Proceedings of the 2nd International Conference on Theory and Practice of Model Transformations, pages 260--283, Berlin, Heidelberg. 2009. Springer-Verlag.

Digital Library

[6]

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

Digital Library

[7]

}}Zinovy Diskin. Algebraic models for bidirectional model synchronization. In International Conference on Model Driven Engineering Languages and Systems (MoDELS), Toulouse, France, pages 21--36, September 2008.

Digital Library

[8]

}}Zinovy Diskin, Yingfei Xiong, and Krzysztof Czarnecki. From state- to delta-based bidirectional model transformations. In Laurence Tratt and Martin Gogolla, editors, ICMT, volume 6142 of Lecture Notes in Computer Science, pages 61--76. Springer, 2010.

Digital Library

[9]

}}J. Nathan Foster, Michael B. Greenwald, Christian Kirkegaard, Benjamin C. Pierce, and Alan Schmitt. Exploiting schemas in data synchronization. Journal of Computer and System Sciences, 73(4), June 2007. Short version in DBPL '05.

Digital Library

[10]

}}J. Nathan Foster, Michael B. Greenwald, Jonathan T. Moore, Benjamin C. Pierce, and Alan 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.

Digital Library

[11]

}}J. Nathan Foster and Benjamin C. Pierce. Boomerang Programmer's Manual, 2009. Available from http://www.seas.upenn.edu/~harmony/.

[12]

}}J. Nathan Foster, Benjamin C. Pierce, and Steve Zdancewic. Updatable security views. In IEEE Computer Security Foundations Symposium (CSF), Port Jefferson, NY, pages 60--74, July 2009.

Digital Library

[13]

}}J. Nathan Foster, Alexandre Pilkiewcz, and Benjamin C. Pierce. Quotient lenses. In ACM SIGPLAN International Conference on Functional Programming (ICFP), Victoria, BC, pages 383--395, September 2008.

Digital Library

[14]

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

Digital Library

[15]

}}Zhenjiang Hu, Shin-Cheng Mu, and Masato Takeichi. A programmable editor for developing structured documents based on bi-directional transformations. Higher-Order and Symbolic Computation, 21(1-2), June, 2008.

Digital Library

[16]

}}C. Barry Jay and J. Robin B. Cockett. Shapely types and shape polymorphism. In Proceedings of the European Symposium on Programming (ESOP), London, UK, pages 302--316, 1994.

Digital Library

[17]

}}Arthur M. Keller. Algorithms for translating view updates to database updates for views involving selections, projections, and joins. In Proceedings of Fourth Annual ACM Symposium on Principles of Database Systems (PODS), pages 154--163, march 1985. Portland, Oregon.

Digital Library

[18]

}}David Lutterkort. Augeas-A configuration API. In Linux Symposium, Ottawa, ON, pages 47--56, 2008.

[19]

}}Kazutaka Matsuda, Zhenjiang Hu, Keisuke Nakano, Makoto Hamana, and Masato Takeichi. Bidirectionalization transformation based on automatic derivation of view complement functions. In ACM SIGPLAN International Conference on Functional Programming (ICFP), Freiburg, Germany, pages 47--58, 2007.

Digital Library

[20]

}}Lambert Meertens. Designing constraint maintainers for user interaction, 1998. Manuscript, available from ftp://ftp.kestrel.edu/pub/papers/meertens/dcm.ps.

[21]

}}Shin-Cheng Mu, Zhenjiang Hu, and Masato Takeichi. An algebraic approach to bi-directional updating. In ASIAN Symposium on Programming Languages and Systems (APLAS), pages 2--20, November 2004.

[22]

}}Hugo Pacheco and Alcino Cunha. Generic point-free lenses. In International Conference on Mathematics of Program Construction (MPC), Québec City, QC, 2010. To appear.

Digital Library

[23]

}}Perdita Stevens. Bidirectional model transformations in QVT: Semantic issues and open questions. In International Conference on Model Driven Engineering Languages and Systems (MoDELS), Nashville, TN, volume 4735 of Lecture Notes in Computer Science, pages 1--15. Springer-Verlag, 2007.

Digital Library

[24]

}}Janis Voigtländer. Bidirectionalization for free! In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), Savannah, GA, pages 165--176, January 2009.

Digital Library

[25]

}}Meng Wang, Jeremy Gibbons, Kazutaka Matsuda, and Zhenjiang Hu. Gradual refinement: Blending pattern matching with data abstraction. In International Conference on Mathematics of Program Construction (MPC), Québec City, QC, 2010. To appear.

Digital Library

[26]

}}Y. Xiong, Z. Hu, H. Zhao, H. Song, M. Takeichi, and H. Mei. Supporting automatic model inconsistency fixing. In ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE), Amsterdam, Netherlands, pages 315--324. 2009.

Digital Library

Cited By

Tran VKato HHu Z(2024)Bidirectional Programming in BIRDSBidirectional Collaborative Data Management10.1007/978-981-97-6429-7_1(3-24)Online publication date: 12-Dec-2024
https://doi.org/10.1007/978-981-97-6429-7_1
Zhang XGuo GHe XHu Z(2023)Bidirectional Object-Oriented Programming: Towards Programmatic and Direct Manipulation of ObjectsProceedings of the ACM on Programming Languages10.1145/35860357:OOPSLA1(230-255)Online publication date: 6-Apr-2023
https://dl.acm.org/doi/10.1145/3586035
ZHANG HTANG WXIE RWANG MHU Z(2023)Contract lenses: Reasoning about bidirectional programs via calculationJournal of Functional Programming10.1017/S095679682300005933Online publication date: 6-Nov-2023
https://doi.org/10.1017/S0956796823000059
Show More Cited By

Index Terms

Matching lenses: alignment and view update
1. Software and its engineering
  1. Software notations and tools
    1. Context specific languages
      1. Specialized application languages

Recommendations

Boomerang: resourceful lenses for string data
POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

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 ...
Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem
Special issue on POPL 2005

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 ...
Matching lenses: alignment and view update
ICFP '10

Bidirectional programming languages are a practical approach to the view update problem. Programs in these languages, called lenses, define both a view and an update policy - i.e., every program can be read as a function mapping sources to views as well ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICFP '10: Proceedings of the 15th ACM SIGPLAN international conference on Functional programming

September 2010

398 pages

ISBN:9781605587943

DOI:10.1145/1863543

General Chair:
Paul Hudak
Yale University, USA
,
Program Chair:
Stephanie Weirich
University of Pennsylvania, USA

ACM SIGPLAN Notices Volume 45, Issue 9
ICFP '10
September 2010
382 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1932681
Issue’s Table of Contents

Copyright © 2010 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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 September 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP '10

Sponsor:

SIGPLAN

ICFP '10: ACM SIGPLAN International Conference on Functional Programming

September 27 - 29, 2010

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

92
Total Citations
View Citations
421
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)5

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tran VKato HHu Z(2024)Bidirectional Programming in BIRDSBidirectional Collaborative Data Management10.1007/978-981-97-6429-7_1(3-24)Online publication date: 12-Dec-2024
https://doi.org/10.1007/978-981-97-6429-7_1
Zhang XGuo GHe XHu Z(2023)Bidirectional Object-Oriented Programming: Towards Programmatic and Direct Manipulation of ObjectsProceedings of the ACM on Programming Languages10.1145/35860357:OOPSLA1(230-255)Online publication date: 6-Apr-2023
https://dl.acm.org/doi/10.1145/3586035
ZHANG HTANG WXIE RWANG MHU Z(2023)Contract lenses: Reasoning about bidirectional programs via calculationJournal of Functional Programming10.1017/S095679682300005933Online publication date: 6-Nov-2023
https://doi.org/10.1017/S0956796823000059
Lemerre M(2023)Reverse Template Processing Using Abstract InterpretationStatic Analysis10.1007/978-3-031-44245-2_18(403-433)Online publication date: 24-Oct-2023
https://doi.org/10.1007/978-3-031-44245-2_18
Yamaguchi MMatsuda KDavid CWang M(2022)Synbit: synthesizing bidirectional programs using unidirectional sketchesFormal Methods in System Design10.1007/s10703-023-00436-961:2-3(198-247)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s10703-023-00436-9
Kumar AWang ZNi SLi C(2020)AmberProceedings of the VLDB Endowment10.14778/3377369.337738113:5(740-753)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.14778/3377369.3377381
Tran VKato HHu Z(2020)Programmable view update strategies on relationsProceedings of the VLDB Endowment10.14778/3377369.337738013:5(726-739)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.14778/3377369.3377380
Miltner AMaina SFisher KPierce BWalker DZdancewic S(2019)Synthesizing symmetric lensesProceedings of the ACM on Programming Languages10.1145/33416993:ICFP(1-28)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341699
Nishida NVidal G(2019)Characterizing Compatible View Updates in Syntactic BidirectionalizationReversible Computation10.1007/978-3-030-21500-2_5(67-83)Online publication date: 23-May-2019
https://doi.org/10.1007/978-3-030-21500-2_5
Xia LOrchard DWang M(2019)Composing Bidirectional Programs MonadicallyProgramming Languages and Systems10.1007/978-3-030-17184-1_6(147-175)Online publication date: 6-Apr-2019
https://doi.org/10.1007/978-3-030-17184-1_6
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.

EPUB

View this article in ePub.

Media

Figures

Other

Tables

View Table of Contents