I Patched the TypeScript Compiler to Add Up Nine Numbers

Lately I’ve been sick of this double life I’m living. By day I write TypeScript for work, by night I write Haskell for my personal projects. The time has come to bring my passion for functional programming and my professional experience in TypeScript together.

How? Why by solving competitive programming problems using only TypeScript’s type system of course! Is it a terrible idea? Absolutely. Let’s get to it!

New to type-level or functional programming? I put together a short primer to get you up to speed and ready to understand the rest of the series. If [infer Head, ...infer Tail] doesn’t look familiar yet, start there and come back.

The Problem - Sum of Odd Numbers

We are given a list of N elements

// input sample
3
2
4
6
5
7
8
0
1

And we need to sum all its odd numbers, so in this case 3 + 5 + 7 + 1 = 16.

Alright, easy enough, in Haskell this would be a simple one-liner (excluding imports).

main = interact $ lines >>> map (read @Int) >>> filter odd >>> sum >>> show

Now where to begin in TypeScript?

Implementing the algorithm at the term level

Let’s start with play typescript. A simple solution could be:

const numbers = [ 3, 2, 4, 6, 5, 7, 8, 0, 1 ]
const isOdd = (n: number) => n % 2 === 1
const result = numbers.filter(isOdd).reduce((acc, n) => acc + n, 0)

Hmmm… We need a way to tell if a number is odd and a way to add numbers together. None of these exist in the typesystem…

Unfortunately there is no way around it, we are going to need to find a way to represent numbers that allows us to manipulate them.

Enter Peano numbers!

Peano numbers are the classical way to represent natural numbers.

// zero, the base case, the smallest natural number
export type Zero = { readonly tag: 'Zero' };
// Succ<N> is the successor of N
export type Succ<N extends Peano> = { readonly tag: 'Succ'; readonly prev: N };

export type Peano = Zero | Succ<any>;

Voilà peano numbers, we could now define constants if we wanted:

type One = Succ<Zero>
type Two = Succ<One>
type Three = Succ<Two>
//   ^?
//   { tag: 'Succ', prev: { tag: 'Succ', prev: { tag: 'Succ', prev: { tag: 'Zero' }}}}

Let’s start by writing a function to convert a number to a peano number, the key here is that we use C, an auxiliary parameter, where we’re going to build a list with the size of the peano number and then we ask for the length.

type ToNumber<N extends Peano, C extends unknown[] = []> = 
  N extends Zero ? C['length']
  : N extends Succ<infer Prev>
    ? ToNumber<Prev, [unknown, ...C]>
    : never;

type A = ToNumber<Three>
//   ^? 
//   3 

And a function that given a number creates a peano number:

type ToPeano<N extends number, Acc extends Peano = Zero, C extends unknown[] = []> = 
  C['length'] extends N 
    ? Acc 
    : ToPeano<N, Succ<Acc>, [unknown, ...C]>;

type A = ToNumber<ToPeano<3>>
//   ^?
//   3

here we use good ol’ tail recursion to build the result in Acc and then return it. to halt recursion we keep building C a tuple and we stop when its size is N, all that’s left to do is to build Succ<Acc> on every step

This representation is not very efficient since it relies on recursion, but it’s very easy to use.

Alright, the hardest part is done, we now have a way to represent numbers and type-level functions to translate between numbers and peano numbers

Adding two peano numbers

Time to write addition, the idea is simple, we keep moving ones from A to B and when A reaches 0 we return B

export type Add<A extends Peano, B extends Peano> = 
  A extends Zero ? B            // base-case A is zero we return B
  : A extends Succ<infer PrevA> // let's decompose A to get its predecessor
    ? Add<PrevA, Succ<B>>       // recursion step we remove 1 from A and add it to B
    : never;                    // unreachable

type A = ToNumber<Add<ToPeano<1>, ToPeano<2>>>
//   ^?
//   3

Multiplication and Subtraction is left as an exercise to the reader.

Checking Parity

The idea is simple, a natural number is even if it is divisible by 2, and it’s divisible by 2 if you can keep subtracting by two until you reach zero, if instead you reach one then the number is odd.

type IsOdd<N extends Peano> = 
  N extends Zero ? false
  : N extends Succ<infer P1> // subtract once to get P1
    ? P1 extends Zero  // here we find out that N is One (because it's pred is Zero)
      ? true           // and therefore the number is odd
      : P1 extends Succ<infer P2> // subtract again
        ? IsOdd<P2>               // and recurse
        : never 
    : never;

type A = IsOdd<ToPeano<1>>
//   ^?
//   true
type B = IsOdd<ToPeano<2>>
//   ^?
//   false

Awesome! Now that we have all the building blocks we just need to compose them

Glueing it all together

type Input = [ 3, 2, 4, 6, 5, 7, 8, 0, 1 ]
type PeanoInput = MapToPeano<Input>
type Filtered = OddInput<PeanoInput>

// map a peano to zero if even
type KeepOdd<N extends Peano> = IsOdd<N> extends true ? N : Zero;

// map numbers to peano
type MapToPeano<T extends number[]> = T extends [infer H extends number, ...infer Rest extends number[]]
  ? [ToPeano<H>, ...MapToPeano<Rest>]
  : [];

// map KeepOdd over the list
type OddInput<T extends Peano[]> = T extends [infer H extends Peano, ...infer Rest extends Peano[]]
  ? [KeepOdd<H>, ...OddInput<Rest>]
  : [];

// sum all peano numbers
type Sum<T extends Peano[], Acc extends Peano = Zero> = 
  T extends [infer H extends Peano, ...infer Rest extends Peano[]] 
  ? Sum<Rest, Add<H, Acc>>
  : Acc;

type Result = ToNumber<Sum<Filtered>>
//   ^?
//   16

We’ve done it!

Testing with larger inputs

Let’s give it a shot with the following input:

3
6
9
12
15
18
21
24
27
30
33
36
39
42
45
48
51
54
57
60
63
66
69
72
75
78
81
84
87
90
93
96
99
1
4
7
10
13
16
19
22
25
28
31
34
37
40
43
46
49
52
55
58
61
64
67
70
73
76
79
82
85
88
91
94
97
100
2
5
8
11
14
17
20
23
26
29
32
35
38
41
44
47
50
53
56
59
62
65
68
71
74
77
80
83
86
89
92
95
98

// ...

type Result = ToNumber<Sum<Filtered>>
//   ^?
//   ERROR: Type instantiation is excessively deep and possibly infinite. [2589]

Ooof. So close…

The reality is that the typescript’s typechecker has that really cool property that all compilers should have that termination is guaranteed. So to maintain that it has some hard-coded limits on recursive jumps.

Now we can either try to find a less expensive way to represent numbers and addition… Which is possible though it would only takes use so far. Or… We could just hack the compiler and rip the constraints out entirely. Yeah of course that’s what we’re going to do, it’s way gnarlier.

Hacking the TypeScript compiler

Alright, time to get the hands dirty.

I cloned the compiler and patched it with two new cli flags.

• --noRecursionLimits - removes all recursion/instantiation depth checks
• --printType <name> - looks for a type <name> = ... in the provided files, and prints its type

Somewhat surprisingly the typescript compiler codebase was in a good shape (at least the parts the parts I read). With the help of claude to guide me through the codebase the changes were trivial to make.

You can find the compiler fork here (UnboundedTypeScript), and the specific commit here.

With that out of the way let’s run it!

➜ time ./bin/tsc  --noEmit --noRecursionLimits --printType Result ./problems/hacker-rank/sum-of-odd-elements/peano_numbers.ts
2500
./bin/tsc --noEmit --noRecursionLimits --printType Result   2.35s user 0.37s system 250% cpu 1.087 total

Awesome, we did it!

2.35s is an insane amount of time for such a simple problem, but oh well, we’re in it for the cursedness of it, not the performance.

➜ time ./bin/tsc  --noEmit --noRecursionLimits --printType Result ./problems/hacker-rank/sum-of-odd-elements/string_numbers.ts 
"2500"
./bin/tsc --noEmit --noRecursionLimits --printType Result   0.57s user 0.04s system 216% cpu 0.285 total

Try it yourself

I pushed the code to the TypescriptCompetitiveProgramming repo you can clone it and follow the README instructions to get started with your own playground. An updated version of the code we just wrote can be found here.

Conclusion

And there you have it. We successfully bypassed the TypeScript compiler’s safety rails just to sum a list of odd numbers in 2.3 seconds. If this wasn’t a good time I don’t know what is.

Genuinely this was a lot of fun, so much fun that I’m thinking of turning this into a series of blog posts. Maybe next time we’ll tackle something even more unhinged. I’m thinking either a Turing Machine or a graph traversal entirely at compile-time.