Coroutine
Encyclopedia
Coroutines are computer program
components that generalize subroutine
s to allow multiple entry points for suspending and resuming execution at certain locations. Coroutines are well-suited for implementing more familiar program components such as cooperative tasks, iterator
s, infinite lists
and pipes
.
The term "coroutine" was originated by Melvin Conway
in a 1963 paper.
. When subroutines are invoked, execution begins at the beginning 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 yielding to, or calling, other coroutines, which allows them to be re-entered at that point again; from the coroutine's point of view, it is not exiting at all but simply calling another coroutine.
Any subroutine can be implemented as a coroutine by simply not using the yielding feature of coroutines.
To implement a programming language with subroutines, only a single stack
that can be preallocated at the beginning of program execution is needed. In contrast, coroutines, able to call on other coroutines as peers, are best implemented using continuation
s. 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
, it is not necessary to have two threads to achieve this: the yield statement can be implemented by a branch directly from one routine into the other.
are also a generalisation of subroutines, but with at first sight less expressive power than coroutines; since generators are primarily used to simplify the writing of iterator
s, the
var q := new queue
generator produce
loop
while q is not full
create some new items
add the items to q
yield consume
generator consume
loop
while q is not empty
remove some items from q
use the items
yield produce
subroutine dispatcher
var d := new dictionary〈generator → iterator〉
d[produce] := start produce
d[consume] := start consume
var current := produce
loop
current := next d[current]
A number of implementations of coroutines for languages with generator support but no native coroutines (e.g. Python prior to 2.5) use this or a similar model.
Since continuation
s can be used to implement coroutines, programming languages that support them can also quite easily support coroutines.
technique, but are supported in some high-level languages. Simula
and Modula-2
are two early examples of languages supporting coroutines, Lua and Go
are two recent examples.
, 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 where 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
(and to a lesser extent fibers
) 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. Threads are widely available in environments that support C (and are supported natively in many other modern languages), are familiar to many programmers, and are usually well-implemented, well-documented and well-supported. However, as they solve a large and difficult problem they include many powerful and complex facilities and have a correspondingly difficult learning curve. As such, when a coroutine is all that is needed, using a thread can be overkill.
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.)
Since fibers are cooperatively scheduled, they provide an ideal base for implementing coroutines above. However, system support for fibers is often lacking compared to that for threads.
Implementation in the .NET Framework
During the development of the .NET Framework 2.0, Microsoft extended the design of the CLR
hosting APIs to handle fiber-based scheduling with an eye towards its use in fiber-mode for SQL server. Prior to release, support for the task switching hook ICLRTask::SwitchOut was removed due to time constraints.
Consequently the use of the fiber API to switch tasks is currently not a viable option in the .NET framework.
Implementation in Mono
The Mono CLR
has support for continuations, from which coroutines can be built.
Implementations for Java
There are several implementations for Coroutines in java, despite the difficulty imposed by the abstractions within the Java language, the JVM does not preclude the possibility. There are four general methods used.
Implementations for C
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 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."
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. 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. Indeed, setjmp/longjmp, because it only countenances a single stack, cannot be used to implement natural coroutines, as variables located on the stack will be overwritten as another coroutine uses the same stack space.
Thus for stack-based coroutines in C, functions are needed to create and jump between alternate stacks. A third function, which can usually be written in machine-specific C, is needed to create the context for a new coroutine. C libraries complying to POSIX
or the Single Unix Specification
provide such routines as getcontext, setcontext, makecontext and swapcontext
. The setcontext family of functions is thus considerably more powerful than setjmp/longjmp, but conforming implementations are as rare if not rarer. 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.
Due to the limitations of standard libraries, some authors have written their own libraries for coroutines. Russ Cox's libtask library 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. Other notable implementations include libpcl, coro, libCoroutine, libconcurrency and libcoro.
Implementations for Python
Implementations for Perl
Coroutines will also be a part of Perl 6
.
Implementations for Smalltalk
Since, in most Smalltalk environments, the execution stack is a first-class citizen, coroutines can be implemented without additional library or VM support.
s, the implementation of coroutines is nearly trivial, requiring only that a queue of continuations be maintained.
, the assembly language of the PDP-11 family
of minicomputers, the “classic” coroutine switch is effected by the instruction "JSR PC,@(SP)+" (which assembles as octal "004736") which jumps to the address popped from the stack and pushes the current (i.e that of the next) instruction address onto the stack. On VAX
en (in Macro-32
) the comparable instruction is "JSB @(SP)+" (which assembles as hex "9E 16" as the assembler shows it (with in effect bytes reversed). Even on a Motorola 6809
there is the instruction "JSR [,S++]", which assembles as (hex) "AD F1"; note the "++", as 2 bytes (of address) are popped from the stack. This instruction is much used in the (standard) 'monitor' Assist 09.
Simply calling back the routine whose address is on the top of the stack, does not, of course, exhaust the possibilities in assembly language(s)!
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
components that generalize subroutine
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
s to allow multiple entry points for suspending and resuming execution at certain locations. Coroutines are well-suited for implementing more familiar program components such as cooperative tasks, iterator
Iterator
In computer programming, an iterator is an object that enables a programmer to traverse a container. Various types of iterators are often provided via a container's interface...
s, infinite lists
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
and pipes
Pipeline (software)
In software engineering, a pipeline consists of a chain of processing elements , arranged so that the output of each element is the input of the next. Usually some amount of buffering is provided between consecutive elements...
.
The term "coroutine" was originated by Melvin Conway
Melvin Conway
Melvin Edward Conway was an early computer scientist, computer programmer, and hacker who coined what's now known as Conway's Law: "Organizations which design systems are constrained to produce designs which are copies of the communication structures of these organizations."Apart from the above,...
in a 1963 paper.
Comparison with subroutines
"Subroutines are special cases of ... coroutines." —Donald KnuthDonald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
. When subroutines are invoked, execution begins at the beginning 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 yielding to, or calling, other coroutines, which allows them to be re-entered at that point again; from the coroutine's point of view, it is not exiting at all but simply calling another coroutine.
Any subroutine can be implemented as a coroutine by simply not using the yielding feature of coroutines.
To implement a programming language with subroutines, only a single stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
that can be preallocated at the beginning of program execution is needed. In contrast, coroutines, able to call on other coroutines as peers, are best implemented using continuation
Continuation
In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...
s. 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
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
, it is not necessary to have two threads to achieve this: the yield statement can be implemented by a branch directly from one routine into the other.
Coroutines and generators
GeneratorsGenerator (computer science)
In computer science, a generator is a special routine that can be used to control the iteration behaviour of a loop. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values...
are also a generalisation of subroutines, but with at first sight less expressive power than coroutines; since generators are primarily used to simplify the writing of iterator
Iterator
In computer programming, an iterator is an object that enables a programmer to traverse a container. Various types of iterators are often provided via a container's interface...
s, the
yield statement in a generator does not specify a coroutine to jump to, but rather passes a value back to a parent routine. However, it is still possible to implement coroutines on top of a generator facility, with the aid of a top-level dispatcher routine (a trampoline, essentially) that passes control explicitly to child generators identified by tokens passed back from the generators:var q := new queue
generator produce
loop
while q is not full
create some new items
add the items to q
yield consume
generator consume
loop
while q is not empty
remove some items from q
use the items
yield produce
subroutine dispatcher
var d := new dictionary〈generator → iterator〉
d[produce] := start produce
d[consume] := start consume
var current := produce
loop
current := next d[current]
A number of implementations of coroutines for languages with generator support but no native coroutines (e.g. Python prior to 2.5) use this or a similar model.
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 modelActor modelIn computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
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). - GeneratorsGenerator (computer science)In computer science, a generator is a special routine that can be used to control the iteration behaviour of a loop. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values...
, and these are useful for input/output and for generic traversal of data structures.
Programming languages supporting coroutines
- Aikido
- AngelScript
- BCPLBCPLBCPL is a procedural, imperative, and structured computer programming language designed by Martin Richards of the University of Cambridge in 1966.- Design :...
- Pascal
- BETABETABETA is a pure object-oriented language originating within the "Scandinavian School" in object-orientation where the first object-oriented language Simula was developed....
- C#
- ChucKChucKChucK is a concurrent, strongly timed audio programming language for real-time synthesis, composition, and performance, which runs on Mac OS X, Linux, Microsoft Windows, and iPhone/iPad. It is designed to favor readability and flexibility for the programmer over other considerations such...
- DD (programming language)The D programming language is an object-oriented, imperative, multi-paradigm, system programming language created by Walter Bright of Digital Mars. It originated as a re-engineering of C++, but even though it is mainly influenced by that language, it is not a variant of C++...
- Dynamic C
- Erlang
- F#
- FactorFactor (programming language)Factor is a stack-oriented programming language created by Slava Pestov. Factor is dynamically typed and has automatic memory management, as well as powerful metaprogramming features. The language has a single implementation featuring a self-hosted optimizing compiler and an interactive development...
- GameMonkey
- GoGo (programming language)Go is a compiled, garbage-collected, concurrent programming language developed by Google Inc.The initial design of Go was started in September 2007 by Robert Griesemer, Rob Pike, and Ken Thompson. Go was officially announced in November 2009. In May 2010, Rob Pike publicly stated that Go was being...
- HaskellHaskell (programming language)Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
- High Level AssemblyHigh Level AssemblyHigh Level Assembler is an assembly language developed by Randall Hyde. It allows the use of higher-level language constructs to aid both beginners and advanced assembly developers. It fully supports advanced data types and object-oriented assembly language programming...
- JavaScriptJavaScriptJavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
(since 1.7) - Icon
- IoIo (programming language)Io is a pure object-oriented programming language inspired by Smalltalk, Self, Lua, Lisp, Act1, and NewtonScript. Io has a prototype-based object model similar to the ones in Self and NewtonScript, eliminating the distinction between instance and class. Like Smalltalk, everything is an object and...
- Limbo
- Lua
- Lucid
- µC++
- MiniDMiniDThe MiniD programming language is a small, lightweight, extension language in the vein of Lua or Squirrel, but designed to be used mainly with the D programming language...
- Modula-2Modula-2Modula-2 is a computer programming language designed and developed between 1977 and 1980 by Niklaus Wirth at ETH Zurich as a revision of Pascal to serve as the sole programming language for the operating system and application software for the personal workstation Lilith...
- Nemerle
- PerlPerlPerl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
(Perl 5 with Coro, Perl 6 native) - PrologPrologProlog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
- PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
(since 2.5) - RubyRuby (programming language)Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
- SatherSatherSather is an object-oriented programming language. It originated circa 1990 at the International Computer Science Institute at the University of California, Berkeley, developed by an international team led by Steve Omohundro...
- Scheme
- Self
- Simula-67SimulaSimula is a name for two programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard...
- Squirrel
- Stackless PythonStackless PythonStackless Python, or Stackless, is a Python programming language interpreter, so named because it avoids depending on the C call stack for its own stack. The most prominent feature of Stackless is microthreads, which avoid much of the overhead associated with usual operating system threads...
- SuperColliderSupercolliderA Supercollider is a high energy particle accelerator. The term may refer to:* Superconducting Super Collider, planned 80 km project in Texas, canceled in 1993...
- TclTclTcl is a scripting language created by John Ousterhout. Originally "born out of frustration", according to the author, with programmers devising their own languages intended to be embedded into applications, Tcl gained acceptance on its own...
(since 8.6) - urbiscriptUrbiscripturbiscript is a programming language for robotics. It features syntactic support for concurrency and event-based programming. It is a prototype-based object-oriented scripting language...
Since continuation
Continuation
In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...
s can be used to implement coroutines, programming languages that support them can also quite easily support coroutines.
Coroutine alternatives and implementations
Coroutines originated as an assembly-languageAssembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
technique, but are supported in some high-level languages. Simula
Simula
Simula is a name for two programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard...
and Modula-2
Modula-2
Modula-2 is a computer programming language designed and developed between 1977 and 1980 by Niklaus Wirth at ETH Zurich as a revision of Pascal to serve as the sole programming language for the operating system and application software for the personal workstation Lilith...
are two early examples of languages supporting coroutines, Lua and Go
Go (programming language)
Go is a compiled, garbage-collected, concurrent programming language developed by Google Inc.The initial design of Go was started in September 2007 by Robert Griesemer, Rob Pike, and Ken Thompson. Go was officially announced in November 2009. In May 2010, Rob Pike publicly stated that Go was being...
are two recent examples.
, 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
Call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the stack"...
subroutine implementation).
In situations where 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
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
(and to a lesser extent fibers
Fiber (computer science)
In computer science, a fiber is a particularly lightweight thread of execution.Like threads, fibers share address space. However, fibers use co-operative multitasking while threads use pre-emptive multitasking. Threads often depend on the kernel's thread scheduler to preempt a busy thread and...
) 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. Threads are widely available in environments that support C (and are supported natively in many other modern languages), are familiar to many programmers, and are usually well-implemented, well-documented and well-supported. However, as they solve a large and difficult problem they include many powerful and complex facilities and have a correspondingly difficult learning curve. As such, when a coroutine is all that is needed, using a thread can be overkill.
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
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
. 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
Event-driven programming
In computer programming, event-driven programming or event-based programming is a programming paradigm in which the flow of the program is determined by events—i.e., sensor outputs or user actions or messages from other programs or threads.Event-driven programming can also be defined as an...
or asynchronous programming.)
Since fibers are cooperatively scheduled, they provide an ideal base for implementing coroutines above. However, system support for fibers is often lacking compared to that for threads.
Implementation in the .NET Framework.NET FrameworkThe .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...
as fibers
During the development of the .NET Framework 2.0, Microsoft extended the design of the CLRCommon Language Runtime
The Common Language Runtime is the virtual machine component of Microsoft's .NET framework and is responsible for managing the execution of .NET programs. In a process known as just-in-time compilation, the CLR compiles the intermediate language code known as CIL into the machine instructions...
hosting APIs to handle fiber-based scheduling with an eye towards its use in fiber-mode for SQL server. Prior to release, support for the task switching hook ICLRTask::SwitchOut was removed due to time constraints.
Consequently the use of the fiber API to switch tasks is currently not a viable option in the .NET framework.
Implementation in MonoMono (software)Mono, pronounced , is a free and open source project led by Xamarin to create an Ecma standard compliant .NET-compatible set of tools including, among others, a C# compiler and a Common Language Runtime....
The Mono CLRCommon Language Runtime
The Common Language Runtime is the virtual machine component of Microsoft's .NET framework and is responsible for managing the execution of .NET programs. In a process known as just-in-time compilation, the CLR compiles the intermediate language code known as CIL into the machine instructions...
has support for continuations, from which coroutines can be built.
Implementations for JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
There are several implementations for Coroutines in java, despite the difficulty imposed by the abstractions within the Java language, the JVM does not preclude the possibility. There are four general methods used.
- Modified JVMs. It is possible to build a patched JVM to support Coroutines more natively. The Da Vinci JVM has had patches created.
- Modified Bytecode. Coroutine functionality is possible by rewriting regular java bytecode, either on the fly or at compile time. One Java Coroutines Project.
- Platform-specific JNI mechanisms. These use JNI methods implemented in the OS or C libraries to provide the functionality to the JVM.
- Thread abstractions. Coroutine libraries which are implemented using threads may be heavyweight, though performance will vary based on the JVM's thread implementation.
Implementations for CC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
Several attempts have been made, with varying degrees of success, to implement coroutines in C with combinations of subroutines and macros. Simon TathamSimon Tatham
Simon Tatham is an English programmer known primarily for creating and maintaining PuTTY, a free software implementation of Telnet and SSH clients for Unix and Windows API platforms, along with an xterm terminal emulator...
's contribution 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."
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. 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. Indeed, setjmp/longjmp, because it only countenances a single stack, cannot be used to implement natural coroutines, as variables located on the stack will be overwritten as another coroutine uses the same stack space.
Thus for stack-based coroutines in C, functions are needed to create and jump between alternate stacks. A third function, which can usually be written in machine-specific C, is needed to create the context for a new coroutine. C libraries complying to POSIX
POSIX
POSIX , an acronym for "Portable Operating System Interface", is a family of standards specified by the IEEE for maintaining compatibility between operating systems...
or the Single Unix Specification
Single UNIX Specification
The Single UNIX Specification is the collective name of a family of standards for computer operating systems to qualify for the name "Unix"...
provide such routines as getcontext, setcontext, makecontext and swapcontext
Setcontext
setcontext is one of a family of C library functions used for context control. The setcontext family allows the implementation in C of advanced control flow patterns such as iterators, fibers, and coroutines...
. The setcontext family of functions is thus considerably more powerful than setjmp/longjmp, but conforming implementations are as rare if not rarer. 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.
Due to the limitations of standard libraries, some authors have written their own libraries for coroutines. Russ Cox's libtask library 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. Other notable implementations include libpcl, coro, libCoroutine, libconcurrency and libcoro.
Implementations for C++
- Boost.Coroutine - Giovanni P. Deretta created while his "Google Summer of Code 2006" project this portable coroutine library which relies heavily on boost and C++ templates. The Boost.Coroutine Documentation is hosted on a non-boost site because the library is unfinished and not part of the official boost release.
- Mordor - In 2010, MozyMozyMozy is an online backup service for both Windows and Mac users. The cloud service allows users to back up data continuously, manually or schedule updates. Mozy is known for offering backup storage space for home and business users. In 2011, they changed to their current tiered pricing model...
open sourced a C++ library implementing coroutines, with an emphasis on using them to abstract Asynchronous I/OAsynchronous I/OAsynchronous I/O, or non-blocking I/O, is a form of input/output processing that permits other processing to continue before the transmission has finished....
into a more familiar sequential model.
Implementations for C#
- MindTouch Dream - The MindTouch Dream REST framework provides an implementation of Coroutines based on the C# 2.0 iterator pattern
- Caliburn - The Caliburn screen patterns framework for WPF uses C# 2.0 iterators to ease UI programming, particularly in asynchronous scenarios.
- Power Threading Library - The Power Threading Library by Jeffrey RichterJeffrey RichterJeffrey Richter is a co-founder of Wintellect. He has written a number of books on programming for Windows and .NET.-Bibliography:* CLR via C#, Third Edition...
implements an AsyncEnumerator that provides simplified Asynchronous Programming Model using iterator-based Coroutines. - Servelat Pieces - The Servelat Pieces project by Yevhen Bobrov provides transparent asynchrony for Silverlight WCF services and ability to asynchronously call any synchronous method. The implementation is based on Caliburn's Coroutines iterator and C# iterator blocks.
- http://msdn.microsoft.com/en-us/library/dscyy5s0(VS.80).aspx - The .NET 2.0+ Framework now provides coroutine functionality through the iterator pattern and yield keyword.
Implementations for PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
- PEP 342 - better support for coroutine-like functionality, based on extended generators (implemented in Python 2.5)
- Greenlets
- gevent
- kiwi tasklets
- multitask
- chiral
- cogen
- Kamaelia
Implementations for Ruby
Implementations for PerlPerlPerl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
Coroutines will also be a part of Perl 6
Perl 6
Perl 6 is a major revision to the Perl programming language. It is still in development, as a specification from which several interpreter and compiler implementations are being written. It is introducing elements of many modern and historical languages. Perl 6 is intended to have many...
.
Implementations for SmalltalkSmalltalkSmalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
Since, in most Smalltalk environments, the execution stack is a first-class citizen, coroutines can be implemented without additional library or VM support.Implementations for Scheme
Since Scheme provides full support for continuationContinuation
In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...
s, the implementation of coroutines is nearly trivial, requiring only that a queue of continuations be maintained.
Implementations for Delphi
- Cool little Coroutines function Coroutine implementation by Bart van der Werf
- C# Yield implementation in Delphi by Sergey Antonov
Implementations in assembly languages
Machine-dependent assembly languages often provide direct methods for coroutine execution. For example, in MACRO-11MACRO-11
MACRO-11 is an assembly language with macro facilities for PDP-11 minicomputers from Digital Equipment Corporation . It is the successor to PAL-11 , an earlier version of the PDP-11 assembly language without macro facilities....
, the assembly language of the PDP-11 family
PDP-11
The PDP-11 was a series of 16-bit minicomputers sold by Digital Equipment Corporation from 1970 into the 1990s, one of a succession of products in the PDP series. The PDP-11 replaced the PDP-8 in many real-time applications, although both product lines lived in parallel for more than 10 years...
of minicomputers, the “classic” coroutine switch is effected by the instruction "JSR PC,@(SP)+" (which assembles as octal "004736") which jumps to the address popped from the stack and pushes the current (i.e that of the next) instruction address onto the stack. On VAX
VAX
VAX was an instruction set architecture developed by Digital Equipment Corporation in the mid-1970s. A 32-bit complex instruction set computer ISA, it was designed to extend or replace DEC's various Programmed Data Processor ISAs...
en (in Macro-32
VAX Macro
VAX Macro is the computer assembly language implementing the instruction set for the line of CPUs designed to run the OpenVMS operating system created by Digital Equipment Corporation in 1977...
) the comparable instruction is "JSB @(SP)+" (which assembles as hex "9E 16" as the assembler shows it (with in effect bytes reversed). Even on a Motorola 6809
Motorola 6809
The Motorola 6809 is an 8-bit microprocessor CPU from Motorola, designed by Terry Ritter and Joel Boney and introduced 1978...
there is the instruction "JSR [,S++]", which assembles as (hex) "AD F1"; note the "++", as 2 bytes (of address) are popped from the stack. This instruction is much used in the (standard) 'monitor' Assist 09.
Simply calling back the routine whose address is on the top of the stack, does not, of course, exhaust the possibilities in assembly language(s)!
External links
- Simon TathamSimon TathamSimon Tatham is an English programmer known primarily for creating and maintaining PuTTY, a free software implementation of Telnet and SSH clients for Unix and Windows API platforms, along with an xterm terminal emulator...
's C oriented comprehensive introduction to coroutines - Dan Sugalski's less formal explanation of coroutines, including a discussion of how to handle resumption with different parameters.
- Softpanorama coroutine page Contains extensive assembler coroutines links.