Valen's Memory Safety: A New Kind of Borrow Checking
verdagon.dev57 points by verdagon 4 hours ago
57 points by verdagon 4 hours ago
Neat!
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).)
It sounds more like "path" borrowing than "group" borrowing to me, but the idea is great! Quite eye opening!
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.
nit: you need a better way of laying out asides/footnotes. when they get bunched up like at the start of this article you start having to scroll full screens back and forth. at least make the numbers on the asides link back to their position in the main text
They're fragment links, so you can use your browser's back button to go back to where you were.
Yes, absolutely, lol. This article is really pushing my notes system past its limits. And it loops between six note colors, which normally isn't a problem, but is here. During the holidays, I want to see if I can implement Tufte notes like in https://edwardtufte.github.io/tufte-css/
Also, as I was writing this, a couple things occurred to me:
* 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 =)
FWIW `foo in bar` implies iteration to me, not a path. In the .NET world, for example, `bar` would be a collection that we’re iterating through, assigning each element to `foo` in turn.
I wonder if nowadays we should be focusing less on scalar data structures and more on languages that facilitate vectorized/SIMD instructions. Languages like Vx lang, Mojo, and Futhark that work both in the CPU or the GPU, although each one works in a different level of abstraction and control.
GPU compilation is definitely something I intend Valen to support. I wrote about it back in 2022, [0] and I learned a lot of lessons on how to do it (and how not to do it!) from working on the Mojo compiler.
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
You are in good company.
https://venge.net/graydon/talks/VectorizedInterpretersTalk-2...
I don’t want to hijack Evan’s post by posting a link, but if you’re interested I’ve implemented many of the ideas in that presentation in the language I’m working on. You can check out the latest link in my post history for a rundown of how it works and a demo.
How likely is it that such a borrow checker could be "backported" to Rust? Maybe in a new edition?
It would have to take &Cell<T> references or the like in order to preserve the existing uniqueness properties for &mut T references. Not so different ultimately from what GhostCell, QCell, LCell etc. do already, except possibly simpler in some ways.
You know, it's not crazy. Niko wrote about lifetimes based on places back in 2024, [0] though it was in the context of shared-xor-mutable, which is consistent with Rust's spirit.
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...
IIRC this Verdagon guy had a language called Vale... is Valen a rename or a new project?
Edit: tfa makes it clear it's a separate project
Hi! Kind of both. Even though Valen reuses 90% of the Vale compiler, its approach (Rust interop, borrow checking with mutable aliasing, etc.) is so different that it really needed a new name.
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 noticed that there is no control flow in the examples.
Next article =) How the borrow checker handles ifs and loops is a pretty fun topic. If-statements work like you'd expect (invalidations from both branches are merged). Loops is where it gets weird: we have to scout all the invalidations that happen inside the loop and then "replay" them _before_ the body of the loop. I can explain it more if you'd like.
I was wondering about the case where a reference points to a different path depending on control flow. I guess you can just design your language to make this impossible but this is still possible to do with pointers in C/C++.
Theoretically, we can have a reference that points to two paths, a "path union" so to speak. If the user explicitly typed out the path union, it would be something like:
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.
Would it then be possible to mutably reference two entries in the same hashmap?
Is it possible to retrofit it to Freepascal, D, Freebasic or even Java?
Maybe! I think about D a lot when designing Valen, since they attempted to blend borrowing with garbage collection. Swift is facing some of the same challenges, and I expect Java could soon too now that Valhalla has landed.
If Valen solves those challenges as well as I think it can, it could be a good direction for them to explore.
Path Borrowing reads clearer to me, "group" made me look for a group type.