165

What is the difference between a coroutine and a continuation and a generator ?

Iskuskov Alexander
  • 4,077
  • 3
  • 23
  • 38
Mehdi Asgari
  • 2,111
  • 3
  • 17
  • 18
  • 3
    I 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? – nalply Jan 14 '11 at 08:53

3 Answers3

141

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'.

starball
  • 20,030
  • 7
  • 43
  • 238
Keith Gaughan
  • 21,367
  • 3
  • 32
  • 30
  • 6
    One nit: _delimited_ continuations are functions, but _undelimited_ continuations aren't: http://okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim – Frank Shearar Sep 16 '11 at 20:36
  • 2
    That'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. – Keith Gaughan Nov 20 '11 at 04:20
  • 1
    Continuations are not functions, although they can be reified into functions. "That said, in most practical applications, when people says 'continuation', they're talking about partial/delimited continuations." Would you point to such usage of the term "continuation"? I've never met such usage. Also you gave an example for an undelimited continuation, by using call/cc. The operators for delimited continuations are usually "reset" and "shift" (they may have other names). – Ivancho Dec 15 '14 at 09:07
  • 4
    Let'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*. – Keith Gaughan Dec 15 '14 at 18:20
  • 2
    I'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. – Ivancho Dec 20 '14 at 20:55
  • 1
    Really? Aside from glossing over whether an undelimited continuation is a function or not, how exactly was my explanation of what a continuation is wrong? That's the *one* thing I said that might be called out as incorrect, and the only reason I did that was to keep the explanation understandable. – Keith Gaughan Dec 23 '14 at 01:58
  • 1
    Your 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. – Ivancho Jan 06 '15 at 12:16
  • 1
    @KeithGaughan Nah, he's just too busy trying to prove he's smarter than you... No way he's going to edit the answer :D – El Ninja Trepador Mar 17 '15 at 16:21
  • In your first example, what is make_coroutine? What is happening in the first example? Can you provide an explanation? – JCF Dec 08 '16 at 17:00
  • 1
    In your second example, does cc just implictly get created? Is this a real thing in Python or are you just making it up to explain what a continuation is? Are continuations actually in Python? – JCF Dec 08 '16 at 17:06
  • Also - what is different between a continuation and just simply calling return? – JCF Dec 08 '16 at 17:07
  • @user2247323 As far as make_coroutine(), it's been a while, and I can't remember. If I come up with a decent explanation, I'll post it. – Keith Gaughan Dec 09 '16 at 01:41
  • In the second example, 'cc' is created by callcc() and passed into foo. In that particular function calling the continuation *is* equivalent to using return; that's actually part of the point, as the return address on the call stack is a continuation. The value of an *explicit* continuation is that you can pass the continuation on like a normal function. Python does have kinds of continuations: any time you raise an exception, call a function, or return from one, you're using a type of limited continuation. There's no callcc() function in Python though. – Keith Gaughan Dec 09 '16 at 01:46
  • @user2247323 I took a read of the code again. `make_coroutine()` is a hypothetical function for turning a generator into a coroutine. At the time I wrote this, the 'asyncio.coroutine()' decorator and 'yield from' didn't exist, nor did the 'await' and 'async' keywords, which can also be used construct coroutines in a more general fashion. 'make_coroutine()' is akin to 'asyncio.coroutine()' in modern Python. – Keith Gaughan Dec 09 '16 at 01:59
  • 1
    `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.` Not really sure this is true. JS has generators and no coroutines, but you're free to pass in a value every time the generator yields. What you're not allowed to do is yield to something other than the caller from the generator. – Asad Saeeduddin Apr 02 '18 at 21:55
  • "Continuations are functions..." sounds like "stack frames are functions...". Absurd. – FrankHB Jul 30 '18 at 20:31
  • FrankHB, feel free to write a better explanation. Also, I didn't write that. – Keith Gaughan Aug 01 '18 at 18:15
  • The coroutine code has syntax errors for Py3 on my side? – IceFire Aug 30 '21 at 06:06
  • @IceFire The code was written against Python 2, which is why you're getting syntax errors. Also, the `make_coroutine` and `callcc` functions are purely hypothetical, just in case you're wondering. – Keith Gaughan Aug 31 '21 at 14:46
  • @KeithGaughan ah makes sense then. It seems that Py3 uses anyway much different syntax, but I found various different variants anyways, let's see – IceFire Sep 06 '21 at 08:19
  • @IceFire The main change needed to make the code more like Python 3 is to change `print ...` to `print(...)`. I'll have to test the code to make sure there aren't other changes needed. Regardless, the code isn't intended to be copied into a REPL and run out of the box anyway: it's using Python as pseudocode. – Keith Gaughan Sep 06 '21 at 12:31
  • @KeithGaughan I tested this because it's an obvious change but it's not really enough I'm afraid... – IceFire Sep 09 '21 at 10:02
  • @IceFire I know it's not enough, because, as mentioned before, there's no `make_coroutine` or `callcc` function in Python. CPython itself doesn't expose continuations as first class objects. PyPy does, via continulets, but it's not a standard part of the language (CPython de facto defines what's standard) nor do I have much experience with PyPy. – Keith Gaughan Sep 09 '21 at 10:56
34

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.

Andriy Volkov
  • 18,653
  • 9
  • 68
  • 83
  • 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 :) – Andriy Volkov Apr 03 '09 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. – Benson Apr 03 '09 at 21:45
  • 2
    A 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. – nalply Jan 14 '11 at 08: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. – NalaGinrut Apr 01 '17 at 04:06
13

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.

Yichuan Wang
  • 723
  • 8
  • 15
  • 4
    But in Python, all `yield` calls must be in the same function, which is called the "Generator". You cannot `yield` 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.) – cdunn2001 Jan 03 '13 at 23:24
  • 9
    @cdunn2001: (comment by Winston) Python3.3 introduced the "yield from" expression which let you yield from sub-generator. – Linus Caldwell Nov 23 '13 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. – Gqqnbig Oct 31 '22 at 04:17