Proof of concept for Python Tail Call Optmization using asyncio

asynctailcall.py

import asyncio, types, inspect, sys

max_stack = 0

def stack_depth():
    count = 0
    f = sys._getframe()
    while f.f_back:
        count += 1
        f = f.f_back
    return count
    

def tailcalloptimize(func):
    depth = 0
    async def inner(*args, **kwargs):
        return func(*args, **kwargs)

    loop = asyncio.get_event_loop()
    
    def wrapper(*args, **kwargs):
        global max_stack
        nonlocal depth

        current_stack_depth = stack_depth()
        max_stack = max(max_stack, current_stack_depth)

        depth += 1
        print(depth, current_stack_depth)
        if DISABLED:
            result = func(*args, **kwargs)
            depth -= 1
            return result
        
        if depth == 1:
            result = loop.run_until_complete(inner(*args, **kwargs))
            while isinstance(result, types.CoroutineType):
                result = loop.run_until_complete(result)
            depth -= 1
            return result
        result = inner(*args, **kwargs)
        depth -= 1
        return result

    return wrapper


@tailcalloptimize
def prod(n, acc=1):
    if n > 1:
        return prod(n -1, n * acc)
    return n * acc

The snippet above includes some instrumentation to compare plain recursion with the "asyncio-based-tail-call-optimization" recursion - cpython current max recursion depth is around 3000 calls deep. With the decorator, that means we can check "prod(1500)" without raising if DISABLED is set. With the async-thing turned on, the snippet above runs 10 times slower at 1500 call depth, but can call recursively the function an arbitrary number of times (e.g. 150000 calls deep vs 3000).