Coroutines

The following generator yields the powers of 2, starting from \(2^{0}\). It's an infinite stream, so when we iterate over it, we have to be careful to only look at a finite prefix.

Rewriting this program to remove some syntactic sugar exposes the call to next that was hidden inside the for loop.

def powers_of_2():
  x = 1
  while True:
    yield x
    x *= 2

gen = powers_of_2()
for i in range(5):
  n = next(gen)
  print(f'2 ** {i} == {n}')

We create the generator with the call powers_of_2(). This does not start the generator, it just creates the generator object. When we call next for the first time inside the loop, control transfers to the body of the generator, and it runs until it encounters a yield. When a yield is encountered, control transfers back to the call to next, and next returns whatever value was yielded.

The next time next is called, the generator resumes execution at the place where it last yielded. The value of local variables is preserved, so it continues to execute the while loop, updating x, until the next yield.

Generators are a limited kind of coroutine that only exercise the ability to yield with a value and then resume later.

Coroutines (in the form of generators) are a natural tool for iterating over data structures, streams, and sequences, but they have many other uses as well. In this section, we'll look at how to use coroutines to solve a backtracking search problem. Specifically, string matching.

Given a pattern like the following ("abc"|"de")."x", we want to determine whether a string matches the pattern. Patterns are constructed using:

1. String literals, written with double quotes. "i am a string literal" is a valid literal.
2. Alternations, written with the | operator. An alternation \(p ~|~ p'\) matches if either \(p\) or \(p'\) matches.
3. Sequences, written with the . operator. A sequence \(p . p'\) matches a string \(s\) if there exist substrings \(s_1\) and \(s_2\) such that \(s = s_1s_2\) and \(p\) matches \(s_1\) and \(p'\) matches \(s_2\).

We should read the pattern ("abc"|"de")."x" as: "abc" or "de" followed by "x". This pattern matches the following strings: "abcx" and "dex".

First we'll write out a syntax for patterns:

from dataclasses import dataclass

@dataclass
class Pattern():
  pass

@dataclass
class Lit(Pattern):
  s : str

@dataclass
class Alt(Pattern):
  lhs : Pattern
  rhs : Pattern

@dataclass
class Seq(Pattern):
  lhs : Pattern
  rhs : Pattern

It would be nice to write our pattern matching function in the way that we have written our big-step interpreters: as a single recursive pass over the pattern. However, the combination of alternation and sequencing operators means that we may need to explore multiple ways for sub-patterns to match.

We're going to use a pattern that is common in search algorithm implementations: representing failure by a list of successes ¹. This pattern allows us to avoid explicit backtracking, and it can be expressed clearly and simply using coroutines.

The key idea is to write a matching function that:

• For each pattern constructor:
  • Takes in a string s and a position start_pos in s.
  • For a given start_pos, searches for and yields an end_pos for each possible match of the pattern.

This function can be written as follows:

def matches(pattern, string, start_pos):
  match pattern:
    case Lit(literal):
      if string[start_pos:].startswith(literal):
	yield (start_pos + len(literal))

    case Alt(lhs, rhs):
      yield from matches(lhs, string, start_pos)
      yield from matches(rhs, string, start_pos)

    case Seq(lhs, rhs):
      for middle_pos in matches(lhs, string, start_pos):
	yield from matches(rhs, string, middle_pos)

yield from call() is Python's way of allowing coroutines to call other coroutines and to yield from inside one of these child coroutines. Generators only yield from inside the body of the generator function. In this code, we are yielding from a nested coroutine call, saving the entire call stack, and resuming it later.

If we run the pattern matching function, we can see that for a pattern, string, and start position, it yields a sequence of end positions for the places where the pattern matches.

Finally, we'll implement concurrency on top of coroutines. Concurrency is about executing parts of a program out of order or interleaved with each other. For example, when one is waiting for a network request, another part continues executing. Concurrent programs have some amount of order-independence—they contain individual computations that can be performed in any order.

Concurrency is distinct from, and more general than, parallelism. Parallelism is about running multiple parts of a program at the same time. Concurrent tasks may be executed in parallel, but they do not need to be. Concurrency is valuable even in single-threaded programs, because it allows the program to continue doing useful work while it is waiting for an IO request to complete. We should think of parallelism as an implementation strategy for concurrent programs.

A key design choice in a concurrent system is: when should we switch from one task to another? In cooperative concurrency, tasks decide when it is safe to switch. This is often implemented as a special yield function that yields control to the task scheduler. Cooperative concurrency gives the programmer control over when tasks may be switched out, but it means that the programmer is responsible for ensuring that all of the tasks yield frequently enough to avoid starving other tasks. In preemptive concurrency, tasks are periodically interrupted by the runtime. We will look at a cooperative concurrency implementation in this section.

Coroutines give us exactly what we need to implement concurrency:

• Ability to to yield control from inside a task.
• Ability to send values back into the task when it is restarted.

We represent concurrent tasks as coroutines. A task yields when it needs to wait for something to happen—for example, when it wants to make a network request, or sleep for some length of time. Tasks yield an object that represents the operation that they want the scheduler to perform. For IO, a task might yield a Read("file.txt", 16) object that represents a request to read 16 bytes from "file.txt". Or it might yield Sleep(10) to sleep for 10 seconds. The scheduler is responsible for multiplexing requests from multiple tasks and determining which tasks are ready to run, and which still need to wait. When the request is complete, the scheduler "wakes" the task by calling send(), which returns a response (the result of the read, or similar) and runs the task to its next yield point. The key idea is that while a task is waiting, we can continue with running other tasks.

Here's an example of a concurrent scheduling function:

from dataclasses import dataclass

@dataclass
class Sleep():
  n : int

def sleep(n):
  msg = yield Sleep(n)
  return msg

def run(tasks, max_iters=15):
  running = [(t, None) for t in tasks]
  sleeping = []
  for _ in range(max_iters):
    for (t, v) in running:
      match t.send(v):
	case Sleep(n):
	  sleeping.append((t, n))
	case _:
	  pass

    running = [(t, 'done sleeping!') for (t, n) in sleeping if n <= 1]
    sleeping = [(t, n - 1) for (t, n) in sleeping if n > 1]

run takes a list of tasks (coroutines). It runs each task up to its next yield by calling send() on it, sending the result of the last "system call" that the task made.

Note that the first time we call send, we send None. This is expected behavior. When we create a coroutine in Python, it starts in a "created" state. The first call to send or next will advance it to its first yield point.

run examines the result of t.send(v), which will be the value yielded by the task. If it's a request to sleep, run will put the task on a sleeping queue along with the number of ticks that it should sleep for.

Next, run moves any tasks that have finished sleeping from the sleeping queue to the running queue, and updates the sleep times for the sleeping tasks.

(run only executes the scheduling loop max_iters times, so it'll always terminate in our examples.)

The following creates and runs four tasks. Three of the tasks sleep for different amounts of time. The final task performs some work and immediately exits.

We can see that the tasks that sleep longer produce output less frequently than the tasks that sleep less.

Both continuations and coroutines give programmers a way to capture the "control context" around a computation and resume that control context later. Coroutines are much more common than continuations; many modern languages provide full-featured coroutine implementations. It's worth asking whether we need to discuss continuations at all. Is there anything that we can do with continuations that we cannot do with coroutines? It turns out that coroutines can express one-shot continuations, but not multi-shot continuations.

A continuation is one-shot if it is invoked at most once; otherwise, it is multi-shot. It's been noted in the literature that most of the applications of continuations only need the one-shot variety, and one-shot continuations are easier to implement efficiently (because they do not require copying the stack). Coroutines are similarly one-shot because we cannot clone them; there's no way to fork a coroutine.

Despite being somewhat less expressive than continuations, coroutines are generally considered easier to understand. Good language designs often trade off expressive power for ease of understanding; this might explain why coroutines are widespread and continuations are not.

Download the code for string matching and concurrency.

• The goal-oriented programming example and the discussion of the relationship with continuations come from "Revisiting Coroutines", De Moura & Ierusalimschy 2009.
• The concurrency example draws from David Beazley's coroutines tutorial.