Tail recursion elimination on conditional types doesn't work

Question

In TS 4.5 tail call optimization was added for recursive generics. The following snippet computes Fibonacci numbers (in unary) up to F₁₂, but for F₁₃ it fails with the usual "Type instantiation is excessively deep and possibly infinite" exception. This implementation of the Fibonacci function was chosen because it uses two calls of itself in non-tail-call positions, and is important for demonstration purposes.

The only recursive function here is Run, the rest of functions (and interface-based function references) should not significantly modify current stack depth. Why TCO didn't work, and how to make it work again?

type Done<A> = { type: 'done', value: A };
type More<F, X> = { type: 'more', value: X, fn: F };
type FlatMap1<X, F> = { type: 'flatMap', value: X, fn: F }

interface FlatMap2<G, F> { a: unknown; r: FlatMap<Call<G, this['a']>, F> }
type FlatMap<X, F> = X extends FlatMap1<infer X, infer G> ? FlatMap1<X, FlatMap2<G, F>> : FlatMap1<X, F>

type Run<T> =
    T extends Done<infer V> ? V :
    Run<
        T extends More<infer F, infer X> ? Call<F, X> :
        T extends FlatMap1<infer X, infer F> ?
            X extends Done<infer V> ? Call<F, V> :
            X extends More<infer G, infer V> ? FlatMap<Call<G, V>, F> :
            X extends FlatMap1<infer V, infer G> ? FlatMap<V, FlatMap2<G, F>> :
            never :
        never
    >

interface Fib2<X> { a: unknown; r: Done<Add<X, this['a']>> }
interface Fib1<N> { a: unknown; r: FlatMap<More<FibR, Sub<N, '11'>>, Fib2<this['a']>> }
interface FibR { a: unknown; r: Fib<this['a']> }
type Fib<N> =
    N extends ('' | '1') ? Done<N> :
    FlatMap<
        More<FibR, Sub<N, '1'>>,
        Fib1<N>
    >

type R1 = Run<Fib<'1111111111111'>>

// utils

interface Fn { a: unknown; r: unknown }
type Call<F, X> = F extends Fn ? (F & {a: X})['r'] : never;

type Add<A, B> = A extends string ? B extends string ? `${A}${B}` : never : never
type Sub<A, B> = B extends string ? A extends `${B}${infer D}` ? D : never : never

Playground.

What happens when TCO works?

Equivalent JavaScript (and intentionally ugly to prove it) code computes much bigger Fibonacci numbers (bigger than F₃₅), barring conversion of tail recursion to explicit loop, and using binary numbers instead of unary. The only limit here is size of the heap, because the whole computation was trampolined (read here about this exact approach, and here is more reader-friendly explanation of the concept).

const done = a => ({type: 'done', value: a});
const more = (f, x) => ({type: 'more', value: x, fn: f});
const flatMap1 = (x, f) => ({type: 'flatMap', value: x, fn: f});

const flatMap2 = (g, f) => y => flatMap(g(y), f);
const flatMap = (x, f) => x.type === 'flatMap' ? flatMap1(x.value, flatMap2(x.fn, f)) : flatMap1(x, f);;

const run = tt => {
    for (let t = tt;;) {
        if (t.type === 'done') { return t.value; } else
        t = (() => {
            if (t.type === 'more') { return t.fn(t.value); } else
            if (t.type === 'flatMap') { const x = t.value, f = t.fn;
                if (x.type === 'done') return f(x.value);
                else if (x.type === 'more') return flatMap(x.fn(x.value), f); 
                else if (x.type === 'flatMap') return flatMap(x.value, flatMap2(x.fn, f));
                else throw new Error();
            }
            else throw new Error();
        })();
    }
};

const fib2 = x => y => done(x + y)
const fib1 = n => x => flatMap(more(fib, n - 2), fib2(x));
const fib = n => n < 2
    ? done(n)
    : flatMap(
        more(fib, n - 1),
        fib1(n),
    );

console.log(run(fib(30)));

Playground.

Answer 1

So it seems I should have been reading better, because in PR Anders clearly states that it's still limited:

the compiler now performs type resolution in a loop that consumes no extra call stack. We permit evaluation of such types to loop 1000 times before we consider the type non-terminating and issue an error.

This would mean we're out of fortune, and Turing-complete computations of arbitrary complexity are impossible, if I didn't learn a trick back in C++ days.

Let's state the problem: we're iterating a certain function numerous times until it "completes". Let's use some simpler function: the one that concatenates a 1 to a string.

type Test0<X> = X extends string ? `${X}1` : never

We can iterate it twice in this way:

type Test1<X> = Test0<Test0<X>>
// Test1<''> = '11'

Each next iteration like this will multiply number of iterations by two:

type Test2<X> = Test1<Test1<X>>
// Test2<''> = '1111'

We abstract over the number of iterations of doubling by adding an extra argument: (unary) number of doublings.

type TestN<X, L extends string> = L extends `1${infer L}` ? TestN<TestN<X, L>, L> : Test0<X>
// TestN<'', '1111111111111111'> = '<one 65536 times>'

This allows us 2⁹⁹⁹ iterations of Test0 with TestN<'', 'one 999 times'>. After that we'll hit instantiation limit. Of course, we don't usually use all the 2^N iterations for every function, so in order to exit early we return some "done" value.

type Ten = '111111111'
type Test0<X> =
    // exit condition
    X extends Ten ? {done: X} :
    // body
    X extends string ? `${X}1` : never

type TestN<X, L extends string> =
    L extends `1${infer L}`
        // const m = testN(x, l);
        ? TestN<X, L> extends infer M
            // if done, exit early, otherwise continue
            ? M extends {done: any} ? M : TestN<M, L>
            : never
        : Test0<X>
// this is very fast compared to possible 2^32 iterations
TestN<'', '11111111111111111111111111111111'>["done"] = Ten

Let's talk about performance. If we called TestN from TestN K times instead of 2, we'd get at most K⁹⁹⁹ iterations of Test0, but even for K = 2 it will be able to iterate until the heat death of the universe.

When the function will be exiting, it will go through "passthrough" route at most once per level (O(K)), multiplied by at most the iteration depth O(L). In order to reduce extraneous computations, branching level should be the smallest (choice of 2 was good), as well as depth aka doubling count.

With this approach I was immediately able to compute F₂₀, and it's not even remotely optimized. There is another undocumented limit though (TS code, instantiateTypeWithAlias) that enforces obfuscated code practices.

instantiationCount >= 5000000