{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T06:40:29Z","timestamp":1782888029802,"version":"3.54.5"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>\n            We propose a novel approach to the\n            <jats:italic>view-update problem<\/jats:italic>\n            for tree-structured data: a domain-specific programming language in which all expressions denote bidirectional transformations on trees. In one direction, these transformations---dubbed\n            <jats:italic>lenses<\/jats:italic>\n            ---map a concrete tree into a simplified abstract view; in the other, they map a modified abstract view, together with the original concrete tree, to a correspondingly modified concrete tree. Our design emphasizes both robustness and ease of use, guaranteeing strong well-behavedness and totality properties for well-typed lenses.\n          <\/jats:p>\n          <jats:p>\n            We begin by identifying a natural space of well-behaved bidirectional transformations over arbitrary structures, studying definedness and continuity in this setting. We then instantiate this semantic framework in the form of a collection of\n            <jats:italic>lens combinators<\/jats:italic>\n            that can be assembled to describe bidirectional transformations on trees. These combinators include familiar constructs from functional programming (composition, mapping, projection, conditionals, recursion) together with some novel primitives for manipulating trees (splitting, pruning, merging, etc.). We illustrate the expressiveness of these combinators by developing a number of bidirectional list-processing transformations as derived forms. An extended example shows how our combinators can be used to define a lens that translates between a native HTML representation of browser bookmarks and a generic abstract bookmark format.\n          <\/jats:p>","DOI":"10.1145\/1232420.1232424","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":289,"title":["Combinators for bidirectional tree transformations"],"prefix":"10.1145","volume":"29","author":[{"given":"J. Nathan","family":"Foster","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael B.","family":"Greenwald","sequence":"additional","affiliation":[{"name":"Bell Labs, Lucent Technologies"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan T.","family":"Moore","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin C.","family":"Pierce","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Schmitt","sequence":"additional","affiliation":[{"name":"INRIA Rh\u00f4ne-Alpes"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"International Conference on Database Theory (ICDT)","author":"Abiteboul S.","unstructured":"Abiteboul , S. , Cluet , S. , and Milo , T . 1997. Correspondence and translation for heterogeneous data . In International Conference on Database Theory (ICDT) . Delphi, Greece. Abiteboul, S., Cluet, S., and Milo, T. 1997. Correspondence and translation for heterogeneous data. In International Conference on Database Theory (ICDT). Delphi, Greece."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050056"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 24th International Conference on Very Large Data Bases (VLDB).","author":"Abiteboul S.","unstructured":"Abiteboul , S. , McHugh , J. , Rys , M. , Vassalos , V. , and Wiener , J. L . 1998. Incremental maintenance for materialized views over semistructured data . In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB). Abiteboul, S., McHugh, J., Rys, M., Vassalos, V., and Wiener, J. L. 1998. Incremental maintenance for materialized views over semistructured data. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB)."},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Abramov S. M. and Gl\u00fcck R. 2000. The universal resolving algorithm: Inverse computation in a functional language. In Mathematics of Program Construction R. Backhouse and J. N. Oliveira Eds. Vol. 1837. Springer-Verlag 187--212.   Abramov S. M. and Gl\u00fcck R. 2000. The universal resolving algorithm: Inverse computation in a functional language. In Mathematics of Program Construction R. Backhouse and J. N. Oliveira Eds. Vol. 1837. Springer-Verlag 187--212.","DOI":"10.1007\/10722010_13"},{"key":"e_1_2_2_5_1","volume-title":"Eds. Lecture Notes in Computer Science","volume":"2566","author":"Abramov S. M.","unstructured":"Abramov , S. M. and Gl\u00fcck , R . 2002. Principles of inverse computation and the universal resolving algorithm. In The Essence of Computation: Complexity, Analysis, Transformation, T. Mogensen, D. Schmidt, and I. H. Sudborough , Eds. Lecture Notes in Computer Science , vol. 2566 . Springer-Verlag, 269--295. Abramov, S. M. and Gl\u00fcck, R. 2002. Principles of inverse computation and the universal resolving algorithm. In The Essence of Computation: Complexity, Analysis, Transformation, T. Mogensen, D. Schmidt, and I. H. Sudborough, Eds. Lecture Notes in Computer Science, vol. 2566. Springer-Verlag, 269--295."},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT'96)","volume":"1057","author":"Atzeni P.","unstructured":"Atzeni , P. and Torlone , R . 1996. Management of multiple models in an extensible database design tool . In Proceedings of the International Conference on Extending Database Technology (EDBT'96) . Lecture Notes in Computer Science , vol. 1057 . Atzeni, P. and Torlone, R. 1996. Management of multiple models in an extensible database design tool. In Proceedings of the International Conference on Extending Database Technology (EDBT'96). Lecture Notes in Computer Science, vol. 1057."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253393"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/645648.664816"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/319628.319634"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115831"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142399"},{"key":"e_1_2_2_13_1","volume-title":"International Workshop on the Web and Databases (WebDB'03)","author":"Braganholo V.","unstructured":"Braganholo , V. , Davidson , S. , and Heuser , C . 2003. On the updatability of XML views over relational databases . In International Workshop on the Web and Databases (WebDB'03) . Braganholo, V., Davidson, S., and Heuser, C. 2003. On the updatability of XML views over relational databases. In International Workshop on the Web and Databases (WebDB'03)."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543633"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1887"},{"key":"e_1_2_2_17_1","volume-title":"An Introduction to Database Systems","author":"Date C. J.","unstructured":"Date , C. J. 2003. An Introduction to Database Systems , 8 th Ed. Addison Wesley . Date, C. J. 2003. An Introduction to Database Systems, 8th Ed. Addison Wesley.","edition":"8"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319740"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the 3rd International Conference on Information Integration and Web-based Applications and Services (IIWAS).","author":"de Paula Braganholo V.","unstructured":"de Paula Braganholo , V. , Heuser , C. A. , and Vittori , C. R. M. 2001. Updating relational databases through XML views . In Proceedings of the 3rd International Conference on Information Integration and Web-based Applications and Services (IIWAS). de Paula Braganholo, V., Heuser, C. A., and Vittori, C. R. M. 2001. Updating relational databases through XML views. In Proceedings of the 3rd International Conference on Information Integration and Web-based Applications and Services (IIWAS)."},{"key":"e_1_2_2_20_1","volume-title":"Program Construction","author":"Dijkstra E. W.","year":"1978","unstructured":"Dijkstra , E. W. 1979. Program inversion . In Program Construction , International Summer School, July-August 1978 . Marktoberdorf, Germany. F. L. Bauer and M. Broy, Eds. Lecture Notes in Computer Science, vol. 69 . Springer . Dijkstra, E. W. 1979. Program inversion. In Program Construction, International Summer School, July-August 1978. Marktoberdorf, Germany. F. L. Bauer and M. Broy, Eds. Lecture Notes in Computer Science, vol. 69. Springer."},{"key":"e_1_2_2_21_1","unstructured":"Fogel S. and Lane P. 2005. Oracle Database Administrator's Guide. Oracle.  Fogel S. and Lane P. 2005. Oracle Database Administrator's Guide. Oracle."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.024"},{"key":"e_1_2_2_23_1","unstructured":"Foster J. N. Pierce B. C. and Schmitt A. 2006. Harmony Programmer's Manual. Available at http:\/\/www.seas.upenn.edu\/~harmony\/.  Foster J. N. Pierce B. C. and Schmitt A. 2006. Harmony Programmer's Manual. Available at http:\/\/www.seas.upenn.edu\/~harmony\/."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/49346.50068"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/112198.112226"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026158013113"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199482"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014007.1014025"},{"key":"e_1_2_2_29_1","unstructured":"International Business Machines Corporation. 2004. IBM DB2 Universal Database Administration Guide: Implementation.  International Business Machines Corporation. 2004. IBM DB2 Universal Database Administration Guide: Implementation."},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 12th Australasian Conference on Database Technologies (ADC'01)","author":"Johnson M.","unstructured":"Johnson , M. , Rosebrugh , R. , and Dampney , C. N. G. 2001. View updates in a semantic data modelling paradigm . In Proceedings of the 12th Australasian Conference on Database Technologies (ADC'01) . IEEE Computer Society, 29--36. Johnson, M., Rosebrugh, R., and Dampney, C. N. G. 2001. View updates in a semantic data modelling paradigm. In Proceedings of the 12th Australasian Conference on Database Technologies (ADC'01). IEEE Computer Society, 29--36."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/325405.325423"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the International Conference on Very Large Database (VLDB'86)","author":"Keller A. M.","year":"1986","unstructured":"Keller , A. M. 1986 . Choosing a view update translator by dialog at view definition time . In Proceedings of the International Conference on Very Large Database (VLDB'86) . Keller, A. M. 1986. Choosing a view update translator by dialog at view definition time. In Proceedings of the International Conference on Very Large Database (VLDB'86)."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.441.0261"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773159"},{"key":"e_1_2_2_35_1","unstructured":"Lorentz D. 2005. Oracle Database SQL Reference. Oracle.  Lorentz D. 2005. Oracle Database SQL Reference. Oracle."},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'84)","author":"Masunaga Y.","year":"1984","unstructured":"Masunaga , Y. 1984 . A relational database view update translation mechanism . In Proceedings of the International Conference on Very Large Databases (VLDB'84) . Masunaga, Y. 1984. A relational database view update translation mechanism. In Proceedings of the International Conference on Very Large Databases (VLDB'84)."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/146486.146557"},{"key":"e_1_2_2_38_1","volume-title":"Automata Studies, Annals of Mathematical Studies","author":"McCarthy J.","unstructured":"McCarthy , J. 1956. The inversion of functions defined by turing machines . In Automata Studies, Annals of Mathematical Studies , C. E. Shannon and J. McCarthy, Eds. Number 34. Princeton University Press , 177--181. McCarthy, J. 1956. The inversion of functions defined by turing machines. In Automata Studies, Annals of Mathematical Studies, C. E. Shannon and J. McCarthy, Eds. Number 34. Princeton University Press, 177--181."},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'85)","author":"Medeiros C. M. B.","unstructured":"Medeiros , C. M. B. and Tompa , F. W . 1985. Understanding the implications of view update policies . In Proceedings of the International Conference on Very Large Databases (VLDB'85) . Medeiros, C. M. B. and Tompa, F. W. 1985. Understanding the implications of view update policies. In Proceedings of the International Conference on Very Large Databases (VLDB'85)."},{"key":"e_1_2_2_40_1","unstructured":"Meertens L. 1998. Designing constraint maintainers for user interaction. Manuscript. Available at ftp:\/\/ftp.kestrel.edu\/pub\/papers\/meertens\/dcm.ps.  Meertens L. 1998. Designing constraint maintainers for user interaction. Manuscript. Available at ftp:\/\/ftp.kestrel.edu\/pub\/papers\/meertens\/dcm.ps."},{"key":"e_1_2_2_41_1","unstructured":"Microsoft 2005. Creating and Maintaining Databases. Microsoft.  Microsoft 2005. Creating and Maintaining Databases. Microsoft."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/373626.373713"},{"key":"e_1_2_2_43_1","volume-title":"ASIAN Symposium on Programming Languages and Systems (APLAS).","author":"Mu S.-C.","unstructured":"Mu , S.-C. , Hu , Z. , and Takeichi , M . 2004a. An algebraic approach to bi-directional updating . In ASIAN Symposium on Programming Languages and Systems (APLAS). Mu, S.-C., Hu, Z., and Takeichi, M. 2004a. An algebraic approach to bi-directional updating. In ASIAN Symposium on Programming Languages and Systems (APLAS)."},{"key":"e_1_2_2_44_1","volume-title":"17th International Conference on Mathematics of Program Construction (MPC).","author":"Mu S.-C.","unstructured":"Mu , S.-C. , Hu , Z. , and Takeichi , M . 2004b. An injective language for reversible computation . In 17th International Conference on Mathematics of Program Construction (MPC). Mu, S.-C., Hu, Z., and Takeichi, M. 2004b. An injective language for reversible computation. In 17th International Conference on Mathematics of Program Construction (MPC)."},{"key":"e_1_2_2_45_1","doi-asserted-by":"crossref","unstructured":"Niehren J. and Podelski A. 1993. Feature automata and recognizable sets of feature trees. In Theory and Practice of Software (TAPSOFT). 356--375.   Niehren J. and Podelski A. 1993. Feature automata and recognizable sets of feature trees. In Theory and Practice of Software (TAPSOFT). 356--375.","DOI":"10.1007\/3-540-56610-4_76"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182623"},{"key":"e_1_2_2_47_1","volume-title":"Algebraic Methods in Semantics","author":"Oles F. J.","unstructured":"Oles , F. J. 1985. Type algebras, functor categories, and block structure . In Algebraic Methods in Semantics , M. Nivat and J. C. Reynolds, Eds. Cambrige University Press . Oles, F. J. 1985. Type algebras, functor categories, and block structure. In Algebraic Methods in Semantics, M. Nivat and J. C. Reynolds, Eds. Cambrige University Press."},{"key":"e_1_2_2_48_1","volume-title":"Harmony: A synchronization framework for heterogeneous tree-structured data.","author":"Pierce B. C.","year":"2006","unstructured":"Pierce , B. C. Bohannon , A. , Foster , J. N. , Greenwald , M. B. , Khanna , S. , Kunal , K. , and Schmidt , A . 2006 . Harmony: A synchronization framework for heterogeneous tree-structured data. Available at http:\/\/www.seas.upenn.edu\/~harmony\/. Pierce, B. C. Bohannon, A., Foster, J. N., Greenwald, M. B., Khanna, S., Kunal, K., and Schmidt, A. 2006. Harmony: A synchronization framework for heterogeneous tree-structured data. Available at http:\/\/www.seas.upenn.edu\/~harmony\/."},{"key":"e_1_2_2_49_1","unstructured":"Pierce B. C. Schmitt A. and Greenwald M. B. 2003. Bringing Harmony to optimism: A synchronization framework for heterogeneous tree-structured data. Tech. rep. MS-CIS-03-42 University of Pennsylvania (Superseded by MS-CIS-05-02).  Pierce B. C. Schmitt A. and Greenwald M. B. 2003. Bringing Harmony to optimism: A synchronization framework for heterogeneous tree-structured data. Tech. rep. MS-CIS-03-42 University of Pennsylvania (Superseded by MS-CIS-05-02)."},{"key":"e_1_2_2_50_1","unstructured":"Pierce B. C. and Vouillon J. 2004. What's in Unison&quest; A formal specification and reference implementation of a file synchronizer. Tech. rep. MS-CIS-03-36 Department of Computer and Information Science University of Pennsylvania.  Pierce B. C. and Vouillon J. 2004. What's in Unison&quest; A formal specification and reference implementation of a file synchronizer. Tech. rep. MS-CIS-03-36 Department of Computer and Information Science University of Pennsylvania."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582107"},{"key":"e_1_2_2_52_1","volume-title":"Proceedings of the 2nd International Conference on Deductive and Object-Oriented Databases (DOOD), C. Delobel, M. Kifer, and Y. Yasunga, Eds.","volume":"566","author":"Scholl M. H.","unstructured":"Scholl , M. H. , Laasch , C. , and Tresch , M . 1991. Updatable views in object-oriented databases . In Proceedings of the 2nd International Conference on Deductive and Object-Oriented Databases (DOOD), C. Delobel, M. Kifer, and Y. Yasunga, Eds. vol. 566 . Springer. Scholl, M. H., Laasch, C., and Tresch, M. 1991. Updatable views in object-oriented databases. In Proceedings of the 2nd International Conference on Deductive and Object-Oriented Databases (DOOD), C. Delobel, M. Kifer, and Y. Yasunga, Eds. vol. 566. Springer."},{"key":"e_1_2_2_53_1","unstructured":"Spoonhower D. 2004. View updates seen through the lens of synchronization. Manuscript. Available at www.cs.cmu.edu\/~spoons\/courses\/15-721\/project\/report.ps.  Spoonhower D. 2004. View updates seen through the lens of synchronization. Manuscript. Available at www.cs.cmu.edu\/~spoons\/courses\/15-721\/project\/report.ps."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375720"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/41625.41653"},{"key":"e_1_2_2_56_1","volume-title":"The Formal Semantics of Programming Languages: An Introduction","author":"Winskel G.","unstructured":"Winskel , G. 1993. The Formal Semantics of Programming Languages: An Introduction . MIT Press . Winskel, G. 1993. The Formal Semantics of Programming Languages: An Introduction. MIT Press."},{"key":"e_1_2_2_57_1","unstructured":"XQuery 2005. XQuery 1.0: An XML Query Language W3C Working Draft. Available at http:\/\/www.w3.org\/TR\/xquery\/.  XQuery 2005. XQuery 1.0: An XML Query Language W3C Working Draft. Available at http:\/\/www.w3.org\/TR\/xquery\/."}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1232420.1232424","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T19:06:41Z","timestamp":1672254401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1232420.1232424"}},"subtitle":["A linguistic approach to the view-update problem"],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1232420.1232424"],"URL":"https:\/\/doi.org\/10.1145\/1232420.1232424","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}