In The Golden Spike, and Resurrecting the Vale(n) Programming Language, we saw how it was possible for a language to call Rust functions directly, without going through C, by directly integrating with the Rust compiler. 0 1
It was one hell of a journey!
At the end, I managed to make the "golden spike", a Valen program that uses a Rust graphics library:
In there, I hinted about how we're doing borrow checking between Valen and Rust:
Welcome to that next post!
In this post, I'll show you how we can uphold memory safety across the Valen/Rust boundary.
Plus, we'll see a certain surprise that happened as I was building it, which led to me breaking a foundational law of the universe.
(If you read the Golden Spike, skip this section)
This is all done in the new Valen programming language (successor to Vale).
It's a very early, experimental language that: 2
It also has plans to add:
One could call it a Rust++, since it can seamlessly call into existing Rust code.
Or it could be more of a Rust--, because it aims to be simpler, andoffers an easier way to use Rust code.
We'll see some of that further below, when it lets us use existing Rust code in a more flexible way than Rust itself.
Let's talk about Valen's memory safety approach!
This is something I'm ridiculously excited about for Valen.
At long last, Valen has an implementation of Nick Smith's Group Borrowing memory safety approach.
Group borrowing is similar to Rust's borrow checking, but without the shared-xor-mutable restriction.
This means that Valen functions can do things like:
This comes with a lot of simplifying powers.
For example, here's a Rust function, and below I'll show what Valen can simplify it to.
// Make attacker_id entity attack defender_id entity.
// Note: Attacker might be defender (attacking self).
fn attack(
entities: &mut SlotMap<DefaultKey, Entity>,
attacker_id: DefaultKey,
defender_id: DefaultKey
) -> Result<(), String> {
let a = entities
.get(attacker_id)
.ok_or_else(|| "Attacker not found in entities map".to_string())?;
let d = entities
.get(defender_id)
.ok_or_else(|| "Defender not found in entities map".to_string())?;
let a_energy_cost = a.calculate_attack_cost(d);
let d_energy_cost = d.calculate_defend_cost(a);
let damage = a.calculate_damage(d);
let a_mut = entities
.get_mut(attacker_id)
.ok_or_else(|| "Attacker not found in entities map".to_string())?;
a_mut.use_energy(a_energy_cost);
let d_mut = entities
.get_mut(defender_id)
.ok_or_else(|| "Defender not found in entities map".to_string())?;
d_mut.use_energy(d_energy_cost);
d_mut.damage(damage);
Ok(())
}The above becomes this Valen function: 7
// Make attacker_id entity attack defender_id entity.
// Note: Attacker might be defender (attacking self).
func attack(a &Entity in g, d &Entity in g) mut(g) {
let a_energy_cost = a.calculate_attack_cost(d);
let d_energy_cost = d.calculate_defend_cost(a);
let damage = a.calculate_damage(d);
a.use_energy(a_energy_cost);
d.use_energy(d_energy_cost);
d.damage(damage);
}This is possible because group borrowing lets us have multiple mutable references to the same object.
This is what the Rust code was trying to express, but Rust's borrow checker doesn't allow it. 10
Specifically, Rust's borrow checker has the shared-xor-mutable restriction, which says:
Group borrowing instead tells the compiler when two references might be pointing at the same thing, and then uses invalidation tracking to make sure that we don't use a reference that might be dangling. 13
You can almost think of it like a compile-time version of generational references (in fact, that's close to how it's implemented in the compiler!)
If you want to know more about group borrowing, check out the original group borrowing post.
For now, just know that it's more flexible because it allows multiple references to an object, and lets us write through any of them.
Now for the surprising part: Valen can also do that with Rust objects.
In other words, we can have multiple mutable references to Rust objects, safely.
I can hear some of you going, "Wait, what?!"
0% of this article was written by AI. More thoughts here.
My stance: if you want someone to take the time to read something, take the time to write it by hand.
Thanks for reading =)
Also thanks to Let's Get Rusty, who made a youtube video on the Golden Spike article. It's a great overview, check it out!
And one correction: I don't work for Mojo anymore. They definitely wouldn't have let me do any of this!
The main differences between Valen and Vale:
Both have linear types.
Their syntax is still mostly the same, but Valen might change to be more of a "simpler Rust" syntactically.
The normal ones, not the Vale-style random generational references.
Things like: a better async story, better enums, better mustprogress optimizations, closures implementing traits, universal function call syntax, good compile times, and maybe if we're lucky we can bring back some subset of perfect replayability.
To be clear about what works today:
Green dragons, specifically.
The biggest takeaway is that the in g on the references tells the compiler that the references might point at the same object. The mut(g) also says that we might mutate it. To really know what's going on here, check out the Group Borrowing article.
Also, if you look very closely, you'll see that the Valen example is probably faster, because it doesn't need all the error-handling branches, and instead of doing 4 lookups like the Rust version, it's doing zero (or two, because we might have just moved them out to the caller, depending on circumstances).
Take that with a grain of salt though, I haven't benchmarked it yet. If true, that'll be a wild post when it comes.
I like this example because it's the clearest, but I've come across more common cases where group borrowing can make something simpler than normal borrow checking. See this section for more examples.
It might seem like we could do this with Cell, but that makes a lot of assumptions about what's inside these methods. Depending on how complicated use_energy and damage are, using a Cell might not be such a great idea. GhostCell might be a better option for this example. There are other group-borrowing examples that GhostCell wouldn't quite work for though, I wouldn't consider it equivalent.
More specifically, a reference must be "shared" or "unique".
We can technically still mutate through a Rust shared reference, if it has an UnsafeCell somewhere inside it. This usually comes with a tradeoff, such as not being able to make references to some things inside it (Cell), run-time errors (RefCell) or unsafe.
"Dangling" means pointing at something that has already been destroyed.
That's right, Valen code can safely have multiple mutable references to Rust objects.
The Rust half of my brain can't even comprehend how blasphemous this is. 14 The mad sorcerer half laughs at the Rust half's discomfort. 15
And yet, it works!
import slotlib.Slot;
exported func main() int {
let slot = Slot.new();
let ref_a = &slot;
let ref_b = &slot;
ref_a.mutate(42);
ref_b.mutate(73);
return ref_a.get();
}
pub struct Slot {
value: i32,
}
impl Slot {
pub fn new() -> Slot { ... }
pub fn get(&self) -> i32 { self.value }
pub fn mutate(&mut self, x: i32) {
self.value = x;
}
}
Note how ref_a and ref_b are both pointing to the same Slot, yet ref_a.mutate(42); is handing one of those references into a Rust &mut reference.
But to understand why that works, let's first talk about temporarily unique references and "noalias", and then I'll explain how they help us call into Rust functions like we did above.
If you've used Rust before, this is surprising because one of the central tenets of Rust is that there can only be one mutable reference to an object at a time.
But we all knew that that was an imprecise model, that's what people mean when they say that Rust's borrow checker is conservative.
(Don't get me wrong, group borrowing is also conservative, just not as much as Rust in this case)
And the third half laughs at how the first two are always bickering over what's possible and/or sane.
A related question I'm often asked is:
A good question, and understanding the answer also helps us understand the Valen/Rust boundary.
TL;DR: Valen uses noalias too, so it's just as fast.
I'll explain the question a bit more, and then explain how Valen does it.
In Rust, when you have a reference parameter pointing at some data, 16 you know that nobody else is writing to that data. rustc makes those into LLVM noalias pointers, so LLVM knows about that, and can optimize better.
This is similar to C's restrict pointers, which also become LLVM noalias pointers.
For example, here's a C function without restrict:
void addMuchRandom(int *destination, struct Rand *random_state) {
for (int i = 0; i < 100; i++)
*destination += next_random(random_state);
}LLVM can't optimize this well. 17
However, if we make that parameter int *restrict destination, like this:
void addMuchRandom(int *restrict destination, struct Rand *random_state) {
for (int i = 0; i < 100; i++)
*destination += next_random(random_state);
}...then it can be optimized better, because the C compiler makes it into an LLVM noalias pointer. 18
Now LLVM can optimize the function to something like this: 19 20
void addMuchRandom(int *restrict destination, struct Rand *random_state) {
register int temp_register = *destination;
for (int i = 0; i < 100; i++)
temp_register += next_random(random_state);
*destination = temp_register;
}This is faster because we load from the pointer once at the beginning and store into it once at the end, instead of in every iteration.
So C restrict pointers are a lot like Rust references. With both, nobody else is writing to that data, and both become LLVM noalias pointers, which are optimized better.
Note this happens for shared references to Freeze data (which means it doesn't contain any UnsafeCell, Cell, RefCell, etc.) or unique references.
It becomes this unoptimized LLVM IR, which optimizes to this optimized LLVM IR, which isn't very optimal, because we're still doing a load and store in every iteration.
It becomes this LLVM IR with noalias which, when optimized, becomes this more optimal
With restrict, LLVM can lift the loads and stores out of the loop.
Before, without restrict, LLVM knows that that int* destination might be pointing anywhere... including into random_state->state_int, in which case lifting the loads and stores would cause weird behavior.
restrict promises LLVM that it won't be called like that.
This isn't exactly how the register keyword works in C, but you get the idea.
Now let's look at our example Valen function again, plus the damage method:
func attack(a &Entity in g, d &Entity in g) mut(g) {
...
d.damage(damage);
}
func damage(entity &Entity mut, amount int) {
entity.hp = max(0, entity.hp - amount);
}The question breaks down into three questions:
Q1: Is damage's parameter entity marked noalias?
Yep, it is.
When a reference is the only reference into its group, Valen makes it into an LLVM noalias pointer.
So in this damage function:
func damage(entity &Entity mut, amount int) {
entity.hp = max(0, entity.hp - amount);
}...which is syntactic sugar for this:
func damage<eg'>(entity &Entity in eg, amount int) mut(eg) {
entity.hp = max(0, entity.hp - amount);
}...Valen sees that entity is the only reference into the group eg.
Therefore, it knows that nobody else is writing to the data that this reference points at.
Therefore, it can be an LLVM noalias pointer.
Q2: Are attack's parameters a and d marked noalias?
Nope, they aren't. This is intentional, because they do alias. That's the user's intent, after all!
More specifically, looking at this attack function:
func attack(a &Entity in g, d &Entity in g) mut(g) {Valen sees that a isn't the only reference into the group g, so it can't be marked noalias.
Same with d.
Q3: Can the d.damage(damage) call hand a non-noalias reference (d) to a noalias parameter?
Quite easily!
This just works™ already in LLVM, because that's how we've been doing it in C for decades. For example this C program hands an aliased pointer into a restrict pointer parameter, and it's fine.
This is safe, as long as the data the pointer is pointing at isn't being accessed through any other argument.
This is also how Rust works under the hood! When a Rust type contains an UnsafeCell (or Cell, or RefCell, or GhostCell, etc.), shared references to it are normal LLVM pointers (no noalias). Then, usually through a safe API around an unsafe block, we can get a &mut reference (LLVM noalias pointer) out of it.
So, now that we know how Valen can make LLVM noalias pointers, let's finally see how that helps Valen call into Rust functions!
Here's the Valen program from above, calling into a Rust library:
import slotlib.Slot;
exported func main() int {
let slot = Slot.new();
let ref_a = &slot;
let ref_b = &slot;
ref_a.mutate(42);
ref_b.mutate(73);
return ref_a.get();
}
pub struct Slot {
value: i32,
}
impl Slot {
pub fn new() -> Slot { ... }
pub fn get(&self) -> i32 { self.value }
pub fn mutate(&mut self, x: i32) {
self.value = x;
}
}
Note how ref_a and ref_b are both pointing to the same Slot, yet ref_a.mutate(42); is handing one of those references into a Rust &mut reference.
Like we saw above, this is safe because, for the duration of that mutate call, only one pointer to slot is being used.
Valen knows that at the callsite because only ref_a is being passed into ref_a.mutate(42).
You could almost think of it like Valen is making ref_a temporarily unique for the call.
And under the hood, we're passing a normal LLVM pointer (ref_a) into a function that receives it as an LLVM noalias pointer, which is fine for the same reasons this C program from above was fine.
Easter egg note!
Cricket-spitting is a sport where people spit a dead cricket as far as they can. Whoever can spit the cricket the furthest is declared the winner. Glorious!
(Source: Wikipedia)
So far, things just seem to work for free, since group borrowing was so similar to Rust.
However, there was a case where group borrowing didn't really understand a reference that came from Rust.
To illustrate, here's an (unsafe) Valen program using a Rust method gem that it needs to understand:
import box_lib.Chest;
import box_lib.Gem;
exported func main() int {
let chest = Chest.new();
let gem_ref = chest.gem();
chest.replace(8);
// Should error here
return gem_ref.get();
}
pub struct Gem {
value: i32,
}
impl Gem {
pub fn get(&self) -> i32 { self.value }
}
pub struct Chest {
gem: Box<Gem>,
}
impl Chest {
pub fn new() -> Chest { ... }
pub fn gem(&self) -> &Gem { &self.gem }
pub fn replace(&mut self, value: i32) {
self.gem = Box::new(Gem { value });
}
}
This Rust function was problematic for Valen:
pub fn gem(&self) -> &Gem { &self.gem }...because Rust doesn't describe where inside self that Gem lives, and Valen definitely wants to know where every reference points.
Valen would love it if Rust said this:
pub fn gem(&self) -> &Gem in self.gem[] { &self.gem }...but alas, we live in that world not.
So, without that information, group borrowing got confused in these lines:
// Where does gem_ref even point to?
let gem_ref = chest.gem();
// Modifies chest, but what does that do to gem_ref?
chest.replace(8);
// Is this line even safe?
return gem_ref.get();It was confused because Valen needed to know where a reference points, to know whether it's dangling.
So, Valen has to add a new concept on top of group borrowing.
Inspired by Vale's isolates, 22 I'm adding a concept called a wildcard descendant path.
Valen now sees the Rust function as if it was this:
pub fn gem(&self) -> &Gem in self... { &self.gem }That self... means "somewhere inside self".
Now Valen sees the lines like this:
// gem_ref is a `&Gem in chest...`
let gem_ref = chest.gem();
// Modifies chest, so invalidates all refs that might point inside `chest`
chest.replace(8);
// Show an error on this line, because `&Gem in chest...` points inside `chest`
return gem_ref.get();And it works! It successfully gives a compile error on that line, because gem_ref.get() is trying to do a use-after-free.
To summarize, Valen's wildcard descendant paths let it understand references that point "somewhere" inside an object. 23
Quite serendipitously, it closed the gap between Valen and Rust.
With that, Valen's borrow checker could uphold safety across the boundary, and thus the second golden spike was complete.
Thanks for reading!
In the next few articles, I'll explain more about group borrowing, and how Valen's group borrow checker is implemented.
And maybe, if we're lucky, I'll have implemented a third golden spike, which has something to do with Rust and linear types.
This is just the tip of the iceberg, so stay tuned by subscribing to my RSS feed, r/valen, or joining the Valen discord. And follow me on Bluesky and Mastodon!
Cheers,
- Evan Ovadia
In Vale's design, you can open an isolate as a region, and then have a reference to anything inside that region. Also, Vale regions are un-typed; in other words, you can have a reference to type X that lives "somewhere inside" object Y's isolate's region.
This was actually already in my plans for Valen, because sometimes we don't want to put an entire path (like &Gem in self.gem[]) in a signature, and it's more readable to just say ... (like &Gem in self...).
Q: When we get a &mut from a Rust callee, isn't it UB to read/write through another reference pointing at the same data? For example:
exported func main() int {
let slot = Slot.new();
let ref_a = &slot;
let ref_b = &slot;
// Is this &mut / noalias?
let g = ref_a.get_mut();
// If so, wouldn't this be UB?
let x = ref_b.peek();
return g.get() + x;
}
pub struct Gem { value: i32 }
impl Gem {
pub fn get(&self) -> i32 { self.value }
}
pub struct Slot { gem: Gem }
impl Slot {
pub fn new() -> Slot { ... }
pub fn get_mut(&mut self) -> &mut Gem {
&mut self.gem
}
pub fn peek(&self) -> i32 { self.gem.value }
}
A: Nope. It would cause problems if Valen was generating Rust MIR that it handed to rustc, but Valen's not doing that. Valen generates LLVM IR directly 24 so the question is really, "Do the rustc-generated LLVM IR and the valenc-generated LLVM IR work together without UB?"
And they do work together, because of noalias's semantics.
In C terms, if a C main has two aliasing pointers, and hands one to a function foo that accepts it as a restrict pointer, and returns a pointer derived from that to main, main then receives it as an aliasing pointer. In other words, the restrict only applied to foo's body.
Transpiling to Rust wouldn't work, because Rust doesn't support things like comptime (which I really want for e.g. The Impossible Optimization).
Transpiling to Rust MIR would almost work, except it doesn't allow fine-grained aliasing information. In Rust MIR, you can specify that something is noalias or not. In LLVM however, you can specify that it's noalias or not or something between. Specifically, you can say that it aliases some things and not other things. In group-borrowing-speak, you can specify what group it's in. This is done via the !alias.scope metadata on loads/stores, and putting noalias metadata on call expressions (rather than just function parameters).
It's also slightly philosophical; while Valen is still experimental, it needs to be more decoupled from constraints, including Rust MIR. As Valen grows and stabilizes, I could see this changing.
One possible way forward would be:
I think Rust would benefit from adding some of Valen's features, like linear types.
However, I'm not certain yet that we should add group borrowing to Rust directly.
Rust's entire culture, ethos, and learning curve is based on a simple principle of shared-xor-mutable. It's unintuitive, but it's consistent enough that once you internalize it, it's a straightforward (if lengthy) path to master Rust.
Valen is all about mutable aliasing, which is the exact opposite. Valen is also consistent, making it a straightforward path to master.
However, if you blend the two wrong, you get an inconsistent mess that theoretically has the benefits of both, but in practice also makes Rust much harder to learn.
I could see a future where Valen pivots a few times, figures out how to do group borrowing well, and armed with that strong data point we can then consider how to add it to Rust. Until then, there's a lot of exploring to do.
Q: Any more examples, besides that func attack one?
A: Sure, here's some more: 25
Ask me in r/valen comments and I can expand on these if you want.
I have a feeling this is just the tip of the iceberg. When we release this to the world, we'll be seeing a lot more patterns.
Also, there will definitely be an article on this soon, stay tuned!
Though, Valen does give the generated LLVM IR into rustc at the very last second to sneak it into rustc's invocations of LLVM's optimization and its linking.
...plus a lot more that enable reference counting and generational references, but I don't want to go too deeply into that yet.