I've long wanted to make my own language. Well, I'm pretty sure most programmers were at times annoyed by some parts of existing languages. In my case, it's bad enough I decided to make my own language. This document details my thought process over a few, well, years actually. It's written a bit crudely - the main goal is to give myself the understanding of what exactly I'm trying to do, hopefully others will also be able to understand some of it.
The first obvious question is - why make a new language? Why not use an existing one? To answer that, a clear conception of the language is needed. Let's start by defining the goals. In my case, it's:
I'm very confident none of the existing languages have a combination of those features - Rust comes close if I were to implement a plugin framework with wasm-based security... And that's a fair point! Rust can serve as the project language - I will implement the runtime in Rust, at least the first version.
Designing a programming language is no easy feat. Well, there are many resources on the matter. I'll just document the steps I'm taking right now.
And right now I need the runtime. If I have a basic runtime, I can write a language on top of it, and if I have a language coupled with a runtime, I can develop them in conjunction with each other. Sounds good? Here comes the first task - ABI
Rust has no stable ABI. You know what does? C. C is the lingua franca of programming as one of the only languages with a stable ABI. Well, it isn't guaranteed by the language standard - rather, the existing implementations don't change it, because there's no need to. It's nicer this way.
This means that while the runtime itself may be written in Rust, the interface has to use C. Rust itself doesn't guarantee any ABI compatibility with anything.
Next question is async. How do you implement it? That's a hot topic! In the language itself, I'd probably implement continuations, since they solve the color problem, and can also give exceptions for free. But this isn't the language, just the async runtime. So what do we do?
To understand that, let's understand what async is and what it needs to do. The core point is to move thread context switching to userspace, it's expected to be faster because there's no need for complicated logic, restoring the stack, etc. But that also means each function's stack has to be managed by the application!
How does Rust do it? Roughly speaking, it tells something called "async executor" to store everything the function needs, and then when whatever the function waited for completes, the executor says "hey function, here's what you stored, and here's the new data you got". This is similar to closures, which are functions that may capture variables from the outside scope. To make sure all temporary references are kept intact, the data stored by the future must never move in memory.
To further complicate the matter, there are two ways to do async I/O.
One is poll-based - the system notifies the application when it needs
to perform the next I/O step, and finally after one or more I/O steps
you get the result. For example, if you want to read a file, you say
"hey system, here's a buffer to write file contents to, can you do it"?
The system says "not yet, wait for now". The system starts filling its
internal buffer, and when it's filled to some extent, it says "here, you
can check again". The application passes the buffer again, and at that
point the system might give you the data you wanted, or tell you that it
still doesn't have enough to fill the entire buffer, and that you will
have to wait until the next update. You may check for new data at any
point in time, but chances are, if you haven't received a notification
from the system, there's no point in checking. That's the model Async
Rust is based upon. Note: this is actually just exactly how it works in
Rust, it might work differently when, for example, working with epoll,
I'm too lazy to check it.
The second one is completion-based. This one is way simpler - you tell the system, "here's a buffer, fill it with file contents, I pinky promise not to touch it while you work with it". The system fills the buffer byte by byte, and when it's done, it says - "task completed, here, take your buffer back".
What's the primary difference? In the poll-based model, there are two buffers - one is controlled by the operating system, one is controlled by the user. The data is read to the system-owned buffer, and for the user to successfully fetch the data, the data must be copied from the OS buffer to the user buffer. Instead, in the completion-based model, the system takes ownership of the user's buffer, meaning it can read the file straight into the target buffer, and no copying will be needed. Clearly, the second option is more performant.
However, that doesn't mean the two models are totally incompatible. After all, tokio-uring exists, (it uses Linux's completion-based IO via Rust's poll-based async system). The question is - which one is the superior abstraction, i.e. which one can handle more use cases, which one is better in this case?
The first difference is that with completion-based I/O, you necessarily need cleanup after the task has completed. You can't touch the buffer while the system is working with it, but after the system is done you can read and write it again. This means task cancellations are more tricky - you can't just stop polling, you must wait until the future ends and only then you can move on. The other difference is that poll-based I/O may have intermediate stages, while completion-based I/O only tells you when the entire task is ready. Poll-based I/O also sounds more lucrative because it's already natively supported by Rust. But let's keep the whole language in mind. Is there any benefit to having completion-based I/O over poll-based I/O? The language will probably expose a single interface for sync and async functions via continuations, so to answer that question, we should focus on the runtime - so let's decide on how to cancel the futures (I believe cancelling support is important).
In case of Rust, canceling a future means simply erasing its data between two polls. Some futures are not "cancel-safe", which is in no way enforced by the compiler. Essentially, some futures are cancelable, and some aren't. I believe this makes sense. Some futures may have to, at some point, temporarily leave the state in an invalid... state. Some futures are very simple - they just read or write a single chunk of data, and if the data doesn't have to be read or written anymore, they simply stop trying to read or write the chunk.
There's also the problem of "async drop" - some resources have to be cleaned up in an asynchronous way, but rust only supports synchronous deinitialization. While simply adding async drop might be lucrative, there's another problem - if you cancel a future, async drop won't be called! This means async drop is inherently non-cancel-safe. In conclusion, some futures are cancelable - let's call them "poll futures", and some aren't - let's call them "completion futures". Let's make sure the runtime knows which futures are and aren't cancelable. In the language itself, I'll probably implement it via "must-consume" and "can-drop" continuations - the first one represents an uninterruptible async function, the second one represents a function that can be interrupted.
Now that we decided on how to implement async I/O, the next questions are - what should the runtime even do? Clearly it should run code, but its other tasks include loading plugins, unloading plugins, reloading plugins, allowing plugins to safely interact, perhaps even storing their data. Well, why don't we start with... all of that?
Rust has an extensive standard library - for reading files, accessing
the network, reading environment arguments... Unfortunately, there are
two problems. 1 - it's synchronous, and 2 - you can't just let plugins
directly and insecurely access the operating system. This means we must
use #[no_std] - that is, the plugins will only have access to
core and maybe
alloc. The former
provides basic primitives, like futures, functions for working with
numbers, some core types like Option and Result, and other. The
latter provides a more extensive API that requires allocation - smart
pointers, vectors, strings, maps... Should we allow the latter?
My answer at the moment is no. The reason is simple. Primitives can
be passed between plugins - there's nothing preventing plugin A from
passing a number to plugin B. Strings and vectors can't, because they
reference the memory of their creator; because they contain pointers.
Anything that contains pointers can't be passed between plugins. This
means that if we want plugins to be able to pass strings to each other,
we must implement a custom string type in the runtime - and the plugins
will reference runtime-owned data. Basically, we will provide our own
version of alloc.
To make sure everything is highly composable, I want to use structural typing and refinement typing. Notably, it differs from typical HM type systems in that there's usually no particular principal types - you only know the type's constraints. This is similar to TypeScript, but TypeScript is kinda a mess because it's made to be a superset of JavaScript.
Remember I also want to support hot reloading! That means I need to be able to detect field renames, additions, removals; I might have to convert the field from one type to another, etc. In other words - I will have to convert the old version of the data into a new version. If some old plugin accesses the data, the new data is converted back into the old data. What does this look like? Well, first, it looks like Protobuf. Protobuf is a Google-developed data serialization format that deals well with field additions and renames. If you want to update some data, you have to add a new field and add custom deserialization code, but it's still pretty close to what I want. Second, it looks like DB migrations. This approach might seem annoying for plain and simple hot reloading - why go through all this effort? Let's split it by pros and cons:
To sum it up, this does offer a substantial benefit in my opinion, but also comes at a significant cost to both the runtime developer and the plugins' developers. Personally, I think it's worth it in this case.
Functions, functions... To properly support plugins, they have to be able to interact with each other. Whether you call it "message passing", "event dispatch", or "functions", the core idea stays the same. The key things of note are - the ABI, continuations, and state/side effects.
Different plugin versions might offer a different function interface. You know what that reminds me of? Of migrations! Let's make the function argument a single value - and that value will be migrated into a new version. It doesn't mean you can only pass, say, one number, it means you can only pass one object, and that object may contain other objects. When a plugin passes an object, it passes the ownership. We can do the same for the return value. While safe Rust will prevent the user from otherwise accessing it, they can still use unsafe Rust, or potential compiler bugs, to access it anyway. Well, they won't be able to do that, because the runtime will keep track of ownership as well.
If any function can use continuations, that means every function has to be like Rust's "async" functions, i.e. store its state in heap, not in stacki. Are functions that don't support continuations necessary? Yes! Read on to find out why!
Now this is the hard part. Handling side effects has been one of The questions of programming language design since forever. Imperative languages just say "whatever, do what you want, I'm not your boss". Object-oriented languages like Smalltalk solve the problem by splitting everything into actors that handle their own state - you can't directly modify their state, but you can ask them to do it. This makes side effects a bit more explicit. Functional languages use annoying concepts like IO monads. Rust solves part of the problem by usually making mutations explicit. You can't know for sure what will change when you call a Rust function, it may shut your PC down for all you know!
In this case, I want to make all side effects explicit. If a function mutates something, it must declare that fact (don't worry, it will be done automatically by the language). If a function calls another function via dynamic dispatch, it must declare that too. If a function accesses the outside world by reading or writing files or working with the network, that too must be declared. This offers two benefits - one is that it allows fine-grained per-plugin permission controls, another is that it gives the runtime the necessary information about what data to lock for thread-safe access by the function. Speaking of locks...
To mutate data safely, it needs to be locked. To read it safely, nobody else must mutate it at the same time, so it needs to be locked. But if you hold a lock for a long time, especially across a continuation, you prevent others from reading or writing the same resource. Locks have to be as granular as necessary, but sometimes you have to lock multiple things at a time to perform atomic transactions. It seems wise to forbid holding locks across a continuation. This means that if a function accesses global state, it may not access the outside world. If a function accesses the outside world, it may not access global state. These are two separate contexts, and the functions have to pass data to each other to fetch info from both contexts. In the language, simple syntax for context switching may be added, but that is of no concern to us right now.
Sometimes, you may want to make sure only one operation is running at
a time. For example, making sure that only one connection to a server
is opened. This can easily be achieved in the above model - a
"state-context" acquires a write lock for the state's is_running
value, and if it equals false, it changes is_running to true,
switches into "world-context" and opens the connection. When it's
done, it switches back into "state-context" and sets is_running
to false.
It also makes sense to add "no-context" functions - i.e. pure functions, functions that don't have any effect on anything at all and simply compute stuff.
To sum it up, there's two function contexts - state-context for accessing the application state, and global-context for potentially longer-running operations that may throw exceptions or take a long time to finish; and there are also contextless functions.
For an outer function to call an inner function, the runtime has to know the outer function will call it, otherwise side effect detection won't work. This is a simple restriction on first sight, but it becomes more complicated when you realize functions can be object fields, or object fields' fields, or part of the global state's objects' fields' fields' fields. Also, global-context functions may have continuations, but state-context continuations may not have them. To access the state, a global-context function must schedule an access operation, to call a long-running operation, a state-context function must schedule it. Hopefully, the nature of the function is well-understood by the programmer so they can set the correct constraints on the field.
We have extensively talked about execution, but we still haven't talked about constraints, besides maybe mutability and locks. To remind you, I want structural+refinement typing. What this effectively means is functions take objects with particular constraints - whether it's a constraint on what fields are present, or what those fields are. Where do those constraints apply? First, they apply on function arguments - functions only accept some particular arguments. Second, they apply on function return values - functions return values from their specific output sets. Third, they apply on the state - the functions may modify existing values in a specific way, and change the constraints that apply to them. That last point is particularly important and easy to forget.
I'd also argue mutability can also be expressed as a constraint. An owned value can be affected in any way you want. A mutable reference can be changed, but you cant destroy it completely, or pass its ownership to others. An immutable reference can only be read. So an owned value is a supertype of a mutable reference, and a mutable reference is a supertype of an immutable reference.
In fact, Rust lifetimes are essentially constraints as well. When you
say "x lives for the entirety of the lifetime 'a", you don't mean
its lifetime is exactly 'a, you mean it's at least 'a.
As another example, &[u8] is a subtype of &mut [u8], &str and
&mut str; and &str is a subtype of String.
Basically every language has product types - aggregates of multiple values: tuples, structs, classes, whatever. It's basically "object of type A, and object of type B, and object of type C...". But not many have sum types - "object of type A, or object of type B, or object of type C...". How do you implement them in this case? Well, first, it may not even be necessary in many cases, if you have field A and field B, you can say "this function takes an object that has field A or field B". But sometimes it is necessary. For example, in the Socks proxy protocol, every command has the same structure - they all take an address and a port, but the commands do different things - one opens a TCP connection, one binds a TCP port, and one associates a UDP port. In that case, the command needs to be a separate field, since there's no principal types in this language.
This way, if command 1 has fields A and B, but command 2 has fields B and C, nothing prevents command 1 from having the field C, or the command 2 from having the field A, but those fields will simply be ignored. The reason I chose this is the same reason Rust doesn't have negative trait bounds - if I added proper "either fields A, or fields B", adding a field can become a breaking change.
An obvious advantage of principal types is overloading - you can say: "this function works one way for type X, but another way for type Y". But without principal types, how would you, for example, iterate over a user-defined collection type? There aren't any fields in common with the default vector type. This means a function somehow has to be provided that defines how to iterate over the collection. The approach I chose is simple - Vtables. You simply pass the necessary methods along with the data. Crude, yes. But not too bad, and it is how every language does it under the hood.
Oh, right we wanted no GC, right? So how do we store the data? First, I want to remind you that plugins can't allocate data by themselves, which means managing everything is entirely up to the runtime.
I want to use something similar to ECS for storage. I won't exactly copy the architecture, but it's roughly similar. Interesting how everyone who attempts to make stuff extensible ends up with similar things, right? What I call "fields", it calls "components"; what I call "object" it calls "entity", and "systems" are what I call "state-context functions".
This allows massively parallel access, and makes GC completely unnecessary because of the way the data is managed. It's been used extensively in games (even though many developers prefer the OOP inheritance style), but I believe it doesn't solely belong to gamedev.
Notably, to efficiently store everything, each field's entire set of possible values must be known. If I store a number in a SQL database, I must know how big it can potentially be; same applies to in-memory databases. Hell, I must at least know whether it's a number or a string. There are ways to store unknown data, but it all comes down to "storing a chunk of data", which isn't exactly efficient. For maximum efficiency, the user must have the ability to declare the fields' constraints
Primitives are objects with hidden implementation. You don't know how numbers work - they just do. You don't know how strings work, or maybe you do know they consist of a pointer and a length, but that info isn't useful since that pointer is only useful in the context of being a string of a particular length. What I mean is the objects are useful for what they are, not what they contain. They are implemented in native code. So, the language will have primitives - that is, objects that can only be handled by using builtin or native functions, and that can't be introspected.
Well, I think this about sums up my thoughts on the matter. I might revisit this article in the future to touch it up or add my new thoughts, but for now I'm pretty confident in what I wrote above.
Have any comments, questions, feedback? You can click here to leave it, publicly or privately!