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.
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?
Firstly, I search what the ways to get a number type from a type in Typescript are. You have your base operation to transform
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
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
B, I recall the
Subtract type with the remaining elements of
H) and the remaining elements of
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
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
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
A to the result, and send the
B is Zero. In this way, we will add
B-times, so we are doing
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
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
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.