{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T06:13:42Z","timestamp":1784182422707,"version":"3.55.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["2303983"],"award-info":[{"award-number":["2303983"]}]},{"name":"Amazon Research Awards","award":["Extensible models and proofs"],"award-info":[{"award-number":["Extensible models and proofs"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,4,29]]},"abstract":"<jats:p>Many obstacles stand in the way of modular, extensible code. Some language constructs, such as pattern matching, are not easily extensible. Inherited code may not be type safe in the presence of extended types. The burden of setting up design patterns can discourage users, and parameter clutter can make the code less readable. Given these challenges, it is no wonder that extensibility often gives way to code duplication. We present our solution: Persimmon, a functional system with nested family polymorphism, extensible variant types, and extensible pattern matching. Most constructs in our language are built-in \"extensibility hooks,\" cutting down on the parameter clutter and user burden associated with extensible code. Persimmon preserves the relationships between nested families upon inheritance, enabling extensibility at a large scale. Since nested family polymorphism can express composable extensions, Persimmon supports mixins via an encoding. We show how Persimmon can be compiled into a functional language without extensible variants with our translation to Scala. Finally, we show that our system is sound by proving the properties of progress and preservation.<\/jats:p>","DOI":"10.1145\/3649836","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T17:53:50Z","timestamp":1714413230000},"page":"698-724","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Persimmon: Nested Family Polymorphism with Extensible Variant Types"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-0357-9690","authenticated-orcid":false,"given":"Anastasiya","family":"Kravchuk-Kirilyuk","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-0891-3041","authenticated-orcid":false,"given":"Gary","family":"Feng","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3181-1407","authenticated-orcid":false,"given":"Jonas","family":"Iskander","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8206-4694","authenticated-orcid":false,"given":"Yizhou","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0830-7248","authenticated-orcid":false,"given":"Nada","family":"Amin","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Florent Balestrieri and Michel Mauny. 2018. Generic programming in OCaml. arXiv preprint arXiv:1812.11665.","DOI":"10.4204\/EPTCS.285.3"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159803.1159836"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263735"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809007205"},{"key":"e_1_2_2_5_1","volume-title":"Associated Types with Class. In ACM Symp. on Principles of Programming Languages (POPL).","author":"Chakravarty Manuel M. T.","year":"2005","unstructured":"Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow. 2005. Associated Types with Class. In ACM Symp. on Principles of Programming Languages (POPL)."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1218563.1218578"},{"key":"e_1_2_2_7_1","volume-title":"European Conference on Object-Oriented Programming. 273\u2013298","author":"Emir Burak","year":"2007","unstructured":"Burak Emir, Martin Odersky, and John Williams. 2007. Matching objects with patterns. In European Conference on Object-Oriented Programming. 273\u2013298."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45337-7_17"},{"key":"e_1_2_2_9_1","volume-title":"European Conference on Object-Oriented Programming. 303\u2013328","author":"Ernst Erik","year":"2003","unstructured":"Erik Ernst. 2003. Higher-order hierarchies. In European Conference on Object-Oriented Programming. 303\u2013328."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111037.1111062"},{"key":"e_1_2_2_11_1","volume-title":"37th European Conference on Object-Oriented Programming (ECOOP","author":"Fan Andong","year":"2023","unstructured":"Andong Fan and Lionel Parreaux. 2023. super-Charging Object-Oriented Programming Through Precise Typing of Open Recursion. In 37th European Conference on Object-Oriented Programming (ECOOP 2023)."},{"key":"e_1_2_2_12_1","volume-title":"Design Patterns: Elements of Reusable Object-Oriented Software","author":"Gamma Erich","year":"1994","unstructured":"Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. 1994. Design Patterns: Elements of Reusable Object-Oriented Software. Addison Wesley."},{"key":"e_1_2_2_13_1","volume-title":"ML workshop. 13","author":"Garrigue Jacques","year":"1998","unstructured":"Jacques Garrigue. 1998. Programming with polymorphic variants. In ML workshop. 13."},{"key":"e_1_2_2_14_1","unstructured":"Jacques Garrigue. 2000. Code reuse through polymorphic variants. Sasaguri Japan."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_12"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297027.1297037"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462194"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591286"},{"key":"e_1_2_2_20_1","volume-title":"Generic and Indexed Programming","author":"Kiselyov Oleg","unstructured":"Oleg Kiselyov. 2012. Typed tagless final interpreters. In Generic and Indexed Programming. Springer, 130\u2013174."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.10798266"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140335.1140352"},{"key":"e_1_2_2_23_1","unstructured":"O. Lehrmann Madsen B. M\u00f8ller-Pedersen and K. Nygaard. 1993. Object Oriented Programming in the BETA Programming Language. Addison-Wesley."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1018203.1018207"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028976.1028986"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167515.1167476"},{"key":"e_1_2_2_27_1","unstructured":"Martin Odersky and Matthias Zenger. 2005. Independently Extensible Solutions to the Expression Problem. ACM."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094815"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31057-7_2"},{"key":"e_1_2_2_30_1","volume-title":"European Conf. on Object-Oriented Programming.","author":"Jones Simon Peyton","year":"2009","unstructured":"Simon Peyton Jones. 2009. Classes, Jim, But Not as We Know Them\u2014Type Classes in Haskell: What, Why, and Whither. In European Conf. on Object-Oriented Programming."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291159"},{"key":"e_1_2_2_32_1","volume-title":"European Conf. on Object-Oriented Programming.","author":"Thorup Kresten Krab","year":"1997","unstructured":"Kresten Krab Thorup. 1997. Genericity in Java with virtual types. In European Conf. on Object-Oriented Programming."},{"key":"e_1_2_2_33_1","unstructured":"Sam Tobin-Hochstadt. 2011. Extensible pattern matching in an extensible language. arXiv preprint arXiv:1106.2578."},{"key":"e_1_2_2_34_1","unstructured":"Philip Wadler. 1998. The expression problem. Discussion on Java-Genericity mailing list. https:\/\/homepages.inf.ed.ac.uk\/wadler\/papers\/expression\/expression.txt"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/507635.507665"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2020.102449"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460228"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133894"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649836","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649836","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:06Z","timestamp":1750287246000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649836"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":37,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2024,4,29]]}},"alternative-id":["10.1145\/3649836"],"URL":"https:\/\/doi.org\/10.1145\/3649836","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"2024-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}