Coroutines

Suppose we find ourselves frequently iterating over a two-dimensional grid, like this:

for (let y = 0; y < height; ++y) {
  for (let x = 0; x < width; ++x) {
    // process x and y
  }
}

Writing these loops a just few times is not much of a burden, but as we add more of them, the noise of their headers starts to drown out the processing. Many languages provide an abstraction that can help: an iterator. Iterators abstract away the initializing, comparing, and incrementing logic of iteration so we can focus on the task to be performed on each iteration.

This code accomplishes the same task as the code above with a single for-each loop that uses an iterator:

for (let [x, y] of GridIterator(width, height)) {
  // process x and y
}

Iterators are nice, but have you ever written one for data more complex than a linked list or an array? When your data structure branches, spans multiple dimensions, or is sparsely distributed across the iteration space, the iterator becomes hard to reason about. Consider this possible implementation of GridIterator:

class GridIterator {
  constructor(width, height) {
    this.width = width;
    this.height = height;
    this.x = 0;
    this.y = 0;
  }

  // The iterator is exhausted once it hits an
  // out-of-bounds row. If it hits an out-of-bounds
  // column, it only wraps to the next row.
  hasNext() {
    return this.y < this.height; 
  }

  // Grab the next 2D point, nudging the cursor forward.
  next() {
    if (this.hasNext()) {
      const point = [this.x, this.y];
      this.nudge();
      return point;
    } else {
      throw Error('no such element');
    }
  }

  // Nudge the cursor forward. Wrap to the next row upon
  // reaching the final column.
  nudge() {
    this.x += 1;
    if (this.x >= this.width) {
      this.x = 0;
      this.y += 1;
    }
  }
}

This code is too complex for the problem that it solves. Iterating over a grid shouldn't be so much work. It's complex because the iterator is not in control of its execution. Some entity on the outside is calling hasNext and next at its whimsy, and the iterator must maintain state so that it can remember where the traversal left off.

The messiness of iterators is solved with coroutines. A coroutine is a companion flow that cooperates with a main flow or other coroutines, but it maintains its own identity and controls its execution from start to finish, unlike the GridIterator. It doesn't run in parallel with other flows. Rather the current flow reaches a point where it needs a companion to do some work. The current flow pauses and the companion starts executing. The companion does its work and then yields its value back to the caller.

Coroutines do not speed up code. Their job is not to parallelize code but to organize it. They separate one logical flow from another. We've been using another tool for separating logical flows for a while now: subprograms. What makes a subprogram different from a coroutine is that a subprogram is expected to fully finish its work and then return control back to its caller. Coroutines run in tandem with their companion flows and can be paused and resumed.

JavaScript provides generators, which are a restricted form of coroutines, that simplify iterators. A generator looks like a function definition, but it's got a * symbol in front of the function name in the header, and it contains one or more yield statements. Here's the equivalent to GridIterator:

function *iterator2(width, height) {
  for (let y = 0; y < height; y += 1) {
    for (let x = 0; x < width; x += 1) {
      yield [x, y];
    }
  }
}

The body of iterator2 is just like the normal nested loops that traverse a grid; it's not like the inverted mess of GridIterator. The yield statement pauses the generator and hands control back to this code that consumes its values:

for (let [x, y] of iterator2(width, height)) {
  console.log(x, y);
}

Each iteration of the for-of loop unpauses the paused generator, which continues where the nested loops left off. Then the generator pauses again when it hits the next yield.

Generators are just a special case of coroutines. A full coroutine implementation allows an arbitrary number of flows to cooperate, not just the caller and generator, and a flow that calls on a coroutine may pass in parameters.

Someday Rust will officially have generators. They've been available unofficially, in experimental versions of the language, since 2017.