Const Generics and the Compile Time Spread Operator

Apr 27, 2022 — Evan Ovadia — Sponsor us on GitHub!

We're happy to announce that the Vale 0.2 beta now has const generics! Generic parameters can contain not only types (like the T in List<T>) but also integers, booleans, and other interesting substances.

This might be familiar from other languages, like C++ and Rust. However, Vale's taking them in a different direction, to enable something called the compile-time spread operator, which will serve as a useful metaprogramming tool for Vale.

This article gives a quick overview of const generics, and then where Vale plans to take them.

Const Generics

Before const generics, we often had a lot of similar classes:

struct Vec2<T> {
elements [#2]T; // 2-element array of T
}
struct Vec3<T> {
elements [#3]T; // 3-element array of T
}
struct Vec4<T> {
elements [#4]T; // 4-element array of T
}

It would be nice if we could pass that 2, 3, 4 in as a generic parameter like we did T!

Enter const generics, which enables just that.

struct Vec<N Int, T> {
elements [#N]T;
}

They're used like Vec<2, int>. Much better!

Besides types and integers, we can also have generic parameters that are:

Booleans
Strings
Functions
Mutability (imm vs mut)
Ownership (own, borrow, share, weak)
Location (inl, heap)
Variability (vary, final)
Type Lists

Compile-time Spread Operator

That last one is particularly interesting, as it allows us to implement tuples in Vale:

struct Tup<T RefList> {
_ ..T;
}

_ means the field is unnamed, and ..T means "use each of these types".

That .. is known as the spread operator. It can basically be thought of as the "compile-time for-each loop".

(int, bool, str) is syntactic sugar for Tup<RefList[int, bool, str]> which expands to this:

struct Tup { 0 int; // an int named 0 1 bool; // a boolean named 1 2 str; // a string named 2 }

The Spread Operator's Future

The above works today, in version 0.2. Now we'll show you a sneak peek of where we're heading with this delightful little operator.

We want to be able to use it for function arguments, and in expressions. For example, we could use it to implement a zero-cost variadic println function:

func println<T RefList>(args T..) { ..print(args..); print("\n"); }

If we called this with println(4, " hello ", true), it's as if the println function contains:

func println(args0 int, args1 str, args2 bool) { print(args0); print(args1); print(args2); print("\n"); }

4 hello true

In the previous snippet, the prefix .. (before print) marks the beginning of the "loop", and the postfix .. (after args) specifies what should change in each iteration.

Spread Method Call

When combined with UFCS, another interesting capability emerges, which we'll call the spread method call. The above snippet can be rewritten as:

func println<T RefList>(args T) { args..print(); print("\n"); }

It's fascinating how one little symbol can enable such a powerful capability!

Thanks for visiting, hope you enjoyed it!

In the coming weeks, I'll be writing more about our "Fearless FFI" plans which will help us more safely use external C code, 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, please consider sponsoring us:

Sponsor us on GitHub!

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

- Evan Ovadia

Side Notes

(interesting tangential thoughts)

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!

Sponsor us on GitHub!