This year's 7-Day Roguelike Challenge has just come to an end, and 202 new roguelike games have been suddenly released into the world. Hundreds of 7DRL developers are leaning back, relaxing after an intense week of coding, debugging, and playtesting.
Only 20% of entries end up successful, because it's surprisingly difficult to make an entire roguelike game within 7 days. I attempted the challenge, and after an epic seven days, slid into a finish 15 minutes before the deadline. 0
In such a short challenge, every hour counts. One has to be careful to keep scope down, and employ good tools to keep bugs away and keep debugging time down. Today, I'll describe one of the tools that saved me some critical hours near the end.
This was the first year I used the Vale programming language, a language I've been contributing to for quite a while.
Vale is bringing three innovations into the programming languages world:
- Generational references, where the compiler will make sure the object is alive when we dereference a reference to it. 1
- The region borrow checker (mentioned in Seamless, Fearless, and Structured Concurrency) which improves upon Rust's borrow checker to handle shared mutable objects.
- Higher RAII, where we use linear types to make sure we explicitly call a function at some point in the future, even past the current scope.
Let's hear more about that last one!
You can find the game here, but be warned, it's just a prototype of using Vale, so not many fun things were added to it!
Generational references are faster than reference counting, and gives us control over our memory layouts for better performance. It's also more flexible than borrow checking, and gives us more freedom with our architectures!
Higher RAII
Higher RAII is based on C++'s "RAII" 2 which automatically calls a zero-argument non-returning function (often called a "destructor") just before we destroy an object. Higher RAII does that, plus much more.
With Higher RAII, we can ensure that we eventually call any function... even ones with parameters, return values, even ones that don't destroy the object.
Imagine that you're dropping your laptop off at a repair shop. They tie a wristband with an ID number around your wrist. This is a "Higher RAII" wristband, in that:
- You're not able to remove this wristband.
- They will remove this wristband from your wrist when you pick your laptop up.
When you get home, you absentmindedly try to remove the wristband, and suddenly realize that you forgot to pick up your laptop. So you get back in your car, and go exchange the wristband for the laptop.
With Higher RAII, you can turn any object into a wristband, and the compiler will enforce that you get rid of it correctly instead of just destroying it.
RAII stands for Resource Acquisition is Initialization, and was developed for C++ primarily by Bjarne Stroustrup and Andrew Koenig. Other languages like D and Rust also offer it in some form.
A Real World Example
C++ uses a promise to send data to another thread's future. For example:
- Thread A calls myIntPromise.set_value(1337).
- Thread B calls myIntFuture.get() which waits and receives that 1337.
The programmer must remember to call set_value. However, sometimes the programmer forgets, and then thread B waits forever.
In Vale, we can use Higher RAII to enforce that we set the value before destroying the promise:
#!DeriveStructDrop
struct Promise<T> {
future &Future<T>;
}
func SetValueAndDestroy<T>(self Promise<T>, new_value T) {
set self.future.value = new_value;
destruct self;
}Here's how that works.
In Vale, every object has exactly one owning reference pointing to it. For example, the parameter self Promise<T> is an owning reference. future &Future<T> is not an owning reference, because it has a &.
The compiler normally automatically destructs the object when we destroy its owning reference's containing scope (or containing object). However, the #!DeriveStructDrop instructs the compiler to never automatically do that, but instead throw a compile error:
func main() {
promise Promise<int> = ...;
// Here, since promise still exists, compiler will try to call its `drop` function.
// Compile error: No function named `drop` exists!
}Now, the user must do something with the owning reference. Thats where SetValueAndDestroy comes in: it will take the owning reference and destruct it, as well as set the future's value:
func main() {
promise Promise<int> = …;
SetValueAndDestroy(promise, 1337);
// The above line moved the promise local variable into the
// SetValueAndDestroy function, so it no longer exists here.
}As you can see, the compiler now enforces that we correctly get rid of the promise, by setting its value.
The TokenedHashMap
This year, I made a TokenedHashMap class that used Higher RAII to make sure I remembered to remove things from it.
For context: in roguelike games, we often need to know if there is a unit 3 in a particular spot in the world, so we have a locationToUnit cache, basically a HashMap<Location, &Unit>.
This map must be carefully maintained:
- When we make a unit, we add it to the locationToUnit cache with its location.
- When we destroy the unit, we remove it from the cache.
However, in past years, I had forgotten to remove it from the cache. This caused units to see other units that were no longer alive, costing me precious hours!
Luckily, Higher RAII can help with this.
Let's make our special TokenedHashMap class:
- When we add something to the hash map, we get a HashMapToken back.
- We can't destroy a HashMapToken. This is like the above wristband.
- We can destroy the HashMapToken by removing something from the hash map.
#!DeriveStructDrop
struct HashMapToken { }
struct TokenedHashMap<K, V> {
inner HashMap<K, V>;
func add(&self, key K, value V) HashMapToken {
self.inner.add(key, value);
return HashMapToken();
}
func remove(self &TokenedHashMap, key K, token HashMapToken) V {
destruct token;
return self.inner.remove(key);
}
...
}The player and all other moving entities are called units.
How the TokenedHashMap saved me
Sure enough, at the very end of this year's 7DRL, I forgot to remove this unit from the locToUnit cache. Normally, this would cause hours of debugging. Luckily, the compiler realized this and signaled an error:
func Destroy(self UnitController, game &GameInstance) {
// Destroys the UnitController
[unit, locToUnitToken, view] = self;
(view).Destroy(game.domino);
// Compile error here, because we didn't do anything with locToUnitToken
}So, after profusely thanking the compiler, I added a game.locToUnit.remove(unit.location, locToUnitToken); which fixed the problem.
Huzzah!
Last year, I wasted over half a day on a bug just like this. I likely wouldn't have succeeded this year, if the compiler didn't catch that bug.
Instead, I have a completed entry, and I've maintained my 4-year success streak!
How else can it be used?
Higher RAII can be applied to a lot of places:
- On the view side, we can have a Dialog class with two buttons. It can only be destroyed if we also supply which button the user pressed.
- The UnitController has a UnitView, and the only way to destroy it is via the Destroy(view, connection) function takes a Connection parameter.
- When we pause the game logic to wait for animations, we often have a "currently acting unit". We can enforce that we correctly finish the unit's actions before starting the next unit's actions.
In general, when we want to make sure that we do something in the future, we should use Higher RAII to make sure it actually happens.
It was exciting to finally use it! I come from a heavy C++ and Rust background, and I've always known that RAII has a lot of untapped potential. Finally, Vale is powerful enough to use, and it feels really good to finally use Higher RAII in a real-life program. It's an incredibly versatile and valuable pattern, one that I hope Vale will bring into the mainstream!
Thanks for reading! In the coming weeks, I'll be writing more about the Vale 7DRL experience, so subscribe to our RSS feed, twitter, or the r/Vale subreddit, and come hang out in the Vale discord.
Afterword: Do any other languages have this?
C++ has had regular RAII since the 90s, and D and Rust have picked it up since then, but they're not quite "Higher" RAII, because:
- They always allow us to destroy any object. In other words, the compiler will automatically take off the wristband at any time, leaving the laptop in the shop for eternity.
- They don't allow us to pass parameters into the function that destroys the object.
This is mostly because of their decisions w.r.t. exceptions and stack-unwinding. When a C++ exception is in flight, or a Rust panic is unwinding the stack, they call the destructors for any object they're destroying.
Vale has a different approach. Basically, when a panic happens, we blast away only the containing region 4 and allow the rest of the program to continue running. 5
To deal with any open resources (like file descriptors, mutex locks, etc), we can either:
- Use a per-region linked-list to track them, which is consumed on panic.
- Ensure every object has a zero-arg drop() function generated. It would be private to preserve our higher RAII, and generally only callable via unwinding.
- Register "panic expressions" for certain scopes, which are invoked immediately when we trigger a panic, similar to algebraic effects.
We're leaning towards that first option, stay tuned for more exploration of the topic!
There are various ways to make new regions, such as creating a thread or mutex or iso object, or "try-calling" a pure function, etc.
The region borrow checker tracks which objects are in which regions.