How Far Can We Exploit the TypeScript Compiler? Let’s Fibonacci It Beyond Integer Max Value
The use of the TypeScript’s type system you didn’t know about
The TypeScript compiler was designed to do beginners' tasks, like type checking with some type manipulations. But if you look closer — and we will — we can do real work at compile time.
Yes, you read correctly, at compile time! Our weapon of choice is the TypeScript type system. We can use the TypeScript type system to perform extensive calculations during compilation. How far can we go? let's go crazy!
Let’s try to calculate some really large Fibonacci numbers during compile time.
Fibonacci Numbers
Fibonacci Numbers are defined recursively as:
Fib(0) = 0Fib(1) = 1Fib(n) = Fib(n-1) + Fib(n-2)
This is the perfect problem to see how powerful the TypeScript’s type system is. First, we need some basic operations. In the beginning, we start with operations on single digit numbers.
Basic Arithmetic Operations for Single Digits
The simplest arithmetic operation is to increment or decrement a number. So let’s define a decrement type Decrement<Digit> which can substrate one from a single digit number.
How do we check if our decrement type works? How do we output the resulting type literal? One possibility is to raise a type error. The easiest way to raise a type error is to assign the wrong type to the resulting type:
Similarly, we can create a Increment<Digit> type to increment a single digit number.
This was easy. Now we can use the increment and decrement type to add an Addition type.
An addition can be implemented as a recursive type that adds one to the first operand and subtracts one from the second operand. Afterward invoke the addition with the results. If the second operand reaches zero, the first operand is the sum of the original operands.
That's it! Now we can calculate some Fibonacci Numbers.
Calculate Fibonacci Numbers During Compile Time
With the script above, we can calculate up to the 6th Fibonacci Number. This is nice, but it can not be the last word on the topic. We should aim for more.
Creating a Composed Number Format
For larger numbers, we could create huge lists for the Increment and Decrement type where for each number the increment or decrement is mapped. But this is a lot of work and pretty boring.
A more clever way to represent larger numbers is to use a hierarchical list:
A list represents a number starting with the last digit to the highest one and it is terminated with null. The number 142 for example is represented as:
Num<2, Num<4, Num<1, null>>>TheDecrement operator for this recursive list becomes recursive with the following rules:
- Decrement of 10 is 9
- If a number ends with 0, the last digit will be 9 and the next item of the number is decremented
- Otherwise we just decrement the last digit
TheIncrement operator for our new number format follows very similar rules:
- Increment of 9 is 10
- If a number ends with 9, the last digit will be 0 and the next item of the number is incremented
- Otherwise we just increment the last digit
The updated Fibonacci Number program — using our composed number format — adds the increment and decrement functions described above.
With this optimization we are able to calculate up to the 18th Fibonacci Number, its 2584! We are getting there.
But the representation of the number 2584 as Num<4, Num<8, Num<5, Num<2, null>>>>is pretty confusing. Can we make the representation of the input and output more readable?
Format the Output nicely
To make the output more readable, the digits must be in a natural ordering and we want to get rid of all these Num<…> types.
The PrettyOutput type transforms a number from our list representation to a string with the natural ordering of the digits. With the PrettyOutput type our error message reads
Format the Input nicely
Also the input for the number 18 (Num<8, Num<1, null>>) is not very readable. We need a similar concept as the Pretty type reverse the order of the digits and get rid of all these Num<…> types.
If we apply the Pretty and the CreateNum type to our Fibonacci type the numbers become more readable.
A More Clever Addition
If we try to calculate the Fibonacci Number of 19 we get the error Type instantiation is excessively deep and possibly infinite. TypeScript only allows us a recursion of a certain depth. Since of 100, our addition can only go to a certain depth.
Many recursions are wasted in the addition because to add the number 130 + 80, we waste 80 recursions. If we look closer at the addition, we realise that the addition must not decrement the addend all the way down to zero. It is sufficient if we reach a zero in the last digit.
Afterward, we only care about the second last digit. If the second last digit is zero, we only care about the third last digit and so on. If we optimize the addition it needs to do the following:
- if the second operand is 0, we’re done. Return the first operand as a result
- if the second operand ends with 0, we only need to look at the higher digits
- otherwise increment the current digit of the first and decrement the current digit of the second operand.
Wow, we can calculate the 70th Fibonacci Number! It’s 190'392'490'709'135. This number does not even fit into a 32 Bit integer and scratches the mantissa size of a double variable.
Story Time
After my master's degree in scientific computing I worked on high-performance C++ applications deployed on the world's largest supercomputers. Then I founded a Web company and turned my eye to TypeScript. I never saw TypeScript as a simple script language, it can stand with the big guys.
