Stackless vs. Stackful Coroutines

It’s 2017 and coroutines are coming to a language near you. Javascript has generators, and is getting async/await functions, while C++ is getting coroutines as part of the N3858 proposal. However, coroutines in languages differ in that some languages support stackful coroutines, but others only support stackless coroutines.

This terminology is a little bit confusing - you might wonder how it’s possible for a coroutine to not have a stack. Javascript has stackless coroutines, but I can call a normal function inside of an async function, as follows.

function g() { return 0; };

async function f() {
  let val = g();
  await sleep_async(10);
  return val;
}

This means there must be a call stack somewhere - how else could g know to return to f? The key distinction is not whether a coroutine ever has a stack, but rather whether a coroutine needs a stack while it is suspended. If you look closely, a Javascript async function doesn’t need a stack while suspended. This is because you can only call await within the body of f itself - we can never suspend while g is running. Thus, we only need a stack while the coroutine is running. When the coroutine suspends, it can serialize it’s local variables into a fixed-size structure, then use the current call stack for executing the next coroutine.

If you look closely, when an async function awaits on other async functions, there is still an implicit stack created, as every coroutine needs to know who transfer control to when it is completed. This pointer stores the information that would otherwise be encoded in the call stack.

In contrast to stackless coroutines, languages with stackful coroutines let you suspend your coroutines at any point. The example below, written in an embedded scripting language called Wren, demonstrates yielding from inside an anonymous function. You cannot do this in Javascript - for example, you can’t yield inside of an Array.forEach call.

var fiber = Fiber.new {
  (1..10).map {|i|
    // Wren can yield from inside this block.
    Fiber.yield(i)
  }
}

Here’s another snippet from Lua, which also supports stackful coroutines. In this example, the producer code calls a send function, which then yields the value passed in.

function send (x)
  coroutine.yield(x)
end

local producer = coroutine.create(function ()
  while true do
    send(io.read())
  end
end)

In both Wren and Lua, coroutines must store an entire stack of activation records, since they can be suspended at any time.

Similar Posts