Talk:Coroutine

From Wikipedia, the free encyclopedia

Contents

[edit] Ruby coroutines

Doesn't Ruby have coroutines? Someone should mention that. --68.35.244.188 05:25, 12 Aug 2004 (UTC)

Python also has coroutines, in the form of the recently (Python 2.3) added generator function. It even has a yield keyword. This could be used to build an excellent example for this article. —Preceding unsigned comment added by 138.38.32.84 (talk • contribs) 2004-11-03 13:26:19

Why did nobody add them? Is there a controversy about whether they really have coroutines?--87.162.67.249 22:13, 9 September 2007 (UTC)

I am not expert in Ruby, but I believe it has only continuations, not coroutines as such. There is a slight difference. Samohyl Jan 05:32, 10 September 2007 (UTC)

[edit] "Editorial" section removed

I removed the content of the Editorial section, on the grounds that it does not belong in an encyclopedia. I agree that the remaining content in the article is written from a POV that favors the use of coroutines, but the way to fix that is to rewrite the article from NPOV, not add a rebuttal to the article itself. The content follows. Neilc 04:35, 24 Oct 2004 (UTC)

[edit] Editorial

The author of this article clearly has a preference for coroutines over the more popular structures in modern, commercial programming languages. Popularity is by no means a justification for something. However, in this case the alternatives to coroutines are popular for good reason.

Coroutines allowed the "thread of execution", however it is implemented, to enter a function, process it for a while, return to the caller, and go back to the function where it left off while maintaining the state of local variables. This all sounds very useful. It is not. There are much better ways of accomplishing whatever task you wish to perform. I will address some of the issues the author mention above.

In situations in which a coroutine would be the natural implementation of a mechanism, but is not available, the typical response is to create a subroutine that uses an ad-hoc assemblage of boolean flags and other state variables to maintain an internal state between calls.

It is true that most procedural and object-oriented programming languages don't let you jump to the middle of a function. You can in standard Pascal using a goto statement, but it is a bad practice. It is such a bad practice that Borland prohibited it in its Turbo Pascal compiler.

Object-oriented languages such as Java and C++ provide a far more elegant solution. Encapsulate the state information and the operations in a class. The internal state persists between calls to the method because the internal state is associated with members of the class.

Object-oriented languages do not specifically provide a more elegant solution. You might as well argue that threads as a whole are unnecessary because you can model any number of threads in your application instead with a state machine. This is not eloquent -- using a state machine imperatively to simulate threads. It is much better and easier to write each object such that each object /believes/ it is in its own thread. This is much more natural than writing state machines. You should consider reading: http://www.stackless.com/ —Preceding unsigned comment added by 24.175.26.71 (talk • contribs) 2005-10-07 06:43:25

Threads resemble coroutines on steroids. Threads provide facilities for managing the realtime cooperative interaction of "simultaneously" executing pieces of code. Because they solve a large and difficult problem, they include many powerful and complex facilities and have a concomitantly difficult learning curve. When a coroutine is all that is needed, using a thread seems like overkill.

I do not consider threads to be complex, difficult to learn how to use, or overkill. Multithreaded programming was always simpler than using interprocess communication. In languages like Java, multithreading is extremely simple and easy to use. Two lines of code.

Thread myThread = new Thread(objectThatImplementsRunnable, "My Thread's Name");
myThread.start();

You can even combine these two lines of code into one if you like. So easy. And despite being so easy, threads are extremely efficient. Context switching is almost non-existent in threads. Plus you get pre-emptive multitasking, thread priority, and suspend/resume capability for free.

Threads and object-oriented programming are the way to go. Coroutines may be a nifty concept, but they can't do anything that threads and classes can't do more eloquently.

Coroutines are for many tasks easier than threads. Consider for instance you want to program a state machine. Without threads or coroutines, you need to remember state, and with each call of the procedure implementing state machine make a jump by the state. This will result in somewhat clumsy and hard-to-read code, because entry point must know how to deal with all states, not only outgoing ones. With threads, you could do this, but you also have to explicitly synchronize them (because you really don't need concurrency for this task). But coroutines make implementation of this easy and natural. For instance, this can be used to program agents in games, where each agent is essentially a state machine, and they interact. Then it nicely separates code for each agent from the rest (main loop), without hassle about synchronization and locking, because they are in fact executed sequentially. Samohyl Jan 10:36, 26 August 2005 (UTC)
I agree with this. You're missing the point if you think that coroutines and threads are tools for the same purpose. They are most certainly not. Pointedly, coroutines can be used (such as in Stackless Python) to provide thread-like behavior for a massive number of independent objects. For example, you could have 100,000 objects each of which is written in a thread-like manner. No real OS could manage that number of threads in a practical way. However, you can write such a system with coroutines. Note that your result is effectively cooperative multitasking, where threads traditionally use pre-emptive multitasking. —Preceding unsigned comment added by 24.175.26.71 (talk • contribs) 06:40, 7 October 2005 (UTC)

[edit] Coroutines originated in languages Simula and Modula-2,

BLISS programming language - what about this ? —Preceding unsigned comment added by 195.42.89.34 (talk • contribs) 2005-12-29 13:35:45

??? For that matter, they originated before BLISS. They were a recognized assembly-language technique. In fact I think that's how Knuth presents coroutines. Dpbsmith (talk) 14:46, 29 December 2005 (UTC)

[edit] Implementation does not require garbage collector

The Detailed Comparison portion contains

In contrast, coroutines, able to call on other coroutines as peers, are best implemented using continuations (which in turn are implemented using a garbage-collected heap) to track the flow of control

As demonstrated by the portable coroutines library linked at the bottom of the page, you don't need a garbage-collected heap to implement continuations. There's nothing unique about a continuation as an object and in fact since in many C libraries coroutines are not copyable (I think that's generally true) and have a defined lifecycle (when the coroutine hits the end of execution, it dies), there's not even a need for reference counting. One think that's interesting about coroutines is that the memory for one can be preallocated and trivially reused (making their creation rather cheap).

I'm going to update this wording. AnthonyLiguori

[edit] called vs. peer coroutines

I don't understand the difference described in this section. I looked for the terms on Google, but I didn't find any explanation. Maybe an example (especially of language that makes this distinction) or at least a citation would be helpful. Samohyl Jan 07:27, 16 July 2006 (UTC)

(moved here)

Hi, Whiner01. Regarding your recent edits at coroutine (about peer and called coroutines). I don't understand the distinction from your description, and I tried to look for some reference of this terminology, but failed. Can you provide an example of a language that actually makes such distinction, and explain the actual difference between the two kinds of coroutines? I know coroutines in Python, and there is no need for such distinction. Samohyl Jan 18:06, 17 July 2006 (UTC)

I came across the word "coroutine" somewhere. I wanted to pin it down because so many times i encounter the term "coroutine" in contexts where it is not justified. "Coroutine" is too often a buzzword whose meaning is not known to the person using it. Google IS sparse on the term. Forgotten by many and puffed out of shape by others.

I was frustrated by an article that didn't tell me much. The discussion page shows a removal of an editorialization on whether or not coroutines are as neat as threads. Very profound.

I tried to roll in what i learned about coroutines from assembly language. I didn't want to exclude any possibilities. Some concrete examples from programming languages might help, but i worry if the language implementations don't exclude meaningful possibilities. If a language "fails to make a distinction", could it mean that they omitted a major form, or it could mean that they found a unification that was not expressed here before, and that i also missed? Can you provide a link to a good discussion of the Python implementation of coroutines?

The few examples on the page and near-at-hand are not very informative. They fail to show or tell why coroutines might be useful, and why understanding of coroutines might be educational. The similarity to subroutines is important, but so is the similarity to threads. The example(s) here don't have a complete syntax.

I re-embroidered from what was here, and so i might be out on a limb. BUT, the examples clearly fall into one style of usage or another. Some speak of "call", or at least "return"ing of values, and some speak of "yield"ing control. The discussions themselves have created two styles, with two grammars. I just spelled it out. I admit i am somewhat lost as to how coroutines are coded in a compiled language. Greater complexities come from the possibility of passing parameters. Parameters can make it so gritty, that I wonder if they bother with parameters at all.

I can easily envision a main program with a coroutine, the coroutine having the maximum resemblance to a subroutine. The coroutine declares formal parameters. The program can "call" the coroutine from many places with actual parameters. At each call, the new parameters are re-passed to the coroutine code. The co-routine starts or resumes each time it is called. It can return from many places. In most languages a subroutine can return only one value, which stores back into the main program by an assigment of the result of the coroutine call. There is an asymmetry here: the main program can jam in multiple parameters, but it can only get back one. But i guess the coroutine could modify its arguments, just like subroutines do. And one earlier assumption need not be locked in: maybe the coroutine can declare different formal parameters at each re-entry point. Why not?

Code for a coroutine -- in a language that uses only one set of formal parameters for the coroutine:

 Coroutine add3(a):
 static t
 do
   t=a
   return -1
   t+=a
   return -1
   t+=a
   return t
 loop

Code for a coroutine -- in a language that uses one set of formal parameters for each [re-]entry:

 Coroutine add3:
 do
   co-entry(a)
   return -1
   co-entry(b)
   return -1
   co-entry(c)
   return a+b+c
 loop


Putting the coroutines on a more equal standing requires a deeper rearrangement of the program syntax. Both coroutines need to have formal parameters declared -- either once at the top, or once at each re-entry. But then how does the first co-routine get started? If a co-routine has declarations at the top, then it cannot also be a main program. There has to be a stub of a main program that falls into one coroutine or the other. How does one of the coroutines get to be declared the main coroutine? Or does the main program have to call one of the coroutines? But then there are two ways in, co-call and call -- not very elegant.

If we allow that there is an "acceptor" declaration to receive formal parameters, the coding of the coroutines will show something interesting. The first co-routine to execute has a co-call before the following accept clause. All other co-routines have an accept clause preceding any co-call statement. A reminder that parameter passing complicates things? Or just a reminder that there has to be a main program.

So, how are coroutines declared in Python, etc.?

--Whiner01 06:07, 18 July 2006 (UTC)

Support of coroutines under several languages seems to consist of pages of debate on how it should be done. Support in other languages seems to involve schedulers, which is not what coroutines are supposed to be about. In other languages, coroutines "can be executed concurrently", so they are something completely unrelated to previous discussions.

--Whiner01 06:36, 18 July 2006 (UTC)

First, before I address your questions, I must said that I consider your changes to article very messy and confusing (both stylistically and factually). Could you please refrain from editing while we have this sorted out? As you said, you have little knowledge of coroutines yourself, so you probably should think twice before making substantial changes to this article, and also the terminology you use may well be unsuitable for Wikipedia, according to WP:OR policy (I am not such a big expert too, so that's why I am actually asking for references to support your claims or terminology).
To your question about Python. Python coroutines are similar to standard Python functions (which can return many values in single pass, thanks to Python tuples or dictionaries), but treated quite differently. If the coroutine is first called, it will return another callable object, which then remembers its state (both instruction pointer and local variables) and can be called repeatedly, and also another parameters can be passed into it. So the first call is very different from subsequent calls. The coroutine returns from the subsequent calls using yield keyword (which is also way how the compiler recognizes it as a coroutine). The reasons for this particular implementation are historic, but though it can look ugly from inside, the usage tends to be pretty elegant actually. The discussion of Python coroutine implementation can be found in the PEPs [1] and [2].
I think the problem you have with coroutine is that you want them to have work in the same way as normal subroutines. But they are different - the coroutine needs to be initialized to work properly. Also, the coroutines are not here to address the problem with passing multiple parameters out of a function - you can pass structure to do that. Also, I don't think it's good idea to allow jump anywhere into the same coroutine (with perhaps different input parameters), just as it isn't a good idea to allow this for a normal function; this is an assembler way of doing things, not a high-level language way (it's almost like infamous goto statement).
I hope I addressed your questions. Samohyl Jan 18:02, 18 July 2006 (UTC)
Just to clear up things up: Python does not have true coroutines, in the sense that other coroutine-supporting languages use the term. What PEP 342 defines is a simple enhancement to Python's generator functionality, which makes it easier and more convenient to implement (some would say "emulate") what real coroutines do (that's why the PEP title is "Coroutines via Enhanced Generators"). --Piet Delport 04:15, 19 July 2006 (UTC)

I have again stumbled into a muddy topic. I can't yet cite Knuth yet because I have to go and find a paper copy of his foundational computer writings.

You are free to inject facts into the article.

For example, the very first sentence of the article contradicts your claim that coroutine is not a subroutine: "In computer science, coroutines are program components that generalize subroutines ...". (The first sentence is of course wrong. Many implementations of coroutines work that way, but a coroutine can be other things.)

The examples shown in Python also fail to provide any counter-example. They only show coroutines that are called and then return values by yielding, as if that was the only kind of coroutine.

The poorly written example in the article shows a different kind of coroutine using "yield to" which implies that the coroutine gets to decide which other coroutine it yields to! (Assuming there are more than two.) That is a distinct thing. I don't see "yield to" in any other examples. Maybe "yield to" does not exist -- but then it's not my facts that are wrong -- the example predates my edits. But coroutines go back to the assembler era, and "yield to" surely existed somewhere.

Coroutine is first of all a concept! The idea of cooperating equals. Two patches of code in the same program, both written as if they are the main program. And switching between each other instantly and effortlessly, or at least as easily subroutine calls and without ever involving a separate thread or a scheduler.

The concept quickly fragments, even before implementation begins. Coroutines can be done in assembler because everything is "roll your own". Similarly, in many languages, coroutines can be done as "roll your own" using switch statements and state variables. After that, macros to hide the ugly switch statements built into the code.

It is hard to roll all of the coroutine possibilities into a compiled language. It is easier to make an elegant version of coroutines by omitting some of the possibilities. A called coroutine fits very neatly into the compiled era. The main program can freely call subroutines and coroutines; subroutines and coroutines can freely call subroutines and coroutines. Even so, I'm surprised it took so long for a called coroutine to get some standard keywords.

Complicating the use of the term coroutine is that people are constantly finding other meanings for it. In "BETA" (i think), they talk about coroutines running "concurrently". WTF.

--Whiner01 01:31, 19 July 2006 (UTC)

I thought about it a little and I think I understand what you mean. When you call a coroutine in Python, it works much as a function call, ie. the return address is recorded somewhere, and you can track the path back (by yielding). But you are right, in the example and perhaps other languages it's more like a jump (or goto) into a function. So, back to the article. Perhaps we could simply say that resuming a coroutine is in some languages like a call (ie. the return address is recorded) and in other languages it is (perhaps) as a jump or goto into a function (so the return address is lost). If you agree, I will rewrite the first paragraph (after the intro) in this sense. Samohyl Jan 19:14, 19 July 2006 (UTC)

I ran out of time to tinker with this one. (Possibly an "event horizon" effect. The article stops getting needed edits or rewrites when it gets too big or complicated to edit or rewrite on one sitting.) In the past I have gotten away with making substantial improvements to pages i did not understand, learning as i go. For example, Fat binary. I hypothesized that a utility must exist that can "remove the fat' from a fat binary. Another editor provided the fact, a utility called "lipo". Under Coroutine, i hypothesized that there are coroutines that can return but not yield. It apparently works that way under C#, with a "yield return" statement.

There are huge problems with the term as "Coroutine" as commonly used and discussed. There is the original notion, predating the popularity of threads and multiprocessing. Coroutines are still the ultimate lightweight thread, even in the days of threading, because of the infinitesimal consumption of resources and the instantaneous [micro-]context switching. Knuth was not the first; the idea of two main programs that trade off has been in print since 1958. Details of the original notion and Knuth's notion, which i have not yet looked up. Many many implementations, home-grown under assembler and many languages. Implementations in languages, most of which are faulty or incomplete, tedious, risky, etc. Modern non-implementations that include fake co-routines using threads, etc. People who think that their particular implementation defines the concept.

Call and Return have native hardware support and acceleration. The method of passing mountains of arguments through the same call-and-return stack is an outgrowth of necessity even for assembly-language programs, which is formalized and highly used in compiled languages. Allocating all local or temporary (non-"static") variables onto a bloated call-and-return stack is another method best managed by languages. It provides for very quick (instant) disposal of the temporary variables. (Passing data through the stack also provides for the helpful and useful "buffer overrun" errors that cross up data and addresses, making every compiled program vulnerable to hijacking.)

Coroutines are far from standardized. Coroutines have no hardware support. Support in languages, if any, is in its infancy. There are many complications and many possibilities for implementation. The possibility of parameters and return values adds its own complexity. Each implementation fails to deliver most or all of the possibilities and adds unnecessary complications of its own. Giving a coroutine every functional possibility probably complicates the support structure so much as to nullify the advantages. Implementing coroutines is supposed to be simple, but (for example) how does one allow recursive [called] coroutines? (or does recusrsing mean anything at all?)

In some languages (or pseudo-languages), you "call" a coroutine and then "resume" the coroutine. But then they say you can "call" it every time and it figures out what to do. A co-routine that does a "yield return" then has no way of actually ending -- the code can fall off the end. Does that code implicitly loop, or does the coroutine die somehow? Yield and return (or "yield return") are far different concepts.

Coroutines that are implemented allowing "yield TO" are vastly different from the callable kind. The main program becomes implicitly a coroutine that can be yielded to.

--Whiner01 08:25, 23 July 2006 (UTC)

See my earlier comment: what you seem to be talking about here (the feature found in C#, Python, and such), are not coroutines at all, but generators. Even though both concepts involve control flow, and both use the word "yield" (to mean various things), they're two distinct things, using two different techniques to solve two different sets of problems.
(Things get slightly confused by the fact that you can implement generators in terms of coroutines, and vica versa (with a bit more trouble), but that does not make them any more similar. The situation is sort of like closures versus objects: either can be implemented entirely in terms of the other, but despite that they don't bear much resemblance in terms of how they're usually used, implemented, and reasoned about.) --Piet Delport 21:34, 24 July 2006 (UTC)

nop 12:32, 20 September 2007 (UTC)

I just wanted to know what coroutine is about. Unfortunately, the introduction was not very clear. I found that Simon Tatham's intro is far more intuitive than the gibberish cited in external links. I tried to modify the introduction to make it more comprehensive.


[edit] Lua coroutines

Someone should note that coroutines are standard in lua. —Preceding unsigned comment added by Chokosabe (talk • contribs) 2007-04-01 13:33:56

[edit] C# yield return statement

Does the yield return statement in C# fit in here? 220.245.146.199 11:47, 13 September 2007 (UTC)

If it specifies where it's yielding to, then yes; otherwise, add it to generator (computer science). EdC 21:43, 13 September 2007 (UTC)

[edit] Green Thread?

The definition of Green Threads seems identical to the historic definition of Coroutines. Only if you insist that a Coroutine cannot suspend in a subroutine (i.e. suspend when there is call stack or context) would there be any difference.

The term Green Thread is quite "new". Coroutines in Simula (and early C++ versions) worked exactly like Green Threads. DRW - Oct 8, 2007 —Preceding unsigned comment added by 207.59.232.138 (talk) 15:55, 8 October 2007 (UTC)