Valen's Memory Safety: A New Kind of Borrow Checking
verdagon.dev
verdagon.dev
The article makes this sound like a problem. It isn't. This restriction frees you from thinking about certain classes of bugs in concurrent code; it's where the "fearless concurrency" comes from. R^w isn't about lifetimes - you could, in spirit (not sure about practice), remove it from Rust without affecting use-after-free at all.
Of course, it means you can't write many completely valid programs, and so we'd hope there's a better solution, but removing it is not one.
If you want to have to think about that (and potentially introduce bugs), that's perfectly fine. The flexibility of not requiring r^w is extremely useful. I'm just clearing up this mis-attribution.
Sure, you could pay the overhead of a managed language and have the runtime handle synchronization behind your back, but that isn't the path Rust went down.
Is that the case because it's easy to avoid concurrency issues, or because people are afraid of even trying to introduce concurrency into their program due to those issues? Because if it's the latter, then trying to support some amount of safe concurrency makes sense.
Either way, the problems that rust takes off the plate don't seem arbitrary for that reason. I don't particularly mind the problems it adds to the plate.
Calling a trade-off a slippery slope to a zero-set language is really disingenuous.
* When a function has a mutable effect into a group, and the function doesn't declare any other groups to alias it (with `in`), it is effectively a unique reference.
* When a function has references into a group, and it declares no `mut` effects into any of them, they are effectively shared/immutable references.
This helps with Valen's structured concurrency in particular, but also helps guard against the single-threaded race conditions in the same way that Rust's borrow checker does. It also helps with Rust interop!
So, TL;DR: Valen lets you choose between shared-xor-mutable and mutable aliasing.
Also note how mutable aliasing is opt-in (via `in`), so there's a subtle influence pushing people towards shared-xor-mutable, so that they only reach for mutable aliasing when it will benefit them.
Just to clarify, Rust's borrow checker can express mutable aliasing via interior mutability (i.e. UnsafeCell<T> and the various Cell<T> types). A &Cell<T> reference is essentially a mutably aliased reference. The goal is exactly that people "only reach for mutable aliasing when it will benefit them". Of course, any ergonomic improvements around the Cell types are quite welcome, especially if they help C/C++ interop - provided that they're proven to be as sound as the existing borrowck.
I would say Valen's real benefit here is in making a more ergonomic way for functions to work with an arbitrary number of GhostTokens / brands, and to track the relationships between them. (But I admit, I'm no expert with GhostCell, happy to be corrected by someone here)
There is ongoing work on a language feature ("field projection") that could alleviate this.
And I think OP's point, more succinctly, is that Valen programs will be much more difficult to parallelize than Rust programs.
It's shockingly easy to make a single-threaded Rust program use all the cores on a machine by slapping in Rayon wherever you have a Vec. Because Rust forces you to do the hard work of proving shared^mutable before getting a single-threaded program running.
The ecosystem-wide consequence of this is that pretty much every compute-intensive program written in Rust (that doesn't rely on non-Rust libraries for compute-intensive stuff) is automatically multicore. This is one of the reasons why Rust programmers seek out Rust libraries first. Because they know they won't get the unpleasant surprise of putting in a lot of work to adopt a library and then get burned when they find out it will only use a single core.
If it helps: AFAICT, Valen's borrow checker preserves the same ecosystem-wide concurrency benefits that Rust has. For precedent, check out GhostCell [0] which is not only _compatible_ with Rust's concurrency but gives it some interesting new abilities. Valen's approach could be thought of as a more ergonomic form of GhostCell that better tracks the relationships between multiple groups (brands).
I could give a better answer if we had an example to toss around where we think Valen might force things to be single-threaded.
That saying does more harm than good, and it counts against the Rust community that it keeps repeating it. Deadlocks are not something that Rust prevents. On the contrary, many beginners to Rust often run into deadlocks, some even spurred on by trying to satisfy the borrow checker. An infamous example is https://fasterthanli.me/articles/a-rust-match-made-in-hell . Instead of making blatantly false claims and causing newcomers to Rust frustration, pain and bugs, the Rust community should warn about concurrency and direct beginners to learn about concurrency, both generally as well as specifically in Rust.
* Rust's type system also allows you to make safe interfaces like Rayon that do genuinely allow for "fearless" concurrency in a way that I don't really see in other general-purpose languages.
One minor thing is that I'm not sure why they had to have "in" keyword for sub-borrows. Wouldn't it be more consistent to see "entity &world.entities[?]" instead of "entity in world.entities[]"? We'd consistently get the borrow "&" symbol and open the door for some contracts on what index (range) is affected.
I'm definitely hoping you succeed. I'd love to be able to write a small language (maybe that didn't do absolutely every last thing you can do in Rust, but was ergonomic and easy to use) that had a borrow checker and didn't require writing a nuclear reactor.
* We _could_ use the function parameter syntax `entities: &world.entities[]` instead of `entities in world.entities[]`.
* "Groups" aren't really central to understanding the idea, so Path Borrowing might be a better name than Group Borrowing.
Opinions welcome =)
Subtree borrowing.
(Single ownership stemming from main is a tree of owners; each path specifies some subtree)
(Btw. I enjoyed reading it)
The biggest decision for Valen is what to lower to:
* Rust MIR, since rustc has CUDA now, [1] (perhaps other cards soon?)
* SPIR-V, like Zig does for its GPU compilation [2]
* MLIR
Rust MIR is looking pretty nice. Valen already has Rust interop by doing some rustc sorcery, [3] and it would be somewhat straightforward to switch from emitting LLVM to emitting Rust MIR. I just need to figure out if Rust MIR can support the optimizations I have planned for Valen.
In a perfect world, Rust would be able to lower its MIR to MLIR, since MLIR has so many backends. I recall there were some efforts to do that, unsure where that ended up.
[0] https://verdagon.dev/blog/next-gen-languages-gpu
[1] https://developer.nvidia.com/blog/introducing-cuda-rust-two-...
[2] https://ziglang.org/devlog/2026/#2026-06-26
[3] https://verdagon.dev/blog/golden-spike-reviving-vale-valen
https://venge.net/graydon/talks/VectorizedInterpretersTalk-2...
> So we spent months sharpening the explanation and figuring out its benefits, and wrote a post 8 on it last year, hoping other languages would pick it up.
My language (see my submissions) has this feature since many years. In its current form it exists roughly since year 2020, but some under-the-hood changes and slight improvements have been done since.
I have a question about immutability. In Rust, if I have a shared reference to T (an &T a variable or a parameter), then I have a restriction that I can't modify T or anything in it (which Valen thinks is annoyingly restrictive, and I tend to agree), but I also have a promise that no one else will modify it. The latter is quite nice: it makes the optimizer happier (improves aliasing analysis), makes threading happier (nothing descended from the reference can have data races while the reference is alive), and makes me happier (I don't need to think about descendent values being mutated).
Valen can call into Rust, and I think I can see how, at the site of any particular call, Valen can tell that no one is mutating the referent or its descendents: in a single-threaded world, the only thing executing is the current line of code or a maybe a few consecutive lines of code, and the compiler can see the function's signature and any mutable references therein, and if there is no permission to modify a descendent, then it doesn't get modified.
But in a multithreaded world, especially if calling into Rust in a thread, doesn't there need to be a way to guarantee the immutability of an object across an entire region of code? How does that work in Valen?
And for making immutability more comprehensible to people and to local analysis in general, would a special type of reference meaning "yes, this one really is fully frozen and there are no mutable paths into it for the entire lifetime of this reference" be a nice feature?
(Aside: I've occasionally contemplated whether Rust would benefit from another flavor of reference: no-access. A no-access reference would guarantee the referent's existence but could coexist with shared and with mutable references. Safe code would be unable to read or write through such a reference. Other than making some cell-like types mildly less mind-bending, I'm not convinced I have an actual justification for this thing. This would give Rust three flavors of references.
But I can imagine a Valen-like language having three flavors of references: frozen references (cannot use them to mutate and there's a promise that no one else can either), exclusive references (fully mutable, etc, just like Rust's &mut) and flexible references (the kind of reference in the blog post).)
Short answer: Valen would have something similar to Fn and FnMut (but phrased in terms of effects rather than Fn vs FnMut). In other words, we would be able to express "a closure that does not modify anything it captures", or rather, "a closure that has no mut effects".
That closure, because it doesn't modify anything it captures, would be safe to share among multiple threads in a structured-concurrency-like / std::thread::scope-ish way.
The key here is that one _can_ express immutable references in Valen; an immutable reference is a reference that the containing function doesn't express a `mut` effect for. And once we have immutable references, we get all of the nice concurrency benefits that Rust trailblazed.
I'd also like to make a way to do the above without a function call, perhaps using something like the `parallel` keyword I described in [0].
A no-access reference is an interesting idea. That could be a more powerful way to express may_dangle. In Valen, I hope to have an "opaque" group to express something like that.
I don't know whether it's a good idea, but in Valen I'm trying to decouple access capabilities away from the reference types as much as possible. We'll see if that bet pays off.
[0] https://verdagon.dev/blog/seamless-fearless-structured-concu...
I'm contemplating this. Is it enough?
Suppose I have an object (I'm not even trying to get the syntax right, especially since Valen's syntax appears a bit different from Rust's):
let obj: T = ...;
let workgroup: StructuredConcurrencyThingy = ...;
workgroup.submit(move || print_in_rust(obj));
But, if I'm understanding you right, the immutability of the referent of obj depends on the signatures of everything in the callchain that might execute during the lifetime of the closure. How does that work?
edit: On further contemplation, I don't think that actual concurrency is needed to illustrate it. I think the same issue exists if I have a T<'a> that has a method that takes an &'a reference (probably like store_a_reference(&mut self, ref: &'a u32)) and dereferences ref both immediately and later and asserts that it sees the same value both times.
In Rust, a reference is forever shared/immutable or forever unique/mutable.
In Valen, a reference is... "it depends". Specifically, it depends on the context.
It's similar to a &GhostCell<T>, where its mutability isn't determined yet because the GhostToken isn't present yet.
So, what determines the mutability at any given point in time? The function's `mut` effects (or lack of them) for the group/path that the reference is pointing to.
So we can imagine a `execute_on_4_threads` function like this:
func execute_on_4_threads<C', F: Func<void, (), C>>(
workgroup: &W,
closure: F
) { ... }
The most relevant fact here is that this function doesn't declare any `mut` effects at all (not on C, not on W's group, nothing), so nothing is being mutated. (And because of that, this function's callees also can't have any `mut` effects; they also can't mutate the data)
Now let's say we changed `workgroup`'s type to `&W in w`, and added a `mut(w)` to the function, to describe that we might modify the workgroup.
At that point, we would still know that we can invoke the closure from 4 threads, because we declared no relationship between `w` and `C`, so the compiler assumes (and enforces) that they're disjoint, have no overlap, nothing in one aliases anything in the other.
Hopefully that helps. Maybe I should write a blog post on this, my posts are usually clearer than my HN comments.
(Also, I'm not sure I understand your edit, if you could clarify that would be much appreciated)
#[derive(Default)]
struct Receiver<'a> {
ref_and_val: Option<(&'a u32, u32)>
}
impl<'a> Receiver<'a> {
fn set(&mut self, reference: &'a u32) -> ()
{
self.ref_and_val = Some((reference, *reference))
}
fn check(&self) -> ()
{
if let Some((reference, val)) = self.ref_and_val {
if *reference != val {
panic!("The impossible happened!")
}
}
}
}
fn valen_inner_fun<'a>(r: &mut Receiver<'a>, val: &'a u32)
{
r.set(val)
}
fn valen_intermediate_fun<'a>(r: &mut Receiver<'a>, val: &'a mut u32)
{
// In a real mixed-language example, this would be in Valen, not Rust,
// and it would declare a mutable effect on val.
valen_inner_fun(r, val);
// And it would do this, which Rust disallows.
*val = 17
}
fn main() {
let mut r: Receiver = Receiver::default();
let mut fortytwo = 42;
valen_intermediate_fun(&mut r, &mut fortytwo);
r.check()
}
My point is that Receiver::set() requires a promise that its parameter's referent is immutable for the entire lifetime 'a, which exceeds the lexical duration of set() itself. And valen_outer_fun in Rust knows this to be true as a result of Rust's shared-xor-mutable system, and Rust's borrow checker verifies this:
a) the code would compile if I removed the offending *val = 17
b) the code, correctly, does not compile as written
c) If I force the issue by replacing *val = 17 with:
unsafe { *(val as *const u32 as *mut u32) = 17 }
But valen_inner_fun does not mutate val, and if I understand right then this means that Valen would accept its Valen equivalent without mut(val), and this seems unsound to me.
When I first thought of this, I imagined set() instead being a work-dispatching function that would run its passed-in closure and hit UB due to a data race with the *val = 17 line, and my edit was my realizing that there's a simpler non-concurrent example.
I've occasionally contemplated whether Rust would benefit from another flavor of reference: no-access.
Rust solves a similar problem in closures with unique immutable references, but they're not quite the same.
Unsafe Rust could promote a no-access reference to a shared or a mutable reference, and the unsafe code would be responsible for not violating exclusivity rules but would have a guarantee that the referent actually exists. Using unsafe code to create a no-access reference to a nonexistent object or to a misaligned object would be UB.
Safe code could convert the other way:
let a: &mut u32 = ...;
let b: &noaccess u32 = a;
let c: &u32 = ...;
let d: &noaccess u32 = c;
So for example:
let mut data = vec!['a', 'b', 'c'];
let b: &noaccess [char] = &data[..];
data.push('d'); // Does this error?
Your example is sneaky, though. Lifetime issues aside (suppose the next line of code uses b), that’s a noaccess reference to memory (an object? a place? I’m not sure what the current term is) that is only guaranteed to exist so long as data is not mutated. So the code with a subsequent use of data would error.
But if it were instead:
let b: &noaccess = data;
That's the one line that defines what's going on here.
If all you want is "no use after free", either reference counts or garbage collection will do the job. That's how most GC-oriented languages work.
Rust enforces stricter rules - single ownership, one writer or N readers. The question is whether that's worth the trouble. In threaded programs, it definitely is, because it prevents race conditions. Whether it's a win for single-thread programs is a good question.
Vale seems to be a way to move much of the overhead of a reference-counted system at compile time. Nothing wrong with that. The main motivation seems to be better interoperability with less restrictive languages. Am I reading that correctly?
I'd describe this as approximately weakening aliasing xor mutability to interior-aliasing xor mutability. The motivation seeming to be to have a more expressive system that rejects fewer correct programs. With a secondary goal of interacting with more (not less) restrictive languages (namely rust).
Edit: tfa makes it clear it's a separate project
Also, I really like where Vale ended up, Vale's generational references + region borrowing was a truly weird and unusual memory safety blend. I didn't want that combination to be lost to time, so I wanted "Vale" to keep referring to that.
I hope they one day upgrade to full group borrowing, it would be a nice fit for them.
Having mutability not be a property of the data, but of the function arguments reminds me a lot of modes from Jane Street’s OxCaml ^1 which is really interesting to me, as OxCaml’s focus is not really about memory management (they still use garbage collection for everything not on the stack). Feels like we might be converging towards a new standard! I can see the morning sun on the horizon :)
I don't know if you were aware of this, but Rust has that too. (Actually it's a property of any binding, not just function parameters)
And Rust already supports forms of mutable aliasing already, such as with Cell, and GhostCell which is halfway towards Valen's approach. I would love to see someone augment GhostCell to have the sort of "invalidation" logic that group borrowing does. In fact, Plecra is working on something like that with their (WIP) "Exclusion Typing". [1]
On top of that, Polonius already thinks in terms of "paths", just like Valen does. So it's not so much a question of compiler design, but of language design, and how Rust would expose it to the user.
[0] https://smallcultfollowing.com/babysteps/blog/2024/06/02/the...
[1] https://dilated.me/blog/posts/introduction-to-exclusion-typi...
let my_ref &Entity in (live_list[], dead_list[]) = if ...
though it would be nicer in practice, because the compiler could infer that.
Haven't implemented it yet of course, but the data structures in the borrow checker are designed with this in mind.
Edit: it turns out, Ante has path unions! https://www.reddit.com/r/ProgrammingLanguages/comments/1x37b...
struct World {
entities Vec<Entity>;
}
func step(world &World, entity in world.entities[] mut) {
entity.advance();
let collision = world.get_collision_for_entity(entity);
entity.resolve(collision);
}That wouldn't be shareable with another thread, because part of it is `mut`. _Theoretically_ we could make this shareable with other threads if we had another kind of effect, let me know if you're curious about that.
The `entity in world.entities[] mut` gives `step` blanket permission to mutate any element inside world.entities. We wouldn't be able to say "all other entities are readonly".
Though, it's worth mentioning that `advance` and `resolve` both receive the entity as a unique reference (since it's the only reference into a group which has a mut effect).
If Valen solves those challenges as well as I think it can, it could be a good direction for them to explore.
The problem with this is that it imposes a cost on abstraction. Zero-cost abstraction is one of the most fundamental design principles behind both C++ and Rust.
A field-path into a struct/enum fundamentally depends on its concrete implementation. If you hide the fields of a struct and use getters/setters, you break the ability to talk about the "paths modified" by a function which uses getters/setters.
Aside: it really annoyed me that I had to read halfway through this article to find the first attempt at defining "group borrowing". The whole first half of the article is basically fluff.
There are multiple links in the article that suggest the reader skip to the good stuff if they are already familiar with how borrow checking works