{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T18:13:55Z","timestamp":1781892835619,"version":"3.54.5"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2017,12,27]],"date-time":"2017-12-27T00:00:00Z","timestamp":1514332800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["12O5515N"],"award-info":[{"award-number":["12O5515N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["FKZ: 13N1S0762"],"award-info":[{"award-number":["FKZ: 13N1S0762"]}],"id":[{"id":"10.13039\/501100002347","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,1]]},"abstract":"<jats:p>There has long been speculation in the scientific literature on how to dynamically enforce parametricity such as that yielded by System F. Almost 20 years ago, Sumii and Pierce proposed a formal compiler from System F into the cryptographic lambda calculus: an untyped lambda calculus extended with an idealised model of encryption. They conjectured that this compiler was fully abstract, i.e. that compiled terms are contextually equivalent if and only if the original terms were, a property that can be seen as a form of secure compilation. The conjecture has received attention in several other publications since then, but remains open to this day.<\/jats:p>\n          <jats:p>More recently, several researchers have been looking at gradually-typed languages that extend System F. In this setting it is natural to wonder whether embedding System F into these gradually-typed languages preserves contextual equivalence and thus parametricity.<\/jats:p>\n          <jats:p>In this paper, we answer both questions negatively. We provide a concrete counterexample: two System F terms whose contextual equivalence is not preserved by the Sumii-Pierce compiler, nor the embedding into the polymorphic blame calculus. This counterexample relies on the absence in System F of what we call a universal type, i.e., a type that all other types can be injected into and extracted from. As the languages in which System F is compiled have a universal type, the compilation cannot be fully abstract; this paper explains why.<\/jats:p>\n          <jats:p>We believe this paper thus sheds light on recent results in the field of gradually typed languages and it provides a perspective for further research into secure compilation of polymorphic languages.<\/jats:p>","DOI":"10.1145\/3158126","type":"journal-article","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T14:21:49Z","timestamp":1514557309000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Parametricity versus the universal type"],"prefix":"10.1145","volume":"2","author":[{"given":"Dominique","family":"Devriese","sequence":"first","affiliation":[{"name":"KU Leuven, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Patrignani","sequence":"additional","affiliation":[{"name":"MPI-SWS, Germany \/ CISPA, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Piessens","sequence":"additional","affiliation":[{"name":"KU Leuven, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,12,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055109"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/103135.103138"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1998.705647"},{"key":"e_1_2_2_4_1","volume-title":"Secure Communications Processing for Distributed Languages. In IEEE Symposium on Security and Privacy. 74\u201388","author":"Abadi Mart\u00edn","year":"1999","unstructured":"Mart\u00edn Abadi , C\u00e9dric Fournet , and Georges Gonthier . 1999 . Secure Communications Processing for Distributed Languages. In IEEE Symposium on Security and Privacy. 74\u201388 . Mart\u00edn Abadi, C\u00e9dric Fournet, and Georges Gonthier. 1999. Secure Communications Processing for Distributed Languages. In IEEE Symposium on Security and Privacy. 74\u201388."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/325694.325734"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2240276.2240279"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2012.12"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411204.1411227"},{"key":"e_1_2_2_9_1","unstructured":"Amal Ahmed Justin Damner Jeremy G. Siek and Philip Wadler. 2017. Theorems for Free for Free. In ICFP.  Amal Ahmed Justin Damner Jeremy G. Siek and Philip Wadler. 2017. Theorems for Free for Free. In ICFP."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480925"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926409"},{"key":"e_1_2_2_13_1","volume-title":"Theorems for low, low prices! (April","author":"Ahmed Amal","year":"2011","unstructured":"Amal Ahmed , Lindsey Kuper , and Jacob Matthews . 2011c. Parametric polymorphism through run-time sealing, or , Theorems for low, low prices! (April 2011 ). http:\/\/www.ccs.neu.edu\/home\/amal\/papers\/paramseal- tr.pdf Amal Ahmed, Lindsey Kuper, and Jacob Matthews. 2011c. Parametric polymorphism through run-time sealing, or, Theorems for low, low prices! (April 2011). http:\/\/www.ccs.neu.edu\/home\/amal\/papers\/paramseal- tr.pdf"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1570506.1570507"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535852"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190253"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837632"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Dominique Devriese Marco Patrignani and Frank Piessens. 2016. Fully-abstract Compilation by Approximate Backtranslation. In Principles of Programming Languages. 164\u2013177.  Dominique Devriese Marco Patrignani and Frank Piessens. 2016. Fully-abstract Compilation by Approximate Backtranslation. In Principles of Programming Languages. 164\u2013177.","DOI":"10.1145\/2914770.2837618"},{"key":"e_1_2_2_19_1","unstructured":"Dominique Devriese Marco Patrignani Frank Piessens and Steven Keuchel. 2017. Modular Fully-Abstract Compilation by Approximate Back-Translation. to appear in LMCS. (2017). http:\/\/arxiv.org\/abs\/1703.09988  Dominique Devriese Marco Patrignani Frank Piessens and Steven Keuchel. 2017. Modular Fully-Abstract Compilation by Approximate Back-Translation. to appear in LMCS. (2017). http:\/\/arxiv.org\/abs\/1703.09988"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.34"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/581478.581484"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429114"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837670"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297081.1297089"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110284"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2011.18"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2016.11"},{"key":"e_1_2_2_29_1","volume-title":"Benjamin C. Pierce, Antal Spector-Zabusky, and Andrew Tolmach.","author":"Juglaret Yannis","year":"2015","unstructured":"Yannis Juglaret , Catalin Hritcu , Arthur Azevedo de Amorim , Benjamin C. Pierce, Antal Spector-Zabusky, and Andrew Tolmach. 2015 . Towards a Fully Abstract Compiler Using Micro-Policies: Secure Compilation for Mutually Distrustful Components. CoRR abs\/1510.00697 (2015). http:\/\/arxiv.org\/abs\/1510.00697 Yannis Juglaret, Catalin Hritcu, Arthur Azevedo de Amorim, Benjamin C. Pierce, Antal Spector-Zabusky, and Andrew Tolmach. 2015. Towards a Fully Abstract Compiler Using Micro-Policies: Secure Compilation for Mutually Distrustful Components. CoRR abs\/1510.00697 (2015). http:\/\/arxiv.org\/abs\/1510.00697"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26529-2_3"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851613.2851796"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-1291-0_2"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78739-6_2"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498926.1498930"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/361932.361937"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/512927.512938"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596550.1596572"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796811000165"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699503"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2016.9"},{"key":"e_1_2_2_41_1","volume-title":"Types and Programming Languages","author":"Pierce Benjamin","unstructured":"Benjamin Pierce . 2002. Types and Programming Languages . MIT Press . Benjamin Pierce. 2002. Types and Programming Languages. MIT Press."},{"key":"e_1_2_2_42_1","unstructured":"Benjamin Pierce and Eijiro Sumii. 2000. Relating Cryptography and Polymorphism. (2000). http:\/\/www.kb.ecei.tohoku.ac. jp\/~sumii\/pub\/infohide.pdf manuscript.  Benjamin Pierce and Eijiro Sumii. 2000. Relating Cryptography and Polymorphism. (2000). http:\/\/www.kb.ecei.tohoku.ac. jp\/~sumii\/pub\/infohide.pdf manuscript."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90044-5"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-06859-7_148"},{"key":"e_1_2_2_45_1","unstructured":"J. C. Reynolds. 1983. Types Abstraction and Parametric Polymorphism. In Information Processing. North Holland 513\u2013523.  J. C. Reynolds. 1983. Types Abstraction and Parametric Polymorphism. In Information Processing. North Holland 513\u2013523."},{"key":"e_1_2_2_46_1","unstructured":"Jeremy Siek and Philip Wadler. 2016. The key to blame: Gradual typing meets cryptography. (2016). http:\/\/homepages.inf. ed.ac.uk\/wadler\/papers\/blame- key\/blame- key.pdf draft.  Jeremy Siek and Philip Wadler. 2016. The key to blame: Gradual typing meets cryptography. (2016). http:\/\/homepages.inf. ed.ac.uk\/wadler\/papers\/blame- key\/blame- key.pdf draft."},{"key":"e_1_2_2_47_1","volume-title":"Siek and Walid Taha","author":"Jeremy","year":"2006","unstructured":"Jeremy G. Siek and Walid Taha . 2006 . Gradual Typing for Functional Languages. In SCHEME. 81\u201392. Jeremy G. Siek and Walid Taha. 2006. Gradual Typing for Functional Languages. In SCHEME. 81\u201392."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SNAPL.2015.274"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010000313106"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-2003-11403"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/964001.964015"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837630"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/99370.99404"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.042"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00590-9_1"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.9"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158126","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158126","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:30Z","timestamp":1750212690000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,27]]},"references-count":54,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1145\/3158126"],"URL":"https:\/\/doi.org\/10.1145\/3158126","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,27]]},"assertion":[{"value":"2017-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}