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.   Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In computer science, a subroutine (function, method, procedure, or subprogram) is a portion of code within a larger program, which performs a specific task and is relatively independent of the remaining code. ... Simula is a programming language developed in the 1960s at the Norwegian Computing Centre in Oslo, by Ole-Johan Dahl and Kristen Nygaard. ... Modula-2 is a computer programming language invented by Niklaus Wirth at ETH around 1978, as a successor to Modula, another language by him. ... In computing, cooperative multitasking (or non-preemptive multitasking) is a form of multitasking in which multiple tasks execute by voluntarily ceding control to other tasks at programmer-defined points within each task. ... In computer science, an iterator is an object allowing one to sequence through all of the elements or parts contained in some other object, typically a container or list. ... In computer programming, lazy evaluation is a technique that attempts to delay computation of expressions until the results of the computation are known to be needed. ... A pipe is an operating system mechanism originating in Unix, which allows the user to direct the output of one shell command through another command. ...

Comparison of coroutines and subroutines

The main program can call a subroutine or it can call into a set of peer coroutines. (Coroutines are thought of as sets because each peer coroutine names one or more of its peers.)

When calling a subroutine, control passes to the top of the subroutine. At the end of every subroutine (and optionally in the middle as well) is a return command, which returns control to the caller.

When calling into a a set of coroutines, control passes to the top of the first coroutine or the specified coroutine. Somewhere within at least one of the coroutines is a return command, which returns control to the caller. Every coroutine must end with either a yield command or a return command.

The yield command is used only between coroutines. It resembles both the call command and the return command, but it is different from both.

The executing coroutine can, at any time, explicitly yield control to any other coroutine. When yielding to another coroutine, control passes to the other coroutine wherever it left off. (If the other coroutine has not executed previously, then it begins execution from the top.) Control might return to the coroutine that yielded, but it might not. If control ever does return, it is not definite from which other coroutine control will be returned. (Assuming there are more than two coroutines in the set.)

The yield command resembles the call command because the coroutine executing it gives up control and might get it back. The yield command resembles the return command, because the coroutine that is yielded to merely resumes executing. Yield is like a return command that does not use the stack, but instead resumes executing the specified named procedure. (Any number of coroutines might be suspended.)

Each coroutine can be re-entered any number times. Each yield is not tracked at all, as there is no reverse of yield. The overhead for coroutines is minimal. There is no context switching at all. Only the addition of an IP (Instruction Pointer) for each coroutine is required to track the re-entry point. The Yield command simply saves the IP of the next instruction in the current coroutine and then jumps to the IP stored for the target coroutine. Also, the entry point for the set of coroutines must reset all of the IPs before execution can begin.

Example of coroutines

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. Many programming languages, operating systems, and other software development environments support what are called threads of execution. ...

The real power of coroutines becomes evident in more compicated examples. If the first coroutine has TWO yield commands, then when control is yielded back to it, it has to continue from the right place. In that case, the functioning of the yield command can no longer be reduced to a simple jump command.

Detailed comparison

Since coroutines can have more points of entry than subroutines, it is possible to implement any subroutine as a lone coroutine. "Subroutines are special cases of ... coroutines." —Donald Knuth Donald Knuth at a reception for the Open Content Alliance. ...

Each time a subroutine is called (invoked), execution starts at the beginning of the invoked subroutine. The first time a coroutine is invoked, execution starts at the beginning of the coroutine. However, each time a coroutine is resumed (by use of the yield command), execution resumes following the place where the coroutine last (yielded from).

A set of coroutines can accept arguments and return values, just as a subroutine.

Coroutines do not pass arguments to each other. The yield command does not have arguments because there is no place in the resumed code to accept them. Still, a coroutine can be useful to generate a series of numbers

Since a subroutine returns only once, returning multiple values requires returning a collection of values. (Some languages, like Forth and Perl allow convenient returning of collections, while other languages like C only permit a single return value, which then needs to be a reference to a collection of values.) In contrast, since coroutines can yield multiple times, passing multiple values merely requires returning additional values upon subsequent calls to the coroutine. (This is a trivial use of coroutines, which could be replaced by inline code.) Routines in which subsequent calls yield additional results are often known as generators. Forth is a procedural, stack-oriented, reflective programming language and programming environment. ... Perl, also Practical Extraction and Report Language (a backronym, see below) is a dynamic procedural programming language designed by Larry Wall and first released in 1987. ... The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language (often, just C) is a general-purpose, procedural, imperative computer programming language developed in the early 1970s by Dennis Ritchie for use... In computer science, a generator is a special routine that can be used to control the iteration behaviour of a loop. ...

Subroutines only require a single stack that can be preallocated at the beginning of program execution. 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. Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ... In computing, a continuation is a representation of the execution state of a program (for example, the call stack or values of variables) at a certain point. ...

Called and peer coroutines

Two distinct kinds of functionality are implied by the term "coroutine". It is not always clear which functionality is being discussed or utilized. What they have in common is, the coroutine preserves its internal state of execution, not just its static variables. A coroutine resembles a spearate executing program.

Called coroutine:

A coroutine is called and it returns just like a subroutine, except that it preserves its internal execution state between calls. A subroutine has one entry point and can use any number of exit points (return statements). When a subroutine is called again, it begins execution at the top. A coroutine has one "initial" entry point and can use any number of return statements. When a coroutine is called "for the first time", it begins execution at the top. When a coroutine is called again, it resumes execution at the point immediately after the return statement that concluded the last call. The coroutine preserves its internal execution state between calls. That lets it do some interesting things. For example, code like "return 5; return 7; return 9;" actually means something, and it is much simpler code than a state-machine subroutine that could do the same thing. Since there is a "first time" provision, there could be a special action to re-initialize the coroutine. In object-oriented scenarios, there would be ways to discard an instance of a coroutine and create a new instance. (Multiple explicit entry points could allow the calling statement could specify where the coroutine should begin or resume executing. But multiple entry can also apply to subroutines, and is a different topic.) It is not untuitively obvious what the arguments passed to a called coroutine should do on calls after the first one. A called coroutine can return multiple values.

Peer coroutines:

A coroutine can yield control to a specified peer coroutine. When a coroutine receives control "for the first time", it begins execution at the top. When a coroutine receives control again, it resumes execution at the point immediately after the Yield statement that released control the last time. Each peer coroutine preserves its internal execution state while it is inactive.

Puzzles arise when trying to combine a called coroutine with peer coroutines. If the called coroutine yields to a peer coroutine, the peer coroutine could return a value. On the next call, where will execution continue? This can be resolved by grouping the peer coroutines as a set, or by not allowing returns from the peer coroutine, only the one that was called.

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.

In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ... In computer science, the Actor model, first published in 1973, is a mathematical model of concurrent computation. ... A computer game is a game composed of a computer-controlled virtual universe that players interact with in order to achieve a defined goal or set of goals. ... In computing, cooperative multitasking (or non-preemptive multitasking) is a form of multitasking in which multiple tasks execute by voluntarily ceding control to other tasks at programmer-defined points within each task. ... In computer science, a generator is a special routine that can be used to control the iteration behaviour of a loop. ...

Programming languages supporting coroutines

• Simula
• Modula-2
• C#
• Python
• Stackless Python
• Lua
• Io
• μC++

Since continuations can be used to implement coroutines, programming languages that support them can also quite easily support coroutines. Simula is a programming language developed in the 1960s at the Norwegian Computing Centre in Oslo, by Ole-Johan Dahl and Kristen Nygaard. ... Modula-2 is a computer programming language invented by Niklaus Wirth at ETH around 1978, as a successor to Modula, another language by him. ... The title given to this article is incorrect due to technical limitations. ... Python is an interpreted programming language created by Guido van Rossum in 1990. ... Stackless Python is a kind of programing language, it an experimental implementation of Python that supports continuations, generators, microthreads, and coroutines similar to Python syntax. ... The Lua (pronounced LOO-ah, or in IPA) programming language is a lightweight, reflective, imperative and procedural language, designed as a scripting language with extensible semantics as a primary goal. ... Wikibooks Programming has more about this subject: Io Io is a pure object-oriented programming language inspired by Smalltalk, Self, Lua, Lisp and NewtonScript. ... μC++, also called uC++, is a programming language, an extension of C++ designed for concurrent programming. ... In computing, a continuation is a representation of the execution state of a program (for example, the call stack or values of variables) at a certain point. ...

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). 2003 is a common year starting on Wednesday of the Gregorian calendar, and also: The International Year of Freshwater The European Disability Year Events January events January 1 Luíz Inácio Lula Da Silva becomes the 37th President of Brazil. ...

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 an 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. A thread in computer science is short for a thread of execution. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... pthreads is an abbreviation for POSIX threads and a library that provides POSIX-compliant functions for creating and manipulating threads. ...

One important difference between threads and coroutines is that threads are typically preemptively scheduled while coroutines are not. Because threads can be rescheduled at any instant and can execute concurrently, programs using threads must be careful about locking. In contrast, because coroutines can only be rescheduled at specific points in the program and do not execute concurrently, programs using coroutines can often avoid locking entirely. (This property is also cited as a benefit of event-driven or asynchronous programming.) In computer science, a lock is a mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. ... Event-driven programming is a computer programming paradigm. ...

Threads can explicitly release the processor by "sleeping". Threads can reactivate sleeping threads by waking them up. The wake-up is not immediate, it depends on the scheduler. Coroutines can hand off control instantly.

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. The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language (often, just C) is a general-purpose, procedural, imperative computer programming language developed in the early 1970s by Dennis Ritchie for use... The C standard library is a now-standardised collection of header files and library routines used to implement common operations, such as input/output and string handling, in the C programming language. ... The source is licensed under the GFDL, but has large invariant sections and cover texts. ...

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." Simon G. Tatham (born May 3, 1977) is a free software author living in Cambridge, who has been involved in a number of projects, including NASM and PuTTY, and most recently a portable collection of puzzle games. ...

A more reliable approach to implementing coroutines in C is to give up on absolute portability and write processor-family-specific implementations, in assembly, of functions to save and restore a coroutine context. A third function, which can usually be written in machine-specific C, is needed to create the context for a new coroutine. Some C libraries provide such routines under the names getcontext, setcontext, and makecontext. Russ Cox's libtask library (see below) is a good example of this genre. It uses the context functions if they are provided by the native C library; otherwise it provides its own implementations for ARM, PowerPC, Sparc, and x86. The main shortcoming of this approach is that the coroutine's stack is a fixed size and cannot be grown during execution. Thus, programs tend to allocate much more stack than they actually need in order to avoid the potential for stack overflow.

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] - Russ Cox's libtask coroutine library for FreeBSD, Linux, OS X, and SunOS.
• [4] - libCoroutine for FreeBSD, Linux, OS X PPC and x86, SunOS, Symbian and others.

To meet Wikipedias quality standards, this article or section may require cleanup. ... The Single UNIX Specification (SUS) is the collective name of a family of standards for computer operating systems to qualify for the name Unix. The SUS is developed and maintained by the Austin Group, based on earlier work by the IEEE and The Open Group. ...

Implementations for Python

• PEP 342 - better support for coroutine-like functionality, based on extended generators (implemented in Python 2.5)
• Greenlets

Python is an interpreted programming language created by Guido van Rossum in 1990. ...

Implementations for Ruby

• Coroutines in Ruby

Ruby is a reflective, object-oriented programming language. ...

Implementations for Perl

• Coro

Perl, also Practical Extraction and Report Language (a backronym, see below) is a dynamic procedural programming language designed by Larry Wall and first released in 1987. ...

Implementations for functional languages

Most functional languages implement coroutines, most notably Scheme, Lisp and Haskell. Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. ... Scheme is a functional programming language and a dialect of Lisp. ... Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ... Haskell is a standardized pure functional programming language with non-strict semantics, named after the logician Haskell Curry. ...

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.

Donald Knuth at a reception for the Open Content Alliance. ...

See also

• Cooperative multitasking
• Iterators
• Generators
• Lazy evaluation
• Pipes
• Protothreads
• Subroutines