The Useless Type Calculator in Typescript

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

Originally posted on my blog 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 Wikipedia article on the subject, and we discovered that many things (like games) were 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 the type system of Typescript is Turing-complete. With this knowledge, I decided to start developing something that would not change anything: a calculator with only Typescript types.

Yes. This is one of the most stupid ideas I got for a while. But this is a fun exercise you can do to prove your skills in typing everything.

The rules

If you want to try to do the calculator, here are the rules of the "game" (if we can call this 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 interface, no enum, only types.
• you have to compute the four basic mathematical operations (with types): add, subtract, multiply and divide. 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 totally optional in the rules. But you must have a 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 read the solution, isn't it?

The solution

Conception

Firstly, I search what the ways to get a number type from a type in Typescript are. You have your base operation to transform BZero and BOne to Zero and One number if you know 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 tuples since 3.0. With this information, I began to write 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 read the length of the tuple to get the desired type number.

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 have to concatenate the two tuples, and we have done an 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 the subtraction. So let's come back to elementary school.

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

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

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

To implement the subtraction, I take each element of MyBalloons one by one and check if each element exists in NewManuBalloons. When I arrive at the moment there's no more element 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 achieve a loop in Typescript?

The answer here is to use a recursive type. And with a condition, we can do that with 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 of 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 the type inference in a second condition to check if the current element exists in B. When there's an element in A and B, I recall the Subtract type with the remaining elements of A (H) and the remaining elements of B (J). If there's no more element in B, we continue to call Subtract, but we increase Res at each call. And when A is empty, we return Res type.

And now, we have a subtraction with only types. Note that this subtraction only works with positive integers. This problem is caused by tuples, because yes, 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. Because there's such a simple method to do a subtraction: subtract B from A and keep the result.

For my defense, I understood that 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 already have seen all the techniques we need to Multiply. So we need to add B times the A number. This is now a piece of cake since the subtraction's hard way.

To multiply, make a loop (with recursive types). In this loop, remove One from B, add A to the result, and send the Res when B is Zero. In this way, we will add A B-times, so we are doing 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 have worked since the beginning with integers. So we can only have a Euclidian division for this part.

In the subtraction, we search if A can contain B and what's remaining. We will do the same thing, except we need to search how many times A contains B. So we have the same primary condition as the subtraction, but we add a recursive type with an incremented result at each loop iteration. When A cannot contain B anymore, send the number of loops done until here.

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 almost the same as the Divide. 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 working calculator with only Typescript types. I thought about implementing the decimal calculator based on the binary representation of decimals. But this is clearly madness. I hope you enjoy reading this piece of programming like 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! From all of us here, I want to wish you happy programming and God Bless, my friend! :)