Eliminating tail recursion for conditional types is ineffective

Question

Eliminating tail recursion for conditional types is ineffective

In TypeScript version 4.5, the feature of tail call optimization was introduced for recursive generics. The code snippet below calculates Fibonacci numbers (in unary) up to F₁₂, but encounters an error when trying to compute F₁₃ due to the "Type instantiation is excessively deep and possibly infinite" exception. This specific implementation of the Fibonacci function intentionally involves two non-tail-call positions for self-calling, serving as a demonstration.

The sole recursive function in this example is Run; the other functions (and references based on the interface) should not significantly impact the stack depth. What prevented TCO from working here, and how can it be resolved?

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 }

// Interfaces and types omitted for brevity...

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

// Additional utilities also included in the original snippet...

Playground.

What happens when TCO works?

An equivalent JavaScript code snippet, purposely made complex, is capable of calculating even larger Fibonacci numbers (exceeding F₃₅). However, this approach requires converting tail recursion into manual loop iteration and implementing binary number usage instead of unary. The primary limitation lies within the heap size, as the entire computation process has been trampolined. To learn more about this technique, refer to the articles linked above.

// JavaScript code for enhanced Fibonacci calculation provided in the original snippet...

Playground.

typescript types functional-programming continuation-passing trampolines

Answer 1

Answer №1

Upon further investigation, I realize the importance of attentive reading. In a PR submitted by Anders, it is explicitly mentioned that there are still limitations:

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 realization leads me to believe that our luck may not be on our side, making computations involving arbitrary complexity seemingly impossible. However, my past experiences with C++ have equipped me with a valuable trick.

Laying out the problem: we are iterating a particular function multiple times until it "completes". Let's simplify this concept using a function that appends a '1' to a string.

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

We can perform two iterations as follows:

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

Subsequent iterations will exponentially increase the number of iterations:

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

We introduce an additional parameter to abstract over the doubling iterations: (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>'

By employing this technique, we can achieve 2⁹⁹⁹ iterations of Test0 with TestN<'', 'one 999 times'>. This should allow us to reach our desired output before hitting any instantiation limits. Despite the potential for so many iterations, not all will be utilized for every function. To ensure early termination, we designate a "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

Addressing performance concerns, increasing the recursive calls from 2 to K results in at most K⁹⁹⁹ iterations of Test0. Even for small values like K = 2, the function can iteratively compute without constraints.

During the exit phase, the function takes the "passthrough" route at most once per level (

O(K)</code), multiplied by the iteration depth <code>O(L)

. To minimize unnecessary computations, the branching level and depth should be optimized. Choosing a value of 2 provides a good balance.

With this strategy, I was pleasantly surprised to find that I could intricately calculate F₂₀, without having focused on optimization techniques. However, there is another undisclosed limitation (TS code, instantiateTypeWithAlias) that encourages obscure coding practices.

instantiationCount >= 5000000

Answer 2

Upon further investigation, I realize the importance of attentive reading. In a PR submitted by Anders, it is explicitly mentioned that there are still limitations:

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 realization leads me to believe that our luck may not be on our side, making computations involving arbitrary complexity seemingly impossible. However, my past experiences with C++ have equipped me with a valuable trick.

Laying out the problem: we are iterating a particular function multiple times until it "completes". Let's simplify this concept using a function that appends a '1' to a string.

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

We can perform two iterations as follows:

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

Subsequent iterations will exponentially increase the number of iterations:

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

We introduce an additional parameter to abstract over the doubling iterations: (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>'

By employing this technique, we can achieve 2⁹⁹⁹ iterations of Test0 with TestN<'', 'one 999 times'>. This should allow us to reach our desired output before hitting any instantiation limits. Despite the potential for so many iterations, not all will be utilized for every function. To ensure early termination, we designate a "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

Addressing performance concerns, increasing the recursive calls from 2 to K results in at most K⁹⁹⁹ iterations of Test0. Even for small values like K = 2, the function can iteratively compute without constraints.

During the exit phase, the function takes the "passthrough" route at most once per level (

O(K)</code), multiplied by the iteration depth <code>O(L)

. To minimize unnecessary computations, the branching level and depth should be optimized. Choosing a value of 2 provides a good balance.

With this strategy, I was pleasantly surprised to find that I could intricately calculate F₂₀, without having focused on optimization techniques. However, there is another undisclosed limitation (TS code, instantiateTypeWithAlias) that encourages obscure coding practices.

instantiationCount >= 5000000

Eliminating tail recursion for conditional types is ineffective

What happens when TCO works?

Answer №1

Similar questions

How can I incorporate the LIKE operator in a query when dealing with PostgreSQL's String array type using TypeORM?

"encountered net::ERR_NAME_NOT_RESOLVED error when trying to upload image to s3 storage

Find out if all attributes of the object are identical

How can I activate TypeScript interface IntelliSense for React projects in VSCode?

Error encountered: "The requested resource does not have the 'Access-Control-Allow-Origin' header in Angular 6 and Nodejs."

Using Angular: Binding Angular variables to HTML for display

Interactive website built on Angular 16 offering advanced search and result display functionalities, along with options to edit and update data

Using Type TTextKey to access TOption is not allowed

Transform array sequences into their own unique sequences

Best practice for importing ts files from an npm package

Utilizing React TypeScript within Visual Studio

My goal is to intentionally trigger an eslint error when importing a file from index.ts

Enhance the variety of types for an external module in TypeScript

The unknown number of arguments in a Typescript generic type

Alert: Attempting to access an undefined value in an indexed type

Having trouble getting Typescript code to function properly when using commonjs style require statements

Instead of returning an object, the underscore groupBy function now returns an array

The return type of Array.find is accurate, however, it contains an error

Tips for preventing a wrapped union type from collapsing

Could someone teach me how to implement icon rotation in Vue.js using Vuetify?