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<
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;
``````

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 TwoResult = Result<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>
: 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;
``````

Smart.

### 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
]
: [];

// 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! You can contact us on the company’s Twitter or LinkedIn. From all of us here, I want to wish you happy programming and God Bless, my friend! :)

Mis à jour :