{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T10:31:34Z","timestamp":1753180294475,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T00:00:00Z","timestamp":1564099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["568751"],"award-info":[{"award-number":["568751"]}],"id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-17-2-0028"],"award-info":[{"award-number":["FA8750-17-2-0028"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2019,7,26]]},"abstract":"<jats:p>Lenses are programs that can be run both \"front to back\" and \"back to front,\" allowing updates to either their source or their target data to be transferred in both directions. Since their introduction by Foster et al., lenses have been extensively studied, extended, and applied. Recent work has also demonstrated how techniques from type-directed program synthesis can be used to efficiently synthesize a simple class of lenses---so-called bijective lenses over string data---given a pair of types (regular expressions) and a small number of examples.<\/jats:p>\n          <jats:p>We extend this synthesis algorithm to a much broader class of lenses, called simple symmetric lenses, including all bijective lenses, all of the popular category of \"asymmetric\" lenses, and a rich subset of the more powerful \"symmetric lenses\" proposed by Hofmann et al. Intuitively, simple symmetric lenses allow some information to be present on one side but not the other and vice versa. They are of independent theoretical interest, being the largest class of symmetric lenses that do not rely on persistent internal state.<\/jats:p>\n          <jats:p>Synthesizing simple symmetric lenses is substantially more challenging than synthesizing bijective lenses: Since some of the information on each side can be \"disconnected\" from the other side, there will, in general, be many lenses that agree with a given example. To guide the search process, we use stochastic regular expressions and ideas from information theory to estimate the amount of information propagated by a candidate lens, generally preferring lenses that propagate more information, as well as user annotations marking parts of the source and target data structures as either irrelevant or essential.<\/jats:p>\n          <jats:p>We describe an implementation of simple symmetric lenses and our synthesis procedure as extensions to the Boomerang language. We evaluate its performance on 48 benchmark examples drawn from Flash Fill, Augeas, the bidirectional programming literature, and electronic file format synchronization tasks. Our implementation can synthesize each of these lenses in under 30 seconds.<\/jats:p>","DOI":"10.1145\/3341699","type":"journal-article","created":{"date-parts":[[2019,7,29]],"date-time":"2019-07-29T20:55:51Z","timestamp":1564433751000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Synthesizing symmetric lenses"],"prefix":"10.1145","volume":"3","author":[{"given":"Anders","family":"Miltner","sequence":"first","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Solomon","family":"Maina","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, 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":[[2019,7,26]]},"reference":[{"volume-title":"Syntax-Guided Synthesis. In Proceedings of the IEEE International Conference on Formal Methods in Computer-Aided Design (FMCAD) . 1\u201317","year":"2013","author":"Alur Rajeev","key":"e_1_2_2_1_1"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872799"},{"key":"e_1_2_2_3_1","unstructured":"Lennart Augustsson. 2004. {Haskell} Announcing Djinn version 2004-12-11 a coding wizard. Mailing List. (2004). 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. (2004). http:\/\/www.haskell.org\/pipermail\/haskell\/2005-December\/017055.html ."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863572"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328487"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142399"},{"key":"e_1_2_2_7_1","unstructured":"Calendars 2016. Calendars. http:\/\/fileformats.archiveteam.org\/wiki\/Calendars . (2016).  Calendars 2016. Calendars. http:\/\/fileformats.archiveteam.org\/wiki\/Calendars . (2016)."},{"volume-title":"Grammatical Interference: Learning Syntax from Sentences, Laurent Miclet and Colin de la Higuera (Eds.)","author":"Carrasco Rafael C.","key":"e_1_2_2_8_1"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02408-5_19"},{"volume":"1","volume-title":"Proceedings of the 28th International Conference on Neural Information Processing Systems -","author":"Ellis Kevin","key":"e_1_2_2_10_1"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737977"},{"key":"e_1_2_2_12_1","unstructured":"Finance and Accounting 2016. Finance and Accounting. http:\/\/fileformats.archiveteam.org\/wiki\/Finance_and_Accounting . (2016).  Finance and Accounting 2016. Finance and Accounting. http:\/\/fileformats.archiveteam.org\/wiki\/Finance_and_Accounting . (2016)."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328897.1328488"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1232420.1232424"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411203.1411257"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462192"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926428"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062345"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594333"},{"volume-title":"Algebraic structures for transitive closure. Theoretical Computer Science 4 (02","year":"1977","author":"Lehmann Daniel","key":"e_1_2_2_23_1"},{"volume-title":"Augeas: A Linux Configuration API. (Feb.","year":"2007","author":"Lutterkort David","key":"e_1_2_2_24_1"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236775"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158089"},{"volume-title":"Synthesizing Symmetric Lenses. CoRR abs\/1810.11527","year":"2018","author":"Miltner Anders","key":"e_1_2_2_27_1"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738007"},{"volume-title":"Formal grammar and information theory: Together again? Philosophical transactions of the royal society 358","year":"2000","author":"Pereira Fernando","key":"e_1_2_2_29_1"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026524328760"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784757"},{"volume-title":"Graph-Theoretic Concepts in Computer Science , Ernst W","author":"Sch\u00fcrr Andy","key":"e_1_2_2_32_1"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480904"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341699","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341699","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341699","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:30Z","timestamp":1750200090000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341699"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,26]]},"references-count":32,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2019,7,26]]}},"alternative-id":["10.1145\/3341699"],"URL":"https:\/\/doi.org\/10.1145\/3341699","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2019,7,26]]},"assertion":[{"value":"2019-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}