User:Kbalaji1993/sandbox
Coroutines refer to a set of two or more independent
Coroutines are well-suited for implementing more familiar program components such as cooperative tasks, exceptions, event loops, iterators, infinite lists and pipes.
According to Donald Knuth, the term coroutine was coined by Melvin Conway in 1958, after he applied it to design of a compiler.[1] The first published explanation of the coroutine appeared later, in 1963.[2]
Comparison with subroutines
Subroutines are special cases of ... coroutines.
In contrast to subroutines, coroutines are responsible for coordinating among themselves in a program. Coroutines can be seen as colleagues whereas sub-routines are slaves to their master (main function). Coroutines do not exit, but yield to other coroutines. The states of the coroutines are saved before yielding, and can continue execution where they left off, if another coroutine yields back [2].
Typical use case of Coroutines
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[6] . 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.
Comparison with Threads
The similarity between Coroutines and threads is the ability to share global variables and have independent stack, local variables and instruction pointer. However, they differ conceptually since many threads can run in parallel, whereas only one coroutine can be in execution at a time [7]. Coroutines pass flow control cooperatively between themselves. There is no preemption involved in Coroutines, unlike in threads. Furthermore, threads are a unit of execution, many of which make up a process [8].
Comparison with generators
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[11] before 2.5) use this or a similar model.
Comparison with mutual recursion
Using coroutines for state machines or concurrency is similar to using
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.
Programming languages with native support
- Aikido
- AngelScript
- BCPL
- Pascal (Borland Turbo Pascal 7.0 with uThreads module)
- BETA
- BLISS
- ChucK
- D
- Dynamic C
- Erlang
- F#
- Factor
- GameMonkey Script
- GDScript (Godot's scripting language)
- Go
- High Level Assembly[14]
- Icon
- Io
- JavaScript (since 1.7)[15]
- Julia[16]
- Limbo
- Lua[17]
- Lucid
- µC++
- MiniD
- Modula-2
- Nemerle
- Perl 5 (using the Coro module)
- Perl 6[18]
- PHP (with HipHop, native since PHP 5.5)
- Picolisp
- Prolog
- Python (since 2.5,[19] with improved support since 3.3 and with explicit syntax since 3.5[20])
- Ruby
- Sather
- Scheme
- Self
- Simula 67
- Squirrel
- Stackless Python
- SuperCollider[21]
- Tcl (since 8.6)
- urbiscript
Since continuations can be used to implement coroutines, programming languages that support them can also quite easily support coroutines.
Implementations
Coroutines originated as an assembly language method, but are supported in some high-level programming languages. Early examples include Simula[22] and Modula-2. More recent examples are Ruby, Lua, Julia, and Go.
As of 2003[update], 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.) 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.
Alternatives
In situations where a coroutine would be the natural implementation of a mechanism, but is not available, the typical response is to use a
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.[23] However, system support for fibers is often lacking compared to that for threads.
Implementation in the .NET Framework as fibers
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.[24] Before release, support for the task switching hook ICLRTask::SwitchOut was removed due to time constraints.[25] 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 Common Language Runtime has support for continuations,[26] from which coroutines can be built.
Implementations for Java
There are several implementations for coroutines in Java. Despite the constraints imposed by Java's abstractions, the JVM does not preclude the possibility.[27] 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.[28]
- 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.
Implementations for Scala
Scala Coroutines is a coroutine implementation for
Scala Coroutines rely on the coroutine
macro that transforms a normal block of code into a coroutine definition. Such a coroutine definition can be invoked with the call
operation, which instantiates a coroutine frame. A coroutine frame can be resumed with the resume
method, which resumes the execution of the coroutine's body, until reaching a yieldval
keyword, which suspends the coroutine frame. Scala Coroutines also expose a snapshot
method, which effectively duplicates the coroutine.[30]
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,[31] based on Duff's device, 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
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
Due to the limits of standard libraries, some authors have written their own libraries for coroutines. Russ Cox's libtask library[34] 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,[35] coro,[36] lthread,[37] libCoroutine,[38] libconcurrency,[39] libcoro,[40] ribs2,[41] and libdill.[42]
Implementations for C++
- 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.[43]
- CO2 - stackless coroutine based on C++ preprocessor tricks, providing await/yield emulation.
- ScummVM - The ScummVM project implements a light-weight version of coroutines based on Simon Tatham's article.
- tonbit::coroutine - C++11 single .h asymmetric coroutine implementation via ucontext / fiber
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 Richter 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.
- [15] - The .NET 2.0+ Framework now provides semi-coroutine (generator) functionality through the iterator pattern and yield keyword.
Implementations for D
D (programming language) implements coroutines as its standard library class Fiber
Generator makes it trivial to expose a fiber function as an InputRange, making any fiber compatible with existing range algorithms.
Implementations for 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.
Implementations for Python
Support libraries for coroutines were implemented in Python 2.5 [16]. Coroutines are useful in scenarios consisting of a producer-consumer relationship between the two routines. “Yield” statement in Python is used to consume values. For example,
value_to_be_consumed = (yield)
Execution is paused at the above statement and waits for the invocation of an object’s send method such as the following
coroutine.send(data_produced)
value_to_be_consumed becomes equal to the data produced. Send() can be used from another coroutine or the console. In order to stop execution of a co-routine, we use close(). Close() raises an exception which can be caught by try/except [44] .
- 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).
- Eventlet
- Greenlet
- gevent
- kiwi tasklets
- multitask
- chiral
- cogen
- Kamaelia
- Shrapnel
- stackless python
Implementations for Ruby
- Ruby 1.9 supports coroutines natively which are implemented as fibers, which are semi-coroutines.[45]
- An implementation by Marc De Scheemaecker
Implementations for Perl
Coroutines are natively implemented in all
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.
Implementations for Scheme
Since Scheme provides full support for continuations, implementing coroutines is nearly trivial, requiring only that a queue of continuations be maintained.
Implementations for Object Pascal (Delphi)
Found MeSDK, MeObjects\src\uMeCoroutine.pas
Implementation of Tool Command Language (Tcl)
Since version 8.6, the Tool Command Language supports coroutines in the core language. [47]
Implementations in assembly languages
Machine-dependent
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)!
See also
- Pipeline (Unix), a kind of coroutine used for communicating between programs[48]
- Protothreads, a stackless lightweight thread implementation using a coroutine like mechanism
References
- ISBN 0-201-89683-4.
- ^ S2CID 10559786.
- ISBN 0-201-89683-4.
- .
- ^ Wilkes, M. V.; Wheeler, D. J.; Gill, S. (1951). Preparation of Programs for an Electronic Digital Computer. Addison-Wesley.
- ^ "Typical use case of co-routines".
- ^ "Comparison with Threads".
- S2CID 5679366.
- ISBN 978-1-56159-248-7. Retrieved 11 May 2013.
- ^ 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." - ^ Mertz, David (July 1, 2002). "Generator-based State Machines". Charming Python. IBM developerWorks. Archived from the original on February 2, 2011. Retrieved Feb 2, 2011.
- ^ "Coroutine: Type-safe coroutines using lightweight session types".
- ^ "Co-routines in Haskell".
- ^ "The Coroutines Module (coroutines.hhf)". HLA Standard Library Manual.
- ^ "New in JavaScript 1.7".
- ^ "Julia Manual - Control Flow - Tasks (aka Coroutines)".
- ^ "Lua 5.2 Reference Manual – 2.6 – Coroutines".
- ^ "Gather and/or Coroutines".
- ^ "Python async/await Tutorial".
- ^ "Python 3 reference: Coroutine function definition".
- ^ McCartney, J. "Rethinking the Computer Music Programming Language: SuperCollider". Computer Music Journal, 26(4):61-68. MIT Press, 2002.
- ^ Dahl,O.-.J. and Hoare,C.A.R.(ed) (1972). "Hierarchical Program Structures" in Structured Programming. pp. 175-220. Academic Press.
{{cite book}}
:|author=
has generic name (help)CS1 maint: multiple names: authors list (link) - MSDN Magazine
- ^ [1], Chris Brumme, cbrumme's WebLog
- ^ [2], Dino Viehland, Dino's Blog
- ^ [3] Mono Continuations
- ^ [4] Lukas Stadler's JVM Continuations (pdf)
- ^ [5] Remi Forax post on JVM coroutine/continuation/fiber
- ^ Scala Coroutines FAQ
- ^ Scala Coroutine Snapshots
- ^ Simon Tatham's implementation of coroutines in C.
- ISBN 0-13-110933-2
- ^ Building coroutines. Dr. C.-K. Shene, Michigan Technical University
- ^ [6] - Russ Cox's libtask coroutine library for FreeBSD, Linux, Mac OS X, and SunOS
- ^ Portable Coroutine Library - C library using POSIX/SUSv3 facilities
- ^ [7] - Edgar Toernig's coro library for x86, Linux & FreeBSD
- ^ [8] - lthread is a multicore/multithread coroutine library written in C
- ^ [9] - libCoroutine for FreeBSD, Linux, OS X PPC and x86, SunOS, Symbian and others.
- ^ [10] - libconcurrency is a simple C library for portable stack-switching coroutines
- ^ [11] - portable coroutines in C, used as the basis for the Coro perl module.
- ^ [12] - Robust Infrastructure for Backend Systems.
- ^ [13] - Structured Concurrency for C.
- ^ [14] - Open Source and Mozy: The Debut of Mozy Code
- ^ "Implementation of Coroutines in Python".
- ^ "semi-coroutines". Archived from the original on October 24, 2007.
{{cite web}}
: External link in
(help)|authorlink1=
- ^ "RFC #31".
- ^ "coroutine manual page - Tcl Built-In Commands". Tcl.tk. Retrieved 2016-06-27.
- S2CID 571269.
Further reading
- Ana Lucia de Moura; Roberto Ierusalimschy (2004). "Revisiting Coroutines". ACM Transactions on Programming Languages and Systems. 31 (2): 1–31. S2CID 9918449.
External links
- Simon Tatham's C oriented comprehensive introduction to coroutines
- Softpanorama coroutine page – contains extensive assembler coroutines links