Abstract
Lenses are one the most popular approaches to define bidirectional transformations between data models. A bidirectional transformation with view-update, denoted a lens, encompasses the definition of a forward transformation projecting concrete models into abstract views, together with a backward transformation instructing how to translate an abstract view to an update over concrete models. In this paper we show that most of the standard point-free combinators can be lifted to lenses with suitable backward semantics, allowing us to use the point-free style to define powerful bidirectional transformations by composition. We also demonstrate how to define generic lenses over arbitrary inductive data types by lifting standard recursion patterns, like folds or unfolds. To exemplify the power of this approach, we “lensify” some standard functions over naturals and lists, which are tricky to define directly “by-hand” using explicit recursion.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Backhouse, R., Doornbos, H.: Mathematics of recursive program construction. Manuscript (2001), http://www.cs.nott.ac.uk/rcb/MPC/papers
Backus, J.: Can programming be liberated from the von Neumann style? a functional style and its algebra of programs. Communications of the ACM 21(8), 613–641 (1978)
Bancilhon, F., Spyratos, N.: Update semantics of relational views. ACM Transactions on Database Systems 6(4), 557–575 (1981)
Berdaguer, P., Cunha, A., Pacheco, H., Visser, J.: Coupled schema transformation and data: Conversion for XML and SQL. In: Hanus, M. (ed.) PADL 2007. LNCS, vol. 4354, pp. 290–304. Springer, Heidelberg (2006)
Bird, R., de Moor, O.: The Algebra of Programming. Prentice-Hall, Englewood Cliffs (1997)
Bohannon, A., Foster, J.N., Pierce, B.C., Pilkiewicz, A., Schmitt, A.: Boomerang: resourceful lenses for string data. In: Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’08), pp. 407–419. ACM, New York (2008)
Bohannon, A., Pierce, B.C., Vaughan, J.A.: Relational lenses: a language for updatable views. In: Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’06), pp. 338–347. ACM, New York (2006)
Capretta, V., Uustalu, T., Vene, V.: Recursive coalgebras from comonads. Information and Computation 204(4), 437–468 (2006)
Cunha, A., Oliveira, J.N., Visser, J.: Type-safe two-level data transformation. In: Misra, J., Nipkow, T., Sekerinski, E. (eds.) FM 2006. LNCS, vol. 4085, pp. 284–299. Springer, Heidelberg (2006)
Cunha, A., Pacheco, H.: Algebraic specialization of generic functions for recursive types. In: Proceedings of the 2nd Workshop on Mathematically Structured Functional Programming (MSFP’08). ENTCS, Elsevier Science Publishers B. V., Amsterdam (2008)
Cunha, A., Pinto, J.S., Proença, J.: A framework for point-free program transformation. In: Butterfield, A., Grelck, C., Huch, F. (eds.) IFL 2005. LNCS, vol. 4015, pp. 1–18. Springer, Heidelberg (2006)
Cunha, A., Visser, J.: Strongly typed rewriting for coupled software transformation. Electronic Notes in Theoretical Computer Science 174(1), 17–34 (2007)
Cunha, A., Visser, J.: Transformation of structure-shy programs with application to XPath queries and strategic functions. Science of Computer Programming (to appear, 2010)
Diskin, Z.: Algebraic Models for Bidirectional Model Synchronization. In: Czarnecki, K., Ober, I., Bruel, J.-M., Uhl, A., Völter, M. (eds.) MODELS 2008. LNCS, vol. 5301, pp. 21–36. Springer, Heidelberg (2008)
Foster, J.N., Greenwald, M.B., Moore, J.T., Pierce, B.C., Schmitt, A.: Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Transactions on Programming Languages and Systems 29(3), 17 (2007)
Frisch, A., Castagna, G., Benzaken, V.: Semantic subtyping: Dealing set-theoretically with function, union, intersection, and negation types. Journal of the ACM 55(4), 1–64 (2008)
Gibbons, J.: Calculating functional programs. In: Blackhouse, R., Crole, R.L., Gibbons, J. (eds.) Algebraic and Coalgebraic Methods in the Mathematics of Program Construction. LNCS, vol. 2297, pp. 149–203. Springer, Heidelberg (2002)
Hinze, R.: Generic programs and proofs. Bonn University, Habilitation (2000)
Hu, Z., Mu, S.-C., Takeichi, M.: A programmable editor for developing structured documents based on bidirectional transformations. Higher Order and Symbolic Computation 21(1-2), 89–118 (2008)
Matsuda, K., Hu, Z., Nakano, K., Hamana, M., Takeichi, M.: Bidirectionalization transformation based on automatic derivation of view complement functions. In: Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming (ICFP’07), pp. 47–58. ACM, New York (2007)
Meertens, L.: Designing constraint maintainers for user interaction (1998), Manuscript available at, http://www.kestrel.edu/home/people/meertens
Meijer, E., Fokkinga, M., Paterson, R.: Functional programming with bananas, lenses, envelopes and barbed wire. In: Hughes, J. (ed.) FPCA 1991. LNCS, vol. 523, pp. 124–144. Springer, Heidelberg (1991)
Morgan, C., Gardiner, P.H.B.: Data refinement by calculation. Acta Informatica 27(6), 481–503 (1990)
Mu, S.-C., Hu, Z., Takeichi, M.: An algebraic approach to bi-directional updating. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol. 3302, pp. 2–20. Springer, Heidelberg (2004)
Oliveira, J.N.: Data transformation by calculation. In: Lämmel, R., Visser, J., Saraiva, J. (eds.) Generative and Transformational Techniques in Software Engineering II. LNCS, vol. 5235, pp. 139–198. Springer, Heidelberg (2008)
Stevens, P.: Bidirectional model transformations in QVT: Semantic issues and open questions. In: Engels, G., Opdyke, B., Schmidt, D.C., Weil, F. (eds.) MODELS 2007. LNCS, vol. 4735, pp. 1–15. Springer, Heidelberg (2007)
Voigtländer, J.: Bidirectionalization for free! (Pearl). In: Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’09), pp. 165–176. ACM, New York (2009)
Wang, M., Gibbons, J., Matsuda, K., Hu, Z.: Translucent Abstraction: Safe Views through Invertible Programming. Draft (2010), http://web.comlab.ox.ac.uk/files/2280/total.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pacheco, H., Cunha, A. (2010). Generic Point-free Lenses. In: Bolduc, C., Desharnais, J., Ktari, B. (eds) Mathematics of Program Construction. MPC 2010. Lecture Notes in Computer Science, vol 6120. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13321-3_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-13321-3_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13320-6
Online ISBN: 978-3-642-13321-3
eBook Packages: Computer ScienceComputer Science (R0)