Kazutaka Matsuda
Skip Abstract Section
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 with respect to some laws. One way to reduce the development and maintenance effort of bidirectional transformations is to have specialized languages in which the resulting programs are bidirectional by construction---giving rise to the paradigm of bidirectional programming. In this paper, we develop a framework for applicative-style and higher-order bidirectional programming, in which we can write bidirectional transformations as unidirectional programs in standard functional languages, opening up access to the bundle of language features previously only available to conventional unidirectional languages. Our framework essentially bridges two very different approaches of bidirectional programming, namely the lens framework and Voigtländer's semantic bidirectionalization, creating a new programming style that is able to bag benefits from both.
- F. Bancilhon and N. Spyratos. Update semantics of relational views. ACM Trans. Database Syst., 6(4):557–575, 1981. Google Scholar
Digital Library
- D. M. J. Barbosa, J. Cretin, N. Foster, M. Greenberg, and B. C. Pierce. Matching lenses: alignment and view update. In P. Hudak and S. Weirich, editors, ICFP, pages 193–204. ACM, 2010. Google ScholarDigital Library
- R. S. Bird, J. Gibbons, S. Mehner, J. Voigtländer, and T. Schrijvers. Understanding idiomatic traversals backwards and forwards. In C. chieh Shan, editor, Haskell, pages 25–36. ACM, 2013. Google ScholarDigital Library
- A. Bohannon, J. N. Foster, B. C. Pierce, A. Pilkiewicz, and A. Schmitt. Boomerang: resourceful lenses for string data. In G. C. Necula and P. Wadler, editors, POPL, pages 407–419. ACM, 2008. Google ScholarDigital Library
- A. Chlipala. Parametric higher-order abstract syntax for mechanized semantics. In J. Hook and P. Thiemann, editors, ICFP, pages 143–156. ACM, 2008. Google ScholarDigital Library
- U. Dayal and P. A. Bernstein. On the correct translation of update operations on relational views. ACM Trans. Database Syst., 7(3):381– 416, 1982. Google ScholarDigital Library
- T. Ellis. Category and lenses, Sep 2012.Google Scholar
- Blog post: http://web.jaguarpaw.co.uk/~tom/blog/posts/ 2012-09-30-category-and-lenses.html.Google Scholar
- L. Fegaras. Propagating updates through XML views using lineage tracing. In F. Li, M. M. Moro, S. Ghandeharizadeh, J. R. Haritsa, G. Weikum, M. J. Carey, F. Casati, E. Y. Chang, I. Manolescu, S. Mehrotra, U. Dayal, and V. J. Tsotras, editors, ICDE, pages 309–320. IEEE, 2010.Google Scholar
- 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 Trans. Program. Lang. Syst., 29(3), 2007. Google ScholarDigital Library
- J. N. Foster, A. Pilkiewicz, and B. C. Pierce. Quotient lenses. In J. Hook and P. Thiemann, editors, ICFP, pages 383–396. ACM, 2008. Google ScholarDigital Library
- N. Foster, K. Matsuda, and J. Voigtländer. Three complementary approaches to bidirectional programming. In J. Gibbons, editor, SSGIP, volume 7470 of Lecture Notes in Computer Science, pages 1–46. Springer, 2010. Google ScholarDigital Library
- Y. Hayashi, D. Liu, K. Emoto, K. Matsuda, Z. Hu, and M. Takeichi. A web service architecture for bidirectional XML updating. In G. Dong, X. Lin, W. Wang, Y. Yang, and J. X. Yu, editors, APWeb/WAIM, volume 4505 of Lecture Notes in Computer Science, pages 721–732. Springer, 2007. Google ScholarDigital Library
- S. J. Hegner. Foundations of canonical update support for closed database views. In S. Abiteboul and P. C. Kanellakis, editors, ICDT, volume 470 of Lecture Notes in Computer Science, pages 422–436. Springer, 1990. Google ScholarDigital Library
- S. Hidaka, Z. Hu, K. Inaba, H. Kato, K. Matsuda, and K. Nakano. Bidirectionalizing graph transformations. In P. Hudak and S. Weirich, editors, ICFP, pages 205–216. ACM, 2010. Google ScholarDigital Library
- M. Hofmann, B. C. Pierce, and D. Wagner. Symmetric lenses. In T. Ball and M. Sagiv, editors, POPL, pages 371–384. ACM, 2011. Google ScholarDigital Library
- Z. Hu, S.-C. Mu, and M. Takeichi. A programmable editor for developing structured documents based on bidirectional transformations. In N. Heintze and P. Sestoft, editors, PEPM, pages 178–189. ACM, 2004. Google ScholarDigital Library
- M. Jaskelioff and R. O’Connor. A representation theorem for secondorder functionals. CoRR, abs/1402.1699, 2014.Google Scholar
- S. Lindley, P. Wadler, and J. Yallop. Idioms are oblivious, arrows are meticulous, monads are promiscuous. Electr. Notes Theor. Comput. Sci., 229(5):97–117, 2011. Google ScholarDigital Library
- S. Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Matheematics. Springer, second edition edition, 1998.Google Scholar
- K. Matsuda, Z. Hu, K. Nakano, M. Hamana, and M. Takeichi. Bidirectionalization transformation based on automatic derivation of view complement functions. In R. Hinze and N. Ramsey, editors, ICFP, pages 47–58. ACM, 2007. Google ScholarDigital Library
- K. Matsuda and M. Wang. Bidirectionalization for free with runtime recording: or, a light-weight approach to the view-update problem. In R. Peña and T. Schrijvers, editors, PPDP, pages 297–308. ACM, 2013. Google ScholarDigital Library
- K. Matsuda and M. Wang. “Bidirectionalization for free” for monomorphic transformations. Science of Computer Programming, 2014. DOI: 10.1016/j.scico.2014.07.008.Google ScholarDigital Library
- C. McBride and R. Paterson. Applicative programming with effects. J. Funct. Program., 18(1):1–13, 2008. Google ScholarDigital Library
- B. Milewski. Lenses, Stores, and Yoneda, Oct 2013.Google Scholar
- blog post: http://bartoszmilewski.com/2013/10/08/ lenses-stores-and-yoneda/.Google Scholar
- S.-C. Mu, Z. Hu, and M. Takeichi. An algebraic approach to bidirectional updating. In W.-N. Chin, editor, APLAS, volume 3302 of Lecture Notes in Computer Science, pages 2–20. Springer, 2004.Google Scholar
- R. O’Connor. Functor is to lens as applicative is to biplate: Introducing multiplate. CoRR, abs/1103.2841, 2011. Accepted in WGP’11, but not included in its proceedings. Google ScholarDigital Library
- H. Pacheco, Z. Hu, and S. Fischer. Monadic combinators for "putback" style bidirectional programming. In W.-N. Chin and J. Hage, editors, PEPM, pages 39–50. ACM, 2014. Google ScholarDigital Library
- R. Paterson. A new notation for arrows. In B. C. Pierce, editor, ICFP, pages 229–240. ACM, 2001. Google ScholarDigital Library
- R. Paterson. Constructing applicative functors. In J. Gibbons and P. Nogueira, editors, MPC, volume 7342 of Lecture Notes in Computer Science, pages 300–323. Springer, 2012. Google ScholarDigital Library
- R. Rajkumar, S. Lindley, N. Foster, and J. Cheney. Lenses for web data. In Preliminary Proceedings of Second International Workshop on Bidirectional Transformations (BX 2013), 2013.Google Scholar
- J. C. Reynolds. Types, abstraction and parametric polymorphism. In R. Mason, editor, Information Processing, pages 513–523. Elsevier Science Publishers B.V. (North-Holland), 1983.Google Scholar
- T. van Laarhoven. Cps based functional references, Jul 2009.Google Scholar
- blog post: http://www.twanvl.nl/blog/haskell/ cps-functional-references.Google Scholar
- J. Voigtländer. Bidirectionalization for free! (pearl). In Z. Shao and B. C. Pierce, editors, POPL, pages 165–176. ACM, 2009. Google ScholarDigital Library
- J. Voigtländer. Free theorems involving type constructor classes: functional pearl. In G. Hutton and A. P. Tolmach, editors, ICFP, pages 173–184. ACM, 2009. Google ScholarDigital Library
- J. Voigtländer, Z. Hu, K. Matsuda, and M. Wang. Combining syntactic and semantic bidirectionalization. In P. Hudak and S. Weirich, editors, ICFP, pages 181–192. ACM, 2010. Google ScholarDigital Library
- J. Voigtländer, Z. Hu, K. Matsuda, and M. Wang. Enhancing semantic bidirectionalization via shape bidirectionalizer plug-ins. J. Funct. Program., 23(5):515–551, 2013.Google ScholarCross Ref
- P. Wadler. Theorems for free! In FPCA, pages 347–359, 1989. 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, MPC, volume 6120 of Lecture Notes in Computer Science, pages 397–425. Springer, 2010. Google ScholarDigital Library
- M. Wang, J. Gibbons, K. Matsuda, and Z. Hu. Refactoring pattern matching. Sci. Comput. Program., 78(11):2216–2242, 2013. Google ScholarDigital Library
- M. Wang, J. Gibbons, and N. Wu. Incremental updates for efficient bidirectional transformations. In M. M. T. Chakravarty, Z. Hu, and O. Danvy, editors, ICFP, pages 392–403. ACM, 2011. Google ScholarDigital Library
- M. Wang and S. Najd. Semantic bidirectionalization revisited. In W.-N. Chin and J. Hage, editors, PEPM, pages 51–62. ACM, 2014. Google ScholarDigital Library
- Y. Xiong, D. Liu, Z. Hu, H. Zhao, M. Takeichi, and H. Mei. Towards automatic model synchronization from model transformations. In R. E. K. Stirewalt, A. Egyed, and B. Fischer, editors, ASE, pages 164– 173. ACM, 2007. Google ScholarDigital Library
- Y. Yu, Y. Lin, Z. Hu, S. Hidaka, H. Kato, and L. Montrieux. Maintaining invariant traceability through bidirectional transformations. In M. Glinz, G. C. Murphy, and M. Pezzè, editors, ICSE, pages 540–550. IEEE, 2012. Google ScholarDigital Library
Index Terms
- Applicative bidirectional programming with lenses
Recommendations
Applicative bidirectional programming with lenses
ICFP 2015: Proceedings of the 20th ACM SIGPLAN International Conference on Functional ProgrammingA 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 ...
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 ...
Monadic combinators for "Putback" style bidirectional programming
PEPM '14: Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program ManipulationBidirectional transformations, in particular lenses, are programs with a forward get transformation and a backward putback transformation that keep source and view data types synchronized. Several bidirectional programming languages exist to aid ...
Comments