[FIXED] Python skips coroutine evaluation

Issue

I've been trying to get around Python's recursion limit using coroutines, and through trial and error arrived at this code which recursively calculates Fibonacci numbers:

import asyncio
from typing import Callable, Coroutine


def recursive(f: Callable[[int], Coroutine]):
    return lambda x: asyncio.create_task(f(x))


m = [0, 1]


@recursive
async def f(x: int):
    if len(m) <= x:
        m.append(await f(x - 1) + await f(x - 2))
    return m[x]


async def main():
    print(await f(2000))


asyncio.run(main())

# prints 4224696333392304878706725602341482782579852840250681098010280137314308
# 58437013070722412359963914151108844608753890960360764019471164359602927198331
# 25987373262535558026069915859152294924539049987222567953169828744824729922639
# 01833716778060607011615497886719879858311468870876264597369086722884023654422
# 29524334796448013951534956297208765265606952980649984197744872015561280266540
# 4554171717881930324025204312082516817125

Could someone explain why this does not cause infinite recursion? As stated in the comments in the linked file, I expected Python to eagerly evaluate f(x) in the lambda, which seems like it would have lead to infinite recursion. What surprised me was that while stepping through the code using a debugger, it seems like the lambda just skipped evaluating f(x) entirely and was somehow immediately able to pass a coroutine to asyncio.create_task. (*)

I should add, this is on Python 3.10.10.

Edit: to clarify (*)

Suppose we had this instead of the lambda:

def my_create_task(c):
    return asyncio.create_task(c)

def recursive(f):

    def callf(x):
        return my_create_task(f(x))

    return callf

What'll happen as I keep pressing "step into" is

1. Enter callf
2. Enter my_create_task, with c bound to a coroutine - I expected the debugger to enter f here
3. Return from my_create_task
4. Return from callf
5. Enter f with x=2000

Solution

yes.

This is actually the way co-routine functions (functions defined with async def) work in Python:

WHen they are called, the code inside their body is not evaluated. Not even the first line inside it. What the runtime does when calling such a "coroutine function" is to create a "coroutine": this is internally like a generator - it has an internal state, ready to run, with all the needed data: passed in parameters, constants, current lime number, etc - these are kept in a Python Frame object.

Only when this co-routine is delegated to the asyncio loop - which can happen either through the await keyword, or by wrapping it in a Future or a Task (and then passing control to the loop), will the code inside the co-routine actually be executed.

And here is why it can bypass the recursion limit: each time an ordinary function call is effected, Python creates a new Frame object, and stack that on top of the Frame for the current running context: there is a Frame stack, and that stack is what is limited in the recursion limit - (it used to be 1000 by default - no sure if it default has been raised).

By using co-routines, the code to be executed is tracked in Frame objects, the same way, but instead of being linked in a stack, these are used in another data structure inside the asyncio.loop (and ordinary list, or a set, does not matter). And since there is no traversal dependency on these co-routine FRames, Python can get hold of 10s of thousands of them concurrently, with no problem.

(although the default implementation has some issues - if one creates about 2500 tasks, each with its own Frame without ever delegating control to the asyncio loop, some of those might get lost along the way. It won't happen in this code because the await expressions pass the control to the asyncio loop after each pair of created tasks).

So in other words: your lambda runs, and creates a task object ready to be executed seemingly in background whenever an "await" is met. It them resolves and is cleared. All the thousands of tasks created in parallel are fine, because they are just appended to a list internally, not taking resources on the Python runtime stackframe.

in time: if you want to see with the debugger when f is actually run, just set a breakpoint in f itself: when it is called as part of the asyncio loop stepping into it, you will be able to go the "upper" context, and see the inner machinery of asyncio itself, instead of your lambda.

Answered By - jsbueno