Fully-Automatic Type Inference for Borrows with Lifetimes
Open Access
- 10 April 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA1) , 597-623
Abstract
We present a new pure functional language and type system with borrows with lifetimes, and a corresponding fully-automatic type inference procedure. Inference provides users the performance benefits of borrows with lifetimes without requiring user annotation. If the user's program cannot be typed, inference inserts a handful of reference count operations so that it can be typed. We provide a heap semantics for our borrowing language and prove a soundness theorem, guaranteeing that well-typed programs do not violate memory safety. We implement our memory management strategy as part of the Morphic language stack and compare it to Perceus, a state-of-the-art reference-counting technique based on linear type inference. We find that our system is able to eliminate almost all reference count operations across a range of programs, reducing reference count increments by 75-100% on all benchmarks with reference count increments under the baseline. As a result, we achieve a 1.48x geomean speedup overall on all benchmarks.Keywords
Funding Information
- National Science Foundation (2216964)
This publication has 16 references indexed in Scilit:
- Reachability types: tracking aliasing and separation in higher-order functional programsProceedings of the ACM on Programming Languages, 2021
- Perceus: garbage free reference counting with reuse2021
- A Lightweight Formalism for Reference Lifetimes and Borrowing in RustACM Transactions on Programming Languages and Systems, 2021
- Stacked borrows: an aliasing model for RustProceedings of the ACM on Programming Languages, 2019
- Counting immutable beans2019
- RustBelt: securing the foundations of the Rust programming languageProceedings of the ACM on Programming Languages, 2017
- Once upon a polymorphic type1999
- The essence of compiling with continuations1993
- Garbage collection in an uncooperative environmentSoftware: Practice and Experience, 1988
- The aggregate update problem in functional programming systems1985