When Lifetimes Liberate: A Type System for Arenas with Higher-Order Reachability Tracking
Statically enforcing safe resource management is challenging due to tensions between flexible lifetime disciplines and expressive sharing patterns. Region-based systems offer lexically scoped regions under a stack discipline, wherein resources are managed in bulk. In many such systems, however, resources are second-class and can neither escape their scope nor be freely returned from functions. Ownership and linear type systems, such as Rust, offer first-class, non-lexical lifetimes with robust static guarantees, but rely on invariants that limit higher-order patterns and expressive sharing.
In this work, we propose a type system that uniformly treats all heap-allocated resources under diverse lifetime, granularity, and sharing settings. Our system provides programmers with three allocation modes: (1) fresh allocation for first-class, non-lexical resources; (2) fresh allocation for second-class resources with lexically bounded lifetimes; and (3) coallocation that groups resources by shadow arenas for bulk tracking and deallocation. Regardless of mode, resources are represented uniformly at the type level, supporting generic abstraction and preserving the higher-order parametric nature of the language.
Obtaining static safety in higher-order languages with flexible sharing is nontrivial. To address this, our solution builds on reachability types, and our extension adds the capability to track both individual and grouped resources, enables the expression of cyclic store structures, and allows the selective enforcing of stack lifetime discipline. These mechanisms are formalized in the $\mathsf{A}{<:}^{\vardiamondsuit}$ and ${\left{\mathsf{A}\right}}{<:}^{\vardiamondsuit}$ type systems, which are proven type safe and memory safe in Rocq.
Wed 7 OctDisplayed time zone: Pacific Time (US & Canada) change
10:30 - 12:00 | Ownership, Lifetimes and RegionsOOPSLA at Junior Ballroom 1&2 Chair(s): Jenna DiVincenzo (Wise) Purdue University | ||
10:30 18mTalk | Tracking Borrows with Regular Expressions OOPSLA Todd Nowacki Mysten Labs, Sam Blackshear Mysten Labs, John Mitchell Stanford University, Shaz Qadeer Microsoft, Ilya Sergey National University of Singapore DOI | ||
10:48 18mTalk | When Lifetimes Liberate: A Type System for Arenas with Higher-Order Reachability Tracking OOPSLA Siyuan He Purdue University, Songlin Jia Purdue University, Yuyan Bao Augusta University, Tiark Rompf Purdue University DOI | ||
11:06 18mTalk | Fully-Automatic Type Inference for Borrows with Lifetimes OOPSLA William Brandon Massachusetts Institute of Technology, Benjamin Driscoll Stanford University, Frank Dai Unaffiliated, Jonathan Ragan-Kelley Massachusetts Institute of Technology, Mae Milano Princeton University, Alex Aiken Stanford University DOI | ||
11:24 18mTalk | Scylla: Translating an Applicative Subset of C to Safe RustDistinguished Paper OOPSLA DOI | ||