What is the difference between a coroutine and a continuation and a generator ?
-
3I wonder if coroutines and continuations are effectively equivalent. I know it is possible to model coroutines with continuations, but is it possible to model continuations with coroutines or not because continuations are strictly more powerful?– nalplyCommented Jan 14, 2011 at 8:53
3 Answers
I'll start with generators, seeing as they're the simplest case. As @zvolkov mentioned, they're functions/objects that can be repeatedly called without returning, but when called will return (yield) a value and then suspend their execution. When they're called again, they will start up from where they last suspended execution and do their thing again.
A generator is essentially a cut down (asymmetric) coroutine. The difference between a coroutine and generator is that a coroutine can accept arguments after it's been initially called, whereas a generator can't.
It's a bit difficult to come up with a trivial example of where you'd use coroutines, but here's my best try. Take this (made up) Python code as an example.
def my_coroutine_body(*args):
while True:
# Do some funky stuff
*args = yield value_im_returning
# Do some more funky stuff
my_coro = make_coroutine(my_coroutine_body)
x = 0
while True:
# The coroutine does some funky stuff to x, and returns a new value.
x = my_coro(x)
print x
An example of where coroutines are used is lexers and parsers. Without coroutines in the language or emulated somehow, lexing and parsing code needs to be mixed together even though they're really two separate concerns. But using a coroutine, you can separate out the lexing and parsing code.
(I'm going to brush over the difference between symmetric and asymmetric coroutines. Suffice it to say that they're equivalent, you can convert from one to the other, and asymmetric coroutines--which are the most like generators--are the easier to understand. I was outlining how one might implement asymmetric coroutines in Python.)
Continuations are actually quite simple beasts. All they are, are functions representing another point in the program which, if you call it, will cause execution to automatically switch to the point that function represents. You use very restricted versions of them every day without even realising it. Exceptions, for instance, can be thought of as a kind of inside-out continuation. I'll give you a Python based pseudocode example of a continuation.
Say Python had a function called callcc()
, and this function took two arguments, the first being a function, and the second being a list of arguments to call it with. The only restriction on that function would be that the last argument it takes will be a function (which will be our current continuation).
def foo(x, y, cc):
cc(max(x, y))
biggest = callcc(foo, [23, 42])
print biggest
What would happen is that callcc()
would in turn call foo()
with the current continuation (cc
), that is, a reference to the point in the program at which callcc()
was called. When foo()
calls the current continuation, it's essentially the same as telling callcc()
to return with the value you're calling the current continuation with, and when it does that, it rolls back the stack to where the current continuation was created, i.e., when you called callcc()
.
The result of all of this would be that our hypothetical Python variant would print '42'
.
-
6One nit: delimited continuations are functions, but undelimited continuations aren't: okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim Commented Sep 16, 2011 at 20:36
-
2That's a good point. That said, in most practical applications, when people says 'continuation', they're talking about partial/delimited continuations. Bringing in the various other kinds of continuations would've muddied the explanation up somewhat. Commented Nov 20, 2011 at 4:20
-
4Let's start off with the fact that it's five years since I wrote this. You're somewhat late to the party. Secondly, I know that undelimited continuations aren't functions, but you about you try explaining how they work without referring to them as such while also keeping the language straightforward. From the point of view of the average programmer, the fact that an undelimited continuation doesn't return just makes it a one-shot function, which isn't correct as per the definition of what a function is, but it's at least understandable. Commented Dec 15, 2014 at 18:20
-
4I'm not late for the party since this is the first result I get in google when I search "coroutine vs generator". I was hoping to find some good information about their differences. Anyway I found it elsewhere. And I'm not the first one to point that your explanation about continuations is wrong. The problem is that someone will get it wrong and possibly be confused later when she or he meets the same word used for something different.– IvanchoCommented Dec 20, 2014 at 20:55
-
2Your answer is far from being understandable, besides being incorrect. The iterators returned by the generators can accept arguments (check JavaScript generators). " Generators, also known as semicoroutines, are a special case of (and weaker than) coroutines, in that they always yield control back to the caller (when passing a value back), rather than specifying a coroutine to jump to" (Wikipedia). You can implement lexers and parsers separately without using coroutines (I did it many times). I already wrote about the continuations. And please use @Ivancho, so I can read your comments.– IvanchoCommented Jan 6, 2015 at 12:16
Coroutine is one of several procedures that take turns doing their job and then pause to give control to the other coroutines in the group.
Continuation is a "pointer to a function" you pass to some procedure, to be executed ("continued with") when that procedure is done.
Generator (in .NET) is a language construct that can spit out a value, "pause" execution of the method and then proceed from the same point when asked for the next value.
-
I realize the answer may not be accurate but at this level of question I tried keeping it simple. Besides, I don't really understand all this myself :) Commented Apr 3, 2009 at 21:30
-
A generator in python is similar to the C# version, but is implemented as a special syntax for creating an instance of an iterator object, which returns the values returned by the "function" definition you provide.– BensonCommented Apr 3, 2009 at 21:45
-
2A small correction: "...including call stack and all variables BUT NOT THEIR VALUES" (or just drop "all variables"). Continuations don't preserve the values, they just contain the call stack.– nalplyCommented Jan 14, 2011 at 8:50
-
No, continuations are not "pointer to a function". In the most naive implementation, it contains a pointer to function and an environment holds the local variables. And it never return unless you use something like call/cc to capture it with a return value. Commented Apr 1, 2017 at 4:06
In newer version of Python, you can send values to Generators with generator.send()
, which makes python Generators effectively coroutines.
The main difference between python Generator, and other generator, say greenlet, is that in python, your yield value
can only return back to the caller. While in greenlet, target.switch(value)
can take you to a specific target coroutine and yield a value where the target
would continue to run.
-
4But in Python, all
yield
calls must be in the same function, which is called the "Generator". You cannotyield
from a sub-function, which is why Python's are called semi-coroutines, while Lua has asymmetric coroutines. (There are proposals to propagate the yields, but I think those only muddy the waters.) Commented Jan 3, 2013 at 23:24 -
9@cdunn2001: (comment by Winston) Python3.3 introduced the "yield from" expression which let you yield from sub-generator. Commented Nov 23, 2013 at 12:58
-
@LinusCaldwell,
yield from
is still written in the generator, not within an arbitary function that may or may not be called in a generator. In that sense, Python's coroutine is yet stackless.– user746461Commented Oct 31, 2022 at 4:17