{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T05:48:35Z","timestamp":1784180915982,"version":"3.55.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"8S","license":[{"start":{"date-parts":[[2015,12,4]],"date-time":"2015-12-04T00:00:00Z","timestamp":1449187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGPLAN Not."],"published-print":{"date-parts":[[2015,12,4]]},"abstract":"<jats:p>\n            We propose a novel approach to the well-known view\n            <jats:italic>update problem<\/jats:italic>\n            for the case of tree-structured data: a domainspecific\\ programming language in which all expressions denote bi-directional transformations on trees. In one direction, these transformations--dubbed lenses--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 identify a natural space of well-behaved bi-directional transformations over arbitrary structures, study definedness and continuity in this setting, and state a precise connection with the classical theory of \"update translation under a constant complement\" from databases. 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 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 bi-directional list-processing transformations as derived forms\n          <\/jats:p>","DOI":"10.1145\/2854695.2854700","type":"journal-article","created":{"date-parts":[[2015,12,7]],"date-time":"2015-12-07T19:33:52Z","timestamp":1449516832000},"page":"49-62","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["POPL 2005"],"prefix":"10.1145","volume":"50","author":[{"given":"J. Nathan","family":"Foster","sequence":"first","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael B.","family":"Greenwald","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"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":"University of Pennsylvania"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,12,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/645502.656099"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050056"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/648085.747302"},{"key":"e_1_2_1_4_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/3-540-36377-7_13","volume-title":"The Essence of Computation: Complexity, Analysis, Transformation","author":"Abramov S. M.","year":"2002","unstructured":"S. M. Abramov and R. Gl\u00fcck . Principles of inverse computation and the universal resolving algorithm . In T. Mogensen, D. Schmidt, and I. H. Sudborough, editors, The Essence of Computation: Complexity, Analysis, Transformation , volume 2566 of Lecture Notes in Computer Science , pages 269 -- 295 . Springer-Verlag , 2002 . S. M. Abramov and R. Gl\u00fcck. Principles of inverse computation and the universal resolving algorithm. In T. Mogensen, D. Schmidt, and I. H. Sudborough, editors, The Essence of Computation: Complexity, Analysis, Transformation, volume 2566 of Lecture Notes in Computer Science, pages 269--295. Springer-Verlag, 2002."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645337.650371"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/319628.319634"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115831"},{"key":"e_1_2_1_8_1","first-page":"2003","article-title":"On the updatability of XML views over relational databases","author":"Braganholo V.","year":"2003","unstructured":"V. Braganholo , S. Davidson , and C. Heuser . On the updatability of XML views over relational databases . In WebDB 2003 , 2003 . V. Braganholo, S. Davidson, and C. Heuser. On the updatability of XML views over relational databases. In WebDB 2003, 2003.","journal-title":"WebDB"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543633"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1887"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319740"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/49346.50068"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199482"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014007.1014025"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/325405.325423"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773159"},{"key":"e_1_2_1_18_1","volume-title":"VLDB'84","author":"Masunaga Y.","year":"1984","unstructured":"Y. Masunaga . A relational database view update translation mechanism . In VLDB'84 , 1984 . Y. Masunaga. A relational database view update translation mechanism. In VLDB'84, 1984."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/146486.146557"},{"key":"e_1_2_1_20_1","volume-title":"VLDB'85","author":"Medeiros C. M. B.","year":"1985","unstructured":"C. M. B. Medeiros and F. W. Tompa . Understanding the implications of view update policies . In VLDB'85 , 1985 . C. M. B. Medeiros and F. W. Tompa. Understanding the implications of view update policies. In VLDB'85, 1985."},{"key":"e_1_2_1_21_1","volume-title":"Designing constraint maintainers for user interaction","author":"Meertens L.","year":"1998","unstructured":"L. Meertens . Designing constraint maintainers for user interaction , 1998 . Manuscript . L. Meertens. Designing constraint maintainers for user interaction, 1998. Manuscript."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30477-7_2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182623"},{"key":"e_1_2_1_24_1","volume-title":"Algebraic Methods in Semantics","author":"Oles F. J.","year":"1985","unstructured":"F. J. Oles . Type algebras, functor categories, and block structure . In M. Nivat and J. C. Reynolds, editors, Algebraic Methods in Semantics . Cambrige University Press , 1985 . F. J. Oles. Type algebras, functor categories, and block structure. In M. Nivat and J. C. Reynolds, editors, Algebraic Methods in Semantics. Cambrige University Press, 1985."},{"key":"e_1_2_1_25_1","volume-title":"Manuscript","author":"Pierce B. C.","year":"2003","unstructured":"B. C. Pierce and A. Schmitt . Lenses and view update translation . Manuscript , 2003 . B. C. Pierce and A. Schmitt. Lenses and view update translation. Manuscript, 2003."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55015-1_10"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375720"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/41625.41653"}],"container-title":["ACM SIGPLAN Notices"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2854695.2854700","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2854695.2854700","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:47Z","timestamp":1750225727000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2854695.2854700"}},"subtitle":["Combinators for Bi-Directional Tree Transformations: Linguistic Approach to the View Update Problem"],"short-title":[],"issued":{"date-parts":[[2015,12,4]]},"references-count":27,"journal-issue":{"issue":"8S","published-print":{"date-parts":[[2015,12,4]]}},"alternative-id":["10.1145\/2854695.2854700"],"URL":"https:\/\/doi.org\/10.1145\/2854695.2854700","relation":{},"ISSN":["0362-1340","1558-1160"],"issn-type":[{"value":"0362-1340","type":"print"},{"value":"1558-1160","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,4]]},"assertion":[{"value":"2015-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}