Pure Borrow: Linear Haskell Meets Rust-Style Borrowing Note: This is an extended version of the PLDI 2026 paper ( MatsushitaIshii26-Pure-Borrow ) with an appendix on the formal calculus and metatheory. Journal: PACMPL CCS: Theory of computation Type theory CCS: Software and its engineering Functional languages
Yusuke Matsushita, Hiromi Ishii · 2026
Read Pure Borrow: Linear Haskell Meets Rust-Style Borrowing Note: This is an extended version of the PLDI 2026 paper ( MatsushitaIshii26-Pure-Borrow ) with an appendix on the formal calculus and metatheory. Journal: PACMPL CCS: Theory of computation Type theory CCS: Software and its engineering Functional languages by Yusuke Matsushita, Hiromi Ishii (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-15290.txt.
Introduction
Matsushita and Ishii bring Rust-style borrowing to Linear Haskell, a pure functional language with linear types, answering whether safe non-local borrowing can live without giving up purity. Their Pure Borrow library lets borrowers split and drop freely while supporting parallel mutation inside pure computation, plus lazy evaluation and leak freedom. A parallel-computing case study shows its power, backed by a formal core and a history-based borrowing model.
Catalog record
| CREATOR | Yusuke Matsushita, Hiromi Ishii |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96439 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.15290
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pure Borrow: Linear Haskell Meets Rust-Style Borrowing Note: This is an extended version of the PLDI 2026 paper ( MatsushitaIshii26-Pure-Borrow ) with an appendix on the formal calculus and metatheory. Journal: PACMPL CCS: Theory of computation Type theory CCS: Software and its engineering Functional languages Yusuke Matsushita, Hiromi Ishii Abstract . A promising approach to unifying functional and imperative programming paradigms is to localize mutation using linear or affine types. Haskell, a purely functional language, was recently extended with linear types by Bernardy et al., in the name of Linear Haskell. However, it remained unknown whether such a pure language could safely support non-local borrowing in the style of Rust, where each borrower can be freely split and dropped without direct communication of ownership back to the lender. We answer this question affirmatively with Pure Borrow , a novel framework that realizes Rust-style borrowing in Linear Haskell with purity. Notably, it features parallel state mutation with affine mutable references inside pure computation, unlike the IO and ST monads and existing Linear Haskell APIs. It also enjoys purity, lazy evaluation, first-class polymorphism and leak freedom, unlike Rust. We implement Pure Borrow simply as a library in Linear Haskell and demonstrate its power with a case study in parallel computing. We formalize the core of Pure Borrow and build a metatheory that works toward establishing safety, leak freedom and confluence, with a new, history-based model of borrowing. † † cc-license: by 1. Introduction Software is the art of embodying human ideals on finite physical machines. This tension naturally leads to two major programming paradigms. One is functional programming , more on the side of humans. It offers high-level abstractions and safety for smooth human reasoning. The other is imperative programming , more geared toward machines. It offers low-level stateful operations, enabling great performance. Unifying these two programming paradigms has been a long-standing, central topic in programming language research. Functional programming favors purity , or the property that the result of the computation is always the same regardless of the timing and context. Purity allows one to safely forget the physical machine state and reason about behaviors just as in mathematics. It enables safe lazy evaluation, safe concurrency, and deep program optimizations such as fusion. Moreover, a number of languages—e.g., Haskell ( HudakPWBFFGHHJKNPP92-Haskell ) , F ⋆ ( SwamyHKRDFBFSKZ16-Fstar ) , and Lean ( MouraKADR15-Lean ) —rigorously ensure that every computation is pure , unless marked otherwise. Especially in the presence of concurrency, purity is really helpful because it eliminates tricky, subtle concurrency bugs that occur only with low probability depending on thread scheduling. Purity is thus desired, but naïvely it causes significant runtime overhead to keep all data persistently. This calls for unifying pure functional programming with performative, stateful imperative programming. A long-known baseline approach to this is the ST monad ( LaunchburyJ94-ST ) . The monad ST {}^{\mkern 3.0mu\textsf{s}} a allows efficient stateful computation, but its result can still be taken out into pure computation, unlike the IO monad ( PeytonJonesW93-IO ) . Table 1 . High-level comparison of our Pure Borrow with existing approaches. Yes 🌑 / No 🌕. Mutate : Supports destructive mutation. Pure : The result can be safely taken out in pure computation. Parallel : Supports safe parallel execution. Aff. mut. : Supports affine mutable references (◐ for droppable but copyable mutable references). Leak-free : Guarantees the absence of resource leaks. Mutate Pure Parallel Aff. mut. Leak-free Pure computation only 🌕 🌑 🌑 - - IO monad ( PeytonJonesW93-IO ) 🌑 🌕 🌑 ◐ 🌕 ST monad ( LaunchburyJ94-ST ) 🌑 🌑 🌕 ◐ 🌕 Rust ( MatsakisK14-Rust ) 🌑 🌕 🌑 🌑 🌕 Pure Linear Haskell ( BernardyBNJS18-Linear-Haskell ) 🌑 🌑 🌑 🌕 🌑 RIO monad ( BernardyBNJS18-Linear-Haskell ) 🌑 🌕 🌑 ◐ 🌑 Our Pure Borrow: BO monad 🌑 🌑 🌑 🌑 🌑 Another promising approach to this goal is to localize mutation using linear or affine types ( Wadler90-linear-type ; TurnerWM95-once-upon ; WansbroughJ99-once-upon-poly ) , requiring resources to be used exactly once (linear) or up to once (affine), inspired by Girard87-linear-logic ’s linear logic. Linear or affine types can localize the effect of state mutation, especially for safety. Also, linearity can prevent resource leaks. Haskell, a purely functional language, was recently extended with linear types by BernardyBNJS18-Linear-Haskell , in the name of Linear Haskell. It achieves safe state mutation inside pure computation, while supporting concurrency and ensuring leak freedom unlike the ST monad. It also introduced a leak-free variant of the IO monad, called the RIO monad. However, it remained unknown whether such a pure language as Linear Haskell could safely support borrowing in the sophisticated style of Rust ( MatsakisK14-Rust ) , a highly successful imperative language with affine types. While Rust-style borrowing originates from the long line of work on region types ( TofteT94-region-type ; FahndrichD02-adoption ; GrossmanMJHWC02-Cyclone-region ; FluetMA06-region ; HallerO10-borrow ) , it features a distinct form of non-locality : each borrower can be freely split and dropped (i.e., affine), and its ownership is non-locally returned to the lender without direct communication. This flexibility offers an advantage over the existing Linear Haskell APIs, which require direct threading of ownership. We answer the question above affirmatively with this work, Pure Borrow . Our contributions are summarized as follows: • We develop Pure Borrow , a novel framework that realizes Rust-style borrowing in Linear Haskell with purity. ( Section 3 ). Table 1 shows a high-level comparison with existing approaches. Notably, Pure Borrow features parallel state mutation with affine mutable references inside pure computation, unlike the IO and ST monads and existing Linear Haskell APIs. It also enjoys purity, lazy evaluation, first-class polymorphism and leak freedom, unlike Rust. • We implement Pure Borrow simply as a library in Linear Haskell and demonstrate its power by a case study on parallel quicksort ( Section 4 ). Notably, our implementation compiles with the current Haskell compiler GHC 9.10+, without any modification to the compiler. • We formalize the core of Pure Borrow and build a metatheory that works toward establishing safety, leak freedom and confluence, with a new, history-based model of borrowing ( Section 5 ). We also explain the background ( Section 2 ), compare Pure Borrow with existing approaches ( Section 6 ), and discuss related and future work ( ). Our Haskell implementation of Pure Borrow and our benchmark suite are archived at ( MatsushitaIshii26-Pure-Borrow-artifact ) , and the latest version is maintained at https://github.com/SoftwareFoundationGroupAtKyotoU/pure-borrow . 2. Background Before diving deeply into our work, Pure Borrow, we briefly review prior approaches to local state mutation inside pure computation in Haskell, namely the ST monad and Linear Haskell. 2.1. ST Monad The classical approach to achieve local mutation in Haskell is the ST monad ( LaunchburyJ94-ST ) , as mentioned in Section 1 . ⬇ instance Monad ST {}^{\mkern 3.0mu\textsf{s}} runST \mkern 1.0mu\mathpunct{::}\allowbreak\mkern 1.0mu ( \forall\mkern 2.0mu s . ST {}^{\mkern 3.0mu\textsf{s}} a ) \to a ⬇ newVector_ST \mkern 1.0mu\mathpunct{::}\allowbreak\mkern 1.0mu [ a ] \to ST {}^{\mkern 3.0mu\textsf{s}} ( Vector_ST {}^{\mkern 3.0mu\textsf{s}} a ) elems_ST \mkern 1.0mu\mathpunct{::}\allowbreak\mkern 1.0mu Vector_ST {}^{\mkern 3.0mu\textsf{s}} a \to ST {}^{\mkern 3.0mu\textsf{s}} [ a ] writeAt_ST \mkern 1.0mu\mathpunct{::}\allowbreak\mkern 1.0mu Int \to a \to Vector_ST {}^{\mkern 3.0mu\textsf{s}} a \to