Meng Wang
Jeremy Gibbons
Nicolas Wu
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.
Supplemental Material
- U. A. Acar, G. E. Blelloch, and R. Harper. Adaptive functional programming. ACM Transactions on Programming Languages and Systems, 28:990--1034, November 2006. Google Scholar
Digital Library
- F. Bancilhon and N. Spyratos. Update semantics of relational views. ACM Transactions on Database Systems, 6(4):557--575, 1981. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- G. Gottlob, P. Paolini, and R. Zicari. Properties and update semantics of consistent views. ACM Transactions on Database Systems, 13(4):486--524, 1988. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- R. Hinze and J. Jeuring. Functional Pearl: Weaving a web. Journal of Functional Programming, 11(6):681--689, nov 2001. Google ScholarDigital Library
- R. Hinze, J. Jeuring, and A. Löh. Type-indexed data types. Science of Computer Programming, 51(1-2):117--151, 2004. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- L. Meertens. Designing constraint maintainers for user interaction. ftp://ftp.kestrel.edu/pub/papers/meertens/dcm.ps, CWI, Amsterdam, 1998.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- S. Peyton Jones, editor. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003.Google Scholar
- P. Stevens. Bidirectional model transformations in QVT: semantic issues and open questions. Software and Systems Modeling, 9:7--20, 2010.Google ScholarCross Ref
- J. Voigtländer. Bidirectionalization for free! (Pearl). In Principles of Programming Languages (POPL), pages 165--176, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- P. Wadler. Theorems for free! In Functional Programming Languages and Computer Architecture, pages 347--359, New York, NY, USA, 1989. ACM. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- Incremental updates for efficient bidirectional transformations
Recommendations
Incremental updates for efficient bidirectional transformations
ICFP '11A 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 ...
Incremental Processing of Structured Data in Datalog
GPCE 2022: Proceedings of the 21st ACM SIGPLAN International Conference on Generative Programming: Concepts and ExperiencesIncremental computations react to input changes by updating their outputs. Compared to a non-incremental rerun, incremental computations can provide order-of-magnitude speedups, since often small input changes trigger small output changes. One popular ...
Comments