Coroutine
In computer science, coroutines are program components that generalize subroutines to allow multiple entry points and suspending and resuming of execution at certain locations. Coroutines are more generic and flexible than subroutines, but are less widely used in practice. Coroutines originated as an assembly-language technique, but are supported in some high-level languages, Simula and Modula-2, being two early examples. Coroutines are well-suited for implementing more familiar program components such as cooperative tasks, iterators, infinite lists, and pipes. Since coroutines are not as widely known as subroutines, a comparison with subroutines may be helpful.
Brief comparison and example
Coroutines are more generic than subroutines. The start of a subroutine is the only point of entry; the start of a coroutine is the first point of entry, and places within a coroutine following returns (yields) are subsequent points of entry. Subroutines can return only once; in contrast, coroutines can return (yield) several times. The lifespan of subroutines is dictated by last in, first out (the last subroutine called is the first to return); in contrast, the lifespan of coroutines is dictated entirely by their use and need.
Here's 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
Each coroutine does as much work as it can before yielding control to the other using the yield command. The yield causes control in the other coroutine to pick up where it left off, but now with the queue modified so that it can do more work. Although this example is often used to introduce multithreading, it's not necessary to have two threads to effect this dynamic: the yield statement can be implemented by a branch directly from one routine into the other.
Detailed comparison
Since coroutines can have more points of entry and exit than subroutines, it is possible to implement any subroutine as a coroutine. Indeed, as Knuth describes it, "subroutines are special cases of ... coroutines."
Each time a subroutine is called (invoked), execution starts at the beginning of the invoked subroutine. Likewise, the first time a coroutine is invoked, execution starts at the beginning of the coroutine; however, each subsequent time a coroutine is invoked, execution resumes following the place where the coroutine last returned (yielded).
Since a subroutine returns only once, returning multiple values requires returning a collection of values. While this is convenient in some languages, like Forth and Perl, other languages like C only permit a single return value so this needs a reference to a collection of values. In contrast, since a coroutine can return multiple times, returning multiple values merely requires returning additional values upon subsequent calls to the coroutine. Coroutines in which subsequent calls yield additional results are often known as generators.
Subroutines are easy to implement with little more than a stack, since subroutines call other subroutines as subordinates. In contrast, coroutines, able to call on other coroutines as peers, are best implemented using continuations (which in turn are implemented using a garbage-collected heap) to track the flow of control.
Common uses of coroutines
Coroutines are useful to implement the following:
- State machines within a single subroutine, where the state is determined by the current entry/exit point of the procedure; this can result in more readable code.
- Actor model of concurrency, for instance in computer games. Each actor has its own procedures (this again logically separates the code), but they voluntarily give up control to central scheduler, which executes them sequentially (this is a form of cooperative multitasking).
- Generators, and these are useful for input/output and for generic traversal of data structures.
Programming languages supporting coroutines
Since continuations are used to implement coroutines, programming languages that support them can also quite easily support coroutines.
Some languages that implement continuations include:
- Scheme
- Lisp
- Haskell
- Most functional languages
Coroutine alternatives and implementations
As of 2003, many of the most popular programming languages, including C and its derivatives, do not have direct support for coroutines within the language or their standard libraries. (This is, in large part, due to the limitations of stack-based subroutine implementation).
In situations in which a coroutine would be the natural implementation of a mechanism, but is not available, the typical response is to create a subroutine that uses an ad-hoc assemblage of boolean flags and other state variables to maintain an internal state between calls. Conditionals within the code result in the execution of different code paths on successive calls, based on the values of the state variables. Another typical response is to implement an explicit state machine in the form of a large and complex switch statement. Such implementations are difficult to understand and maintain.
Threads are a suitable alternative to coroutines in mainstream programming environments today. Threads provide facilities for managing the realtime cooperative interaction of "simultaneously" executing pieces of code. Because they solve a large and difficult problem, they include many powerful and complex facilities and have a concomitantly difficult learning curve. When a coroutine is all that is needed, using a thread can be overkill. However—unlike other alternatives—threads are widely available in environments that support C, are familiar to many programmers, and are usually well-implemented, well-documented and well-supported. A standard and well-defined thread implementation is available within POSIX under the name pthread.
Implementations for C
The standard C library includes functions named setjmp and longjmp which can be used to implement a form of coroutine. Unfortunately, as Harbison and Steele note, "the setjmp and longjmp functions are notoriously difficult to implement, and the programmer would do well to make minimal assumptions about them." What this means is if Harbison and Steele's many cautions and caveats are not carefully heeded, uses of setjmp and longjmp that appear to work in one environment may not work in another. Worse yet, faulty implementations of these routines are not rare.
Several attempts have been made, with varying degrees of success, to implement coroutines in C with combinations of subroutines and macros. Simon Tatham's contribution (see below) is a good example of the genre, and his own comments provide a good evaluation of the limitations of this approach. The use of such a device truly can improve the writability, readability and maintainability of a piece of code, but is likely to prove controversial. In Tatham's words: "Of course, this trick violates every coding standard in the book... [but] any coding standard which insists on syntactic clarity at the expense of algorithmic clarity should be rewritten. If your employer fires you for using this trick, tell them that repeatedly as the security staff drag you out of the building."
Notable implementations:
- [1] - Simon Tatham's implementation of coroutines in C.
- Portable Coroutine Library - C library using POSIX/SUSv3 facilities.
- [2] - Edgar Toernig's coro library for x86, Linux & FreeBSD.
- [3] - Simple reentrant coroutines in C++.
Implementations for Python
Implementations for Ruby
References
- Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 1.4.2: Coroutines, pp.193–200.
- C: A Reference Manual. Samuel P. Harbison and Guy L. Steele, Jr. Third edition; Prentice-Hall, 1991, ISBN 0-13-110933-2.