They have been described as "functions whose execution you can pause".[1]
Melvin Conway coined the term coroutine in 1958 when he applied it to the construction of an assembly program.[2] The first published explanation of the coroutine appeared later, in 1963.[3]
Definition and types
There is no single precise definition of coroutine. In 1980 Christopher D. Marlin[4] summarized two widely-acknowledged fundamental characteristics of a coroutine:
the values of data local to a coroutine persist between successive calls;
the execution of a coroutine is suspended as control leaves it, only to carry on where it left off when control re-enters the coroutine at some later stage.
Besides that, a coroutine implementation has 3 features:
the control-transfer mechanism. Asymmetric coroutines usually provide keywords like yield and resume. Programmers cannot freely choose which frame to yield to. The runtime only yields to the nearest caller of the current coroutine. On the other hand, in symmetric coroutines, programmers must specify a yield destination.
whether coroutines are provided in the language as first-class objects, which can be freely manipulated by the programmer, or as constrained constructs;
whether a coroutine is able to suspend its execution from within nested function calls. Such a coroutine is a stackful coroutine. One to the contrary is called stackless coroutines, where unless marked as coroutine, a regular function can't use the keyword yield.
The paper "Revisiting Coroutines"[5] published in 2009 proposed term full coroutine to denote one that supports first-class coroutine and is stackful. Full Coroutines deserve their own name in that they have the same expressive power as one-shot continuations and delimited continuations. Full coroutines are either symmetric or asymmetric. Importantly, whether a coroutine is symmetric or asymmetric has no bearing on how expressive it can be as they are equally as expressive, though full coroutines are more expressive than non-full coroutines. While their expressive power is the same, asymmetrical coroutines more closely resemble routine based control structures in the sense that control is always passed back to the invoker, which programmers may find more familiar.
Comparison with
Subroutines
Subroutines are special cases of coroutines.[6] 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, and does not hold state between invocations. By contrast, coroutines can exit by calling other coroutines, which may later return to the point where they were invoked in the original coroutine; from the coroutine's point of view, it is not exiting but calling another coroutine.[6] Thus, a coroutine instance holds state, and varies between invocations; there can be multiple instances of a given coroutine at once. 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 relationship 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.[7]
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 loopwhile q is not full create some new items add the items to q yield to consume coroutine consume loopwhile q is not empty remove some items from q use the items yield to produce call 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 as an introduction to multithreading, two threads are not needed for this: the yield statement can be implemented by a jump directly from one routine into the other.
Threads
Coroutines are very similar to threads. However, coroutines are cooperatively multitasked, whereas threads are typically preemptively multitasked. Coroutines provide concurrency, because they allow tasks to be performed out of order or in a changeable order, without changing the overall outcome, but they do not provide parallelism, because they do not execute multiple tasks simultaneously. The advantages of coroutines over threads are that they may be used in a hard-realtime context (switching between coroutines need not involve any system calls or any blocking calls whatsoever), there is no need for synchronization primitives such as mutexes, semaphores, etc. in order to guard critical sections, and there is no need for support from the operating system.
It is possible to implement coroutines using preemptively-scheduled threads, in a way that will be transparent to the calling code, but some of the advantages (particularly the suitability for hard-realtime operation and relative cheapness of switching between them) will be lost.
Generators, also known as semicoroutines,[8] are a subset of coroutines. Specifically, while both can yield multiple times, suspending their execution and allowing re-entry at multiple entry points, they differ in coroutines' ability to control where execution continues immediately after they yield, while generators cannot, instead transferring control back to the generator's caller.[9] That is, since generators are primarily used to simplify the writing of iterators, 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 loopwhile q is not full create some new items add the items to q yieldgenerator consume loopwhile q is not empty remove some items from q use the items yieldsubroutine dispatcher var d := new dictionary(generator → iterator) d[produce] := start consume d[consume] := start produce var current := produce loopcall current current := next d[current] call dispatcher
A number of implementations of coroutines for languages with generator support but no native coroutines (e.g. Python[10] before 2.5) use this or a similar model.
Using coroutines for state machines or concurrency is similar to using mutual recursion with tail calls, as in both cases the control changes to a different one of a set of routines. However, coroutines are more flexible and generally more efficient. Since coroutines yield rather than return, and then resume execution rather than restarting from the beginning, they are able to hold state, both variables (as in a closure) and execution point, and yields are not limited to being in tail position; mutually recursive subroutines must either use shared variables or pass state as parameters. Further, each mutually recursive call of a subroutine requires a new stack frame (unless tail call elimination is implemented), while passing control between coroutines uses the existing contexts and can be implemented simply by a jump.
Common uses
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 compared to use of goto, and may also be implemented via mutual recursion with tail calls.
Actor model of concurrency, for instance in video 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 streams–particularly input/output–and for generic traversal of data structures.
Communicating sequential processes where each sub-process is a coroutine. Channel inputs/outputs and blocking operations yield coroutines and a scheduler unblocks them on completion events. Alternatively, each sub-process may be the parent of the one following it in the data pipeline (or preceding it, in which case the pattern can be expressed as nested generators).
Reverse communication, commonly used in mathematical software, wherein a procedure such as a solver, integral evaluator, ... needs the using process to make a computation, such as evaluating an equation or integrand.
Since continuations can be used to implement coroutines, programming languages that support them can also quite easily support coroutines.
Implementations
As of 2003[update], many of the most popular programming languages, including C and its derivatives, do not have built-in support for coroutines within the language or their standard libraries. This is, in large part, due to the limitations of stack-based subroutine implementation. An exception is the C++ library Boost.Context, part of boost libraries, which supports context swapping on ARM, MIPS, PowerPC, SPARC and x86 on POSIX, Mac OS X and Windows. Coroutines can be built upon Boost.Context.
In situations where a coroutine would be the natural implementation of a mechanism, but is not available, the typical response is to use a closure–a subroutine with state variables (static variables, often boolean flags) to maintain an internal state between calls, and to transfer control to the correct point. 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 or via a goto statement, particularly a computed goto. Such implementations are considered difficult to understand and maintain, and a motivation for coroutine support.
Threads, and to a lesser extent fibers, are an alternative to coroutines in mainstream programming environments today. Threads provide facilities for managing the real-time 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.[23] However, system support for fibers is often lacking compared to that for threads.
C
In order to implement general-purpose coroutines, a second call stack must be obtained, which is a feature not directly supported by the C language. A reliable (albeit platform-specific) way to achieve this is to use a small amount of inline assembly to explicitly manipulate the stack pointer during initial creation of the coroutine. This is the approach recommended by Tom Duff in a discussion on its relative merits vs. the method used by Protothreads.[24][non-primary source needed] On platforms which provide the POSIXsigaltstack system call, a second call stack can be obtained by calling a springboard function from within a signal handler[25][26] to achieve the same goal in portable C, at the cost of some extra complexity. C libraries complying to POSIX or the Single Unix Specification (SUSv3) provided such routines as getcontext, setcontext, makecontext and swapcontext, but these functions were declared obsolete in POSIX 1.2008.[27]
Once a second call stack has been obtained with one of the methods listed above, the setjmp and longjmp functions in the standard C library can then be used to implement the switches between coroutines. These functions save and restore, respectively, the stack pointer, program counter, callee-saved registers, and any other internal state as required by the ABI, such that returning to a coroutine after having yielded restores all the state that would be restored upon returning from a function call. Minimalist implementations, which do not piggyback off the setjmp and longjmp functions, may achieve the same result via a small block of inline assembly which swaps merely the stack pointer and program counter, and clobbers all other registers. This can be significantly faster, as setjmp and longjmp must conservatively store all registers which may be in use according to the ABI, whereas the clobber method allows the compiler to store (by spilling to the stack) only what it knows is actually in use.
Due to the lack of direct language support, many authors have written their own libraries for coroutines which hide the above details. Russ Cox's libtask library[28] 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,[29] coro,[30] lthread,[31] libCoroutine,[32] libconcurrency,[33] libcoro,[34] ribs2,[35] libdill.,[36] libaco,[37] and libco.[26]
In addition to the general approach above, several attempts have been made to approximate coroutines in C with combinations of subroutines and macros. Simon Tatham's contribution,[38] based on Duff's device, is a notable example of the genre, and is the basis for Protothreads and similar implementations.[39] In addition to Duff's objections,[24] Tatham's own comments provide a frank evaluation of the limitations of this approach: "As far as I know, this is the worst piece of C hackery ever seen in serious production code."[38] The main shortcomings of this approximation are that, in not maintaining a separate stack frame for each coroutine, local variables are not preserved across yields from the function, it is not possible to have multiple entries to the function, and control can only be yielded from the top-level routine.[24]
C++
C++20 introduced standardized coroutines as stackless functions that can be suspended in the middle of execution and resumed at a later point. The suspended state of a coroutine is stored on the heap.[40] Implementation of this standard is ongoing, with the G++ and MSVC compilers currently fully supporting standard coroutines in recent versions.[41]
concurrencpp - a C++20 library which provides third-party support for C++20 coroutines, in the form of awaitable-tasks and executors that run them.
Boost.Coroutine - created by Oliver Kowalke, is the official released portable coroutine library of boost since version 1.53. The library relies on Boost.Context and supports ARM, MIPS, PowerPC, SPARC and X86 on POSIX, Mac OS X and Windows.
Boost.Coroutine2 - also created by Oliver Kowalke, is a modernized portable coroutine library since boost version 1.59. It takes advantage of C++11 features, but removes the support for symmetric coroutines.
Mordor - In 2010, Mozy open sourced a C++ library implementing coroutines, with an emphasis on using them to abstract asynchronous I/O into a more familiar sequential model.[42]
CO2 - stackless coroutine based on C++ preprocessor tricks, providing await/yield emulation.
C# 2.0 added semi-coroutine (generator) functionality through the iterator pattern and yield keyword.[44][45]C# 5.0 includes await syntax support. In addition:
The MindTouch Dream REST framework provides an implementation of coroutines based on the C# 2.0 iterator pattern.
The Caliburn (Archived 2013-01-19 at archive.today ) screen patterns framework for WPF uses C# 2.0 iterators to ease UI programming, particularly in asynchronous scenarios.
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.
StreamThreads is an open-source, light-weight C# co-routine library based on iterator extension methods. It supports error handling and return values.
Clojure
Cloroutine is a third-party library providing support for stackless coroutines in Clojure. It's implemented as a macro, statically splitting an arbitrary code block on arbitrary var calls and emitting the coroutine as a stateful function.
D
D implements coroutines as its standard library class Fiber A generator makes it trivial to expose a fiber function as an input range, making any fiber compatible with existing range algorithms.
Go
Go has a built-in concept of "goroutines", which are lightweight, independent processes managed by the Go runtime. A new goroutine can be started using the "go" keyword. Each goroutine has a variable-size stack which can be expanded as needed. Goroutines generally communicate using Go's built-in channels.[46][47][48][49] However, goroutines are not coroutines (for instance, local data does not persist between successive calls).[50]
Java
There are several implementations for coroutines in Java. Despite the constraints imposed by Java's abstractions, the JVM does not preclude the possibility.[51] There are four general methods used, but two break bytecode portability among standards-compliant JVMs.
Modified JVMs. It is possible to build a patched JVM to support coroutines more natively. The Da Vinci JVM has had patches created.[52]
Modified bytecode. Coroutine functionality is possible by rewriting regular Java bytecode, either on the fly or at compile time. Toolkits include Javaflow, Java Coroutines, and Coroutines.
Platform-specific JNI mechanisms. These use JNI methods implemented in the OS or C libraries to provide the functionality to the JVM.[citation needed]
Thread abstractions. Coroutine libraries which are implemented using threads may be heavyweight, though performance will vary based on the JVM's thread implementation.
Kotlin implements coroutines as part of a first-party library.
Lua
Lua has supported first-class stackful asymmetric coroutines since version 5.0 (2003),[54] in the standard library coroutine.[55][56]
Modula-2
Modula-2 as defined by Wirth implements coroutines as part of the standard SYSTEM library.
The procedure NEWPROCESS() fills in a context given a code block and space for a stack as parameters, and the procedure TRANSFER() transfers control to a coroutine given the coroutine's context as its parameter.
Mono
The Mono Common Language Runtime has support for continuations,[57] from which coroutines can be built.
.NET Framework
During the development of the .NET Framework 2.0, Microsoft extended the design of the Common Language Runtime (CLR) hosting APIs to handle fiber-based scheduling with an eye towards its use in fiber-mode for SQL server.[58] Before release, support for the task switching hook ICLRTask::SwitchOut was removed due to time constraints.[59] Consequently, the use of the fiber API to switch tasks is currently not a viable option in the .NET Framework.[needs update]
OCaml
OCaml supports coroutines through its Thread module.[60] These coroutines provide concurrency without parallelism, and are scheduled preemptively on a single operating system thread. Since OCaml 5.0, green threads are also available; provided by different modules.
Coroutine implemented in a way that resembles Python functions, and some Go, many examples showing there code converted with same number of lines and behavior.
Python
Python 2.5 implements better support for coroutine-like functionality, based on extended generators (PEP 342)
Python 3.3 improves this ability, by supporting delegating to a subgenerator (PEP 380)
Python 3.4 introduces a comprehensive asynchronous I/O framework as standardized in PEP 3156, which includes coroutines that leverage subgenerator delegation
Python 3.5 introduces explicit support for coroutines with async/await syntax (PEP 0492).
Since Python 3.7, async/await have become reserved keywords.[62]
Racket provides native continuations, with a trivial implementation of coroutines provided in the official package catalog. Implementation by S. De Gabrielle
Ruby
Ruby 1.9 supports coroutines natively which are implemented as fibers, which are semi-coroutines.[63]
Since Scheme provides full support for continuations, implementing coroutines is nearly trivial, requiring only that a queue of continuations be maintained.
Smalltalk
Since, in most Smalltalk environments, the execution stack is a first-class citizen, coroutines can be implemented without additional library or VM support.
Tool Command Language (Tcl)
Since version 8.6, the Tool Command Language supports coroutines in the core language. [64]
Vala
Vala implements native support for coroutines. They are designed to be used with a Gtk Main Loop, but can be used alone if care is taken to ensure that the end callback will never have to be called before doing, at least, one yield.
Assembly languages
Machine-dependent assembly languages often provide direct methods for coroutine execution. For example, in MACRO-11, the assembly language of the PDP-11 family of minicomputers, the "classic" coroutine switch is effected by the instruction "JSR PC,@(SP)+", 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 VAXen (in VAX MACRO) the comparable instruction is "JSB @(SP)+". Even on a Motorola 6809 there is the instruction "JSR [,S++]"; note the "++", as 2 bytes (of address) are popped from the stack. This instruction is much used in the (standard) 'monitor' Assist 09.
Pipeline, a kind of coroutine used for communicating between programs[65]
Protothreads, a stackless lightweight thread implementation using a coroutine like mechanism
Related Research Articles
In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system. In many cases, a thread is a component of a process.
In computer science, control flow is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an imperative programming language from a declarative programming language.
In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements (reifies) the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process's execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment. Continuations are useful for encoding other control mechanisms in programming languages such as exceptions, generators, coroutines, and so on.
In computer science, a generator is a routine that can be used to control the iteration behaviour of a loop. All generators are also iterators. 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. However, instead of building an array containing all the values and returning them all at once, a generator yields the values one at a time, which requires less memory and allows the caller to get started processing the first few values immediately. In short, a generator looks like a function but behaves like an iterator.
In computer programming, a return statement causes execution to leave the current subroutine and resume at the point in the code immediately after the instruction which called the subroutine, known as its return address. The return address is saved by the calling routine, today usually on the process's call stack or in a register. Return statements in many programming languages allow a function to specify a return value to be passed back to the code that called the function.
In the Scheme computer programming language, the procedure call-with-current-continuation, abbreviated call/cc, is used as a control flow operator. It has been adopted by several other programming languages.
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recursion is particularly useful, and is often easy to optimize in implementations.
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This type of stack is also known as an execution stack, program stack, control stack, run-time stack, or machine stack, and is often shortened to simply the "stack". Although maintenance of the call stack is important for the proper functioning of most software, the details are normally hidden and automatic in high-level programming languages. Many computer instruction sets provide special instructions for manipulating stacks.
Stackless Python, or Stackless, is a Python programming language interpreter, so named because it avoids depending on the C call stack for its own stack. In practice, Stackless Python uses the C stack, but the stack is cleared between function calls. The most prominent feature of Stackless is microthreads, which avoid much of the overhead associated with usual operating system threads. In addition to Python features, Stackless also adds support for coroutines, communication channels, and task serialization.
A protothread is a low-overhead mechanism for concurrent programming.
In computer science, a fiber is a particularly lightweight thread of execution.
Cooperative multitasking, also known as non-preemptive multitasking, is a style of computer multitasking in which the operating system never initiates a context switch from a running process to another process. Instead, in order to run multiple applications concurrently, processes voluntarily yield control periodically or when idle or logically blocked. This type of multitasking is called cooperative because all programs must cooperate for the scheduling scheme to work.
setjmp.h is a header defined in the C standard library to provide "non-local jumps": control flow that deviates from the usual subroutine call and return sequence. The complementary functions setjmp and longjmp provide this functionality.
In computer programming, a green thread is a thread that is scheduled by a runtime library or virtual machine (VM) instead of natively by the underlying operating system (OS). Green threads emulate multithreaded environments without relying on any native OS abilities, and they are managed in user space instead of kernel space, enabling them to work in environments that do not have native thread support.
In computing, a channel is a model for interprocess communication and synchronization via message passing. A message may be sent over a channel, and another process or thread is able to receive messages sent over a channel it has a reference to, as a stream. Different implementations of channels may be buffered or not, and either synchronous or asynchronous.
Goto is a statement found in many computer programming languages. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control. The jumped-to locations are usually identified using labels, though some languages use line numbers. At the machine code level, a goto is a form of branch or jump statement, in some cases combined with a stack adjustment. Many languages support the goto statement, and many do not.
In computer programming, a function is a callable unit of software logic that has a well-defined interface and behavior and can be invoked multiple times.
In computer programming, the async/await pattern is a syntactic feature of many programming languages that allows an asynchronous, non-blocking function to be structured in a way similar to an ordinary synchronous function. It is semantically related to the concept of a coroutine and is often implemented using similar techniques, and is primarily intended to provide opportunities for the program to execute other code while waiting for a long-running, asynchronous task to complete, usually represented by promises or similar data structures. The feature is found in C#, C++, Python, F#, Hack, Julia, Dart, Kotlin, Rust, Nim, JavaScript, and Swift.
In computer programming, a virtual thread is a thread that is managed by a runtime library or virtual machine (VM) and made to resemble "real" operating system thread to code executing on it, while requiring substantially fewer resources than the latter.
↑ Knuth, Donald Ervin (1997). Fundamental Algorithms(PDF). The Art of Computer Programming. Vol.1 (3rded.). Addison-Wesley. Section 1.4.5: History and Bibliography, pp.229. ISBN978-0-201-89683-1. Archived(PDF) from the original on 2019-10-21.
1 2 Knuth, Donald Ervin (1997). Fundamental Algorithms. The Art of Computer Programming. Vol.1 (3rded.). Addison-Wesley. Section 1.4.2: Coroutines, pp.193–200. ISBN978-0-201-89683-1.
↑ See for example The Python Language Reference "https://docs.python.org/reference/expressions.html#yieldexpr 5.2.10. Yield expressions]": "All of this makes generator functions quite similar to coroutines; they yield multiple times, they have more than one entry point and their execution can be suspended. The only difference is that a generator function cannot control where should the execution continue after it yields; the control is always transferred to the generator's caller."
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
