Coroutine - Comparison With Subroutines

Comparison With Subroutines

"Subroutines are special cases of ... coroutines." –Donald Knuth.

When subroutines are invoked, execution begins at the start and once a subroutine exits, it is finished; an instance of a subroutine only returns once. Coroutines are similar except they can also exit by calling other coroutines, which may later return to the point of calling in the original coroutine; from the coroutine's point of view, it is not exiting at all but simply calling another coroutine. The difference between calling another coroutine by means of "yielding" to it and simply calling another routine (which then, also, would return to the original point), is that the latter is entered in the same continuous manner as the former. The relation between two coroutines which yield to each other is not that of caller-callee, but instead symmetric.

Any subroutine can be translated to a coroutine which does not call yield.

To implement a programming language with subroutines, only a single stack that can be preallocated at the start of program execution is needed. In contrast, coroutines, able to call on other coroutines as peers, are best implemented using continuations. Continuations may require allocation of additional stacks and therefore are more commonly implemented in garbage-collected high-level languages. Coroutine creation can be done cheaply by preallocating stacks or caching previously allocated stacks.

Here is a simple example of how coroutines can be useful. Suppose you have a consumer-producer relationship where one routine creates items and adds them to a queue and another removes items from the queue and uses them. For reasons of efficiency, you want to add and remove several items at once. The code might look like this:

var q := new queue coroutine produce loop while q is not full create some new items add the items to q yield to consume coroutine consume loop while q is not empty remove some items from q use the items yield to produce

The queue is then completely filled or emptied before yielding control to the other coroutine using the yield command. The further coroutines calls are starting right after the yield, in the outer coroutine loop.

Although this example is often used to introduce multithreading, two threads are not needed for this: the yield statement can be implemented by a jump directly from one routine into the other.