{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:58Z","timestamp":1750221118598,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2019,1,2]],"date-time":"2019-01-02T00:00:00Z","timestamp":1546387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2017R1A2B3012020 and 2017M3C4A7068177"],"award-info":[{"award-number":["NRF-2017R1A2B3012020 and 2017M3C4A7068177"]}],"id":[{"id":"10.13039\/501100003725","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,1,2]]},"abstract":"<jats:p>Many object-oriented languages provide method overloading, which allows multiple method declarations with the same name. For a given method invocation, in order to choose what method declaration to invoke, multiple dispatch considers the run-time types of the arguments. While multiple dispatch can support binary methods (such as mathematical operators) intuitively and consistently, it is difficult to guarantee that calls will be neither ambiguous nor undefined at run time, especially in the presence of expressive language features such as multiple inheritance and parametric polymorphism. Previous efforts have formalized languages that include such features by using overloading rules that guarantee a unique and type-sound resolution of each overloaded method call; in many cases, such rules resolve ambiguity by treating the arguments asymmetrically. Here we present the first formal specification of a strongly typed object-oriented language with symmetric multiple dispatch, multiple inheritance, and parametric polymorphism with variance. We define both a static (type- checking) semantics and a dynamic (dispatching) semantics and prove the type soundness of the language, thus demonstrating that our novel dynamic dispatch algorithm is consistent with the static semantics. Details of our dynamic dispatch algorithm address certain technical challenges that arise from structural asymmetries inherent in object-oriented languages (e.g., classes typically declare ancestors explicitly but not descendants).<\/jats:p>","DOI":"10.1145\/3290324","type":"journal-article","created":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T13:33:51Z","timestamp":1546608831000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Polymorphic symmetric multiple dispatch with variance"],"prefix":"10.1145","volume":"3","author":[{"given":"Gyunghee","family":"Park","sequence":"first","affiliation":[{"name":"KAIST, South Korea \/ Oracle Labs, USA"}]},{"given":"Jaemin","family":"Hong","sequence":"additional","affiliation":[{"name":"KAIST, South Korea"}]},{"given":"Guy L.","family":"Steele Jr.","sequence":"additional","affiliation":[{"name":"Oracle Labs, USA"}]},{"given":"Sukyoung","family":"Ryu","sequence":"additional","affiliation":[{"name":"KAIST, South Korea"}]}],"member":"320","published-online":{"date-parts":[[2019,1,2]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Eric Allen David Chase J. J. Hallett Victor Luchangco Jan-Willem Maessen Sukyoung Ryu Guy L. Steele  Jr. and Sam Tobin-Hochstadt. 2008. The Fortress Language Specification Version 1.0.  Eric Allen David Chase J. J. Hallett Victor Luchangco Jan-Willem Maessen Sukyoung Ryu Guy L. Steele Jr. and Sam Tobin-Hochstadt. 2008. The Fortress Language Specification Version 1.0."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1244002.1244245"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048140"},{"key":"e_1_2_2_4_1","volume-title":"Shah","author":"Bezanson Jeff","year":"2015","unstructured":"Jeff Bezanson , Alan Edelman , Stefan Karpinski , and Viral B . Shah . 2015 . Julia : A Fresh Approach to Numerical Computing (v4). CoRR abs\/1411.1607 (July 2015), 1\u201337. http:\/\/arxiv.org\/abs\/1411.1607 Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B. Shah. 2015. Julia: A Fresh Approach to Numerical Computing (v4). CoRR abs\/1411.1607 (July 2015), 1\u201337. http:\/\/arxiv.org\/abs\/1411.1607"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/141000671"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263743"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/141471.141537"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1033"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676991"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/353171.353181"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133651.1133655"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535855"},{"key":"e_1_2_2_13_1","unstructured":"EPFL. 2017. A class for immutable linked lists representing ordered collections of elements of type \u2018A\u2018 {implementation of class List for the Scala programming language}. https:\/\/github.com\/scala\/scala\/blob\/2.13.x\/src\/library\/scala\/collection\/ immutable\/List.scala . Accessed: 2017-11-27.  EPFL. 2017. A class for immutable linked lists representing ordered collections of elements of type \u2018A\u2018 {implementation of class List for the Scala programming language}. https:\/\/github.com\/scala\/scala\/blob\/2.13.x\/src\/library\/scala\/collection\/ immutable\/List.scala . Accessed: 2017-11-27."},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the Second Asian Workshop on Programming Languages and Systems (APLAS\u201901)","author":"Garrigue Jacques","year":"2001","unstructured":"Jacques Garrigue . 2001 . Simple Type Inference for Structural Polymorphism . In Proceedings of the Second Asian Workshop on Programming Languages and Systems (APLAS\u201901) . 329\u2013343. Also presented as { Garrigue 2002 }. Jacques Garrigue. 2001. Simple Type Inference for Structural Polymorphism. In Proceedings of the Second Asian Workshop on Programming Languages and Systems (APLAS\u201901). 329\u2013343. Also presented as { Garrigue 2002 }."},{"key":"e_1_2_2_15_1","volume-title":"Simple Type Inference for Structural Polymorphism. In Ninth International Workshop on Foundations of Object-Oriented Languages. 1\u201311","author":"Garrigue Jacques","year":"2002","unstructured":"Jacques Garrigue . 2002 . Simple Type Inference for Structural Polymorphism. In Ninth International Workshop on Foundations of Object-Oriented Languages. 1\u201311 . http:\/\/www.cs.cmu.edu\/{\\char\u2019 176}aldrich\/FOOL\/papers9\/garrigue.ps Also presented as { Garrigue 2001 }. Jacques Garrigue. 2002. Simple Type Inference for Structural Polymorphism. In Ninth International Workshop on Foundations of Object-Oriented Languages. 1\u201311. http:\/\/www.cs.cmu.edu\/{\\char\u2019 176}aldrich\/FOOL\/papers9\/garrigue.ps Also presented as { Garrigue 2001 }."},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the Eighth Asian Symposium on Programming Languages and Systems (APLAS 2010","author":"Garrigue Jacques","year":"2010","unstructured":"Jacques Garrigue . 2010 . A Certified Implementation of ML with Structural Polymorphism. In Programming Languages and Systems, Kazunori Ueda (Ed.). Springer Berlin Heidelberg, 360\u2013375. LNCS 6461 . Proceedings of the Eighth Asian Symposium on Programming Languages and Systems (APLAS 2010 ), Shanghai, China. More complete journal version is { Garrigue 2015 }. Jacques Garrigue. 2010. A Certified Implementation of ML with Structural Polymorphism. In Programming Languages and Systems, Kazunori Ueda (Ed.). Springer Berlin Heidelberg, 360\u2013375. LNCS 6461. Proceedings of the Eighth Asian Symposium on Programming Languages and Systems (APLAS 2010), Shanghai, China. More complete journal version is { Garrigue 2015 }."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129513000066"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1152649.1152650"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25379-9_20"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785477_21"},{"volume-title":"ECOOP","author":"Millstein Todd","key":"e_1_2_2_21_1","unstructured":"Todd Millstein and Craig Chambers . 1999. Modular Statically Typed Multimethods . In ECOOP \u2019 99 \u2014 Object-Oriented Programming, Rachid Guerraoui (Ed.). Springer Berlin Heidelberg , Berlin, Heidelberg, 279\u2013303. Todd Millstein and Craig Chambers. 1999. Modular Statically Typed Multimethods. In ECOOP\u2019 99 \u2014 Object-Oriented Programming, Rachid Guerraoui (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 279\u2013303."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2002.3103"},{"key":"e_1_2_2_24_1","volume-title":"Programming in Scala","author":"Odersky Martin","unstructured":"Martin Odersky , Lex Spoon , and Bill Venners . 2016. Programming in Scala ( 3 rd ed.). Artima Press , Walnut Creek , California, USA. ISBN 978-0981531687. Martin Odersky, Lex Spoon, and Bill Venners. 2016. Programming in Scala (3rd ed.). Artima Press, Walnut Creek, California, USA. ISBN 978-0981531687.","edition":"3"},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Gyunghee Park Jaemin Hong Guy L. Steele  Jr. and Sukyoung Ryu. 2018. Polymorphic Symmetric Multiple Dispatch with Variance (Extended Report).  Gyunghee Park Jaemin Hong Guy L. Steele Jr. and Sukyoung Ryu. 2018. Polymorphic Symmetric Multiple Dispatch with Variance (Extended Report).","DOI":"10.1145\/3290324"},{"key":"e_1_2_2_26_1","unstructured":"Guy Steele and David Chase. 2012. Personal communication.  Guy Steele and David Chase. 2012. Personal communication."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018773"},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the 16th Ada-Europe International Conference on Reliable Software Technologies (Ada-Europe\u201911)","author":"Taft S. Tucker","year":"2011","unstructured":"S. Tucker Taft . 2011 . Multicore Programming in ParaSail: Parallel Specification and Implementation Language . In Proceedings of the 16th Ada-Europe International Conference on Reliable Software Technologies (Ada-Europe\u201911) . Springer-Verlag, Berlin, Heidelberg, 196\u2013200. http:\/\/dl.acm.org\/citation.cfm?id= 2018027.2018049 S. Tucker Taft. 2011. Multicore Programming in ParaSail: Parallel Specification and Implementation Language. In Proceedings of the 16th Ada-Europe International Conference on Reliable Software Technologies (Ada-Europe\u201911). Springer-Verlag, Berlin, Heidelberg, 196\u2013200. http:\/\/dl.acm.org\/citation.cfm?id=2018027.2018049"},{"volume-title":"a new programming language (blog)","author":"Taft S. Tucker","key":"e_1_2_2_29_1","unstructured":"S. Tucker Taft . 2016. Designing ParaSail , a new programming language (blog) . http:\/\/parasail- programming- language. blogspot.com . Accessed: 2018-04-09. S. Tucker Taft. 2016. Designing ParaSail, a new programming language (blog). http:\/\/parasail- programming- language. blogspot.com . Accessed: 2018-04-09."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429121"},{"key":"e_1_2_2_31_1","volume-title":"FHJ: A Formal Model for Hierarchical Dispatching and Overriding. In 32nd European Conference on Object-Oriented Programming, ECOOP 2018","author":"Wang Yanlin","year":"2018","unstructured":"Yanlin Wang , Haoyuan Zhang , Bruno C. d. S. Oliveira , and Marco Servetto . 2018 . FHJ: A Formal Model for Hierarchical Dispatching and Overriding. In 32nd European Conference on Object-Oriented Programming, ECOOP 2018 , July 16-21, 2018, Amsterdam, The Netherlands. 20:1\u201320:30. Yanlin Wang, Haoyuan Zhang, Bruno C. d. S. Oliveira, and Marco Servetto. 2018. FHJ: A Formal Model for Hierarchical Dispatching and Overriding. In 32nd European Conference on Object-Oriented Programming, ECOOP 2018, July 16-21, 2018, Amsterdam, The Netherlands. 20:1\u201320:30."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1093"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290324","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3290324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:07Z","timestamp":1750208527000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,2]]},"references-count":31,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2019,1,2]]}},"alternative-id":["10.1145\/3290324"],"URL":"https:\/\/doi.org\/10.1145\/3290324","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2019,1,2]]},"assertion":[{"value":"2019-01-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}