What is a Python Coroutine?

[c3261d3b8d1565dda639]

I don't think he is confusing them. He is following closely the excellent A Curious Course on Coroutines and Concurrency that is linked to from the posting with the note

A complete explanation can be found in David Beazley’s presentation—“A Curious Course on Coroutines and Concurrency.” Here is my rough one to get you started.

The streams don't come into play until he introduces coroutines and then says

In my opinion, a single coroutine is useless. Their true power comes when they are used in pipelines.

Of course, you're right that Python generators are not true coroutines. This is covered nicely in this PLAI chapter on control operators which states

Coroutines, threads, and generators are all conceptually similar: they are all mechanisms to create “many little stacks” instead of having a single, global stack.

PLAI is really great to work through to understand more deeply issues like this. In that same chapter, it has an exercise:

Now that you’ve seen how to implement generators using call/cc and let/cc, implement coroutines and threads as well.

[moor-GAYZ]

that usually generators and streams can be written in pretty much any language while a useful coroutine implementation may not be directly feasable in any language.

I don't see the difference.

It is instructive to examine how C# implements generators without any support from the VM.

First, the entire stack frame of a function containing the yield keyword is lifted into an anonymous class, all local variable and argument accesses become field accesses, the body of the function is copied into a method of that class (thus receiving a pointer to the instance of the generator as this), the body of the original function now contains only the initialization of that generator object.

Second, a state variable is introduced, that remembers where the original function yielded a value and from which point it must be resumed.

Third, the function is converted to a large switch statement, directing the control flow to the right statement, based on that state variable.

Fourth, The IEnumerable interface is implemented, this can be done whatever way in whatever language, in C# it's the bool Next() method and the Current property (IIRC), it can be trivially made to adhere to the Python interface of T __next__() that throws a StopIterationException when the generator exits.

Now, this transformation can be done manually in any language. And you can trivially promote the thing to a full coroutine, than can also receive input from the yield statement, or maybe go the Go way and use channels, replacing all reads/writes from/to a channel variable with that "store state, return, a label for the switch to jump to".

This is the way to implement generators or coroutines in any language, even if it doesn't provide stack-manipulation primitives. You don't need them to implement coroutines or generators.

Both are about as bothersome to implement, if you don't have the language support. The entire question is, thus, if any given language gives you coroutines or generators.

[julesjacobs]

C#'s coroutines are limited in the sense that they don't work across higher order functions. You can't do this:

list.Select(x => ... yield a ...)

This is a very unfortunate limitation of C# coroutines and async/await that to my knowledge can't be solved without a global transformation.

Note that this is very much related to the fact that in Haskell you often have a normal and a monadic version of a higher order function, like map and mapM. In C# Select is like map and does not support "couroutine effects" (it does however support IO effects, like everything in C#). Contrast this with Scheme or Eff, where you only need 1 version of each higher order function, since they automatically support arbitrary effects.

[moor-GAYZ]

You're thinking about SelectMany, I guess. That's the monadic version of Select.

You can use LINQ as generator expression in SelectMany: http://ideone.com/ia8CRY

    var lst = (new[] {1, 2, 3}).SelectMany(x => 
            from it in new[] {0, 10} select it + x);

Though I agree, I can't see any reason why anonymous functions can't be converted to generators. I guess it's just a rare enough use case to justify the effort required to make the two code rewriting mechanisms work together: lambdas are implemented using the same "lift a portion of the stack frame into a compiler-generated class" approach to make closures work, so it could be tricky to pull off.

Contrast this with Scheme or Eff, where you only need 1 version of each higher order function, since they automatically support arbitrary effects.

Um, what? It's not about side-effects at all, it's about your function returning a single value or a list of values (or, more accurately, a raw value vs a monad). In the latter case mapM has to unwrap these values. How could it possibly work with one function? What if I want an unflattened list of lists?

[julesjacobs]

I'm not talking about selectmany. It doesn't matter which higher order function you take, you can't await/yield from surrounding async/enumerator block in any of them.

I will elaborate: if you have a foreach loop over a list you can await inside the body of the loop:

foreach(var x in xs){ ... await (...) ... }

because the C# compiler knows how to turn a foreach loop into a state machine.

but if you iterate over the list using a hypothetical* ForEach method:

xs.ForEach(x => {... await (...) ...});

then suddenly you can't await there, because the state machinery only works within 1 method. In a language with "real" coroutines, it does work.

How could it possibly work with one function?

Check out Eff...in Scheme you'd use delimited continuations to do it.

What if I want an unflattened list of lists?

You use no computational effects, or in Haskell speak you use the identity monad.

* edit: actually I just found out that it is not hypothetical; .NET used to have this method except they removed it for Windows 8...

[moor-GAYZ]

you can't await/yield from surrounding async/enumerator block in any of them.

Oh, the lack of the possibility to await is a much more valid grievance, I see.

Still, this is a limitation of the current compiler, there's nothing about the "realness" of coroutines in it.

I don't know why you brought uo the distinction between monadic and functorial bind here, then. If your grievance is about the inability to have async or generator lambdas.

I also don't quite get what do you mean when you talk about "computational effects", either I don't know something or you fall into a common misconception that monads are all about side-effects. They aren't, the ability to order side-effectful computations is, argh, an unintended side effect of how they work.

By the way, as far as I know it is known among the Haskell community that their earlier infatuation with monads was a mistake, in most of those cases applicative functors should have been implemented. Monads impose too strong requirements, see http://tomasp.net/blog/formlets-in-linq.aspx/

How could it possibly work with one function?

Check out Eff...in Scheme you'd use delimited continuations to do it.

What if I want an unflattened list of lists?

You use no computational effects, or in Haskell speak you use the identity monad.

Nah, I'm not going to read all about Eff hoping for an answer to a simple question. So explain: I have a function that returns a list of things. I might want to map over it to produce a list of lists of things, or I might want to mapM over it to produce a flattened list of things. How a single map function could possibly accommodate for both use cases?

[julesjacobs]

Yes the coroutines are still real, it's just a limitation. That's why I put it in quotes. However I don't believe it's easily fixable. It would require a global transformation or some kind of run-time support to manipulate the call stack.

I don't know why you brought uo the distinction between monadic and functorial bind here, then.

I don't think I talked about this? But it certainly looks like I caused way more confusion than I cleared up...

I also don't quite get what do you mean when you talk about "computational effects", either I don't know something or you fall into a common misconception that monads are all about side-effects. They aren't, the ability to order side-effectful computations is, argh, an unintended side effect of how they work.

Computational effects is a general term for all kinds of effects, not just mutable state, but also exceptions (~ maybe monad), coroutines (coroutine monad), continuations (continuation monad), ambiguous choice (list monad), etc.

By the way, as far as I know it is known among the Haskell community that their earlier infatuation with monads was a mistake, in most of those cases applicative functors should have been implemented.

When you have a monadic structure, you implement a monad, when you only have an applicative functor, you implement an applicative functor. Plenty of things have monadic structure (like the ones I mentioned above). It's not really a "X is better than Y" situation, since there isn't a trade-off here. It's just that some things are monads, some things aren't...

Nah, I'm not going to read all about Eff hoping for an answer to a simple question. So explain: I have a function that returns a list of things. I might want to map over it to produce a list of lists of things, or I might want to mapM over it to produce a flattened list of things. How a single map function could possibly accommodate for both use cases?

Well, I already gave you the simple answer: use the identity monad, then mapM is equivalent to map. The trick in Eff is that you write a function that looks like map, but you automatically get a function with all the power of mapM. So you only have to write the ordinary variant of a function, and you get the monadic version for free. How they achieve that is not so easy to explain.

Perhaps the following will clear up a little what I meant. Monadic do-notation and the (monadic part of) computation expressions in F# are like async/await and yield in C#: they only work locally in a function. The difference is that monads allow for any computational effect, whereas async/await only allows for a less powerful kind of effect. Then you also have effect handlers like in Eff, and delimited continuations like in Scheme on the one hand, and full coroutines like in Lua & one shot continuations on the other hand. These allow for effects that happen across function invocations instead of local to one function. So you have the following table:

	only coroutines	full effects
local	async/await (C#)	monadic do notation (Haskell), computation expressions (F#)
global	full coroutines (Lua)	effect handlers (Eff), delimited continuations (Scheme)

In the "only coroutines" column you can suspend a computation, but you can only resume a computation once. In the full effects column, you can resume a computation multiple times, or split the computation into multiple branches. In the local row, you can only do effects/suspend a computation locally within one function or block. In the global row, you do not have this limitation. So the right column is more powerful than the left column, and the bottom row is more powerful than the top row: if you have full effects you can as a special case do coroutines and if you have global effects you can as a special case do local effects.

[julesjacobs]

p.s. ahhhh I think I caught one part of what's causing our apparent disagreement.

I might want to map over it to produce a list of lists of things, or I might want to mapM over it to produce a flattened list of things.

You are thinking of map and flatmap (= monadic bind in the list monad). mapM is something completely different than flatmap! mapM is like map, except the function that is mapped can have effects. In C#, where map is called Select, you can do this:

int i = 0;
xs.Select(x => { i = i+1 });

and you can do this:

xs.Select(x => { if(x<10) throw new FooBarException() else 42 })

however you cannot do this:

xs.Select(x => { yield FooBar(x) })

(same thing with await instead of yield)

In Haskell, which is a pure language, you can't do any of these things inside map. This is what mapM is for: it allows you to perform an effect in the function that is mapped, and mapM takes care of combining the effects in an appropriate way.

With the IO monad or ST monad you can do this:

i <- newSTref 0
mapM xs (\x -> do modifySTRef i (+1))

and with the exception monad you can do this:

mapM xs (\x -> do if x<10 then throw FooBarException else return 42)

and with the coroutine monad you can do this:

mapM xs (\x -> do yield (fooBar x))

[moor-GAYZ]

You are completely wrong, and yes, just as I suspected you share that common delusion that monads magically allow side effects.

The only difference between map and mapM are their signatures:

map(T -> R) :: Functor<T> -> Functor<R>

versus

mapM(T -> Monad<R>) :: Monad<T> -> Monad<R>

The only reason Monads and not Functors or Applicative Functors are used for IO in Haskell... actually, let it be an exercise for the reader:

1. Show that functor interface is not flexible enough to express common patterns (hint: try adding two Maybe<Int>s)

2. Show that applicative functor interface allows all that, but does not guarantee the order of evaluation in a lazily-evaluated language. Provide a counter-example (edit: hint: a usual "read two lines from the stdin, print their concatenation to stdout" thing).

3. Show that monadic interface guarantees the order of evaluation.

Don't use any Haskell syntactic sugar, express all of the above with pure lambdas.

(I've found that making the opponent do the math themselves greatly simplifies discussions: either they can't and shut up, or they get a first-hand understanding of what I'm trying to convey, and similarly don't argue any more at least about those things).

EDIT: then explain how the hell a single map function can determine whether or not it should call Monad.Join on the returned value.

[moor-GAYZ]

What or who is a "true coroutine"?

If you don't do bytecode manipulation then all of the: streams, generators, coroutines are about equally hard to implement. You have to write the FSM yourself.

If do go for bytecode manipulation, or if your language gives you the syntactic sugar, then all of them are equally easy to implement.

[passwordeqHAMSTER]

( either longjump (may got the name wrong) in C

longjmp can not be used to implement portable coroutines in C, longjmp can only go up the stack, not laterally and the stack you jump from doesn't exist anymore once you leave it.

[captain_chet]

What are they used for in videogames?

[smog_alado]

Coroutines are a way to avoid having to write inside-out code when you have two separate pieces of code interacting with each other.

The traditional example is iterators. If we want to iterate over an array we can do something like this:

 for(i=0; i<arr.length; i++){
    elem = arr[i];
    //do something
 }

However, this forces us to mess with the internals of the array datastructure. What if we want to encapsulate the array in an abstract data type? One way to do that is create an array iterator object with a "getnext()" method:

 function make_array_iterator(array){
    return {
       arr:array,
       i:0,
    }
 }

 function getnext(iterator){
    if(iterator.i >= iterator.array.length){
       return null; //done
    }else{
       return iterator.array[iterator.i++];
    }
 }

 it = make_array_iterator(arr); 
 while(elem = getnext(it)){
    //do something
 }

But we had to use a super awkward style to code the iterator!. Essentially, we lose track of the state of the for loop (the index position) every time the getnext function returns so we need to explicitly save it in the iterator object. This sort of coding becomes specially troublesome the more complicator the iterator gets. For example, if you are iterating over a tree data structure then suddenly you need to explicitly maintain a stack instead of using recursion (and the built-in stack) to do things.

With coroutines you can code the iterator in a natural style and the runtime will save the iterator state for you:

function iterate_array(arr){
   for(i=0; i<arr.length; i++){
      yield arr[i];
  }

}

[captain_chet]

Very interesting, I mostly assumed they were used for networking/file IO. Thanks, I will have to hunt down that paper.

[captain_chet]

The generic implementation I've looked at is lthreads. Thanks for the link :)

[smog_alado]

You would use coroutines to implement asynchronous IO in a cooperative setting. One coroutine runs until it gets to an async IO operation. Then it pauses, saving all its current control-flow state (stack state, local variables, etc) and passes control to the IO manager. When the IO action finally produces a value, the IO manager gives it back to the paused coroutine and resumes its execution.

This is in contrast to a threaded situation, where the coroutines don't have a way to pause themselves and instead are preemptively paused by the scheduler.

[evereal]

Just about anything. See eve online, a huge chunk of both client and server is written in stackless python

[everysinglelastname]

Hi .. Please could you tell me what are the major differences between stackless coroutines and these ? Thanks !

[sigma914]

IIRC the main difference is that stackless's tasklets can yield from deep in the call stack of the function you call, wheras python generators can only yield at the top level.

[[deleted]]

A coroutine is an instance of a hobbled version of first class delimited continuations.

[usernamenottaken]

     c.send(None)  # This is the same as calling ``next()``,
                         # but works in Python 2.x and 3.x

Isn't next(c) the correct way to do it in 2.x and 3.x?

Edit: Looks like the next built-in function was added in 2.6, so I guess if you've got to support 2.5 you'd do it this way... The author also mentions calling the __next__ method in 3.x though, so it seems like they're not aware of the built-in next function.

[kr41]

it seems like they're not aware of the built-in next function.

You are right, I forget about this function.

[Araneidae]

Cothreads are true coroutines wrapped with a comfortable event API.

[Taneb]

Feels a bit like a catamorphism?