Davi M.J. Barbosa
Nate Foster
Michael Greenberg
Benjamin C. Pierce
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.
Supplemental Material
- }}François Bancilhon and Nicolas Spyratos. Update semantics of relational views. ACM Transactions on Database Systems, 6(4):557--575, December 1981. Google Scholar
Digital Library
- }}Jean Berstel, Dominique Perrin, and Christophe Reutenauer. Codes and Automata. Cambridge University Press, 2009.Google ScholarCross Ref
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}J. Nathan Foster and Benjamin C. Pierce. Boomerang Programmer's Manual, 2009. Available from http://www.seas.upenn.edu/~harmony/.Google Scholar
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}David Lutterkort. Augeas-A configuration API. In Linux Symposium, Ottawa, ON, pages 47--56, 2008.Google Scholar
- }}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. Google ScholarDigital Library
- }}Lambert Meertens. Designing constraint maintainers for user interaction, 1998. Manuscript, available from ftp://ftp.kestrel.edu/pub/papers/meertens/dcm.ps.Google Scholar
- }}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.Google ScholarCross Ref
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}Janis Voigtländer. Bidirectionalization for free! In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), Savannah, GA, pages 165--176, January 2009. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
- }}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. Google ScholarDigital Library
Index Terms
- Matching lenses: alignment and view update
Recommendations
Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem
Special issue on POPL 2005We 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: Proceedings of the 15th ACM SIGPLAN international conference on Functional programmingBidirectional 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 ...
Quotient lenses
ICFP '08: Proceedings of the 13th ACM SIGPLAN international conference on Functional programmingThere are now a number of BIDIRECTIONAL PROGRAMMING LANGUAGES, where every program can be read both as a forward transformation mapping one data structure to another and as a reverse transformation mapping an edited output back to a correspondingly ...
Comments