Different ways of implementing a coroutine

Question

I can currently think of two ways of implementing a coroutine:

1. Whenever a coroutine is started, instead of storing local variables on stack, get a piece of memory from heap and use it to store local variables. This way, local variables are not destroyed, and any called function can return to this function later in time. But in this case, any called function which is not a coroutine has to run on main call stack. I don't know if this could cause any problem. Can someone confirm it!
2. Whenever a coroutine is started, allocate a bigger amount of memory than required to that coroutine. This would act like some kind of custom call stack for that coroutine. In this case, all the sub-functions called by this would be stored together with this coroutine. But this implementation may require too much of redundant memory.

I think these two are popularly known as stackless and stackful coroutines.

What are other theoretically possible ways of implementing a coroutine? What are advantages and disadvantages of them? Which languages use which implementations?

Answer 1

Your option (1) is indeed a stackless coroutine, and this is how it's implemented in Kotlin, and usually Javascript (async/await), for example. This is how you do it when you don't necessarily have the low-level control of the call stack that other methods require. Languages that use this strategy require suspendable functions to be marked in some way. That's called the "red/blue function problem". See: https://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/

Languages that do have low-level control of the call stack can implement coroutines in various ways, but none of them look like your option (2). They generally involve copying data into and out of the call stack when required (like Java project Loom) or using a completely different data structure in place of the call stack (like early Go implementations). In these languages, coroutine-callable functions don't usually need special markings.