{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:56:39Z","timestamp":1750308999187,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,7,30]]},"abstract":"<jats:p>\n            <jats:italic>Quotient lenses<\/jats:italic>\n            are bidirectional transformations whose correctness laws are \u201cloosened\u201d by specified equivalence relations, allowing inessential details in concrete data formats to be suppressed. For example, a programmer could use a quotient lens to define a transformation that ignores the order of fields in XML data, so that two XML files with the same fields but in different orders would be considered the same, allowing a single, simple program to handle them both. Building on a recently published algorithm for synthesizing plain bijective lenses from high-level specifications, we show how to synthesize bijective quotient lenses in three steps. First, we introduce\n            <jats:italic>quotient regular expressions<\/jats:italic>\n            (QREs), annotated regular expressions that conveniently mark inessential aspects of string data formats; each QRE specifies, simulteneously, a regular language and an equivalence relation on it. Second, we introduce\n            <jats:italic>QRE lenses<\/jats:italic>\n            , i.e., lenses mapping between QREs. Our key technical result is a proof that every QRE lens can be transformed into a functionally equivalent lens that canonizes source and target data just at the \u201cedges\u201d and that uses a bijective lens to map between the respective canonical elements; no internal canonization occurs in a lens in this normal form. Third, we leverage this normalization theorem to\n            <jats:italic>synthesize<\/jats:italic>\n            QRE lenses from a pair of QREs and example input-output pairs, reusing earlier work on synthesizing plain bijective lenses. We have implemented QREs and QRE lens synthesis as an extension to the bidirectional programming language Boomerang. We evaluate the effectiveness of our approach by synthesizing QRE lenses between various real-world data formats in the Optician benchmark suite.\n          <\/jats:p>","DOI":"10.1145\/3236775","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T19:41:18Z","timestamp":1533066078000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Synthesizing quotient lenses"],"prefix":"10.1145","volume":"2","author":[{"given":"Solomon","family":"Maina","sequence":"first","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anders","family":"Miltner","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kathleen","family":"Fisher","sequence":"additional","affiliation":[{"name":"Tufts University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin C.","family":"Pierce","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Walker","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steve","family":"Zdancewic","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Lennart Augustsson. 2004. {Haskell} Announcing Djinn version 2004-12-11 a coding wizard. Mailing List. http: \/\/www.haskell.org\/pipermail\/haskell\/2005-December\/017055.html .  Lennart Augustsson. 2004. {Haskell} Announcing Djinn version 2004-12-11 a coding wizard. Mailing List. http: \/\/www.haskell.org\/pipermail\/haskell\/2005-December\/017055.html ."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328487"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.01.006"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411203.1411209"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89330-1_15"},{"key":"e_1_2_2_6_1","unstructured":"Alcino Cunha. 2010. A relational approach to bidirectional transformations. (2010).  Alcino Cunha. 2010. A relational approach to bidirectional transformations. (2010)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062351"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737977"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1232420.1232424"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411203.1411257"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1925844.1926423"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462192"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10270-016-0568-3"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1925844.1926428"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014007.1014025"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159803.1159830"},{"key":"e_1_2_2_18_1","volume-title":"Linux Symposium","author":"Lutterkort David","year":"2008","unstructured":"David Lutterkort . 2008 . Augeas\u2013a configuration API . In Linux Symposium , Ottawa, ON. 47\u201356. David Lutterkort. 2008. Augeas\u2013a configuration API. In Linux Symposium, Ottawa, ON. 47\u201356."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37036-6_6"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158089"},{"volume-title":"An Algebraic Approach to Bi-directional Updating","author":"Mu Shin-Cheng","key":"e_1_2_2_21_1","unstructured":"Shin-Cheng Mu , Zhenjiang Hu , and Masato Takeichi . 2004. An Algebraic Approach to Bi-directional Updating . Springer Berlin Heidelberg , Berlin, Heidelberg , 2\u201320. Shin-Cheng Mu, Zhenjiang Hu, and Masato Takeichi. 2004. An Algebraic Approach to Bi-directional Updating. Springer Berlin Heidelberg, Berlin, Heidelberg, 2\u201320."},{"key":"e_1_2_2_22_1","first-page":"129","article-title":"Bidirectionalizing Tree Transformation Languages: A Case Study","volume":"23","author":"Shin-Cheng MU","year":"2006","unstructured":"Shin-Cheng MU , Zhenjiang HU, and Masato TAKEICHI. 2006 . Bidirectionalizing Tree Transformation Languages: A Case Study . Computer Software 23 , 2 (2006), 129 \u2013 141 . Shin-Cheng MU, Zhenjiang HU, and Masato TAKEICHI. 2006. Bidirectionalizing Tree Transformation Languages: A Case Study. Computer Software 23, 2 (2006), 129\u2013141.","journal-title":"Computer Software"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738007"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2643135.2643141"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908093"},{"key":"e_1_2_2_26_1","volume-title":"Lenses for web data. Electronic Communications of the EASST 57","author":"Rajkumar Raghu","year":"2014","unstructured":"Raghu Rajkumar , Nate Foster , Sam Lindley , and James Cheney . 2014. Lenses for web data. Electronic Communications of the EASST 57 ( 2014 ). Raghu Rajkumar, Nate Foster, Sam Lindley, and James Cheney. 2014. Lenses for web data. Electronic Communications of the EASST 57 (2014)."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784757"},{"volume-title":"Springer Berlin Heidelberg","author":"Sippu Seppo","key":"e_1_2_2_28_1","unstructured":"Seppo Sippu and Eljas Soisalon-Soininen . 1988. Regular Languages . Springer Berlin Heidelberg , Berlin, Heidelberg , 65\u2013114. Seppo Sippu and Eljas Soisalon-Soininen. 1988. Regular Languages. Springer Berlin Heidelberg, Berlin, Heidelberg, 65\u2013114."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236775","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236775","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:28Z","timestamp":1750282888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236775"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":27,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2018,7,30]]}},"alternative-id":["10.1145\/3236775"],"URL":"https:\/\/doi.org\/10.1145\/3236775","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}