The Useless Type Calculator in TypeScript

It’s time for one of the most useless things I’ve ever made — something beyond reason, where logic stops being rational and void becomes reality. It’s time to create a calculator using only types from TypeScript.

Originally posted on my blog the October, 5th 2021 : https://aamulumi.info/Dev/The-Useless-Type-Calculator-in-Typescript

—

A few days ago, I remembered a discussion with a friend about Turing-complete systems. We checked the Wikipedia article on the subject, and we discovered that many things (like games) are Turing-complete. So yes, Minecraft is Turing-complete, Factorio too, Dwarf Fortress too, and it seems that Habbo Hotel and Magic: The Gathering (yes, the cards game) are also Turing-complete.

We also found somewhere that TyepScript’s type system is Turing-complete. With this knowledge, I decided to start developing something that would serve no practical purpose: a calculator using only TypeScript types.

Yes. This is one of the stupidest ideas I‘ve had in a while. But it’s a fun exercise to prove your skill in typing everything.

The rules

If you’d like to try creating the calculator, here are the rules of the “game” (if we can even call it a game):

• you have to start with only two types: BZero (for Boolean Zero) and BOne (for Boolean One).

type BZero = false;
type BOne = true;

• you can only use types. No interfaces, no enums, only types.
• you need to implement the four basic mathematical operations (using types): addition, subtraction, multiplication, and division. You can also add modulo.
• this code should works:

// Equivalent of (6 + 6 * (1 + 2)) / (6 - 2) = 6
type StrangeOperation = Divide<
  Add<Multiply<Six, Add<One, Two>>, Six>,
  Subtract<Six, Two>
>;

Due to the way I implement the calculator, I use another type Result to read the result:

type OpResult = Result<StrangeOperation>;

This type is completely optional in the rules. However you must have an exact number type at the end of the computation. For example, you should have:

type OpResult = 6;

And here you go! It’s time for you to code!

…

…

…

Yeah, better to just read the solution, right?

The solution

Conception

Firstly, I searched for ways to get a number type from a type in Typescript. You have your basic operation to transform BZero and BOne to Zero and One number if you‘re familiar with this.

I tried something based on array indexes, but there was no way to get a number. So I discovered that Typescript tuples have a length property. And it works with variable-length tuples since 3.0. With this information, I started writing a calculator based on tuples.

type TypeNumber = Array<any>;

The first types we need are the Zero and the One based on tuples. In this way, I write a simple conditional type that returns a tuple with the number of elements equivalent to the number it describes. For example:

type ToTypeNumber<A> = A extends true ? [true] : [];
 
type Zero = ToTypeNumber<BZero>;
type One = ToTypeNumber<BOne>;
 
// Result
type Zero = [];
type One = [true];

In this way, we need a type to determine the length in order to obtain the desired number type.

type Result<A extends TypeNumber> = A["length"];
 
// Example
type C = Result<One>;
 
// Result
type C = 1;

Operation 1 : Add

With this conception, the Add type is the most straightforward operation to implement, thanks to TypeScript 4.0. We simply need to concatenate the two tuples to create Add type.

type Add<A extends TypeNumber, B extends TypeNumber> = [...A, ...B];
 
// Example
type Two = Add<One, One>;
type TwoResult = Result<Two>;
type Four = Add<Two, Two>;
type FourResult = Result<Four>;
 
// Result
type Two = [true, true];
type TwoResult = 2;
type Four = [true, true, true, true];
type FourResult = 4;

Operation 2 : Subtract

The hard way

Now, the fun begins.

We need to think about the computation behind subtraction. So let’s go back to elementary school.

I have 6 balloons. I give 4 balloons to Manu. I now have 2 balloons left.

In terms of tuples, we can represent the problem with this:

type MyBalloons = [true, true, true, true, true, true];
type NewManuBalloons = [true, true, true, true];
type NewMyBalloons = [true, true];

To implement subtraction, I take each element of MyBalloons one by one and check if it exists in NewManuBalloons. I reach the point where there are no more elements in NewManuBallooons, I start to increment a variable which will be the result.

But there’s a problem: it looks like a loop. How can we implement a loop in Typescript?

The answer is to use a recursive type. With a condition, we can achieve this using a recursive conditional type. Here’s the code:

type Subtract<
  A extends TypeNumber,
  B extends TypeNumber,
  Res extends TypeNumber = []
> = A extends [boolean, ...infer H]
  ? B extends [boolean, ...infer J]
    ? Subtract<H, J, Res>
    : Subtract<H, B, Add<Res, One>>
  : Res;

Oh yeah, there’s another tip: I use type inference to remove elements from a tuple. For example, if I have type A = [true, true, true], I will get type H = [true, true]. This is because I check if A 's first element is a boolean, and I send the rest of the tuple in another type variable.

I use type inference in a second condition to check if the current element exists in B. When there's an element in both A and B, I recall the Subtract type with the remaining elements of A (H) and the remaining elements of B (J). If there are no more elements in B, we continue to call Subtract, but we increase Res at each call. When A is empty, we return the Res type.

And now, we have subtraction implemented using only types. Note that this subtraction only works with positive integers. This limitation arises from the nature of tuples, because you cannot have a tuple with a negative length.

// Example
type TwoFromSubtract = Subtract<Four, Two>;
type TwoFromSubtractResult = Result<TwoFromSubtract>;
 
// Result
type TwoFromSubtract = [true, true];
type TwoFromSubtractResult = 2;

The smart way

The hard way is a pure example of overengineering. There’s actually a much simpler way to perform subtraction: subtract B from A and keep the result.

In my defense, I realized I could use type inference between 2 dynamic types when working on Divide. But you can shame me, and it's okay.

Here’s the code:

type BetterSubtract<A extends TypeNumber, B extends TypeNumber> = A extends [
  ...B,
  ...infer Res
]
  ? Res
  : Zero;

Operation 3 : Multiply

We have already covered all the techniques we need for multiplication. To multiply, we simply need to add A to itself B times. This is now a piece of cake since we tackled the hard way of subtraction.

To perform multiplication, we create a loop (using recursive types). In this loop, remove One from B, add A to the result, and return Res when B is Zero. In this way, we will add A B times, effectively performing A x B.

type Multiply<A extends TypeNumber, B extends TypeNumber> = B extends [
  boolean,
  ...infer S
]
  ? Add<Multiply<A, S>, A>
  : [];
 
// Example
type MultTest = Multiply<Four, Six>;
type MultTestResult = Result<MultTest>;
 
// Result
type MultTest = [
  true,
  ... 22 more,
  true
];
type MultTestResult = 24;

Operation 4 : Divide

We’ve been working with integers from the start, so for this part, we can only perform a Euclidian division.

In subtraction, we check if A can contain B and determine the remainder. We will do the same thing here, except we need to find out how many times A contains B. So, we use the same primary condition as in subtraction, but we add a recursive type that increments the result with each loop iteration. When A can no longer contain B, we return the number of loops completed up to that point.

type Divide<
  A extends TypeNumber,
  B extends TypeNumber,
  Res extends TypeNumber = Zero
> = A extends [...B, ...infer T] ? Divide<T, B, Add<Res, One>> : Res;
 
// Example
type DivideTest = Divide<MultTest, Six>;
type DivideTestResult = Result<DivideTest>;
type DivideTest2 = Divide<Six, Four>;
type DivideTest2Result = Result<DivideTest2>;
 
// Result
type DivideTest = [true, true, true, true];
type DivideTestResult = 4;
type DivideTest2 = [true];
type DivideTest2Result = 1;

Operation Bonus : Modulo

Modulo is very similar to division. We keep checking how many times A contains B, and when we reach the end, we return the remaining value instead of the number of iterations. And tadaaaaaa, we get the modulo operation.

type Modulo<T extends TypeNumber, U extends TypeNumber> = T extends [
  ...U,
  ...infer S
]
  ? Modulo<S, U>
  : T;
 
// Example
type ModuloTest = Modulo<MultTest, Six>;
type ModuloTestResult = Result<ModuloTest>;
type ModuloTest2 = Modulo<Six, Four>;
type ModuloTest2Result = Result<ModuloTest2>;
 
// Result
type ModuloTest = [];
type ModuloTestResult = 0;
type ModuloTest2 = [true, true];
type ModuloTest2Result = 2;

So here we have a fully functional calculator using only TypeScript types. I considered implementing a decimal calculator based on the binary representation of decimals, but that would have been madness.

I hope you enjoyed reading this piece of programming as much as I enjoyed writing it. And last but not least, here’s the topic of the initial discussion I had with my friend about Turing-Complete TypeScript.

Thanks for reading! On behalf of all of us here, I want to wish you happy programming and God Bless, my friend! 🙂

Many thanks to Aude for her proofreading and corrections.

Originally published at https://aamulumi.info on October 5, 2021.

---

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