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

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
]
? 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! 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! :)