typescript - 条件类型的尾递归消除不起作用

Question

在 TS 4.5 尾调用优化 was added对于递归泛型。以下代码段计算 F₁₂ 以内的斐波那契数(一元)，但对于 F₁₃，它会失败并出现通常的“类型实例化过深且可能无限”异常。选择斐波那契函数的这个实现是因为它在非尾调用位置使用了两个自身调用，并且对于演示目的很重要。

此处唯一的递归函数是Run，其余函数(和基于interface 的函数引用)不应显着修改当前堆栈深度。为什么 TCO 不起作用，如何让它再次起作用？

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.

当 TCO 起作用时会发生什么？

等效的 JavaScript(故意丑陋地证明它)代码计算更大的斐波那契数(大于 F₃₅)，禁止将尾递归转换为显式循环，并使用二进制数而不是一元数。这里唯一的限制是堆的大小，因为整个计算都是蹦床式的(阅读 here 了解这种确切的方法，here 是对这个概念更便于读者理解的解释)。

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

看来我应该读得更好，因为in PR Anders 明确指出它仍然是有限的:

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.

这将意味着我们运气不好，如果我在 C++ 时代没有学到技巧，那么任意复杂度的图灵完备计算是不可能的。

让我们陈述一下问题:我们对某个函数进行多次迭代，直到它“完成”。让我们使用一些更简单的函数:将 1 连接到字符串的函数。

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

我们可以这样迭代两次:

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

像这样的每次下一次迭代都会将迭代次数乘以二:

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

我们通过添加一个额外的参数来抽象加倍的迭代次数:(一元)加倍次数。

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

这允许我们对 Test0 进行 2⁹⁹⁹ 次迭代与 TestN<'', 'one 999 times'> .之后我们将达到实例化限制。当然，我们通常不会对每个函数都使用所有 2^N 迭代，因此为了尽早退出，我们返回一些“完成”值。

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

让我们谈谈性能。如果我们调用TestN来自 TestN K 次而不是 2 次，我们最多得到 Test0 的 K⁹⁹⁹ 次迭代, 但即使是 K = 2它将能够迭代直到宇宙热寂。

当函数将退出时，它会在每个级别(O(K))最多通过一次“passthrough”路由，最多乘以迭代深度O(L) .为了减少无关的计算，分支级别应该是最小的(选择 2 是好的)，以及深度也就是加倍计数。

通过这种方法，我立即 able to compute F₂₀，它甚至没有进行远程优化。不过，还有另一个未记录的限制(TS code、instantiateTypeWithAlias)强制执行混淆代码实践。

instantiationCount >= 5000000