python - トランポリンされたcpsバージョンのfib関数を高速化し、Pythonで相互再帰をサポートするには?

Question

フィボナッチ関数の cps バージョンにトランポリンを実装しようとしました。しかし、高速化 (キャッシュを追加) して相互再帰をサポートすることはできません。

実装コード:

import functools
from dataclasses import dataclass
from typing import Optional, Any, Callable

START = 0
CONTINUE = 1
CONTINUE_END = 2
RETURN = 3


@dataclass
class CTX:
    kind: int
    result: Any    # TODO ......
    f: Callable
    args: Optional[list]
    kwargs: Optional[dict]


def trampoline(f):
    ctx = CTX(START, None, None, None, None)

    @functools.wraps(f)
    def decorator(*args, **kwargs):
        nonlocal ctx
        if ctx.kind in (CONTINUE, CONTINUE_END):
            ctx.args = args
            ctx.kwargs = kwargs
            ctx.kind = CONTINUE
            return
        elif ctx.kind == START:
            ctx.args = args
            ctx.kwargs = kwargs
            ctx.kind = CONTINUE

        result = None
        while ctx.kind != RETURN:
            args = ctx.args
            kwargs = ctx.kwargs
            result = f(*args, **kwargs)
            if ctx.kind == CONTINUE_END:
                ctx.kind = RETURN
            else:
                ctx.kind = CONTINUE_END

        return result

    return decorator

これが実行可能な例です。

@functools.lru_cache
def fib(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

@trampoline
def fib_cps(n, k):
    if n == 0:
        return k(1)
    elif n == 1:
        return k(1)
    else:
        return fib_cps(n - 1, lambda v1: fib_cps(n - 2, lambda v2: k(v1 + v2)))

def fib_cps_wrapper(n):
    return fib_cps(n, lambda i:i)


@trampoline
def fib_tail(n, acc1=1, acc2=1):
    if n < 2:
        return acc1
    else:
        return fib_tail(n - 1, acc1 + acc2, acc1)


if __name__ == "__main__":
    print(fib(100))
    print(fib_tail(10000))
    print(fib_cps_wrapper(40))

数を実行するには遅すぎます40。が大きい場合、取得fibした最大再帰深度を超えました。nしかし、追加後lru_cacheは高速になります。iter トランポリン バージョンは、再帰の深さに問題がなく、非常に高速に実行されます。

他の人の作品は次のとおりです。

1. サポート cps バージョン キャッシュ: https://davywybiral.blogspot.com/2008/11/trampolining-for-recursion.html
2. 相互再帰のサポート: https://github.com/0x65/trampolineしかし、理解するにはハックすぎます。