A Brainfuck Interpreter That Runs in the Typechecker

Welcome back to the compile-time crimes series, today’s crime scene is particularly gruesome. Let me set the scene.

A laptop sits on the table, fans ablaze, as if trying to lift off and run away from the horrors it just witnessed. But it can’t. It’s pinned down by the weight of the 8.4 GB of RAM the NodeJS V8 process is taking. And for what, for what possible reason?! For computing the first 4, let me repeat that, the first four prime numbers, in Brainfuck, running inside TypeScript’s type system, running inside the compiler, running on NodeJS.

Let’s go back in time, to when it all started, to when I had the brilliant idea of implementing Brainfuck in the type system.

A refresh on Brainfuck

Brainfuck is a classic Turing tarpit, a programming language that is technically Turing-complete, but intentionally designed to be an absolute nightmare to use.

It operates just like a theoretical Turing machine: you have an infinitely long tape of memory cells (1-byte long), and a data pointer that starts at index 0 and moves along as the program runs.

A program consists of just eight valid instructions. Everything else is ignored as a comment.

Example

1:  +++  (add 3 at ix 0)
2:  >++  (add 2 at ix 1)
3:  <    (go back to ix 0)
4:  [    (jump to 9 if byte at ix 0 is 0)
5:   -   (decrement at ix 0) 
6:   >+  (increment at ix 1)
7:   <   (go back to ix 0)
8:  ]    (loop back to 5 if byte at ix 0 is greater than 0)
9:

This program is equivalent to the following JS program:

const tape = [3, 2];    // +++>++<
while (tape[0] !== 0) { // [
    tape[0] -= 1;       // - >
    tape[1] += 1;       // + <
}                       // ]

To implement the interpreter we’re going to need:

1. A Tape that we can navigate forward and backward
2. But also a list of instructions, that we need to be able to navigate forward (and backward because of the ] operation)

Implementing the Tape - Say hello to Zippers

Now that we know the rules, how do we actually model an infinite, mutable tape in a purely functional, immutable environment?

An imperative programmer would immediately reach for an array and an index variable:

type Tape = {
  array: [0]
  ix: 0
}

And you might actually get away with it because typescript’s performance characteristics are different from that of a typical pure functional programming language.

But instead we’re going to use a classic functional programming data structure, the Zipper, where every tape operation is a single pattern match.

A Zipper lets us store a list alongside a focus/cursor.

type Zipper<
  P extends any[] = any[], // previous values
  C extends any = any,     // the current value (aka focus/cursor)
  N extends any[] = any[]  // next values
> = {
  prev: P;
  curr: C;
  next: N;
};

// Our Tape is just a Zipper constrained to hold Peano (natural) numbers
type Tape<
  P extends Peano[] = Peano[], 
  C extends Peano = Peano, 
  N extends Peano[] = Peano[]
> = Zipper<P, C, N>

// A tape with [1, 2, 3, 4, 5] and a focus on 3
// would be the following zipper:
// { prev: [1, 2], curr: 3, next: [4, 5]}

Let’s begin writing the function to advance the cursor

type Advance<T extends Zipper, Z = Zero> =
  T extends Zipper<infer P, infer C, [infer H, ...infer Rest]> //pattern match on N to extract the next
    ? Zipper<[...P, C], H, Rest> // push C onto the end of prev, H becomes curr
    : T extends Zipper<infer P, infer C, []> // if there's no more values
      ? Zipper<[...P, C], Z, []> // Out of bounds! insert a Z
      : never;

Let’s give our new zipper a spin:

type A = ListToZipper<[1, 2, 3, 4, 5]>
//   ^?
//   { prev: [], curr: 1, next: [2, 3, 4, 5]}

type B = Advance<Advance<ListToZipper<[1, 2, 3, 4, 5]>>>
//   ^?
//   { prev: [1, 2], curr: 3, next: [4, 5]}

Beautiful. Now let’s take a quick look at how to implement Inc (+)

// Inc takes a Tape not a generic Zipper
// because it operates on Peano numbers
type Inc<T extends Tape> =
  T extends Tape<infer P, infer C, infer N>
    ? Tape<
        P,
        Succ<C> extends ToPeano<256> ? Zero : Succ<C>, // `add 1, mod 256`
        N
      >
    : never;

Easy enough, those Peano numbers really make working with numbers easy.

I’ll skip the implementations for Rewind, PeekZipper, Write etc., for brevity.

type Rewind<T extends Zipper> =
  T extends Zipper<[...infer Rest, infer Last], infer C, infer N>
    ? Zipper<Rest, Last, [C, ...N]>
    : never;

type PeekZipper<T extends Zipper> =
  T extends Zipper<any, infer C, any> ? C : null;

type PeekPrev<T extends Zipper> =
  T extends Zipper<[...any[], infer Last], any, any> ? Last : null;

type Dec<T extends Tape> =
  T extends Tape<infer P, infer C, infer N>
    ? C extends Succ<infer CMinus1>
      ? Tape<P, CMinus1, N>
      : Tape<P, Zero, N> // can't go negative
    : never;

type Write<T extends Tape, V extends Peano> =
  T extends Tape<infer P, any, infer N> ? Tape<P, V, N> : never;

type ListToZipper<L extends any[]> = L extends [infer H, ...infer Rest]
  ? { prev: []; curr: H; next: Rest }
  : never;

The Instructions

Now that we have the data tape we need to model a list of instructions. It needs an instruction pointer that points to the next instruction to execute, and we need to be able to advance and rewind the pointer and peek the current value… Seems familiar?

Hell yeah! That’s right, another Zipper! Bet you didn’t see this one coming.

// an Op is either a char (alas, string in TS) or false meaning HALT
type Op = string | false

// just a zipper of Ops
type Instructions<
  P extends Op[] = Op[],
  C extends Op = Op,
  N extends Op[] = Op[]> = Zipper<P, C, N>

The Interpreter State

Time to model the state of our virtual machine.

We have the data tape and the instructions, all we’re missing is stdout and stdin

• For stdout (which the . operator writes to), all we need to do is push items onto it, so that can be a simple list.
• stdin (which the , operator reads from) could be trickier, we still don’t have a way to pause the typechecker and give it input… Oh well, we’ll just have to cheat. Let’s assume that all of the stdin was given prior to the program running, so it’s just a list of things waiting to be popped.

Let’s build this bad boy:

// The Interpreter's state
type State<
  TTape extends Tape = Tape,
  TCode extends Instructions = Instructions,
  TStdin extends Peano[] = Peano[],
  TStdout extends Peano[] = Peano[]
> = { tape: TTape; code: TCode; stdin: TStdin; stdout: TStdout };

Slaps State, this bad boy can run so many ops/sec. Not really, but you get the point…

Executing Instructions

Because we’ve already laid out all the groundwork most handlers are extremely simple, they’re just functions from State to State that use all the helpers we’ve defined.

// dp = data pointer
// ip = instruction pointer

// > advance dp and ip
type ExecAdvance<S extends State> =
  // given a state
  S extends State<infer Tape, infer TCode, infer TStdin, infer TStdout>
    // return a state where the tape and the instructions advanced once.
    ? State<Advance<Tape, Zero>, Advance<TCode, false>, TStdin, TStdout>
    : never;

That’s it, pretty simple right? I’ll spare you the remaining handlers so we can jump to the most interesting one.

// . get the value at dp and push it to stdout
type ExecPrint<S extends State> =
  S extends State<infer Tape, infer TCode, infer TStdin, infer TStdout>
    ? State<Tape, Advance<TCode, false>, TStdin, [PeekZipper<Tape>, ...TStdout]>
    : never;

// < rewind dp, advance ip
type ExecRewind<S extends State> =
  S extends State<infer Tape, infer TCode, infer TStdin, infer TStdout>
    ? State<Rewind<Tape>, Advance<TCode, false>, TStdin, TStdout>
    : never;

// + increment the value at dp
type ExecInc<S extends State> =
  S extends State<infer Tape, infer TCode, infer TStdin, infer TStdout>
    ? State<Inc<Tape>, Advance<TCode, false>, TStdin, TStdout>
    : never;

// - decrement the value at dp
type ExecDec<S extends State> =
  S extends State<infer Tape, infer TCode, infer TStdin, infer TStdout>
    ? State<Dec<Tape>, Advance<TCode, false>, TStdin, TStdout>
    : never;

// , pop the head from stdin and write to dp
type ExecRead<S extends State> =
  S extends State<
    infer Tape,
    infer TCode,
    [infer Head extends Peano, ...infer StdIn extends Peano[]],
    infer TStdout
  >
    ? State<Write<Tape, Head>, Advance<TCode, false>, StdIn, TStdout>
    : never;

// NOOP - advances ip only
// it's useful for skipping unknown instructions
type ExecNoop<S extends State> =
  S extends State<infer Tape, infer TCode, infer TStdin, infer TStdout>
    ? State<Tape, Advance<TCode, false>, TStdin, TStdout>
    : never;

Let’s take a close look at [

If the byte at the data pointer is zero, jump past the matching ]

We need to check the byte and decide whether to jump or not. Then we need to find the matching ], not the next one, the matching closing one, and jump to the instruction after that.

All we need to do is keep a counter of depth, and return when we’re at 0. Here’s a small illustration of how depth evolves:

        [  -  >  +  <  [  +  +  ]  >  -  ]  .
depth:  1  1  1  1  1  2  2  2  1  1  1  0

Let’s write it:

type ExecJZ<S extends State> =
  S extends State<infer Tape, infer Code, infer Stdin, infer Stdout>
    ? PeekZipper<Tape> extends Zero
      // Tape is Zero: skip forward past the matching `]`
      // TODO implement SkipForward
      ? State<Tape, SkipForward<Advance<Code, false>>, Stdin, Stdout>
      // Tape is non-Zero: continue normally
      : State<Tape, Advance<Code, false>, Stdin, Stdout> 
    : never;

ExecJZ just determines whether to jump or not, and delegates the jumping to the matching ] to SkipForward.

type SkipForward<
  Code extends Instructions, 
  Depth extends Peano = Succ<Zero> // we begin at depth 1 (we just entered '[')
  > = 
  Depth extends Zero ? // base-case, depth is 0 ? we've reached the right place
    Code
  : PeekZipper<Code> extends "[" ? // if "[" then we keep going and increment depth
    SkipForward<Advance<Code, false>, Succ<Depth>>
  : PeekZipper<Code> extends "]" ? // if "]" 
    Depth extends Succ<infer Rest> ? // if Depth is not-zero we keep going but we're now shallower
      SkipForward<Advance<Code, false>, Rest>
      : never // unreachable - it's impossible for depth to be 0 when reaching a "]" that would move us to depth -1
  : PeekZipper<Code> extends false | null ? // EOF sanity
    Code
    : SkipForward<Advance<Code, false>, Depth>;

Oof, I’m sorry you had to see that, there’s really no great way to format so many nested ternaries, here’s a naive Haskell version of it, if it helps:

skipForward :: Instructions -> Number -> Instructions
skipForward code 0 = code
skipForward code depth
| peek code == "[" = skipForward (advance code) (depth + 1)
| peek code == "]" && depth > 0 = skipForward (advance code) (depth - 1)
| peek code == "]" && depth == 0 = error "unreachable"
| isEOF (peek code) = code
| otherwise = skipForward (advance code) depth

type ExecJNZ<S extends State> =
  S extends State<infer Tape, infer Code, infer Stdin, infer Stdout>
    ? PeekZipper<Tape> extends Zero
      // Tape is Zero: exit loop normally
      ? State<Tape, Advance<Code, false>, Stdin, Stdout> 
      // Tape is non-Zero: rewind all the way back to the matching `[`
      : State<Tape, SkipBackward<Code>, Stdin, Stdout> 
    : never;

type SkipBackward<Code extends Instructions, Depth extends Peano = Succ<Zero>> =
  Depth extends Zero
    ? Code // Code is now sitting perfectly on `[`
    : PeekPrev<Code> extends "]"
      ? SkipBackward<Rewind<Code>, Succ<Depth>> // deeper
      : PeekPrev<Code> extends "["
        ? Depth extends Succ<infer Rest>
          ? SkipBackward<Rewind<Code>, Rest> // shallower
          : never
        : PeekPrev<Code> extends null // BOF safety
          ? Code
          : SkipBackward<Rewind<Code>, Depth>;

The Final Interpreter

Now that we have the state and instruction handlers it’s time to assemble the interpreter. The Eval function takes a State and keeps running it until the program halts (or the TS compiler process runs out of memory).

type Eval<S extends State> =
  S extends State<any, infer Code, any, any>
    ? PeekZipper<Code> extends "+" ? Eval<ExecInc<S>> // execute instruction and recurse
    : PeekZipper<Code> extends "-" ? Eval<ExecDec<S>>
    : PeekZipper<Code> extends "." ? Eval<ExecPrint<S>>
    : PeekZipper<Code> extends "," ? Eval<ExecRead<S>>
    : PeekZipper<Code> extends ">" ? Eval<ExecAdvance<S>>
    : PeekZipper<Code> extends "<" ? Eval<ExecRewind<S>>
    : PeekZipper<Code> extends "[" ? Eval<ExecJZ<S>>
    : PeekZipper<Code> extends "]" ? Eval<ExecJNZ<S>>
    : PeekZipper<Code> extends false ? S //halted
    : Eval<ExecNoop<S>>
  : never //unreachable

Such beauty.

Let’s give it a spin

type EmptyTape = { prev: []; curr: ToPeano<0>; next: [] };

// A program that takes no stdin
type SimpleProgram<S extends string, T extends Tape = EmptyTape> = {
  code: ListToZipper<ToCharList<S>>,
  tape: T,
  stdin: [],
  stdout: []
}

type HelloWorld = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."

// evals a program, converts the stdout to ascii and returns it as a string
type RunProgram<S extends string> = Eval<SimpleProgram<S>> extends infer R extends State
  ? FormatStdout<Reverse<R['stdout']>>
  : never;

type Result = RunProgram<HelloWorld>

❯ time tsc --noEmit --noRecursionLimits --printType Result ./problems/misc/brainfuck.ts
"Hello World!\n"
0.83s

type ToCharList<S extends string> =
  S extends `${infer H}${infer Rest}`
    ? [H, ...ToCharList<Rest>]
    : [];

type Reverse<T extends any[]> =
  T extends [infer Head, ...infer Rest]
  ? [...Reverse<Rest>, Head]
  : []

type PeanoToChar<P extends Peano> = ToNumber<P> extends keyof AsciiTable
  ? AsciiTable[ToNumber<P>]
  : "<UNSUPPORTED_CHAR>"; // unsupported or unprintable

type FormatStdout<T extends Peano[], Acc extends string = ""> =
  T extends [infer H extends Peano, ...infer Rest extends Peano[]]
    ? FormatStdout<Rest, `${Acc}${PeanoToChar<H>}`>
    : Acc;

type AsciiTable = {
  10: "\n";
  32: " "; 33: "!"; 34: "\""; 35: "#"; 36: "$"; 37: "%"; 38: "&"; 39: "'";
  40: "("; 41: ")"; 42: "*"; 43: "+"; 44: ","; 45: "-"; 46: "."; 47: "/";
  48: "0"; 49: "1"; 50: "2"; 51: "3"; 52: "4"; 53: "5"; 54: "6"; 55: "7";
  56: "8"; 57: "9"; 58: ":"; 59: ";"; 60: "<"; 61: "="; 62: ">"; 63: "?";
  64: "@"; 65: "A"; 66: "B"; 67: "C"; 68: "D"; 69: "E"; 70: "F"; 71: "G";
  72: "H"; 73: "I"; 74: "J"; 75: "K"; 76: "L"; 77: "M"; 78: "N"; 79: "O";
  80: "P"; 81: "Q"; 82: "R"; 83: "S"; 84: "T"; 85: "U"; 86: "V"; 87: "W";
  88: "X"; 89: "Y"; 90: "Z"; 91: "["; 92: "\\"; 93: "]"; 94: "^"; 95: "_";
  96: "`"; 97: "a"; 98: "b"; 99: "c"; 100: "d"; 101: "e"; 102: "f"; 103: "g";
  104: "h"; 105: "i"; 106: "j"; 107: "k"; 108: "l"; 109: "m"; 110: "n"; 111: "o";
  112: "p"; 113: "q"; 114: "r"; 115: "s"; 116: "t"; 117: "u"; 118: "v"; 119: "w";
  120: "x"; 121: "y"; 122: "z"; 123: "{"; 124: "|"; 125: "}"; 126: "~";
};

:‘) Our first “Hello World!” running on Brainfuck, running on the TypeScript compiler running on NodeJS’ V8 engine. Yet somehow “at compile time”?

And hey! Under a second! Not too shabby!

Let’s try something spicier

Calculating Prime Numbers

I found this program online that will print all prime numbers up to an upper bound. Let’s start off easy, and let it compute only up to 8.

const primeNumbers = `
++++++++ //upper bound - find all prime numbers less than this number
[
  [>+>+<<-]>>[<<+>>-]<
  --
  [
    +>>[-]<<
    <[>>+>+<<<-]>>>[<<<+>>>-]<
    >+
    [
      <
      [>>>>>+>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<<<<<
      [
        >[-]<<
        [>>+>+<<<-]>>>[<<<+>>>-]
        <<[>>+>+<<<-]>>>[<<<+>>>-]<
        [<->-]<
        >>>+<<<
        [>>>-<<<[-]]<
        -
      ]
      >>>>>[<<<<<+>>>>>-]
      <[[-]<<<<<[>->+<<-]>>[<<+>>-]+>]<
    ]
    <<<>>>>>>>+<<<<<<<[>>>>>>>-<<<<<<<[-]]
    <--
  ]
  >>>>>>>>>+<[>-<[-]]>
  [
  -<<<<<<<<<<[>>>>>>>>>>+>+<<<<<<<<<<<-]>>>>>>>>>>>[<<<<<<<<<<<+>>>>>>>>>>>-]<
  
  [>>+>+<<<-]>>>[<<<+>>>-]<<+>[<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]
  ++++++++[<++++++>-]>[<<+>>-]>[<<+>>-]<<]>]<[->>++++++++[<++++++>-]]<[.[-]<]<
  [-]>[-]<
  >++++[<+++++++++++>-]<.
  ------------.
  [-]
  ]
  <<<<<<<<<<-
]
` as const

type PrimeNumbers = RunProgram<typeof primeNumbers>

➜ command time -l \
  tsc --noRecursionLimits --noEmit \
      --printType PrimeNumbers ./problems/misc/brainfuck.ts
"7, 5, 3, 2, 1, "
  59.77 real        96.95 user         6.41 sys
    8026472448  maximum resident set size
    8485496192  peak memory footprint

Holy… We created a monster. This must’ve been what Victor Frankenstein felt.

It took 8.4 GB of ram and 60 seconds just to compute the first four prime numbers.

The honest fix would be to optimize our data structures and data access patterns… The dishonest fix is much more fun though.

So what if I told you we can make this the fastest program to print the first four prime numbers? Because we can totally do that with just a little bit of cheating. And when I say cheating I mean hacking the compiler once more! Hell yeah!

So here’s my…

Totally valid plan to make the fastest program to print the first 4 prime numbers that’s definitely not cheating!

Here’s the idea: Do you know how as const “lifts” values to the type level?

const john = "Cleese" as const
//    ^? type: "Cleese"

"Cleese" was brought into our universe of types from the literal "Cleese".

Weeeel, what if we did the same, but backwards…

Introducing as comptime

My latest hack to the compiler, “drags” types back down to the value level.

Let’s see it in action:

// test.ts
function getThree(): 3 { return 3 }

const a = getThree() as comptime

This snippet would typically compile to:

// ...
const a = getThree()

However, running our forked tsc with --comptime now compiles to:

// ...
const a = 3

as comptime checks the type of the expression, and replaces the expression with the resulting literal. Effectively getting rid of all runtime computations.

Here’s a few more examples, so you get a feel for it:

const a = null as unknown as Omit<{ a: 1, b: 2 }, 'b'> as comptime
// compiles to:
const a = { a: 1 }
// instead of const a = null

// we can define a helper
function evaluate<T>(): T { 
  throw "Sike! this never actually runs. So long as you don't forget to call it with comptime" 
}

const b = evaluate<[1, 2, 3]>() as comptime
// compiles to:
const b = [1, 2, 3]
// instead of const b = evaluate()

If the typechecker knows what the value of a computation will be, why even bother running it in the first place?

I think you see where I’m going with this…

console.log(
  evaluate<
    RunProgram<
      typeof primeNumbers
    >
  >() as comptime)

compiles (after 59s lmao) down to:

console.log("7, 5, 3, 2, 1, ")

Hehehe, let’s run this bad boy and compare the times

Great Success!

And without cheating! You see, I promised “the fastest program to print the first 4 prime numbers” I didn’t say it would compute them at runtime.

Conclusion

Look at all we achieved today:

• We implemented a Turing complete language inside a Turing complete typesystem
• We managed to find the first 4 prime numbers in under a minute and 9 GBs of RAM
• And then we optimized it down to .03s and 12 MB by adding a new feature to TypeScript.

This is prime compile-time crimes content. It’s exactly what I wanted to do with this series, and I hope you enjoyed it.

If you want to play around with the code, you can clone the repo here.

Our crime for next week is still up for discussion, so I would love to hear your suggestions.

A few ideas I have:

1. Let’s build and invert a binary-tree to show those damn interviewers we can do it, even at compile time.
2. Solve harder problems, maybe a graph traversal, maybe a dynamic programming one.
3. Hack the compiler to add impure types (read side-effects) to TS (ie. ReadLine and Print<T extends string> to read from and print to the console). Then this brainfuck compiler would truly be capable of reading stdin and printing to stdout.

Finally I’d like to end this post with a quote from the book I’m currently reading, that inspired me to write this useless blog.

We can forgive a man for making a useful thing as long as he does not admire it. The only excuse for making a useless thing is that one admires it intensely. All art is quite useless.

- Lord Henry Wotton from The Picture of Dorian Gray