Brainfuck is an esoteric (not meant for practical use) programming language often used to prove turing-completeness of other languages or environments.
In colloquial usage, the terms "Turing-complete" and "Turing-equivalent" are used to mean that any real-world general-purpose computer or computer language can approximately simulate the computational aspects of any other real-world general-purpose computer or computer language. In real life, this leads to the practical concepts of computing virtualization and emulation. - Wikipedia
The interpreter runs purely at compile time as it is written in types.
See main.ts.
type Compute0 = Brainfuck<"++++++[>+++++<-]>+++.">
type O = Output;Hovering Output in VSCode will show the result of the brainfuck program: "!" in this case.
The reason that Output (and that you can't just import and use the Brainfuck type like a function) exists is because of TypeScript's recursion limit. Without splitting the computation into 200 types like I have, the recursion limit is hit for even simpler programs.
There seems to also be a limit which stops programs much longer than the one I have provided. I've got no idea what this limit actually is, and whether it applies to just TS-Server or tsc. This doesn't happen with the programs that can run within my 200-type limit.
The reason this is all possible is because TypeScript types are turing complete. Essentially, they are a primitive functional programming language. As an example I can write the equivalent of the following runtime JavaScript function in TypeScript types.
// Recursively creates a true[] of the specified length
const createArray = (targetLength: number, array: true[] = []) =>
array.length === targetLength ?
array
:
createArray(targetLength, [...array, true]);
createArray(5) // [true, true, true, true, true]Before we get into the type-level equivalent, I should explain why the function is written so bizzarely. In functional programming languages, including the TypeScript type system, a function body can only be an expression. This is why I opted for an arrow function.
If you were implementing this function yourself, I'd imagine that recursion wouldn't be your first choice, however without multiple statements and mutable state, this becomes impossible. Functional programming languages necessitate that variables cannot change, so instead of writing a loop, recursion is used everywhere loops would be used in procedural languages.
Now, the fun part. The function above can be implemented at the type level like so:
type CreateArray<TargetLength extends number, Array extends true[] = []> =
Array['length'] extends TargetLength ?
Array
:
CreateArray<TargetLength, [...Array, true]>;
type MyArray = CreateArray<5>; // [true, true, true, true, true]It's weird, but on further inspection, it's not much different to the JavaScript function. The generics match up to the function parameters. Most of the magic here is in the extends keyword and the ternary operator. First, we're checking if the array is already at the target length. extends here is effectively functioning as ===, and the TypeScript compiler implements the length property of arrays. The rest is really no different to the JavaScript function.
As I previously mentioned, TypeScript has a recursion limit. This is no issue for any practical use of the type system but I do find it to be a bit of a killjoy. Only 1000 type instantiations are permitted from a single "call" to a type.
This sounds insignificant. 1000 instantiations is a lot, but the unfortunately it isn't enough because of the next challenge.
Numbers in TypeScript are difficult.
type X = 1 + 2; // ❌ ';' expected.You can't add, subtract, divide or multiply at the type level. This sounds like quite the issue, however there are some limited ways around it. To represent the instruction and data pointers in Brainfuck, I went with a true[]. The length of the array represents a number. In Brainfuck, you only ever need to increment or decrement a pointer. Incrementing was trivial:
type Increment<n extends true[]> = [...n, true];Decrementing, on the other hand, requires use of the infer keyword - one of the more mind-bending features of TypeScript types.
type Decrement<n extends true[]> = n extends [infer first, ...infer rest] ?
rest
:
[];Woah. That was crazy. Let's look at the condition a little closer.
n extends [infer first, ...infer rest]We're checking if n is an array that takes the shape [first, ...rest]. The infer keyword extracts a type and gives it a name - like declaring a variable. As usual, this maps to a concept in functional programming known as (pattern matching)[https://en.wikipedia.org/wiki/Pattern_matching], and it's supported in a variety of languages such as Rust and Haskell.
When implementing interpreters, generally the state of the program is kept in a variable somewhere and mutated. This is impossible in an immuntable functional programming language such as the TypeScript type system. I got around this by just passing the state around everywhere. This is unfortunately detrimental to performance in an interpreter but it's unavoidable. Take a look at my Exec and State types.
type State = {
memory: { [key: string]: number },
dataPointer: true[],
program: string[],
instructionPointer: true[],
stdout: string[],
}
type Exec<state extends State> = GetInstruction<state> extends infer instruction
? instruction extends undefined ? state["stdout"] : instruction extends ">"
? IncDataPtr<state>
: instruction extends "<"
? DecDataPtr<state>
: instruction extends "["
? OpenBracket<state>
: instruction extends "]"
? CloseBracket<state>
: instruction extends "+"
? IncMemory<state>
: instruction extends "-"
? DecMemory<state>
: instruction extends "."
? PrintMemory<state>
: state : state;Assuming that the TypeScript compiler doesn't specifically optimise for this, the entire state of the interpreter is copied and passed into every type. This, in the worst case, means 6 copies of the state for 1 instruction. Horrific. And there's absolutely nothing I can do about it. Chances are, this is actually happening too; I doubt the TypeScript developers saw this coming.
I'm obviously not the first to tackle this challenge, but that doesn't matter. Heck, Michigan TypeScript got DOOM to run, albeit with the recursion limit removed. But regardless, I think that implementing this was a great way to brush up on my more advanced TypeScript skills.