Coroutine vs Continuation vs Generator

Question

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

Solution 1

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

I hope that helps, and I'm sure my explanation can be improved on quite a bit!

Solution 2

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.

Solution 3

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.

Comments

[nalply]

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?

[Mas Biru]

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 :)

[Benson]

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.

[nalply]

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.

[user1025901]

One nit: delimited continuations are functions, but undelimited continuations aren't: okmij.org/ftp/continuations/undelimited.html#delim-vs-undeli‌​m

[jkh]

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.

[cdunn2001]

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

[Linus Caldwell]

@cdunn2001: (comment by Winston) Python3.3 introduced the "yield from" expression which let you yield from sub-generator.

[Ivancho]

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

[jkh]

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.

[Ivancho]

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.

[jkh]

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.

[Ivancho]

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.

[El Ninja Trepador]

@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

[JCF]

In your first example, what is make_coroutine? What is happening in the first example? Can you provide an explanation?

[JCF]

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]

Also - what is different between a continuation and just simply calling return?

[jkh]

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

[jkh]

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.

[jkh]

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

[NalaGinrut]

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.

[Asad Saeeduddin]

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.

[FrankHB]

"Continuations are functions..." sounds like "stack frames are functions...". Absurd.

[jkh]

FrankHB, feel free to write a better explanation. Also, I didn't write that.

[IceFire]

The coroutine code has syntax errors for Py3 on my side?

[jkh]

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

[IceFire]

@KeithGaughan ah makes sense then. It seems that Py3 uses anyway much different syntax, but I found various different variants anyways, let's see

[jkh]

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

[IceFire]

@KeithGaughan I tested this because it's an obvious change but it's not really enough I'm afraid...

[jkh]

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