{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T12:30:20Z","timestamp":1790425820427,"version":"4.1.0"},"reference-count":35,"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\/"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC Starting Grant SECOMP (715753)"],"award-info":[{"award-number":["ERC Starting Grant SECOMP (715753)"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1453796"],"award-info":[{"award-number":["CCF-1453796"]}],"id":[{"id":"10.13039\/100000001","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":[[2018,7,30]]},"abstract":"<jats:p>\n            Gradually typed languages allow statically typed and dynamically typed code to interact while maintaining benefits of both styles. The key to reasoning about these mixed programs is Siek-Vitousek-Cimini-Boyland\u2019s (dynamic) gradual guarantee, which says that giving components of a program more precise types only adds runtime type checking, and does not otherwise change behavior. In this paper, we give a semantic reformulation of the gradual guarantee called\n            <jats:italic>graduality<\/jats:italic>\n            . We change the name to promote the analogy that graduality is to gradual typing what parametricity is to polymorphism. Each gives a local-to-global, syntactic-to-semantic reasoning principle that is formulated in terms of a kind of observational approximation.\n          <\/jats:p>\n          <jats:p>\n            Utilizing the analogy, we develop a novel logical relation for proving graduality. We show that\n            <jats:italic>embedding-projection pairs (ep pairs)<\/jats:italic>\n            are to graduality what relations are to parametricity. We argue that casts between two types where one is \u201cmore dynamic\u201d (less precise) than the other necessarily form an ep pair, and we use this to cleanly prove the graduality cases for casts from the ep-pair property. To construct ep pairs, we give an analysis of the\n            <jats:italic>type dynamism<\/jats:italic>\n            relation\u2014also known as type precision or na\u00efve subtyping\u2014that interprets the rules for type dynamism as compositional constructions on ep pairs, analogous to the coercion interpretation of subtyping.\n          <\/jats:p>","DOI":"10.1145\/3236768","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T19:41:18Z","timestamp":1533066078000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Graduality from embedding-projection pairs"],"prefix":"10.1145","volume":"2","author":[{"given":"Max S.","family":"New","sequence":"first","affiliation":[{"name":"Northeastern University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amal","family":"Ahmed","sequence":"additional","affiliation":[{"name":"Northeastern University, USA \/ Inria, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11693024_6"},{"key":"e_1_2_2_2_1","volume-title":"With and Without Types. In International Conference on Functional Programming (ICFP)","author":"Ahmed Amal","year":"2017","unstructured":"Amal Ahmed , Dustin Jamner , Jeremy G. Siek , and Philip Wadler . 2017 . Theorems for Free for Free: Parametricity , With and Without Types. In International Conference on Functional Programming (ICFP) , Oxford, United Kingdom. Amal Ahmed, Dustin Jamner, Jeremy G. Siek, and Philip Wadler. 2017. Theorems for Free for Free: Parametricity, With and Without Types. In International Conference on Functional Programming (ICFP), Oxford, United Kingdom."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2013.06.006"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628136.2628149"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796804005398"},{"key":"e_1_2_2_6_1","volume-title":"Workshop on Foundations of Object-Oriented Languages (FOOL), informal proceedings.","author":"Boyland John Tang","year":"2014","unstructured":"John Tang Boyland . 2014 . The Problem of Structural Type Tests in a Gradual-Typed Language . In Workshop on Foundations of Object-Oriented Languages (FOOL), informal proceedings. John Tang Boyland. 2014. The Problem of Structural Type Tests in a Gradual-Typed Language. In Workshop on Foundations of Object-Oriented Languages (FOOL), informal proceedings."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837632"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009863"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951933"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796818000011"},{"key":"e_1_2_2_11_1","volume-title":"Correctness of compiling polymorphism to dynamic typing. Journal of Functional Programming 27","author":"Keun-Bang","year":"2017","unstructured":"Keun-Bang Hou (Favonia), Nick Benton , and Robert Harper . 2017. Correctness of compiling polymorphism to dynamic typing. Journal of Functional Programming 27 ( 2017 ). Keun-Bang Hou (Favonia), Nick Benton, and Robert Harper. 2017. Correctness of compiling polymorphism to dynamic typing. Journal of Functional Programming 27 (2017)."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90014-7"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11737414_16"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/581478.581484"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837670"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837670"},{"key":"e_1_2_2_17_1","volume-title":"Sage: Hybrid Checking for Flexible Specifications. In Scheme and Functional Programming Workshop (Scheme). 93\u2013104","author":"Gronski Jessica","year":"2006","unstructured":"Jessica Gronski , Kenneth Knowles , Aaron Tomb , Stephen N. Freund , and Cormac Flanagan . 2006 . Sage: Hybrid Checking for Flexible Specifications. In Scheme and Functional Programming Workshop (Scheme). 93\u2013104 . Jessica Gronski, Kenneth Knowles, Aaron Tomb, Stephen N. Freund, and Cormac Flanagan. 2006. Sage: Hybrid Checking for Flexible Specifications. In Scheme and Functional Programming Workshop (Scheme). 93\u2013104."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(94)00004-2"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10990-011-9066-z"},{"key":"e_1_2_2_20_1","volume-title":"Gradual Session Types. In International Conference on Functional Programming (ICFP)","author":"Igarashi Atsushi","year":"2017","unstructured":"Atsushi Igarashi , Peter Thiemann , Vasco Vasconcelos , and Philip Wadler . 2017 b. Gradual Session Types. In International Conference on Functional Programming (ICFP) , Oxford, United Kingdom. Atsushi Igarashi, Peter Thiemann, Vasco Vasconcelos, and Philip Wadler. 2017b. Gradual Session Types. In International Conference on Functional Programming (ICFP), Oxford, United Kingdom."},{"key":"e_1_2_2_21_1","volume-title":"On Polymorphic Gradual Typing. In International Conference on Functional Programming (ICFP)","author":"Igarashi Yuu","year":"2017","unstructured":"Yuu Igarashi , Taro Sekiyama , and Atsushi Igarashi . 2017 a. On Polymorphic Gradual Typing. In International Conference on Functional Programming (ICFP) , Oxford, United Kingdom. Yuu Igarashi, Taro Sekiyama, and Atsushi Igarashi. 2017a. On Polymorphic Gradual Typing. In International Conference on Functional Programming (ICFP), Oxford, United Kingdom."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048114"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009856"},{"key":"e_1_2_2_24_1","volume-title":"New and Amal Ahmed","author":"Max","year":"2018","unstructured":"Max S. New and Amal Ahmed . 2018 . Graduality from Embedding-Projection Pairs (Extended Version). ArXiv e-prints (July 2018). arXiv: 1807.02786 Max S. New and Amal Ahmed. 2018. Graduality from Embedding-Projection Pairs (Extended Version). ArXiv e-prints (July 2018). arXiv: 1807.02786"},{"key":"e_1_2_2_25_1","volume-title":"Licata","author":"New Max S.","year":"2018","unstructured":"Max S. New and Daniel R . Licata . 2018 . Call-by-Name Gradual Type Theory. In 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018) (Leibniz International Proceedings in Informatics (LIPIcs)), H\u00e9l\u00e8ne Kirchner (Ed .), Vol. 108 . http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9194 Max S. New and Daniel R. Licata. 2018. Call-by-Name Gradual Type Theory. In 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018) (Leibniz International Proceedings in Informatics (LIPIcs)), H\u00e9l\u00e8ne Kirchner (Ed.), Vol. 108. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9194"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Dana Scott. 1972. Continuous lattices. In Toposes algebraic geometry and logic. 97\u2013136.  Dana Scott. 1972. Continuous lattices. In Toposes algebraic geometry and logic. 97\u2013136.","DOI":"10.1007\/BFb0073967"},{"key":"e_1_2_2_27_1","volume-title":"1st Summit on Advances in Programming Languages (SNAPL","author":"Siek Jeremy","year":"2015","unstructured":"Jeremy Siek , Micahel Vitousek , Matteo Cimini , and John Tang Boyland . 2015. Refined Criteria for Gradual Typing . In 1st Summit on Advances in Programming Languages (SNAPL 2015 ). Jeremy Siek, Micahel Vitousek, Matteo Cimini, and John Tang Boyland. 2015. Refined Criteria for Gradual Typing. In 1st Summit on Advances in Programming Languages (SNAPL 2015)."},{"key":"e_1_2_2_28_1","volume-title":"Gradual Typing for Functional Languages. In Scheme and Functional Programming Workshop (Scheme). 81\u201392","author":"Jeremy","unstructured":"Jeremy G. Siek and Walid Taha. 2006 . Gradual Typing for Functional Languages. In Scheme and Functional Programming Workshop (Scheme). 81\u201392 . Jeremy G. Siek and Walid Taha. 2006. Gradual Typing for Functional Languages. In Scheme and Functional Programming Workshop (Scheme). 81\u201392."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706342"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535889"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/96709.96747"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176617.1176755"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328486"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00590-9_1"},{"key":"e_1_2_2_35_1","volume-title":"Gradual Typestate. In Proceedings of the 25th European Conference on Object-oriented Programming (ECOOP\u201911)","author":"Wolff Roger","year":"2011","unstructured":"Roger Wolff , Ronald Garcia , \u00c9ric Tanter , and Jonathan Aldrich . 2011 . Gradual Typestate. In Proceedings of the 25th European Conference on Object-oriented Programming (ECOOP\u201911) . Roger Wolff, Ronald Garcia, \u00c9ric Tanter, and Jonathan Aldrich. 2011. Gradual Typestate. In Proceedings of the 25th European Conference on Object-oriented Programming (ECOOP\u201911)."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236768","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236768","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236768","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\/3236768"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":35,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2018,7,30]]}},"alternative-id":["10.1145\/3236768"],"URL":"https:\/\/doi.org\/10.1145\/3236768","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"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"}}]}}