{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T07:52:04Z","timestamp":1790927524335,"version":"4.1.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","funder":[{"name":"FNSNF","award":["TMAG-2_209506\/1"],"award-info":[{"award-number":["TMAG-2_209506\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,10,9]]},"abstract":"<jats:p>Capturing types in Scala unify static effect and resource tracking with object capabilities, enabling lightweight effect polymorphism with minimal notational overhead. However, their expressiveness has been insufficient for tracking capabilities embedded in generic data structures, preventing them from scaling to the standard collections library - an essential prerequisite for broader adoption. This limitation stems from the inability to name capabilities within the system's notion of box types.<\/jats:p>\n                  <jats:p>This paper develops System Capless, a new foundation for capturing types that provides the theoretical basis for reach capabilities (rcaps), a novel mechanism for naming \"what's in the box\". The calculus refines the universal capability notion into a new scheme with existential and universal capture set quantification. Intuitively, rcaps witness existentially quantified capture sets inside the boxes of generic types in a way that does not require exposing existential capture types in the surface language. We have fully mechanized the formal metatheory of System Capless in Lean, including proofs of type soundness and scope safety. System Capless supports the same lightweight notation of capturing types plus rcaps, as certified by a type-preserving translation, and also enables fully optional explicit capture-set quantification to increase expressiveness.<\/jats:p>\n                  <jats:p>Finally, we present a full reimplementation of capture checking in Scala 3 based on System Capless and migrate the entire Scala collections library and an asynchronous programming library to evaluate its practicality and ergonomics. Our results demonstrate that reach capabilities enable the adoption of capture checking in production code with minimal changes and minimal-to-zero notational overhead in a vast majority of cases.<\/jats:p>","DOI":"10.1145\/3763112","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:49:50Z","timestamp":1759999790000},"page":"1726-1753","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["What\u2019s in the Box: Ergonomic and Expressive Capture Tracking over Generic Data Structures"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2089-6767","authenticated-orcid":false,"given":"Yichen","family":"Xu","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3569-4869","authenticated-orcid":false,"given":"Oliver","family":"Bra\u010devac","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2543-3309","authenticated-orcid":false,"given":"Cao Nguyen","family":"Pham","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3923-8993","authenticated-orcid":false,"given":"Martin","family":"Odersky","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"crossref","unstructured":"Ellen Arvidsson Elias Castegren Sylvan Clebsch Sophia Drossopoulou James Noble Matthew J. Parkinson andTobias Wrigstad. 2023. Reference capabilities for flexible memory management. Proc. ACM Program. Lang. 7 OOPSLA2 1363-1393 (cit. on p. 25).","DOI":"10.1145\/3622846"},{"key":"e_1_3_1_3_2","doi-asserted-by":"crossref","unstructured":"Thibaut Balabonski Fran\u00e7ois Pottier and Jonathan Protzenko. 2016. The design and formalization of Mezzo a permission-based programming language. ACM Trans. Program. Lang. Syst. 38 4 14:1-14:94 (cit. on p. 25).","DOI":"10.1145\/2837022"},{"key":"e_1_3_1_4_2","doi-asserted-by":"crossref","unstructured":"Yuyan Bao Guannan Wei Oliver Bra\u010devac Yuxuan Jiang Qiyang He and Tiark Rompf. 2021. Reachability types: Tracking aliasing and separation in higher-order functional programs. Proc. ACM Program. Lang. 5 OOPSLA 1-32 (cit. on p. 23).","DOI":"10.1145\/3485516"},{"key":"e_1_3_1_5_2","first-page":"579","volume-title":"Uniqueness typing for functional languages with graph rewriting semantics","author":"Barendsen Erik","year":"1996","unstructured":"Erik Barendsen and Sjaak Smetsers. 1996. Uniqueness typing for functional languages with graph rewriting semantics. Math. Struct. Comput. Sci., 6, 6, 579-612 (cit. on p. 24)."},{"key":"e_1_3_1_6_2","doi-asserted-by":"crossref","unstructured":"Aleksander Boruch-Gruszecki Martin Odersky Edward Lee Ondrej Lhot\u00e1k and Jonathan Immanuel Brachth\u00e4user. 2023. Capturing types. ACM Trans. Program. Lang. Syst. 45 4 21:1-21:52 (cit. on pp. 1-5 7 10-14 17 25).","DOI":"10.1145\/3618003"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604156"},{"key":"e_1_3_1_8_2","unstructured":"Oliver Bra\u010devac Guannan Wei Songlin Jia Supun Abeysinghe Yuxuan Jiang Yuyan Bao and Tiark Rompf. 2023. Graph IRs for impure higher-order languages (technical report). CoRR abs\/2309.08118 (cit. on p. 23)."},{"key":"e_1_3_1_9_2","doi-asserted-by":"crossref","unstructured":"Oliver Bra\u010devac Guannan Wei Songlin Jia Supun Abeysinghe Yuxuan Jiang Yuyan Bao and Tiark Rompf. 2023. Graph IRs for impure higher-order languages: Making aggressive optimizations affordable with precise effect dependencies. Proc. ACM Program. Lang. 7 OOPSLA2 400-430 (cit. on p. 23).","DOI":"10.1145\/3622813"},{"key":"e_1_3_1_10_2","first-page":"1","volume-title":"Effects, capabilities, and boxes: From scope-based reasoning to type-based reasoning and back","author":"Brachth\u00e4user Jonathan Immanuel","year":"2022","unstructured":"Jonathan Immanuel Brachth\u00e4user, Philipp Schuster, Edward Lee, and Aleksander Boruch-Gruszecki. 2022. Effects, capabilities, and boxes: From scope-based reasoning to type-based reasoning and back. Proc. ACM Program. Lang., 6, OOPSLA, 1-30 (cit. on pp. 1, 2, 24)."},{"key":"e_1_3_1_11_2","doi-asserted-by":"crossref","unstructured":"Jonathan Immanuel Brachth\u00e4user Philipp Schuster and Klaus Ostermann. 2020. Effects as capabilities: Effect handlers and lightweight effect polymorphism. Proc. ACM Program. Lang. 4 OOPSLA 126:1-126:30 (cit. on pp. 1 2).","DOI":"10.1145\/3428194"},{"key":"e_1_3_1_12_2","unstructured":"2021. Canthrow capabilities. Accessed: 2025-07-28.https:\/\/docs.scala-lang.org\/scala3\/reference\/experimental\/canthrow.html(cit. on p. 24)."},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","unstructured":"Dave Clarke Johan \u00d6stlund Ilya Sergey and Tobias Wrigstad. 2013. Ownership types: A survey. In Aliasing in Object-Oriented Programming. Lecture Notes in Computer Science. Vol. 7850. Springer 15-58 (cit. on p. 24).","DOI":"10.1007\/978-3-642-36946-9_3"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2824815.2824816"},{"key":"e_1_3_1_15_2","first-page":"72:1","volume-title":"Orca: GC and type system co-design for actor languages","author":"Clebsch Sylvan","year":"2017","unstructured":"Sylvan Clebsch, Juliana Franco, Sophia Drossopoulou, Albert Mingkun Yang, Tobias Wrigstad, and Jan Vitek. 2017. Orca: GC and type system co-design for actor languages. Proc. ACM Program. Lang., 1, OOPSLA, 72:1-72:28 (cit. on p. 25)."},{"key":"e_1_3_1_16_2","first-page":"1","volume-title":"Doo bee doo bee doo.","author":"Convent Lukas","year":"2020","unstructured":"Lukas Convent, Sam Lindley, Conor McBride, and Craig McLaughlin. 2020. Doo bee doo bee doo. 7. Funct. Program., 30, e9 (cit. on pp. 1, 2, 25)."},{"key":"e_1_3_1_17_2","first-page":"28","volume-title":"Generic universe types. In ECOOP (Lecture Notes in Computer Science).","author":"Dietl Werner","year":"2007","unstructured":"Werner Dietl, Sophia Drossopoulou, and Peter M\u00fcller. 2007. Generic universe types. In ECOOP (Lecture Notes in Computer Science). Vol. 4609. Springer, 28-53 (cit. on p. 24)."},{"key":"e_1_3_1_18_2","first-page":"34","volume-title":"A case study in language-based security: Building an I\/O library for Wyvern","author":"Fish Jennifer A.","year":"2020","unstructured":"Jennifer A. Fish, Darya Melicher, and Jonathan Aldrich. 2020. A case study in language-based security: Building an I\/O library for Wyvern. In Onward! ACM, 34-47 (cit. on p. 25)."},{"key":"e_1_3_1_19_2","first-page":"192","volume-title":"A theory of type qualifiersIn PLDI","author":"Foster Jeffrey S","year":"1999","unstructured":"Jeffrey S. Foster, Manuel F\u00e4hndrich, and Alexander Aiken. 1999.A theory of type qualifiers. In PLDI. ACM, 192-203 (cit. on p. 25)."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2020.10"},{"key":"e_1_3_1_21_2","first-page":"282","volume-title":"Regionbased memory management in Cyclone","author":"Grossman Dan","year":"2002","unstructured":"Dan Grossman,J. Gregory Morrisett, Trevor Jim, Michael W. Hicks, Yanling Wang, and James Cheney. 2002. Regionbased memory management in Cyclone. In PLDI. ACM, 282-293 (cit. on p. 24)."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/174675.178053"},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","unstructured":"Mark P. Jones. 1994. A theory of qualified types. Sci. Comput. Program. 22 3 231-256 (cit. on p. 25).","DOI":"10.1016\/0167-6423(94)00005-0"},{"key":"e_1_3_1_24_2","unstructured":"2015. Leaking local reach capability. Accessed: 2025-03-23. https:\/\/github.com\/scala\/scala3\/issues\/21442(cit. on pp. 3 8)."},{"key":"e_1_3_1_25_2","doi-asserted-by":"crossref","unstructured":"Edward Lee Yaoyu Zhao Ondrej Lhot\u00e1k James You Kavin Satheeskumar and Jonathan Immanuel Brachth\u00e4user. 2024. Qualifying system F_<: Some terms and conditions may apply. Proc. ACM Program. Lang. 8 OOPSLA1 583-612 (cit. on p. 25).","DOI":"10.1145\/3649832"},{"key":"e_1_3_1_26_2","first-page":"500","volume-title":"Do be do be doIn POPL","author":"Lindley Sam","year":"2017","unstructured":"Sam Lindley, Conor McBride, and Craig McLaughlin. 2017. Do be do be do. In POPL. ACM, 500-514 (cit. on pp. 1, 2, 25)."},{"key":"e_1_3_1_27_2","first-page":"30 pages","volume-title":"Oxidizing OCaml with modal memory management","author":"Lorenzen Anton","year":"2024","unstructured":"Anton Lorenzen, Leo White, Stephen Dolan, Richard A. Eisenberg, and Sam Lindley. 2024. Oxidizing OCaml with modal memory management. Proc. ACM Program. Lang., 8, ICFP, Article 253, (Aug. 2024), 30 pages (cit. on p. 25)."},{"key":"e_1_3_1_28_2","first-page":"47","article-title":"Polymorphic effect systems","author":"Lucassen John M","year":"1988","unstructured":"John M. Lucassen and David K. Gifford. 1988. Polymorphic effect systems. In POPL. ACM Press, 47-57 (cit. on p. 24).","journal-title":"In POPL"},{"key":"e_1_3_1_29_2","first-page":"394","volume-title":"Associated effects: Flexible abstractions for effectful programming","author":"Lutze Matthew","year":"2024","unstructured":"Matthew Lutze and Magnus Madsen. 2024. Associated effects: Flexible abstractions for effectful programming. Proc. ACM Program. Lang., 8, PLDI, 394-416 (cit. on p. 25)."},{"key":"e_1_3_1_30_2","first-page":"346","article-title":"Linearity and uniqueness: An entente cordiale","volume":"13240","author":"Marshall Danielle","year":"2022","unstructured":"Danielle Marshall, Michael Vollmer, and Dominic Orchard. 2022. Linearity and uniqueness: An entente cordiale. In ESOP (Lecture Notes in Computer Science). Vol. 13240. Springer, 346-375 (cit. on p. 24).","journal-title":"In ESOP (Lecture Notes in Computer Science)"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2663171.2663188"},{"key":"e_1_3_1_32_2","first-page":"20:1","volume-title":"A capability-based module system for authority controlIn ECOOP (LIPIcs)","author":"Melicher Darya","year":"2017","unstructured":"Darya Melicher, Yangqingwei Shi, Alex Potanin, and Jonathan Aldrich. 2017. A capability-based module system for authority control. In ECOOP (LIPIcs). Vol. 74. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 20:1-20:27 (cit. on p. 25)."},{"key":"e_1_3_1_33_2","doi-asserted-by":"crossref","unstructured":"Darya Melicher Anlun Xu Valerie Zhao Alex Potanin and Jonathan Aldrich. 2022. Bounded abstract effects. ACM Trans. Program. Lang. Syst. 44 1 5:1-5:48 (cit. on p. 25).","DOI":"10.1145\/3492427"},{"key":"e_1_3_1_34_2","first-page":"2","volume-title":"Robust Composition: Towards a Unified Approach to Access Control and Concurrency Control","author":"Miller Mark S","year":"2006","unstructured":"Mark S. Miller. 2006. Robust Composition: Towards a Unified Approach to Access Control and Concurrency Control. Ph.D. Dissertation. John Hopkins University (cit. on pp. 2, 25)."},{"key":"e_1_3_1_35_2","doi-asserted-by":"crossref","unstructured":"Aleksandar Nanevski Frank Pfenning and Brigitte Pientka. 2008. Contextual modal type theory. ACM Trans. Comput. Log. 9 3 23:1-23:49 (cit. on p. 24).","DOI":"10.1145\/1352582.1352591"},{"key":"e_1_3_1_36_2","first-page":"158","article-title":"Flexible alias protection.","volume":"1445","author":"Noble James","year":"1998","unstructured":"James Noble, Jan Vitek, and John Potter. 1998. Flexible alias protection. In ECOOP (Lecture Notes in Computer Science). Vol. 1445. Springer, 158-185 (cit. on p. 24).","journal-title":"In ECOOP (Lecture Notes in Computer Science)"},{"key":"e_1_3_1_37_2","unstructured":"Robert Nystrom. 2015. What colour is your function? Accessed: 2024-09-09. https:\/\/web.archive.org\/web\/20241009152925\/\/journal.stuffwithstuff.com\/2015\/02\/01\/what-color-is-your-function\/(cit. on p. 23)."},{"key":"e_1_3_1_38_2","doi-asserted-by":"crossref","unstructured":"Martin Odersky Olivier Blanvillain Fengyun Liu Aggelos Biboudis Heather Miller and Sandro Stucki. 2018. Simplicitly: Foundations and applications of implicit function types. Proc. ACM Program. Lang. 2 POPL 42:1-42:29 (cit. on p. 18).","DOI":"10.1145\/3158130"},{"key":"e_1_3_1_39_2","first-page":"1","volume-title":"Safer exceptions for ScalaIn SCALA\/SPLASH","author":"Odersky Martin","year":"2021","unstructured":"Martin Odersky, Aleksander Boruch-Gruszecki, Jonathan Immanuel Brachth\u00e4user, Edward Lee, and Ondrej Lhot\u00e1k. 2021. Safer exceptions for Scala. In SCALA\/SPLASH. ACM, 1-11 (cit. on pp. 5, 24)."},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984009"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3679005.3685979"},{"key":"e_1_3_1_42_2","unstructured":"[SW Mod.] Pony Pony Programming Language 2024 Pony Development Team. url:https:\/\/web.archive.org\/web\/20241007175842\/https:\/\/www.ponylang.io\/ vcs:https:\/\/github.com\/ponylang\/ponyc (cit. on p. 25)."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167500"},{"key":"e_1_3_1_44_2","unstructured":"2015. Reach capabilities get dropped in cv. Accessed: 2025-03-23. https:\/\/github.com\/scala\/scala3\/issues\/19571 (cit. on pp. 3 8)."},{"key":"e_1_3_1_45_2","unstructured":"2015. Reach capabilities of function arguments get ignored. Accessed: 2025-03-23. https:\/\/github.com\/scala\/scala3\/issues\/20503 (cit. on pp. 3 8)."},{"key":"e_1_3_1_46_2","doi-asserted-by":"crossref","unstructured":"Tiark Rompf and Nada Amin. 2016. Type soundness for dependent object types (DOT). In OOPSLA. ACM 624-641 (cit. on pp. 22 25).","DOI":"10.1145\/2983990.2984008"},{"key":"e_1_3_1_47_2","doi-asserted-by":"crossref","unstructured":"Jean-Pierre Talpin and Pierre Jouvelot. 1994. The type and effect discipline. Inf. Comput. 111 2 245-296 (cit. on p. 24).","DOI":"10.1006\/inco.1994.1046"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3720476"},{"key":"e_1_3_1_49_2","doi-asserted-by":"crossref","unstructured":"Mads Tofte and Jean-Pierre Talpin. 1997. Region-based memory management. Inf. Comput. 132 2 109-176 (cit. on p. 24).","DOI":"10.1006\/inco.1996.2613"},{"key":"e_1_3_1_50_2","first-page":"561","volume-title":"Linear types can change the world! In Programming Concepts and Methods.","author":"Wadler Philip","year":"1990","unstructured":"Philip Wadler. 1990. Linear types can change the world! In Programming Concepts and Methods. North-Holland, 561 (cit. on p. 24)."},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/99370.99404"},{"key":"e_1_3_1_52_2","doi-asserted-by":"crossref","unstructured":"Guannan Wei Oliver Bra\u010devac Songlin Jia Yuyan Bao and Tiark Rompf. 2024. Polymorphic reachability types: Tracking freshness aliasing and separation in higher-order generic programs. Proc. ACM Program. Lang. 8 POPL 393-424 (cit. on pp. 23 24).","DOI":"10.1145\/3632856"},{"key":"e_1_3_1_53_2","first-page":"15:1","article-title":"What if we don't pop the stack? The return of 2nd-class values","volume":"222","author":"Xhebraj Anxhelo","year":"2022","unstructured":"Anxhelo Xhebraj, Oliver Bra\u010devac, Guannan Wei, and Tiark Rompf. 2022. What if we don't pop the stack? The return of 2nd-class values. In ECOOP (LIPIcs). Vol. 222. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1-15:29 (cit. on p. 25).","journal-title":"In ECOOP (LIPIcs)"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","unstructured":"Yichen Xu Aleksander Boruch-Gruszecki and Martin Odersky. 2024. Degrees of separation: A flexible type system for safe concurrency. Proc. ACM Program. Lang. 8 OOPSLA1 1181-1207. doi:10.1145\/3649853(cit. on p. 23).","DOI":"10.1145\/3649853"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","unstructured":"[SW] Yichen Xu Oliver Bra\u010devac Cao Nguyen Pham and Martin Odersky Artifact for \"What's in the Box: Ergonomic and Expressive Capture Tracking over Generic Data Structures\" Aug. 2025. doi:10.5281\/zenodo.16922930 (cit. on pp. 4 26).","DOI":"10.5281\/zenodo.16922930"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","unstructured":"Yichen Xu Oliver Bra\u010devac Cao Nguyen Pham and Martin Odersky. 2025. What's in the Box: Ergonomic and Expressive Capture Tracking over Generic Data Structures (Extended Version). doi:10.48550\/arXiv.2509.07609 (cit. on pp. 10 12 13 16-18).","DOI":"10.48550\/arXiv.2509.07609"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3660829.3660851"},{"key":"e_1_3_1_58_2","unstructured":"Yichen Xu and Martin Odersky. 2023. Formalizing box inference for capture calculus. ArXiv abs\/2306.06496(cit. on p. 6)."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:07:34Z","timestamp":1784196454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":57,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763112"],"URL":"https:\/\/doi.org\/10.1145\/3763112","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-03-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}