167

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

1
  • 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
    Commented Jan 14, 2011 at 8:53

3 Answers 3

139

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

26
  • 6
    One 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
  • 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. Commented Nov 20, 2011 at 4:20
  • 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. Commented Dec 15, 2014 at 18:20
  • 4
    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
    Commented Dec 20, 2014 at 20:55
  • 2
    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
    Commented Jan 6, 2015 at 12:16
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.

4
  • 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.
    – Benson
    Commented Apr 3, 2009 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
    Commented 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.
    – NalaGinrut
    Commented Apr 1, 2017 at 4:06
15

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.

3
  • 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
    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.
    – user746461
    Commented Oct 31, 2022 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.