One of the stupidest ideas you’ll ever read in your life

We don’t know what the future holds. We don’t know where we’re going. We don’t even know why we do our jobs. Life is a constant cycle of renewing our ideas, our opinions, and our desires. Everything moves. Everything changes. Endlessly. Leaving us with no hope for a truly peaceful existence. But there’s one thing that will never change. Something that was there at the birth of the universe. Something that will (probably) vanish when the Sun will explode. Yes, we will always find a stupid idea. And this one is uber-stupid.

So, you clicked on this article because :

• you read the word Brainfuck and thought it sounded funny: you will regret this.
• you read the word Interpreter and thought it sounded interesting: you will regret this.
• you read the word Typescript and wanted to learn about upcoming features: you will regret this.
• you read the title: you will regret this.
• you clicked randomly because you needed something to pretend you’re working on: you’ll be back to work very soon.

Every time I talk about writing this article to a colleague or a friend, they ask me: “Why the f*** are you doing this?”. Honestly? I don’t know. There’s no real purpose. No company will hire me because I wrote an article about a Brainfuck interpreter using only Typescript types. No conference will invite me. My colleagues will say: “Oh, that’s the Brainfuck pal. Let’s go somewhere else before it spreads.”. I won’t find love, fame, or fortune with this article. My parents will still think I fix printers. Yes, this article won’t change anything (except maybe for the colleague thing, damn).

But sometimes, you just want to prove something. You have to do it. There’s no reason except to say: “I did it.” You want to be the only person on Earth who’s done this. And maybe I’m the second, the third, the thousandth — I hope not, for the sake of humanity — but I can say it loud and proud: I wrote a Brainfuck interpreter using only Typescript types.

Rules

• You have to write a Brainfuck interpreter (see a bit further for the definition of Brainfuck). This code has to work:

type Program = [
  // First letter
  P, P, P, P, J, R, P, P, P, P, J, R, P, P, P, P, L, M, B, L, M, B, R, R, P, P, P, O, L, L,
  // Second letter 
  P, P, P, P, J, R, P, P, P, P, J, R, P, P, L, M, B, L, M, B, R, R, P, P, P, P, P, O, 
  // Third letter
  M, M, M, O, 
  // Fourth letter,
  P, P, P, O,
];

• You can only use Typescript types. Any form of Javascript is strictly prohibited.
• If you think the challenge is too easy (lul), you can make it even harder by banning the use of numbers entirely. That’s what I did by using my custom number system from the first article.

The Brainfuck definition

Brainfuck is a language created in 1993 by Urban Müller. In Brainfuck, you have a memory composed of cells of integers. You also have one pointer pointing to the current memory cell.

This language uses 8 operators and so 8 characters to write code.

• + increments the value of the current cell.
• – decrements the value of the current cell.

• > moves the pointer to the cell to the right.
• < moves the pointer to the cell to the left.

• [ is the start of a loop. If the current cell value is 0, the interpreter jumps to the matching ], skipping the loop body. Otherwise, it continues with the next instruction.
• ] is the end of a loop. If the current cell value is not 0, the interpreter jumps back to the matching [, repeating the loop. Otherwise, it continues with the next instruction.

Here’s an example of the loop usage with the program: ++[>+++<-]

When evaluating [ (the start of the loop), we have 2 in our current cell. So we don’t jump out of the loop and we execute the loop body.

Now, when evaluating ] (the end of the loop), we have 1 in our current cell. So we jump back to the beginning of the loop and execute the loop body a second time.

This time, when evaluating ], the current cell value is 0. So we continue the program which finish because it was the last instruction. And yes, this little program performed the mathematical operation 2×3.

• , reads a character from the input. However, this operator doesn’t have to be implemented because we can’t access stdin using Typescript types.
• . sends the output character corresponding to the ASCII value from of the current cell. For example, if you want to output an A, your cell must contain the value 65. Here’s the full ASCII table.

Since Typescript doesn’t accept non-letter characters in type names, we’ll use letters to represent each operator. Here’s my syntax:

• + is P (Plus)
• – is M (Minus)
• < is L (Left)
• > is R (Right)
• . is O (Output)
• , is I (Input)
• [ is J (Jump)
• ] is B (Back)

Have fun… I guess?

Theorical solution: write a Brainfuck interpreter in a functional way

For this exceptional project — and because of the complexity of the Typescript code written — I’ll start by explaining the theory. Then, we’ll dive into the Typescript syntax and the horror of types with too many lines.

In my last article, I explained how writing programs using Typescript types is similar to functional programming without higher-order functions. With this predicate, we first need to understand how to build the interpreter using functional programming principles before translating it into Typescript syntax.

So, what is a Brainfuck program? It’s a sequence of simple instructions, executed one by one. Following that logic, our program should be represented as an array (a list of instructions), and our interpreter should be a recursive function that executes the current instruction, then calls itself with the remaining instructions. Here’s a simple example with the program ++> and a function Execute(prog):

execute (++>) = 
  Use + and 
  execute (+>) = 
    Use + and 
    execute (>) = 
      Use >

With this idea in mind, how do we manage memory while executing more instructions? The solution is simple: we add a memory argument to our function. Each execution step updates the memory based on the current instruction, then passes the updated memory to the next execution. Since the memory only contains integer values, we can represent it using a simple integer array.

execute (++>, [0]) = execute (+>, [1]) = execute (>, [2]) = [2, 0]

The next step is to simulate stdout. It’s just a simple string that gets new characters whenever we encounter the . (or O) operator. We could also simulate input by passing a string to the Execute function, and after each , (or I), we’d pop the first character. I didn’t do that, but it wouldn’t be hard to do.

Now come the hardest operators: [ and ]. When I started coding them, I used a storage-based approach. You have a two-dimensional array of operators. The first dimension represents the current loop nesting level. Each time we enter a loop, we increment this nesting level. We push each instruction to the current and previous nesting levels as we execute them. Then, when we reach the end of a loop and the current cell value is not zero, we prepend the instructions from the current nesting level to the remaining instructions — effectively re-executing the loop.

It’s a decent solution, but I ran into quite a few bugs during implementation. Therefore, I preferred to go for something smarter and simpler. In the previous approach, we already had the entire program stored at the first index of our array. So why don’t we keep the full program and store the instruction index for the beginning of each loop? That’s the approach I ended up using for this interpreter.

We can repeat instructions, but currently, we can’t skip the entire loop execution if the initial condition is false. To fix that, I added another parameter to the Execute(program) function which is the nested level we must reach before resuming execution.

With this theoretical working interpreter, we can now implement it with our types — or at least give it a shot.

Before your brain starts turning into slime, take a 2 minutes break.
Listen to this ambient new age music and gaze at beautiful trees and breathtaking landscapes.

https://medium.com/media/78ed3d4f878ba0e3eb3afcda1f636544/href

Okay. Here comes the bad guy.

Practical solution: write a Brainfuck interpreter with types

To define our Brainfuck instructions, we are using our good ol’ TypeNumber written with types. Each instruction is represented as a number between 1 and 8, and we define a union type that includes all valid operators.

 type P = One;
 type M = Add<One, P>;
 type L = Add<One, M>;
 type R = Add<One, L>;
 type O = Add<One, R>;
 type I = Add<One, O>;
 type J = Add<One, I>;
 type B = Add<One, J>;

 type Operators = P | M | L | R | O | I | J | B;

To make our syntax a bit more manageable when writing the Execute function, we’ll introduce a type that behaves like a switch-case in traditional languages. But since Typescript’s conditional types only allow us to build if-else chains, well… let’s go ahead and write this awful monster.

 type IFOP<
  Op extends Operators,
  PCase,
  MCase,
  LCase,
  RCase,
  OCase,
  ICase,
  JCase,
  BCase,
 > =
  EQ<Op, P> extends true
   ? PCase
   : EQ<Op, M> extends true
    ? MCase
    : EQ<Op, L> extends true
     ? LCase
     : EQ<Op, R> extends true
      ? RCase
      : EQ<Op, O> extends true
       ? OCase
       : EQ<Op, I> extends true
        ? ICase
        : EQ<Op, J> extends true
         ? JCase
         : EQ<Op, B> extends true
          ? BCase
          : never;

Now that we have our first monster, it needs a good friend. This one will be the definition of the Execute function, based on the theory paragraph. So if you remember correctly, we had a lot of parameters:

• the program
• the memory
• the current cell index
• the output
• the current nested loop level
• the skip nested loop level
• the entire program
• the current program index
• the array of loop beginning indexes
• an error parameter to catch bugs (though we won’t explain that one in this article)

Now, just imagine writing a type with all of those parameters…

type Execute<
  P extends Array<Operators>,
  Memory extends Array<TypeNumber> = [Zero],
  CurrentCell extends TypeNumber = Zero,
  CurrentError extends InterpreterError | null = null,
  Output extends string = '',
  LoopLevel extends TypeNumber = One,
  SkipUntilLoopLevel extends TypeNumber = One,
  InitialProgram extends Array<Operators> = P,
  CurrentProgramIndex extends TypeNumber = Zero,
  LoopBackPointers extends Array<TypeNumber> = [Zero, Zero],
 > = never;

Based on these parameters, we need to define how each part of our interpreter should behave for each instruction. So, let’s start with the Program (P) behavior.

Each time the Execute function is called, we must extract the current instruction and call the function again with the remaining instructions. We’re using a conditional type here, just like we did in our previous articles:

P extends [infer Op extends Operators, ...infer Rest]
  ? Execute<
    Rest extends Array<Operators>
      // Call the next instruction with remaining instructions
      ? Rest
      // Call the last Execute call without any instruction
      //  because there's not any remaining instruction
      : [],
    // Current instruction is available in the Op variable
    ...>
  // No more Op to execute = the end of the program
  : [] // This is the type returned at the end

Memory parameter: Plus, Minus and a bit of Right

Each instruction is executed one by one. For the Memory part, two instructions modify its value: P (+) and M (-). The first one increments the current cell’s value, while the second one decrements it. We also introduce two behaviors that are not defined in the original interpreter spec:

• When decrementing, we check the current value. If it’s 0, the interpreter throws an error. I added this because my current number implementation doesn’t support negative numbers.
• When moving to the next cell with R (>), we push a new cell if none exists. Technically, Brainfuck interpreters use a fixed-size memory, but I prefer to expand it dynamically as needed.

IFOP<
  Op,
  // P case
  IncrementCell<Memory, CurrentCell>,
  // M case (with a non-zero check to avoid negative numbers)
  GT<
    Memory[ToRealNumber<CurrentCell>],
    Zero
  > extends true
    ? DecrementCell<Memory, CurrentCell>
    : Memory,
  Memory,
  // R case (with an auto-scaling memory)
  AddCellIfNeeded<Memory, Add<CurrentCell, One>>,
  Memory,
  Memory,
  Memory,
  Memory
>

The IncrementCell function seems pretty straightforward: it just increments the value of a specific cell. But since we’re using functional programming with only basic operations, we don’t have any helper to locate the correct cell and update its value directly. I see two simple ways to handle this:

• Split the memory into three parts: the part before the current cell, the current cell itself, and the part after. Then replace the current cell with its incremented value.
• Iterate through the memory array until we reach the target index, then return the updated value along with the remaining cells.

I went with the second approach, but honestly, the first one feels cleaner.

type IncrementCell<
  Memory extends Array<TypeNumber>,
  // CurrentCell is our counter decremented after each function iteration
  CurrentCell extends TypeNumber,
> = Memory extends [
  infer Current extends TypeNumber,
  ...infer Rest extends Array<TypeNumber>,
]
  ? IF<
    // True = we reach the good cell index
    EQ<CurrentCell, Zero>,
    // Increment and return the new memory
    [Add<Memory[ToRealNumber<CurrentCell>], One>, ...Rest],
    // Continue recursive calls with a decremented CurrentCell
    [Current, ...IncrementCell<Rest, Sub<CurrentCell, One>>]
   >
  : [Zero];

CurrentCell parameter: Right and Left

The CurrentCell parameter keeps the index of our current cell used. These rules are applied to this parameter:

• When we get an R (>), we increment CurrentCell.
• When we get an L(<), we decrement CurrentCell.

IFOP<
  Op,
  CurrentCell,
  CurrentCell,
  // L case: we check if we're not at the beginning of the memory
  GT<CurrentCell, Zero> extends true
    ? Sub<CurrentCell, One>
    : CurrentCell,
  // R case: go to next cell by incrementing the CurrentCell index
  Add<CurrentCell, One>,
  CurrentCell,
  CurrentCell,
  CurrentCell,
  CurrentCell
>

If you read the previous code carefully, you might have noticed a function called AddCellIfNeeded that we haven’t explained yet. This function simply creates a new cell when the CurrentCell moves to a non-existent cell on the “right” side of the memory (the end). We could technically do the same for movements to the left, but that wouldn’t be compliant with the Brainfuck specifications — assuming such specifications even exist.

type AddCellIfNeeded<
  Memory extends Array<TypeNumber>,
  CurrentCell extends TypeNumber,
> = IF<
  GTE<CurrentCell, NumberOfElements<Memory>>,
  // True -> Create a new cell
  [...Memory, Zero],
  // False -> Do nothing
  Memory
>;

Output parameter

The Output parameter is a simple template literal, using this cool feature of Typescript 4.1. We also use a basic Char table — essentially just an ASCII table — to convert code into characters. It looks like this:

EQ<Op, O> extends true
  ? `${Output}${Char[ToRealNumber<Memory[ToRealNumber<CurrentCell>]>]}`
  : Output,

You need a break. Because the ugliest part of the article is just few pixels away.
You need to see cute animals. With a piano. A very calm piano.
Work is far away. Typescript is far away.
There are only cute animals watching you.
You are a cute animal.

https://medium.com/media/273895819b8a247919bc5e5df28df031/href

Time’s up!

Come back to the reality and prepare yourself for the horror.

The five parameters to create loops

If we summarize our current program implementation, we have a big recursive function named Execute that iterates over each instruction until there are no instructions left in the program. But since we want to be able to loop though the program, we need to update it with some new features.

When we encounter on a B (]) instruction, we change the following things in the next Execute iteration, but only if the current cell value is not 0 (because we have to re-execute the loop):

• We replace the program with the one containing the full loop instructions (to re-execute the loop).
• We update the CurrentProgramIndex to point to the instruction right after the beginning of the current loop.

But if the cell value is 0, the loop ends, so:

• We decrement the current LoopLevel.
• We remove the last LoopBackPointer (because we won’t go back to the beginning of the loop anymore).

For the J ([) instruction, it’s pretty much the same. If the current cell value is not 0 (meaning we need to execute the loop code):

• We increment the current LoopLevel.
• We add the next instruction to the LoopBackPointers (so we can jump back to it if needed at the end of the loop).

If the current cell value of 0, we simply need to ignore all instructions until we reach the end of the loop. And that’s why we did some theory before diving into this mess: we’ll add some conditions before the Execute function to skip each instruction one by one until we return to the correct loop level.

At this point, the code is especially long because we have to write multiple Execute cases with all of its arguments. The main pain point I had was figuring how to recreate the program state at the start of the loop. But by using some pointers to save that index, it wasn’t that hard.

// Program recomputation
Rest extends Array<Operators>
  ? EQ<Op, B> extends true
    ? Memory[ToRealNumber<CurrentCell>] extends Zero
      ? Rest
      : GetProgramFromIndex<
        InitialProgram,
        LoopBackPointers[ToRealNumber<LoopLevel>]
      >
    : Rest
  : [],

The GetProgramFromIndex is a simple loop which is iterating recursively on the original program until it reaches the good index.

type GetProgramFromIndex<
  Program extends Array<Operators>,
  CurrentIndex extends TypeNumber,
> =
  EQ<CurrentIndex, Zero> extends true
    ? Program
    : GetProgramFromIndex<
        Program extends [
          infer _,
          ...infer Elements extends Array<Operators>,
        ]
        ? Elements
        : [],
      Sub<CurrentIndex, One>
>;

And … yes, we dit it.

Program result

It’s time to discover what was hidden behind this strange Brainfuck code. Maybe it’s the recipe for happiness. Or the secret bank code to transfer all the money in the world on your account. Or maybe…

Cheh is a French slang that can be translated as “deserved” or “serves you right”. Like: “Oh, you spent a few hours writing a wonderful Brainfuck compiler and it’s completely useless? CHEH”

Yes, it’s a terrible reward.

So yes, we wrote this Brainfuck compiler with only Typescript types. The code is available here. Honestly, it took me a few months to be able to write this article, because this mess is clearly… a giant mess. I’m not even sure what the interest of this article is, except to show off some Typescript dark magic. And I really hope you enjoyed it — or at least learned something.

I won’t write about this subject again for the next months. After writing the code, it felt like there wasn’t much more to learn from this kind of stupid but funny exercise. I’m currently studying other topics, like programming language quality assessment or reverse-engineering from assembly to C. These might lead to new articles on more accessible subjects, so feel free to follow me if you’re interested (especially if you read French, since I want to go back to writing in my native language 🥖).

If you need more Typescript stupid things, here’s someone who runs DOOM with the Typescript types. Yes, it’s another level of stupidity.

Thanks a lot for reading this big Typescript mess. You rock. xoxo

Thanks to Nicolas and Elodie from ekino for their suggestions and corrections on this article 🫶

---

The Useless Brainfuck Interpreter in Typescript was originally published in ekino-france on Medium, where people are continuing the conversation by highlighting and responding to this story.