Virtual Machine in Rust's type system

This is a repository showcasing that the Rust type system (when using the new-gen trait solver) can express a virtual machine in its type resolution, with an instruction set that can perform bitwise operations, branch on data, contain loopy code, etc. It is meant to be a fun demonstration and I would recommend against doing this in any serious project or library.

Check out my blog post for an explanation of how this VM was developed and some details about how it all works.

Building

1. Clone the repository.
2. Make sure to use a nightly Rust toolchain. If using rustup, you don't need to anything: the rust-toolchain.toml file already makes rustup use a nightly version when invoked from the directory.
3. Compile with -Znext-solver (the default solver will not work):

RUSTFLAGS="-Znext-solver" cargo build

4. To see execution outputs, run target/debug/type-system-vm.

Example programs

A couple of example programs are in src/programs.rs.

Writing your own programs

A program (in this VM) is a type that looks like this:

type Program = InitState<asm! {
    /* instructions ... */
}>;

Where instructions is a comma-separated list of instruction types. The full instruction set is as follows:

Instruction	Effect
(register manipulation)
SetA<Bxx>	Set register A to the given immediate value Bxx.
SetB<Bxx>	Set register B to the given immediate value Bxx.
IncA	Increment register A.
DecA	Decrement register A.
AddAB	Add register B to register A, storing the result in register A.
NotA	Bitwise negate register A.
AndAB	Bitwise AND register A with register B, storing the result in register A.
XorAB	Bitwise XOR register A with register B, storing the result in register A.
OrAB	Bitwise OR register A with register B, storing the result in register A.
EqAB	Compare register A to register B, storing B01 if they match in register A, or B00 if they do not.
SwapAB	Swap the values in register A and B.
(stack-register interaction)
PushA	Push register A to the stack. Register A is not modified.
PushB	Push register B to the stack. Register B is not modified.
PopA	Pop a value off of the stack into register A.
PopB	Pop a value off of the stack into register B.
(stack manipulation)
Pop	Pop a value off of the stack, discarding it.
SwapTop	Swap the top two values on the stack.
(control flow)
Nop	Do nothing.
JumpForward<Bxx>	Jump forward Bxx instructions. When Bxx is B00, this instruction is a no-op, when Bxx is B01, one instruction is skipped, etc.
JumpForwardIfA<Bxx>	Jump forward Bxx instructions if register A is B01. Do nothing when register A is B00. Other values of register A are invalid!
JumpBackward<Bxx>	Jump backward Bxx instructions. When Bxx is B00, this instruction is an infinite loop, when Bxx is B01, jump to the previous instruction, etc.

Note that the immediate values represented by Bxx above are meant to be replaced with a concrete 8-bit value, using one of the B00, B01, ... BFF types.

Program execution happens at compile time using the VMStep trait, but you can use the Valued trait to extract the final result into a const value, usable in, e.g., a print statement (see main.rs):

println!("output: 0x{:02x}", <<Program as VMStep>::Next as Valued>::VALUE);

Invalid programs will result in ugly type errors!