词条 | Coroutine |
释义 |
Coroutines are computer program components that generalize subroutines for non-preemptive multitasking, by allowing execution to be suspended and resumed. Coroutines are well-suited for implementing familiar program components such as cooperative tasks, exceptions, event loops, iterators, infinite lists and pipes. According to Donald Knuth, Melvin Conway coined the term coroutine in 1958 when he applied it to construction of an assembly program. The first published explanation of the coroutine appeared later, in 1963.[2] Comparison with subroutinesSubroutines are special cases of coroutines.[3] 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.[3] 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.[5] 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 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. Comparison with threadsCoroutines are very similar to threads. However, coroutines are cooperatively multitasked, whereas threads are typically preemptively multitasked. This means that coroutines provide concurrency but not parallelism. 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 synchronisation 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. Comparison with generatorsGenerators, also known as semicoroutines,[1] 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.[2] That is, since generators are primarily used to simplify the writing of iterators, the 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: '''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[8] before 2.5) use this or a similar model. Comparison with mutual recursion{{Further|Mutual recursion}}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 usesCoroutines are useful to implement the following:
Programming languages with native supportCoroutines originated as an assembly language method, but are supported in some high-level programming languages. Early examples include Simula[3], Smalltalk, and Modula-2. More recent examples are Ruby, Lua, Julia, and Go. {{Div col|colwidth=18em}}
{{div col end}} Since continuations can be used to implement coroutines, programming languages that support them can also quite easily support coroutines. Implementations{{As of|2003}}, many of the most popular programming languages, including C and its derivatives, do not have direct support for coroutines within the language or their standard libraries. (This is, in large part, due to the limitations of stack-based subroutine implementation.) 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{{snd}}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 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.[15] However, system support for fibers is often lacking compared to that for threads. Implementations for CIn 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[16]. On platforms which provide the POSIX sigaltstack system call, a second call stack can be obtained by calling a springboard function from within a signal handler[17][18] 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 [19]. 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. 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[20] 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,[21] coro,[22] lthread,[23] libCoroutine,[24] libconcurrency,[25] libcoro,[26] ribs2,[27] libdill.[28], libaco [29], and libco[18]. 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,[30] based on Duff's device, is a notable example of the genre, and is the basis for Protothreads and similar implementations.[31] In addition to Duff's objections[16], 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."[30] 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[16]. Implementations for C++
Implementations for C#
C# 5.0 includes await syntax support. Implementations for Clojure[https://github.com/leonoel/cloroutine 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. Implementations for DD (programming language) implements coroutines as its standard library class FiberGenerator makes it trivial to expose a fiber function as an InputRange, making any fiber compatible with existing range algorithms. Implementations for JavaThere are several implementations for coroutines in Java. Despite the constraints imposed by Java's abstractions, the JVM does not preclude the possibility.[34] There are four general methods used, but two break bytecode portability among standards-compliant JVMs.
Implementations for Kotlin[https://kotlinlang.org Kotlin] implements coroutines as part of a [https://github.com/Kotlin/kotlinx.coroutines first-party library]. Implementations in JavaScript
Implementation in MonoThe Mono Common Language Runtime has support for continuations,[36] from which coroutines can be built. Implementation in the .NET Framework as fibersDuring 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.[37] Before release, support for the task switching hook ICLRTask::SwitchOut was removed due to time constraints.[38] Consequently, the use of the fiber API to switch tasks is currently not a viable option in the .NET Framework. Implementations for Python
Implementations for Ruby
Implementations for Perl
Coroutines are natively implemented in all Perl 6 backends.[40] Implementations for RustThere is a library for Rust that provides coroutines.[41] Generators are an experimental feature available in nightly rust that provides an implementation of coroutines with async/await.[42] Implementations for ScalaScala Coroutines is a coroutine implementation for Scala. This implementation is a library-level extension that relies on the Scala macro system to statically transform sections of the program into coroutine objects. As such, this implementation does not require modifications in the JVM, so it is fully portable between different JVMs and works with alternative Scala backends, such as Scala.js, which compiles to JavaScript.[43]Scala Coroutines rely on the Implementations for SmalltalkSince, in most Smalltalk environments, the execution stack is a first-class citizen, coroutines can be implemented without additional library or VM support. Implementations for SchemeSince Scheme provides full support for continuations, implementing coroutines is nearly trivial, requiring only that a queue of continuations be maintained. Implementation for Tool Command Language (Tcl)Since version 8.6, the Tool Command Language supports coroutines in the core language. [45]Implementations for ValaVala 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 in assembly languagesMachine-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 Macro-32) 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. See also
References1. ^{{cite book|author=Anthony Ralston|title=Encyclopedia of computer science|url=https://books.google.com/books?id=yQ9LAQAAIAAJ|accessdate=11 May 2013|year=2000|publisher=Nature Pub. Group|isbn=978-1-56159-248-7}} [46][47] [48][49][50]2. ^See for example [https://docs.python.org/reference/index.html 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." 3. ^{{cite book|title=Structured Programming|author=Dahl, O.-J. and Hoare, C.A.R. (ed)|publisher=Academic Press|year=1972|isbn=978-0122005503|location=London, UK|pages=175–220|chapter=Hierarchical Program Structures}} 4. ^{{cite web| title = Coroutine: Type-safe coroutines using lightweight session types| url = http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Coroutine}} 5. ^{{cite web| title = Co-routines in Haskell| url = https://axman6.com/posts/2016-07-10-Linear-resources-in-haskell.html}} 6. ^{{cite web| title = The Coroutines Module (coroutines.hhf)| url = http://www.plantation-productions.com/Webster/HighLevelAsm/HLADoc/HLAStdlib/1_HTML/HLAStdlib.htm#50618574_pgfId-998318| work = HLA Standard Library Manual}} 7. ^{{cite web| title = New in JavaScript 1.7| url = https://developer.mozilla.org/en/docs/New_in_JavaScript_1.7}} 8. ^{{cite web | title=Julia Manual - Control Flow - Tasks (aka Coroutines)|url=http://docs.julialang.org/en/latest/manual/control-flow#man-tasks-1}} 9. ^{{cite web | title=What's New in Kotlin 1.1|url=https://kotlinlang.org/docs/reference/whatsnew11.html#coroutines-experimental}} 10. ^{{cite web |title=Lua 5.2 Reference Manual – 2.6 – Coroutines|url=http://www.lua.org/manual/5.2/manual.html#2.6}} 11. ^{{cite web | title=Gather and/or Coroutines|url=https://perl6advent.wordpress.com/2012/12/19/gather-andor-coroutines/}} 12. ^{{cite web |title=Python async/await Tutorial|url=http://stackabuse.com/python-async-await-tutorial/}} 13. ^{{cite web |title=Python 3 reference: Coroutine function definition|url=https://docs.python.org/3/reference/compound_stmts.html#async-def}} 14. ^McCartney, J. "Rethinking the Computer Music Programming Language: SuperCollider". Computer Music Journal, 26(4):61-68. MIT Press, 2002. 15. ^Implementing Coroutines for .NET by Wrapping the Unmanaged Fiber API, Ajai Shankar, MSDN Magazine 16. ^1 2 https://brainwagon.org/2005/03/05/coroutines-in-c/#comment-1878 17. ^https://www.gnu.org/software/pth/rse-pmt.ps 18. ^1 https://byuu.org/library/libco/ 19. ^http://man7.org/linux/man-pages/man3/getcontext.3.html 20. ^ - Russ Cox's libtask coroutine library for FreeBSD, Linux, Mac OS X, and SunOS 21. ^Portable Coroutine Library - C library using POSIX/SUSv3 facilities 22. ^ - Edgar Toernig's coro library for x86, Linux & FreeBSD 23. ^[https://github.com/halayli/lthread] - lthread is a multicore/multithread coroutine library written in C 24. ^{{cite web|url=http://dekorte.com/projects/opensource/libcoroutine/|title=libcoroutine: A portable coroutine implementation}} for FreeBSD, Linux, OS X PPC and x86, SunOS, Symbian and others 25. ^{{cite web|url=http://code.google.com/p/libconcurrency/libconcurrency|title=libconcurrency - A scalable concurrency library for C}} a simple C library for portable stack-switching coroutines 26. ^{{cite web|url=http://software.schmorp.de/pkg/libcoro.html|title=libcoro: C-library that implements coroutines (cooperative multitasking) in a portable fashion}} used as the basis for the Coro perl module. 27. ^{{cite web|url=https://github.com/Adaptv/ribs2|title=RIBS (Robust Infrastructure for Backend Systems)}} 28. ^{{cite web|url=http://libdill.org|title=Structured Concurrency for C}} 29. ^{{cite web|url=https://github.com/hnes/libaco|title=A blazing fast and lightweight C asymmetric coroutine library with detailed math proof}} 30. ^1 {{cite web|url=http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html|author=Simon Tatham|title=Coroutines in C|year=2000}} 31. ^{{cite web|url=https://github.com/jsseldenthuis/coroutine|title=coroutine - Stackless coroutine implementation in C and C++}} 32. ^ - Open Source and Mozy: The Debut of Mozy Code 33. ^[https://twitter.com/eric01/status/867473461836263424] - EricWF: Coroutines are now in Clang Trunk! Working on the Libc++ implementation now. 34. ^{{cite web|url=http://www.wiki.jvmlangsummit.com/images/2/2b/JVMLanguageSummit_Stadler_Continuations.pdf|author=Lukas Stadler|series=JVM Language Summit|title=JVM Continuations|year=2009}} 35. ^{{cite web|url=http://weblogs.java.net/blog/forax/archive/2009/11/19/holy-crap-jvm-has-coroutinecontinuationfiber-etc|author=Remi Forax|archiveurl=https://web.archive.org/web/20150319052055/http://weblogs.java.net/blog/forax/archive/2009/11/19/holy-crap-jvm-has-coroutinecontinuationfiber-etc|archivedate=19 March 2015|title=Holy crap: JVM has coroutine/continuation/fiber etc.|date=19 November 2009}} 36. ^ Mono Continuations 37. ^ , Chris Brumme, cbrumme's WebLog 38. ^ , Dino Viehland, Dino's Blog 39. ^{{cite web|url=http://www.ruby-forum.com/topic/126011 |authorlink1=https://web.archive.org/web/20071024123936/http://www.ruby-forum.com/topic/126011 |title=semi-coroutines |archivedate=October 24, 2007 |language=English |deadurl=yes |archiveurl=https://web.archive.org/web/20071024123936/http://www.ruby-forum.com/topic/126011 }} 40. ^{{cite web | title = RFC #31 | url = http://www.perl6.org/archive/rfc/31}} 41. ^{{cite web|url=https://crates.io/crates/coroutine|title=coroutine - Cargo: packages for Rust|accessdate=2017-06-24}} 42. ^{{cite web|title=Tracking issue for RFC 2033: Experimentally add coroutines to Rust|url=https://github.com/rust-lang/rust/issues/43122|website=GitHub}} 43. ^Scala Coroutines FAQ 44. ^Scala Coroutine Snapshots 45. ^{{cite web|url=https://www.tcl.tk/man/tcl/TclCmd/coroutine.htm |title=coroutine manual page - Tcl Built-In Commands |publisher=Tcl.tk |date= |accessdate=2016-06-27}} 46. ^1 {{Cite journal | last1 = Conway | first1 = M. E. | doi = 10.1145/366663.366704 | title = Design of a Separable Transition-Diagram Compiler| journal = Communications of the ACM | volume = 6 | issue = 7| pages = 396–408 | date =July 1963 }} 47. ^1 2 {{Cite book | first = Donald Ervin | last = Knuth | series = The Art of Computer Programming | volume = 1 | title = Fundamental Algorithms | edition = 3rd | publisher = Addison-Wesley | year = 1997| isbn = 978-0-201-89683-1 | at = Section 1.4.2: Coroutines, pp. 193–200}} 48. ^1 {{Cite book | first = Dennis M. | last = Ritchie | title = The Evolution of the Unix Time-sharing System | url = http://cm.bell-labs.com/cm/cs/who/dmr/hist.html | journal = Lecture Notes in Computer Science | year = 1980 | volume = 79 | issue = Language Design and Programming Methodology | pages = 25–35 | doi=10.1007/3-540-09745-7_2| isbn = 978-3-540-09745-7 }} 49. ^1 {{Cite journal| last1 = Perlis | first1 = Alan J.| doi = 10.1145/947955.1083808| title = Epigrams on programming| journal = ACM SIGPLAN Notices| volume = 17| issue = 9| pages = 7–13|date=September 1982| url = http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epigrams.html| archiveurl = https://web.archive.org/web/19990117034445/http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epigrams.html| archivedate = January 17, 1999| quote = 6. Symmetry is a complexity reducing concept (co-routines include sub-routines); seek it everywhere}} 50. ^1 {{cite web|url=http://www.ibm.com/developerworks/library/l-pygen.html |title=Generator-based State Machines |work=Charming Python |first=David |last=Mertz |publisher=IBM developerWorks |date=July 1, 2002 |accessdate=Feb 2, 2011 |archiveurl=https://www.webcitation.org/5wCZa062h?url=http://www.ibm.com/developerworks/library/l-pygen.html |archivedate=February 2, 2011 |deadurl=yes |df= }} }} Further reading
External links
2 : Concurrent computing|Subroutines |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。