A while ago, I created a Rust project to execute code using only the type system. Why? Mostly because I could, but also to see what kind of magic would be possible with the (stable!) Rust type system.

This entire project is the very definition of “let’s see how far I can go with this”. Do not expect anything with an immediate practical impact. Probably the only value of this is the knowledge gained while creating the project.

The Goal

Now, you may ask what the point of this is. It is already known that the Rust type system is Turing-complete (here, here, and here). Therefore, we can already answer that it is possible to execute code (specifically, anything that a Turing machine could execute) in the type system, right? Well yeah, but that is not the point of this post.

The result should be something that looks roughly like normal code, but can be evaluated through types. Additionally, it should be relatively ergonomic to write. Assembly is also Turing-complete, but many prefer higher-level languages due to various reasons.

In the following chapters, we will gradually build towards executing actual code and tackle the problems we find along the way. One requirement is that the code should compile in stable Rust 1.88 or later.

Target Audience

This series dives into some fairly technical details of the Rust programming language. However, I make an effort to explain what is going on whenever the code is nontrivial. You should still be familiar with the syntax of Rust and roughly understand its type system notation.

First Steps

Let’s start with actually representing a program or function. Normally in Rust, it could look something like this:

fn main() {
    println!("Hello, World!");
}

In fact, this is the default template for the main.rs file created by cargo new --bin myproject. The snippet defines a simple main function, which prints the string Hello, World! to the console when the program is executed.

Now, let’s see what this could look like when translated to the type system. For now, we will simply try to get the main function working without any body.

pub trait Program {
    type Execute;
}

pub struct MyProject;

impl Program for MyProject {
    type Execute = ();
}

We have defined a Program trait with an associated type Execute. The value of this type should be the result of the program execution. Then, we define a unit struct MyProject, which implements the Program trait and simply “returns” the unit type () as the execution result.

This is already a good start, but right now this does absolutely nothing, so let’s add some functionality. For that, let’s first define a function abstraction like so:

pub trait Function<Args> {
    type Result;
    type Io;
}

Whenever a type implements this trait now, we can give it parameters using the generic type parameters and also extract the output in Result and Io. You may have noticed that this looks quite similar to Haskell, with its distinction between function return values and IO outputs. Partially because of the way the type system is set up in Rust, this project will end up being very similar to functional programming languages.

To be continued! >> Part 2