Grokking Type-level Programming: Crafting Arithmetic in TypeScript without Digits and Operators Grokking Type-Level Programming: Crafting Arithmetic in TypeScript without Digits and OperatorsPhoto by Chris Liverani onUnsplashYou 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 getstarted!In the middle ofnowhere“The journey of a thousand miles begins with one step.” — LaoTzuEvery 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 uponit.type Zero = “🇺🇦”;Here are two key points about this codeline: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 (Доброговечора!)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 externaltypes.Numbers as a numeral systemlanguage“Numbers are the universal language offered by the deity to humans as confirmation of the truth.” — St. Augustine ofHippoIn 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 typesystem.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 numbersrelationtype Next = { prev: T };And finally, the prominent citizens of our village — thenumbers!type One = Next;type Two = Next;type Three = Next;type Four = Next;type Five = Next;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.” — AlbertEinsteinWe 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 returnvalue.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 thatcase:But we talked about the matter of predecessor-successor relations between types. How do literal types preserveit?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 internaltypes.// The definition of “external” numberstype StringNumber = “Zero” | “One” | “Two” | “Three” | “Four” | “Five”;// Here, we convert “internal” types to “external”type StringifyNumber = 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 “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 somewarm-up.Increment: the first step into the world ofCalculus“From a tiny spark may a great fire grow.” — Dante AlighieriFor 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 ouralgebra.type Increment = T extends Max ? never : Next;As you see, we infer all exceeded values of our computations tonever.Let’s integrate this mathematical function with our I/O system from the previoussection:Referencing the schema above, we can introduce our first mathematical calculation crafted only on TypeScript types!type Increment = StringifyNumber>>;Let’s see what we have in the finalstage:Voila! We have a complete mathematical operation in the world withoutdigits!Addition without“+”“Mathematics is the art of giving the same name to different things.” — HenriPoincaré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 considerthem:(a, b) parameters signature — as we have done with the increment function, generic parameters take care ofitb === 0?…:… condition — with the help of extends, TypeScript provides conditional typesadd(…) recursion invocation — TypeScript allows recursive genericsa + 1 — we already implemented the increment in the previous paragraph(b — 1) — the last secret puzzle that weneedNow, I propose you come to the start and recall what we define as the number of our numeralsystem:type Number = Zero | { prev: Number };Notice the subtle hint about subtracting one from anumber?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 previousnumber.This may be a dangerous intention because our definition of numbers includes a zero, which doesn’t have a reference to a previousvalue.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” thetype:type NonZero = T extends Zero ? never : T;Next, the single subtraction by a prev reference:type Prev = NonZero[“prev”];And finally, ladies and gentlemen, the final form of addition!type Add = B extends Zero ? A : A extends Max ? never : Add, Prev>;Wrapping it to the user-friendly I/O…type Add = StringifyNumber, ParseNumber>>;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 anarray“Nature is an infinite sphere whose center is everywhere and whose circumference is nowhere.”— BlaisePascalSo 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’slength.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 inferredtypes.type Head = T extends [infer First, …infer Rest] ? First : never;type Tail = 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 anarray.Can we represent the length function as a recursion? Sure, wecan!We already have all the puzzles for the implementation of this recursion, so let’s implement it!type ArrLength = T extends [] ? Zero : Increment>>;And convert the result to a meaningful output…type ArrLength = _StringifyNumber>;Let’s check theresult:Kinda works,hah?Final wordsNo 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 onlylimit.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 nextstep?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 likethis.Keep your types in shape!🚀Article references:TypeScripts Type System is TuringCompleteFlappy Bird written in type-level TypescriptConway’s Game ofLifeTypeScript types can runDOOMThank you for being a part of the communityBefore yougo:Be sure to clap and follow the writer️👏️️Follow us: X | LinkedIn | YouTube | Newsletter | Podcast |DifferCheck 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.comGrokking Type-level Programming: Crafting Arithmetic in TypeScript without Digits and Operators was originally published in JavaScript in Plain English on Medium, where people are continuing the conversation by highlighting and responding to this story. You can include dynamic values by using placeholders like: https://drewdru.local.press/articles/fa562c0f-db3e-4fe6-9f4c-56afb479bee4, Drew Dru, https://javascript.plainenglish.io/grokking-type-level-programming-crafting-arithmetic-in-typescript-without-digits-and-operators-71af0127041a?source=rss-b714250038a5------2, drewdru, drewdru, drewdru, drewdru These will automatically be replaced with the actual data when the message is sent.