Master TypeScript: Let's Do Math In Type System

Introduction

In our day to day lives we do Mathematical operations without any hassle and worry. Because we have all the tools we need like, numbers and the operators. Like 5 + 2 = 7, here we know that 5, 2, and 7 are numbers and what we are essentially doing is adding because of the operator +.

Now, just imagine you don’t know what the numbers mean or their actual interpretation. You also don’t know the meaning of the + symbol, but you still want to add two numbers. It's like a toddler trying to do this!

I welcome you to the world of TypeScript where you cannot do all these stuffs. TypeScript does understand numbers but doesn’t have the understanding of what numbers represent and how big they are, what exactly are mathematical operations.

So in this blogpost, I will be explaining you folks, how to do the exact same thing and try to make it more humane.

Prerequisites

• Conditional Types in TypeScript
• Variadic Elements and Tuples in TypeScript

Who is this blog post not for?

Let me tell you the hard truth upfront: this blog post is one of those rare cases where you might not need it. The purpose of this post is to understand the marvelous concepts used to implement such things in TypeScript.

I love TypeScript, and for fun, I am trying to dig into this!

What are we building?

In TypeScript you cannot do any arithmetic operation like the above 5+2 which is equal to 7. You can represent numbers in typescript like 5 or 2 but you cannot do anything with them.

In this blogpost we will be building typescript generic utilities that will help you to implement the arithmetic operations:

• Addition
• Subtraction
• Multiplication
• Division

After going through this blogpost, you will be able to achieve the following in TYPES!!!

type addResult = Add<5, 2> // 7
type subRes = Sub<50, 3>; // 47
type mulRes = Mul<2,10>; // 20
type divRes = Div<10, 2>; // 5

The Basics

Every good code that is implemented is based on a good foundation. In this section we will talk about the foundation of implementing the above generic utilities.

There are two main thing that we need to understand:

• Recursion
• And Tail Recursion

These concepts are really important and drive the entire thought process about these generic arithmetic utilities in TypeScript.

So let us start off by understanding recursion.

What is Recursion?

Recursion is the way through which you can perform certain action by calling the same action. In terms of real life example, recursion can look like this:

If you hold a mirror in front of a mirror then you see an endless mirror within mirrors.

In the similar way, recursion in programming is a way for a function to achieve the results by calling it self. To explain this further let me give you a classic yet simple example,

const sum1ToN = (num: number) => {
    if(num === 0){
        return 0;
    }
    return num + sum1ToN(num - 1)
}

This function will return the sum of all the numbers from 1 to N.

To give you guys a quick look let us see what happens from call stack perspective(I know this is a bit off the route but trust me this will help us understand the later section of the blogpost):

If you execute sum1ToN(4). This is what happens

4 + sum1ToN(3)

4 + 3 + sum1ToN(2)

4 + 3 + 2 + sum1ToN(1)

4 + 3 + 2 + 1 + sum1ToN(0) // <-------

4 + 3 + 2 + 1

4 + 3 + 3

4 + 6

10

In the call stack, numbers are unraveled until num = 0. Once all numbers are spread out, reverse addition occurs, consuming more of the call stack. For example, when num was 4, it took 8 stacks to finish. Imagine if num is 100.

This unpacking method in recursion is inefficient because the last statement in sum1ToN performs two operations: unpacking the number and calling the next number in recursion. The program must remember the previous steps.

But why study this? What does recursion have to do with efficiency?

Find out in the next section.

Limitations in TypeScript

All the arithmetic generic utilities that we are going to build involves heavy recursion to achieve the results. Next, the typescript has limitation on its call stack size. Following are the TypeScript limits of the call stack:

• If it is a normal statement in TS then recursion limit is 100.
• If it is inside a conditional statement then limit is below 1000.

Hence, if we go with the above normal recursion methods to implement our utilities then it would fill up these limits easily even with small numbers like 200 or so if the utilities are not implemented correctly.

The aim of our utilities would be that they should take inputs less 1000.

You can read more about these TS limits in this PR: https://github.com/microsoft/TypeScript/pull/45711

What is Tail Recursion?

There is a way out to this normal recursion technique where you can do these calculations efficiently by reducing the call stack sizes. This method is called as tail recursion. I am not going to go in-depth about tail recursion in this post but I will help you understand how it affects the call stack.

So tail recursion is a technique in which the last statement of the recursive function just calls the function it self and doesn’t do any further calculations combined with it.

For example, in the above sum1ToN function the last statement num + sum1ToN(num -1) should not be present in the tail recursion method according to its definition.

If we cannot do combined operation as the last call in our recursive function then how are we going to achieve results? Its simple, just make use of accumulator to remember the addition of the already visited numbers. Below is the quick look of tail recursion version of sum1ToN:

const sum1ToN = (num: number, acc: number = 0) => {
    if(num === 0)
        return acc;

    return sum1ToN(num - 1, acc + num);
}

Here, we introduce the second argument acc to the function with a default value of 0. This way, the program doesn’t need to remember previous calls. In our case, while unpacking the numbers in the call stack, we are also performing the calculations in the accumulator as shown below:

sum1ToN(3, 0 + 4)
sum1ToN(2, 0 + 4 + 3)
sum1ToN(1, 0 + 4 + 3 + 2)
sum1ToN(0, 0 + 4 + 3 + 2 + 1) // finally the acc is returned

See how the call stack got reduced!!! we don’t need to go through all the next steps of addition because we are doing addition while we are doing the unpacking of the numbers. Isn’t this great 🙂

💡 NOTE Even though this technique is efficient still at some point in our utilities we hit the above mentioned limits.

You can find out more about tail recursion in the below detailed and fantastic videos:

• https://www.youtube.com/watch?v=-PX0BV9hGZY
• https://www.youtube.com/watch?v=_JtPhF8MshA

Let us dive into the implementation

In this section we will be implementing the following arithmetic utilities which look like below:

type Add<A extends number, B extends number> = [
  ...GetRange<A>,
  ...GetRange<B>,
]["length"];

type Sub<
  A extends number,
  B extends number,
  Num1 extends Array<number> = GetRange<A>,
  Num2 extends Array<number> = GetRange<B>,
> = Num2 extends [...Num1, ...infer R] // A < B; res = -ve
  ? `-${R["length"]}`
  : Num1 extends [...Num2, ...infer T] // A > B; res = +ve
  ? T["length"]
  : 0;

 type Mul<
  A extends number,
  B extends number,
  Counter = 0,
  Acc extends Array<number> = [],
  Num1 extends Array<number> = GetRange<A>,
> = B extends Counter
  ? Acc["length"]
  : Mul<A, B, Inc<number & Counter>, [...Acc, ...Num1]>;

type Div<
  N extends number,
  D extends number,
  Acc extends Array<number> = [],
  ReducedN extends number = GetRange<N> extends [...GetRange<D>, ...infer T] ? T["length"] : 0,
> = N extends 0 
    ? Acc['length']
    : Div<ReducedN, D, [...Acc, 0]>;

I know these generic might look way difficult but trust me they are easy to understand. I will break down each and every part of these generic utilities so that you guys can grasp the concept behind it.

So without further ado, let us start by implementing our first utility Add.

Add

In terms of arithmetic this is a no brainer, Add utility will just add two numbers. There are couple of things that you need to understand before we start off with the implementation:

• We cannot do addition or any arithmetic operation of that sort. So to by-pass this we convert each input number into a tuple of numbers. For example, a number 4 will be represented as a tuple of four 0s i.e. [0, 0, 0, 0].
• We will need an utility to generate tuples out of the input numbers
• Numbers greater than 1000 cannot be used because we might reach the TS stack limit discussed above.

So here is how our Add utility will look like:

 type Add<A extends number, B extends number> = [
  ...GetRange<A>,
  ...GetRange<B>,
]["length"];

Before we jump into the implementation, let us understand what the GetRange utility is:

/**
 * Generates a tuple of 0s for the specified number
 */
type GetRange<
  N extends number,
  Acc extends Array<number> = [],
> = Acc["length"] extends N ? Acc : GetRange<N, [0, ...Acc]>;

This utility will generate a tuple filled with 0s equal to number passed as input. So indeed it will do something like below:

type res = GetRange<4> // res = [0, 0, 0, 0]

The GetRange utility works in the following manner:

• It takes input number for which the tuple range needs to be created which is N.
• It also makes use of accumulator Acc which stores the actual range in each step of recursion.
• Its a simple recursion where we check if the length of Acc equals to the number N then we stop the recursion and return the Acc.
• If not, we again call the GetRange<N, [0, ...Acc]> which passes updated Acc to the GetRange with an addition of 0 and the previous values of Acc by destructing it an array like this [0, ...Acc].

Taking a closer look at this utility, we can see that we are using the Tail recursion mechanism, since the last statement in the recursion is only the recursive call to the function and no other operation. And also we are making use of accumulator Acc.

Now let us re-visit our Add utility. In this utility we simple destructure the tuples from GetRange<A> and GetRange<B> inside an array. Finally we return the length of this array:

type Add<A extends number, B extends number> = [
  ...GetRange<A>,
  ...GetRange<B>,
]["length"];

type sum1 = Add<10, 5>; // 15

Subtract

Here is how the subtraction utility will look like in TypeScript:

/**
 * Substracts two numbers
 */
type Sub<
  A extends number,
  B extends number,
  Num1 extends Array<number> = GetRange<A>,
  Num2 extends Array<number> = GetRange<B>,
> = Num2 extends [...Num1, ...infer R] // A < B; res = -ve
  ? `-${R["length"]}`
  : Num1 extends [...Num2, ...infer T] // A > B; res = +ve
  ? T["length"]
  : 0; 

The output of this utility is either string when the output is a negative or a number when output is positive.

type subRes = Sub<50, 3>; // subRes = 47

type subRes = Sub<3, 50>; // subRes = "-47"

To understand this utility take a look at this flowchart:

Let us go through it step by step:

• Sub take 2 mandatory inputs which are A and B. It also has 2 default parameters Num1 and Num2 with the default value of GetRange's of A and B.
• Throughout the utility we make we make use of Num1 and Num2 because it makes easier for comparison as we will see in the next steps.
• It’s easier to compare the array’s with the help of variadic tuple feature of TypeScript. We first compare that if B is greater than A , if it is then our output would be negative i.e. A-B = -res
• We do that by comparing Num2 tuple with an destructured tuple of Num1 and a variadic element R. Here R represents the left over 0s from Num2 which in our case is the result.
• If this is the case then we return a string -R's length.

• You can imagine this calculation in this way:
  

  Sub<2,3, Num1=[0,0], Num2=[0,0,0]>
  
  // Inside Sub this is what happens when A < B:
  
  Sub<2,3, Num1=[0,0], Num2=[0,0,0]> = 
  
  [0, 0, 0] extends [...[0,0], ...infer R] // Here R's value becomes [0]
  
  ? `-[0]['length']` // -1
  
  

• Similarly if A is greater than B then the output will be positive and the result of the residue is stored in T in this case which is a Tuple whose length we return as the output.

Multiplication

The Multiplication utility is a bit different than the Add and Sub. Here is how it looks like:

/**
 * Multiplies two numbers
 */
type Mul<
  A extends number,
  B extends number,
  Counter = 0,
  Acc extends Array<number> = [],
  Num1 extends Array<number> = GetRange<A>,
> = B extends Counter
  ? Acc["length"]
  : Mul<A, B, Inc<number & Counter>, [...Acc, ...Num1]>;

This utility works on the following principle:

• Consider an example of Mul<2,3>, to generate an output of 6 we should add number 2 three times to get the value as 6.
• So in this utility the first number, is the input that will be repeatedly added with itself B number of times which is our second input to Mul.

Here is what happens inside the utility:

• The utility takes 2 mandatory number based inputs A and B. It takes 3 optional parameters Counter Acc and Num1 with it’s respective default values mentioned in the utility.
• Since we are add A to itself B number of times therefore we need to check if we have actually done that or not. To do that we compare B with the Counter, if it matches then we return the length of the Acc i.e. Accumulator which keeps track of this addition.
• Or else we again call Mul with A B, with an incremented Counter with the help of Inc utility and finally we pass a tuple with desctructure value of Acc and Num1.
• The last parameter to Mul in the recursive call is important because it stores the actual results.
• The Incremented counter value is also important because it helps to stop the recursion.
• Here is how the Inc utility looks like, it is pretty straight forward hence not going to explain:

/**
 * Utility to increment the number
 */
type Inc<N extends number> = [0, ...GetRange<N>]["length"];

Division

Similar to multiplication utility, in Division we try to reduce the numerator by denominator till the numerator becomes 0. While this is happening we maintain the count of no. of times numerator was reduced.

For this utility we are apply the following constraints:

• The numerator should be greater than the denominator.
• Numerator should be perfectly divisble by the denominator.

We are going to keep these constraints to our Div utility because implementing use cases such as not divisble numbers, floating point numbers, negative numbers, recurring decimal digits etc makes the utility too complicated and is out of scope of this blog post.

Here is how the utility will look like:

/**
 * Divides two numbers
 */
type Div<
  N extends number,
  D extends number,
  Acc extends Array<number> = [],
  ReducedN extends number = GetRange<N> extends [...GetRange<D>, ...infer T] ? T["length"] : 0,
> = N extends 0 
    ? Acc['length']
    : Div<ReducedN, D, [...Acc, 0]>;

Inside the utility following things happen:

• There are 2 mandatory inputs N and D which stands for Numerator and Denominator.
• Next, we have 2 optional inputs Acc and ReducedN with their respective default values.
• Acc is the accumulator tuple that we use to keep a count of number of times we subtracted D from N.
• ReducedN has a default value GetRange<N> extends [...GetRange<D>, ...infer T] ? T["length"] : 0 which compares the N tuple with a tuple of D and a varidiac element T. This value is nothing but subtraction of D from N. You can refer to the Sub utility for this to understand the logic.
• Next, inside the actual utility we check that if N has been exhausted completely i.e. N is equal to 0. If it is then we return the length of the Acc or else we again call the Div with ReducedN as N, with same D as the denominator, and with an incremented Acc by appending 0 to it.

Limitation

The purpose of these utilities is to understand different concepts and the power of typescript. Below are some of the uses cases that are purposely not implemented since it would overcomplicate stuff and would be out of scope of this blog post:

• For Add utility, we didn’t consider addition of negative numbers or combination of negative and positive numbers. This also leads to connectivity between Sub utility as well. This limitation also applies to Mul and Div
• For all the utilities, operations related floating point numbers is not considered.
• Due to call stack limitation of TS we cannot do operations on numbers more than 999.

Summary

I know this blogpost isn’t going to be that fruitful in real life use cases but take a look at what are the things we learned from it today:

• We understood recursion and Tail recursion
• How does tail recursion helps in optimizing the code by reducing the call stack consumption.
• We saw how Typescript interprets numbers and also saw that we cannot do arithematic operations
• We learned Typescript’s limitation of its call stack size.
• We learned how we can interpret numbers in the form of tuple like GetRange and Inc.
• Lastly, we saw how we can leverage the above technique to create Add Sub Mul and Div utilities.

So that’s all folks!. Hope you like my blog post.

You can follow me on twitter, github, and linkedIn.