Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-27T20:48:03.838Z Has data issue: false hasContentIssue false
  • English
  • Français

Applicative bidirectional programming

Mixing lenses and semantic bidirectionalization

Published online by Cambridge University Press:  21 June 2018

KAZUTAKA MATSUDA  and
MENG WANG
KAZUTAKA MATSUDA
Affiliation:
Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan (e-mail: [email protected])
MENG WANG
Affiliation:
Department of Computer Science, University of Bristol, Bristol BS8 1TH, UK (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 obtain benefits from both.

Type
Research Article
Information
Journal of Functional Programming , Volume 28 , 2018 , e15
Copyright
Copyright © Cambridge University Press 2018 

References

Bancilhon, F. & Spyratos, N. (1981) Update semantics of relational views. ACM Trans. Database Dyst. 6 (4), 557–575.CrossRefGoogle Scholar
Bernardy, J.-P., Jansson, P. & Paterson, R. (2012) Proofs for free–-Parametricity for dependent types. J. Funct. Program. 22 (2), 107–152.CrossRefGoogle Scholar
Bird, R. S., Gibbons, J., Mehner, S., Voigtländer, J. & Schrijvers, T. (2013) Understanding idiomatic traversals backwards and forwards. In Haskell, Shan, C.-C. (ed). ACM, pp. 25–36.CrossRefGoogle Scholar
Bohannon, A., Foster, J. N., Pierce, B. C., Pilkiewicz, A. & Schmitt, A. (2008) Boomerang: Resourceful lenses for string data. In POPL, Necula, G. C. & Wadler, P. (eds). ACM, pp. 407–419.CrossRefGoogle Scholar
Church, A. (1940) A formulation of the simple theory of types. J. Symb. Log. 5 (2), 56–68.CrossRefGoogle Scholar
Davi, B. M. J., Cretin, J., Foster, N., Greenberg, M. & Pierce, B. C. (2010) Matching lenses: Alignment and view update. In ICFP, September 27–29, 2010. Baltimore, Maryland, USA: ACM.Google Scholar
Dayal, U. & Bernstein, P. A. (1982) On the correct translation of update operations on relational views. ACM Trans. Database Syst. 7 (3), 381–416.CrossRefGoogle Scholar
Ellis, T. (2012) Category and lenses. Blog post [online]. Accessed October 17, 2014. Available at: http://web.jaguarpaw.co.uk/~tom/blog/posts/2012-09-30-category-and-lenses.htmlGoogle Scholar
Fegaras, L. (2010) Propagating updates through XML views using lineage tracing. In ICDE, Li, F., Moro, M. M., Ghandeharizadeh, S., Haritsa, J. R., Weikum, G., Carey, M. J., Casati, F., Chang, E. Y., Manolescu, I., Mehrotra, S., Dayal, U. & Tsotras, V. J. (eds). IEEE, pp. 309–320.CrossRefGoogle Scholar
Foster, J. N., Greenwald, M. B., Moore, J. T., Pierce, B. C. & Schmitt, A. (2007) Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Trans. Program. Lang. Syst. 29 (3).CrossRefGoogle Scholar
Foster, J. N., Pilkiewicz, A. & Pierce, B. C. (2008) Quotient lenses. In ICFP, Hook, J. & Thiemann, P. (eds). ACM, pp. 383–396.CrossRefGoogle Scholar
Foster, N., Matsuda, K. & Voigtländer, J. (2010) Three complementary approaches to bidirectional programming. In SSGIP, Gibbons, J. (ed), Lecture Notes in Computer Science, vol. 7470. Springer, pp. 1–46.Google Scholar
Hayashi, Y., Liu, D., Emoto, K., Matsuda, K., Hu, Z. & Takeichi, M. (2007) A web service architecture for bidirectional XML updating. In APWeb/WAIM, Dong, G., Lin, X., Wang, W., Yang, Y. & Yu, J. X. (eds), Lecture Notes in Computer Science, vol. 4505. Springer, pp. 721–732.CrossRefGoogle Scholar
Hegner, S. J. (1990) Foundations of canonical update support for closed database views. In ICDT, Abiteboul, S. & Kanellakis, P. C. (eds), Lecture Notes in Computer Science, vol. 470. Springer, pp. 422–436.CrossRefGoogle Scholar
Hidaka, S., Hu, Z., Inaba, K., Kato, H., Matsuda, K. & Nakano, K. (2010) Bidirectionalizing graph transformations. In ICFP, September 27–29, 2010. Baltimore, Maryland, USA: ACM.CrossRefGoogle Scholar
Hofmann, M., Pierce, B. C. & Wagner, D. (2011) Symmetric lenses. In POPL, Ball, T. & Sagiv, M. (eds). ACM, pp. 371–384.CrossRefGoogle Scholar
Hu, Z., Mu, S.-C. & Takeichi, M. (2004) A programmable editor for developing structured documents based on bidirectional transformations. In PEPM, Heintze, N. & Sestoft, P. (eds), ACM, pp. 178–189.CrossRefGoogle Scholar
Huet, G. P. & Lang, B. (1978) Proving and applying program transformations expressed with second-order patterns. Acta Inf. 11, 31–55.CrossRefGoogle Scholar
Jaskelioff, M. & O'Connor, R. (2015) A representation theorem for second-order functionals. J. Funct. Program. 25 (e13), 1–36.CrossRefGoogle Scholar
Ko, H.-S., Zan, T. & Hu, Z. (2016) BIGUL: A formally verified core language for putback-based bidirectional programming. In PEPM, January 20–22, 2016, Erwig, M. & Rompf, T. (eds). St. Petersburg, FL, USA: ACM, pp. 61–72.CrossRefGoogle Scholar
Lindley, S., Wadler, P. & Yallop, J. (2011) Idioms are oblivious, arrows are meticulous, monads are promiscuous. Electr. Notes Theor. Comput. Sci. 229 (5), 97–117.CrossRefGoogle Scholar
Liu, D., Hu, Z. & Takeichi, M. (2007) Bidirectional interpretation of XQuery. In Proceedings of the SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, January 15–16, 2007, Ramalingam, G. & Visser, E. (eds). Nice, France: ACM, pp. 21–30.CrossRefGoogle Scholar
Mac Lane, S. (1998) Categories for the Working Mathematician, 2nd ed., Graduate Texts in Mathematics, vol. 5. Springer.Google Scholar
Matsuda, K., Hu, Z., Nakano, K., Hamana, M. & Takeichi, M. (2007) Bidirectionalization transformation based on automatic derivation of view complement functions. In ICFP, Hinze, R. & Ramsey, N (eds). ACM, pp. 47–58.CrossRefGoogle Scholar
Matsuda, K. & Wang, M. (2013) Bidirectionalization for free with runtime recording: Or, a light-weight approach to the view-update problem. In PPDP, Peña, R. & Schrijvers, T. (eds). ACM, pp. 297–308.CrossRefGoogle Scholar
Matsuda, K. & Wang, M. (2014) “Bidirectionalization for free” for monomorphic transformations. Sci. Comput. Program. 111 (1), 79–109. DOI: 10.1016/j.scico.2014.07.008.CrossRefGoogle Scholar
Matsuda, K. & Wang, M. (2015) Applicative bidirectional programming with lenses. In ICFP, September 1–3, 2015, Fisher, K. & Reppy, J. H. (eds). Vancouver, BC, Canada: ACM, pp. 62–74.CrossRefGoogle Scholar
Matsuda, K. & Wang, M. (2018) HOBiT: Programming lenses without using lens combinators. In ESOP, Ahmed, A. (ed). Lecture Notes in Computer Science, vol. 10801, Springer, pp. 31–59.CrossRefGoogle Scholar
McBride, C. & Paterson, R. (2008) Applicative programming with effects. J. Funct. Program. 18 (1), 1–13.CrossRefGoogle Scholar
Milewski, B. (2013) Lenses, Stores, and Yoneda. Blog post [online]. Accessed September 29, 2014. Available at: http://bartoszmilewski.com/2013/10/08/lenses-stores-and-yoneda/Google Scholar
Miller, D. & Nadathur, G. (1987) A logic programming approach to manipulating formulas and programs. In Proceedings of the 1987 Symposium on Logic Programming, August 31–September 4. San Francisco, California, USA: IEEE-CS, pp. 379–388.Google Scholar
Mu, S.-C., Hu, Z. & Takeichi, M. (2004) An algebraic approach to bi-directional updating. In APLAS, Chin, W.-N. (ed), Lecture Notes in Computer Science, vol. 3302. Springer, pp. 2–20.CrossRefGoogle Scholar
O'Connor, R. (2011) Functor is to lens as applicative is to biplate: Introducing multiplate. Corr abs/1103.2841. Accepted in WGP'11, but not included in its proceedings.Google Scholar
Pacheco, H., Hu, Z. & Fischer, S. (2014b) Monadic combinators for “putback” style bidirectional programming. In PEPM, January 20–21, 2014. San Diego, California, USA: ACM.CrossRefGoogle Scholar
Pacheco, H., Zan, T. & Hu, Z. (2014a) BiFluX: A bidirectional functional update language for XML. In Proceedings of the 16th International Symposium on Principles and Practice of Declarative Programming, September 8–10, 2014, Chitil, O., King, A. & Danvy, O. (eds). Kent, Canterbury, United Kingdom: ACM, pp. 147–158.CrossRefGoogle Scholar
Paterson, R. (2001) A new notation for arrows. In ICFP, Pierce, B. C. (ed). ACM, pp. 229–240.CrossRefGoogle Scholar
Paterson, R. (2012) Constructing applicative functors. In MPC, Gibbons, J. & Nogueira, P. (eds), Lecture Notes in Computer Science, vol. 7342. Springer, pp. 300–323.CrossRefGoogle Scholar
Pfenning, F. & Elliott, C. (1988) Higher-order abstract syntax. In PLDI, June 22–24, 1988, Wexelblat, R. L. (ed). Atlanta, Georgia, USA: ACM, pp. 199–208.CrossRefGoogle Scholar
Rajkumar, R., Lindley, S., Foster, N. & Cheney, J. (2013) Lenses for web data. Electron. Commun. EASST 57.Google Scholar
Reynolds, J. C. (1983) Types, abstraction and parametric polymorphism. In Information Processing, Mason, R. E. A. (ed). North-Holland: Elsevier Science Publishers B.V., pp. 513–523.Google Scholar
van Laarhoven, T. (2009) CPS based functional references. Blog post [online]. Available at: http://www.twanvl.nl/blog/haskell/cps-functional-references.Google Scholar
Voigtländer, J. (2009a) Bidirectionalization for free! (pearl). In POPL, Shao, Z. & Pierce, B. C. (eds). ACM, pp. 165–176.CrossRefGoogle Scholar
Voigtländer, J. (2009b) Free theorems involving type constructor classes: Functional pearl. In ICFP, Hutton, G. & Tolmach, A. P. (eds). ACM, pp. 173–184.CrossRefGoogle Scholar
Voigtländer, J., Hu, Z., Matsuda, K. & Wang, M. (2010) Combining syntactic and semantic bidirectionalization. In ICFP, September 27–29, 2010. Baltimore, Maryland, USA: ACM.CrossRefGoogle Scholar
Voigtländer, J., Hu, Z., Matsuda, K. & Wang, M. (2013) Enhancing semantic bidirectionalization via shape bidirectionalizer plug-ins. J. Funct. Program. 23 (5), 515–551.CrossRefGoogle Scholar
Vytiniotis, Dimitrios & Weirich, Stephanie. (2010) Parametricity, type equality, and higher-order polymorphism. J. Funct. Program. 20 (2), 175–210.CrossRefGoogle Scholar
Wadler, P. (1989) Theorems for free! In FPCA '89, pp. 347–359.Google Scholar
Wallace, M. & Runciman, C. (1999) Haskell and XML: Generic combinators or type-based translation? In ICFP, Rémy, D. & Lee, P. (eds). ACM, pp. 148–159.Google Scholar
Wang, M., Gibbons, J., Matsuda, K. & Hu, Z. (2010) Gradual refinement: Blending pattern matching with data abstraction. In MPC, Bolduc, C., Desharnais, J. & Ktari, B. (eds), Lecture Notes in Computer Science, vol. 6120. Springer, pp. 397–425.CrossRefGoogle Scholar
Wang, M., Gibbons, J., Matsuda, K. & Hu, Z. (2013) Refactoring pattern matching. Sci. Comput. Program. 78 (11), 2216–2242.CrossRefGoogle Scholar
Wang, M., Gibbons, J. & Wu, N. (2011) Incremental updates for efficient bidirectional transformations. In ICFP, Chakravarty, M. M. T., Hu, Z. & Danvy, O. (eds). ACM, pp. 392–403.CrossRefGoogle Scholar
Wang, M. & Najd, S. (2014) Semantic bidirectionalization revisited. In PEPM, January 20–21, 2014. San Diego, California, USA: ACM.CrossRefGoogle Scholar
Xiong, Y., Liu, D., Hu, Z., Zhao, H., Takeichi, M. & Mei, H. (2007) Towards automatic model synchronization from model transformations. In ASE, Stirewalt, R. E. K., Egyed, A. & Fischer, B. (eds). ACM, pp. 164–173.CrossRefGoogle Scholar
Yu, Y., Lin, Y., Hu, Z., Hidaka, S., Kato, H. & Montrieux, L. (2012) Maintaining invariant traceability through bidirectional transformations. In ICSE, Glinz, M., Murphy, G. C. & Pezzè, M. (eds). IEEE, pp. 540–550.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.