Grokking Type-Level Programming: Crafting Arithmetic in TypeScript without Digits and Operators

Photo by Chris Liverani on Unsplash

You may have heard that the TypeScript typing system is Turing complete. Literally, it means that you can write your own programming language or emulate Conway’s Game of Life using its types. Moreover, nowadays, there are complete 2D games written in TypeScript types (breaking news: there is DOOM in TypeScript types)!

In this article, I want to demonstrate the power of type-level programming in TypeScript, starting from the very basics. And what’s the beginning for us, the programmers? That’s right — numbers. I want to create the numeral system using only TypeScript types. By the end of this article, you’ll be able to manipulate numbers — even arrays of numbers — without using any digits or operators. Let’s get started!

In the middle of nowhere

“The journey of a thousand miles begins with one step.” — Lao Tzu

Every calculus or measurement system starts with zero. Zero is the neutral element for symmetric groups, where addition is a group operation in the group theory. Sorry, that got a bit nerdy. In short, we must define a zero for our type-level system to build everything else upon it.

type _Zero = "🇺🇦";

Here are two key points about this code line:

1. Abstracting from digits. I intentionally haven't used a "0" character (or even a 0-digit as a type, which I could). To abstract entirely from any pre-existing numeric representation, I decided to use my country's flag as a symbolic stand-in (Доброго вечора!)
2. Underscore prefix. I will use underscores to differentiate the internal types in my arithmetic system. Later, when we discuss the system's I/O, I will explain the relationship between internal and external types.

Numbers as a numeral system language

“Numbers are the universal language offered by the deity to humans as confirmation of the truth.” — St. Augustine of Hippo

In our algebra, we will operate on a set of positive integer numbers limited by the maximum. We will stop at 5, which will be enough to demonstrate the power of the TypeScript type system.

You might suspect, till now, that if we haven't provided any contextual sense for a zero in our system and put the flag emoji in it, what should we do with other numbers? Digits, Roman numerals, or other symbology don't matter when interpreting numbers in Turing complete systems. Relations matter!

Having a zero in our domain-specific language, we can define the number as the next recursion type:

type _Number = _Zero | { prev: _Number };

Every integer is the successor of the previous one, making this relationship crucial for future operations. Let's define the first generic, responsible for numbers relation

type _Next<T extends _Number> = { prev: T };

And finally, the prominent citizens of our village — the numbers!

type _One = _Next<_Zero>;
type _Two = _Next<_One>;
type _Three = _Next<_Two>;
type _Four = _Next<_Three>;
type _Five = _Next<_Four>;

type _Max = _Five;

Once again, we are responsible for defining the maximum value for our numeral system. Enforcing this limit will be helpful in future operations.

User-Friendly I/O

“Everything should be made as simple as possible, but not simpler.” — Albert Einstein

We are close to starting to create something computational. For now, we have defined the numeral system's "numbers" as TypeScript types.

Running ahead, I will not reveal a big secret if I say that the system's "functions" would be TypeScript generics. Generics take parameters like function arguments, and TypeScript’s type inference determines the return value.

However, using our already declared numeric types might be cumbersome because our users must always keep these definitions on hand. Fortunately, TypeScript provides literal types that we can consider as values of the numeral system. Let's imagine, for a while, how the function of adding would look in that case:

But we talked about the matter of predecessor-successor relations between types. How do literal types preserve it?

Let's consider previously defined numbers as internal types of our numeric system and literal types as external types. We will match them in a 1:1 relation—the user will provide literal-type arguments as input and receive the result in a literal-type view as output. However, the system will calculate the resulting type inferences based on internal types.

// The definition of "external" numbers
type _StringNumber = "Zero" | "One" | "Two" | "Three" | "Four" | "Five";

// Here, we convert "internal" types to "external"
type _StringifyNumber<T extends _Number> = T extends _Zero ? "Zero" 
    : T extends _One ? "One" 
    : T extends _Two ? "Two" 
    : T extends _Three ? "Three" 
    : T extends _Four ? "Four" 
    : T extends _Five ? "Five" : never;

// And vice versa, from "external" to "internal"
type _ParseNumber<T extends _StringNumber> =  T extends  "Zero" ? _Zero 
    : T extends "One" ? _One 
    : T extends "Two" ? _Two 
    : T extends "Three" ? _Three 
    : T extends "Four" ? _Four 
    : T extends "Five" ? _Five : never;

As you remember, I mentioned that types with underscore prefixes are considered internal types. It means that users of our type-level system will not use them for user calculations. Eventually, to demonstrate user-specific types, let's start with some warm-up.

Increment: the first step into the world of Calculus

“From a tiny spark may a great fire grow.” — Dante Alighieri

For computer science, the increment is the most fundamental and, simultaneously, the most trivial operation. Attentive readers may have noticed that we have already implemented it as a _Next type. That will be right, but let's refine it to consider the upper limit of our algebra.

type _Increment<T extends _Number> = T extends _Max ? never : _Next<T>;

As you see, we infer all exceeded values of our computations to never.

Let’s integrate this mathematical function with our I/O system from the previous section:

Referencing the schema above, we can introduce our first mathematical calculation crafted only on TypeScript types!

type Increment<T extends _StringNumber> = 
  _StringifyNumber<_Increment<_ParseNumber<T>>>;

Let's see what we have in the final stage:

Voila! We have a complete mathematical operation in the world without digits!

Addition without “+”

“Mathematics is the art of giving the same name to different things.” — Henri Poincaré

Let's move forward and create the most popular operation of arithmetics: addition. Looking at the implementation of our I/O converters, we can assert that iteration is not a big friend of type-level programming. The idea of gradual iteration from the first number to the sum of the numbers is natural but hard to complete in type-level systems.

What if we contract to the iteration's antagonist — recursion? It turns out that's a key! We can interpret the addition as the following recursion formula:

Can we implement this in terms of our numeral system? Let's break a formula into some meaningful tokens and consider them:

• (a, b) parameters signature — as we have done with the increment function, generic parameters take care of it
• b === 0 ? ... : ... condition — with the help of extends, TypeScript provides conditional types
• add(...) recursion invocation — TypeScript allows recursive generics
• a + 1 — we already implemented the increment in the previous paragraph
• (b — 1) — the last secret puzzle that we need

Now, I propose you come to the start and recall what we define as the number of our numeral system:

type _Number = _Zero | { prev: _Number };

Notice the subtle hint about subtracting one from a number?

Reference to the prev! The previous number is the result of subtraction by one. So, we need to create a function that takes a number as an argument and returns its previous number.

This may be a dangerous intention because our definition of numbers includes a zero, which doesn't have a reference to a previous value.

Let's look at the recursion formula of an addition once again. In the condition predicate, we check the parameter's equality to zero. We use b only in the conditional branch, where b can't be a zero. This means we can create a non-zero assertion and use it in our decremental function.

Okay, we dive deeply this time, so let's push off from the bottom and rise to the surface together!

At first, the non-zero assertion that "narrows" the type:

type _NonZero<T extends _Number> = T extends _Zero ? never : T;

Next, the single subtraction by a prev reference:

type _Prev<T extends _Number> = _NonZero<T>["prev"];

And finally, ladies and gentlemen, the final form of addition!

type _Add<A extends _Number, B extends _Number> =  
  B extends _Zero 
    ? A 
    : A extends _Max 
      ? never 
      : _Add<_Next<A>, _Prev<B>>;

Wrapping it to the user-friendly I/O…

type Add<A extends _StringNumber, B extends _StringNumber> = 
  _StringifyNumber<_Add<_ParseNumber<A>, _ParseNumber<B>>>;

And finally, we have the long-awaited result!

Oops! The result exceeded our algebraic maximum.

The subtraction operation can also be represented as recursion. Could you guess the formula in the comments? We can also implement this in our numeral system, which will be left in your exercise.

Bonus chapter: mapping of an array

“Nature is an infinite sphere whose center is everywhere and whose circumference is nowhere.”— Blaise Pascal

So far, we have defined a concept of number in our numeral system, implemented the basic mathematical operations in the realm of numbers, and finally convinced ourselves of the power of type-level programming.

So, if we defined the number as a TypeScript type, what’s stopping us from determining the array type of these "numbers"? Correct, nothing! The final trick for today will be implementing the function that returns the array's length.

This example doesn't require converting every array item by "parse-stringify" manipulations as we did above because we don't care about array content. We care about the array structure, which is so popular, particularly in functional programming languages.

To get the head and the tail or the array type, we must be able to use inferred types.

type Head<T> = T extends [infer First, ...infer Rest] ? First : never;

type Tail<T> = T extends [infer First, ...infer Rest] ? Rest : never;

What do we need it for? Okay, now let's return to our initial idea of calculating the length of an array.

Can we represent the length function as a recursion? Sure, we can!

We already have all the puzzles for the implementation of this recursion, so let's implement it!

type _ArrLength<T extends _StringNumber[]> = 
  T extends [] 
    ? _Zero 
    : _Increment<_ArrLength<Tail<T>>>;

And convert the result to a meaningful output…

type ArrLength<T extends _StringNumber[]> = _StringifyNumber<_ArrLength<T>>;

Let's check the result:

Kinda works, hah?

Final words

No digits, no operators — just as I promised at the beginning, we did it! This numeric system, built purely with TypeScript types, can evolve into even more sophisticated forms — your imagination is the only limit.

For example, my next step was the creation of the map function for arrays with the transformation callback as a generic parameter. And what do you suggest considering as a next step?

Thank you for reading the article. This article was in my mind for a year, and I finally put it on paper. Did it spark your curiosity, even for a moment? If so, give it a clap or drop a comment if you want to see more content like this.

Keep your types in shape! 🚀

Article references:

• TypeScripts Type System is Turing Complete
• Flappy Bird written in type-level Typescript
• Conway's Game of Life
• TypeScript types can run DOOM

Thank you for being a part of the community

Before you go:

• Be sure to clap and follow the writer ️👏️️
• Follow us: **X | [LinkedIn](https://www.linkedin.com/company/inplainenglish/) | [YouTube](https://www.youtube.com/channel/UCtipWUghju290NWcn8jhyAw) | [Newsletter](https://newsletter.plainenglish.io/) | [Podcast](https://open.spotify.com/show/7qxylRWKhvZwMz2WuEoua0) | [Differ](https://differ.blog/inplainenglish)**
• **Check out CoFeed, the smart way to stay up-to-date with the latest in tech 🧪**
• **Start your own free AI-powered blog on Differ** 🚀
• **Join our content creators community on Discord** 🧑🏻‍💻
• For more content, visit **plainenglish.io + [stackademic.com](https://stackademic.com/)**