> I mean, with "traditional" coroutines, it isn't the "language's runtime" which calls back into my code: it is whatever code completed the event. I get that the important part of this sentence is the interest in "push" vs. "poll", but this concept of the existence of a "language's runtime" is a bit strange to me, as my mental model of a coroutine doesn't involve a "runtime" and certainly doesn't involve an "executor".

Syntactically, many languages represent the operation of calling into the next continuation as a regular return (for green threads) or a regular function call (call/cc), but there's always some degree of runtime magic involved in the generated code. For instance, rather than just incrementing or decrementing the stack pointer, you've got to potentially set it to point into a totally different runtime-allocated stack. In principle, that can probably be implemented as just special-case code generation rather than an actual call into the runtime's routines, but that still leaves the need to clean up the current task's stack after it returns (or does a tail call into another stack), which will be either an explicit runtime call or rely on the runtime's garbage collector.

The real magic, though, isn't so much in the user-written continuations as it is on "async blocking" calls for things like I/O.

> In a more complex scenario, the function A is going to do something mysterious and later get a callback from something -- which you might call a "runtime" but which almost certainly isn't implemented by the "language" -- on some random background thread running an I/O loop, or maybe due to a signal / handler from the operating system, or whatever random mechanism it has in place to run code later (which again: isn't part of the "language") and it will run the continuation it was passed.

This is precisely what Rust's async runtime libraries are. They provide the event loop/callback mechanisms, which are necessary for truly async code. (Otherwise, what is there to wait for?) You can totally write and call an async function in Rust that doesn't use a runtime, but there's no way for it to "asynchronously block"; you'd just poll it and get back, "Yep, I'm done; here's my result."

> This does, likely, result in some heap allocation somewhere in order to type erase the continuation in the general case. However, this seems to only be due to how the asynchronous code has been given a harder challenge of dealing with arbitrarily deep stacks with minimal overhead, while people seem totally OK with synchronous code causing random stack overflows :/. If you are willing to relax that assumption a bit then you can elide that allocation almost every time.

It's not just the depth of the stack; it's that, once you yield, another task may take over the thread's flow control entirely. Let's say that function A spawns a coroutine B without waiting for it to finish. Now let's imagine that B allocates space on the same thread stack that A was using (on top of A's stack frame) and then yields. At the yield point, something (e.g. the runtime) has to say, "OK, B is stuck, so what do we run next on the thread?" Eventually, it's A's turn to finish running, and it returns. If it does this naïvely, it'll rewind the stack pointer, dropping the stack frames for both A and B. But B isn't done running yet; it's just blocked, so now we've got a problem because its stack just got clobbered. To avoid this, languages that use "stackful" coroutines have to allocate coroutines' stacks on the heap in many cases because the traditional single-stack model isn't just running out of space; it totally breaks down.

Rust uses stackless coroutines, which impose some restrictions on how the coroutine is structured (mostly involving unbounded recursion) so that the state the task has to store between yield points has a fixed size.