LanguagesArchitecture

There's an old mantra in game development:

"Don't make a game engine, make a game." - Confucius, 1337 A.D.

It's a wise saying, because we game developers have so much fun making the underlying foundations, that we never get around to adding the actual gameplay.

This is an article about how badly I disregarded that advice, and what happened because of it.

As you can guess, I made my own game engine.

It was an gloriously unwise decision, and delayed my game for a long time. This is what's known as yak-shaving: getting so distracted by the details that you lose track of the original goal.

I learned a valuable lesson from that mistake: don't get distracted trying to make the perfect tools.

So, having learned that lesson thoroughly, I then made the same mistake again! Not being satisfied with C#, C++, Rust, and other languages in the landscape, 0 I made an entire programming language, Vale, and rewrote the game engine with that.

It wasn't on purpose, it just happened. You start out making a simple DSL, 1 and you find yourself working on it more than the game itself. Then, momentum just carries you forward, because you're having so much fun.

After eight years, I finally had an entire general-purpose programming language and engine that I could use in the 7 Day Roguelike Challenge.

Side Notes
(interesting tangential thoughts)
0

These languages are mostly fine... but C# is slow, Rust can't handle a lot of basic safe patterns, and C++ doesn't have the syntactic goodies that I'm so used to.

1

Domain-Specific Language, usually a tiny language that helps with one specific task.

The Unexpected

Making a programming language is like raising a child. They start out helpless and generally oblivious, and they constantly fall and spout nonsense. Adorable, indecipherable nonsense. 2

Eventually, you teach them how to walk, how to do basic math, how to follow instructions, and how to signal basic syntax errors... and then the impossible happens: they win an argument with you. They point out a mistake you made, and they were right.

It's a complex mix of emotions: embarassment because you were wrong, sorrow because they no longer need you, and pride because you taught them well.

In the 7DRL challenge, Vale found a bug in one of my caches at compile time because it uses something called "Higher RAII" which doublechecks we actually fulfill our responsibilities. 3

2

This nonsense usually comes in the form of toddler-speak or s-expressions, depending on the time of day.

The Good Parts

There's a certain joy from using a new language that nobody else has ever used before. I felt like an Indiana Jones, exploring a tomb that no modern eyes have beheld.

There's a freedom one feels when not slowed down by garbage collection or reference counting, and not constrained by a borrow checker. 4 I'm free to implement what I want, and know that the language will help me do it safely. It's like I've been driving a Honda Civic in city traffic, and now I'm in a BMW cruising down the highway.

It was also nice to see that Vale is heading in the right direction. I found a lot of places that were just begging to harness Hybrid-Generational Memory and seamless structured concurrency.

For example, those two features would make it so there's zero memory safety overhead for the entire below function, by my estimation. 5 For a language with shared mutability to have that is unheard of and makes me quite excited for Vale's future.

vale
pure func CellularAutomata(
considerCornersAdjacent bool,
rand &XS32Rand,
map &PatternMap<bool>)

PatternMap<bool> {
new_map = PatternMap<bool>(make_pentagon_9_pattern());

foreach [loc, tile] in &map.tiles { 6
neighbors = map.GetAdjacentExistingLocations(loc, considerCornersAdjacent);
num_walkable_neighbors = 0;
foreach neighbor in &neighbors { 7
if map.tiles.get(neighbor).get() { 8
set num_walkable_neighbors = num_walkable_neighbors + 1;
}

}

new_impassable =
if num_walkable_neighbors * 2 == neighbors.len() {
(rand.Next() mod 2i64) == 0i64
}
else {
num_walkable_neighbors > neighbors.len() / 2
}
;

new_map.tiles.add(loc, new_impassable); 9
}


return new_map;
}
4

I have a particular wariness for the borrow checker, after learning it that it's incompatible with observers, most dependency injection, most RAII, and it can sometimes influence one into more complicated architecture with no performance benefit). This is why I made the Region Borrow Checker, which should handle shared mutability a bit better.

5

To reiterate, these features are not yet complete, and we only have a theoretical understanding of how many generation-checks they eliminate. Currently:

6

If we add parallel in front of this loop, it can perform these iterations in parallel on multiple threads, using seamless structured concurrency.

7

Hybrid-Generational Memory would notice that we're iterating over a piece of data we own, so it wouldn't have to keep checking it still exists.

8

Because we're accessing data that was a parameter to a pure function, it doesn't have to check that the data is still alive or increment any reference counters, see Zero-Cost References with Regions.

9

PatternMap would contain an "iso" HashMap, which means nobody outside has any references to it. Because of this, PatternMap can freely mutate it without memory safety overhead.

The Bad Parts

The Vale compiler is written in Scala, for its great development speed. 10 11

However, Scala is slow as heck so the Vale compiler runs slow, which means Vale code takes a long time to compile. 12

This was the biggest risk in this year's challenge, and almost pushed me past the deadline. Now I know that this year's priority should be to rewrite the compiler in Vale itself, which would be much faster.

10

I use Scala it in a mostly imperative fashion, more like Kotlin than any pure functional approach.

11

In case you're curious, the backend is in C++, because I'm a madman.

12

Moral of the story for language designers: Pay attention to your compile speed. Don't over-optimize, but at least track performance regressions and leave some TODOs around your codebase so you know where potential slowdowns might be when you do decide to optimize.

The Result

After the longest yak-shave in history, I still don't have much of a game. It's only about 6,000 lines of Vale code.

It's clear that if I spent all this time working on an actual game instead, instead of making the perfect programming language for game design, then I'd have three or four games by now! In this timeline, I don't have those games.

Still, I'm very glad I spent this time working on a programming language, because I ended up creating something so weird, so unrecognizable 13 that it blows people's minds, and that's a really great feeling.

I also now have something that can help a lot of people for decades to come. Speed and safety has always incurred a lot of complexity burden on the programmer, and maybe with this language, I can help with that.

That's all!

Thanks for visiting, and I hope you enjoyed reading about this experience as much as I enjoyed writing it!

In the coming weeks, I'll be writing more about our "region borrow checker" which helps eliminate Vale's memory safety overhead, so subscribe to our RSS feed, twitter, or the r/Vale subreddit, and come hang out in the Vale discord.

If you found this interesting or entertaining, please consider sponsoring me:

With your help, I can write this kind of nonsense more often!

13

Nobody would have thought that there was an alternative to GC, RC, and borrow checking!

Vale's Vision

Vale aims to bring a new way of programming into the world that offers speed, safety, and ease of use.

The world needs something like this! Currently, most programming language work is in:

  • High-overhead languages involving reference counting and tracing garbage collection.
  • Complex languages (Ada/Spark, Coq, Rust, Haskell, etc.) which impose higher complexity burden and mental overhead on the programmer.

These are useful, but there is a vast field of possibilities in between, waiting to be explored!

Our aim is to explore that space, discover what it has to offer, and make speed and safety easier than ever before.

In this quest, we've discovered and implemented a lot of new techniques:

  • Generational Memory, for a language to ensure an object still exists at the time of dereferencing.
  • Higher RAII, a form of linear typing that enables destructors with parameters and returns.
  • Fearless FFI, which allows us to call into C without risk of accidentally corrupting Vale objects.
  • Perfect Replayability, to record all inputs and replay execution, and completely solve heisenbugs and race bugs.

These techniques have also opened up some new emergent possibilities, which we hope to implement:

  • Region Borrow Checking, which adds mutable aliasing support to a Rust-like borrow checker.
  • Hybrid-Generational Memory, which ensures that nobody destroys an object too early, for better optimizations.
  • Seamless concurrency, the ability to launch multiple threads that can access any pre-existing data without data races, without the need for refactoring the code or the data.
  • Object pools and bump-allocators that are memory-safe and decoupled, so no refactoring needed.

We also gain a lot of inspiration from other languages, and are finding new ways to combine their techniques:

  • We can mix an unsafe block with Fearless FFI to make a much safer systems programming language!
  • We can mix Erlang's isolation benefits with functional reactive programming to make much more resilient programs!
  • We can mix region borrow checking with Pony's iso to support shared mutability.

...plus a lot more interesting ideas to explore!

The Vale programming language is a novel combination of ideas from the research world and original innovations. Our goal is to publish our techniques, even the ones that couldn't fit in Vale, so that the world as a whole can benefit from our work here, not just those who use Vale.

Our medium-term goals:

  • Finish the Region Borrow Checker, to show the world that shared mutability can work with borrow checking!
  • Prototype Hybrid-Generational Memory in Vale, to see how fast and easy we can make single ownership.
  • Publish the Language Simplicity Manifesto, a collection of principles to keep programming languages' learning curves down.
  • Publish the Memory Safety Grimoire, a collection of "memory safety building blocks" that languages can potentially use to make new memory models, just like Vale combined generational references and scope tethering.

We aim to publish articles biweekly on all of these topics, and create and inspire the next generation of fast, safe, and easy programming languages.

If you want to support our work, please consider sponsoring us on GitHub!

With enough sponsorship, we can:

  • Work on this full-time.
  • Turn the Vale Language Project into a 501(c)(3) non-profit organization.
  • Make Vale into a production-ready language, and push it into the mainstream!