Difference between CSP (channels) and coroutines (yield)
Elazar Leibovich
the similarity between Go's channels, and, say, python's coroutines.
For instance, given an input channel in go
ch := make(chan int)
go func(ch chan<- int) {
...
ch <- val
...
}(ch)
fromChan := <- ch
go func(ch <-chan int) {
val := <- ch
}(ch)
toChan
an equivalent python version would be
def f():
...
yield val
def g():
val = yield
ich = f()
och = g()
fromChan = ch.next()
och.send(toChan)
The only difference seems the limited scheduling in coroutines, that
limits cpu usage, but the expressive power seems identical.
Another difference is that a specific channel is coupled with the
implementation using it. But can you think of a real example where
this is really important? You can always emulate two goroutines
sending to the same channel with a single coroutine yielding the
output of two coroutine.
For example, the power-series example in Go, can be expressed in a
similar manner by coroutines, as a teaser, here's multiply by constant
def Cmul(c,ps):
def f():
while True:
yield c*ps.next()
return f()
the lexer example can be emulated with coroutines in similar way.
Are they indeed similar, or am I missing something? I'll be very glad
if you could come up with something that is difficult to express with
coroutines, but easy with channels.
Ian Lance Taylor
> Are they indeed similar, or am I missing something? I'll be very glad
> if you could come up with something that is difficult to express with
> coroutines, but easy with channels.
I don't know much about Python's coroutines. I guess my first question
would be whether they can support something like (untested):
struct Request {
op int
reply chan int
}
func Server(reqs chan Request) {
for {
r := <-reqs
switch r.op {
case O1, O2, O3:
r.reply <- serializedOp(op)
case O7, O8, O9:
go func() {
r.reply <- parallelOp(op)
}()
}
}
}
The point of this approach is that some operations are serialized, some
can be run in parallel. So that the clients don't get confused, each
client passes in the channel used to send the reply.
What I'm trying to get at is that it's easy and sometimes useful to send
a channel on a channel. Can you do an equivalent operation using Python
coroutines?
Ian
Russ Cox
as Erlang's processes, tie the communication to a specific
process. In Go, the communication can go to any goroutine
that is using a specific channel. The channel represents
the ability to communicate, and it can be passed around
as a first-class value.
One thing you cannot implement with Python's coroutines,
then, is something where you do
c := make(chan int)
and then kick off 5 goroutines generating data on c and
10 goroutines consuming data on c. That kind of communication
pattern is impossible when the act of communication is always
targeted at a specific coroutine. And while it's a simple example
it's not a made up one. I've used communication patterns
like that in my own programs before.
Russ
Gustavo Niemeyer
> def f():
> ...
> yield val
Please note that this is a generator, not a coroutine, and it has
several limitations in comparison to a real channel.
For instance, the f function is the only scope in which you can emit a
value out of this generator. Go channels are first class values that
may be passed around in your program, used by multiple senders and
receivers, be bufffered so that the sender doesn't necessarily block,
etc.
Another very interesting distinction between generators and channels
relates to the order of processing. In the function you provided f
will _start_ running to build the next value at the time you _ask_ for
the next value. In Go channels, even if they are not buffered, they
will block when they're ready to _deliver_ the next value, and as soon
as the next value is consumed they will start processing the follow up
item.
In practice:
>>> def f():
... for i in range(5):
... print "Building item"
... yield "item"
...
>>> g = f()
>>> g.next()
Building item
'item'
>>> g.next()
Building item
'item'
--
Gustavo Niemeyer
http://niemeyer.net
http://niemeyer.net/plus
http://niemeyer.net/twitter
http://niemeyer.net/blog
-- I'm not absolutely sure of anything.
Nigel Tao
> Are they indeed similar, or am I missing something? I'll be very glad
> if you could come up with something that is difficult to express with
> coroutines, but easy with channels.
You can also select on multiple channels in Go. I don't know if you
can do so with Python coroutines.
Elazar Leibovich
Python's coroutines, like CSP's original model as well
as Erlang's processes, tie the communication to a specific
process.
One thing you cannot implement with Python's coroutines,
then, is something where you do
c := make(chan int)
and then kick off 5 goroutines generating data on c and
10 goroutines consuming data on c.
Elazar Leibovich
On Dec 2, 1:41 am, Gustavo Niemeyer <gust...@niemeyer.net> wrote:
> Hey Elazar,
>
> > def f():
> > ...
> > yield val
>
> Please note that this is a generator, not a coroutine, and it has
> several limitations in comparison to a real channel.
About the limitations, please see my response to Russ, I think most of
them relate to the scheduler.
About the terminology, I must recommend the paper Coroutines in
Java[1]. I think it's OK to call those coroutines, as the paper
states:
> In contrast to other programming language concepts (e.g., continuations), the
> semantics of coroutines have no strict de nition. Coroutines may not even be
> recognizable as such, and depending on their semantics and expressiveness they
> are called generators [13, 18], coexpressions [13], bers [23], iterators [18], green
> threads [24], greenlets [22], or cooperative thread
[1] http://ssw.jku.at/General/Staff/LS/coro/CoroIntroduction.pdf
Jim Whitehead II
There are certainly similarities between coroutines and channels, but
I do not believe it goes as deeply as an isomorphism (but I haven't
given that much thought). I also think you're massively
over-simplifying things by saying that "the limitations are in the
scheduler", because you wind up pushing the operational semantics of
channels into the scheduler yet claim you don't need to consider them.
This can be seen in your response to the example Russ gave you. He
asked for a single channel, where there are five producers and 10
consumers on the channel. In Go, this definition is quite simple, and
the implementation is not tied to any specific scheduler at all, but
rather to the semantics of the channel data structure in the runtime.
Your solution has quite different behaviour in that the scheduling
(round robin) is included in the implementation itself.
So not only do you have to have a scheduler at the top level to make
your program "go" in the first place, but you also need to implement
your own scheduler on a process-by-process basis and I think this is a
severely limiting factor that should not be overlooked.
I think if the question is: "Can you implement channels using
coroutines in a way that allows for concise and disciplined programs",
then I think the answer is yes. I just don't think you can discard the
scheduling issue and call it a done deal.
Having recently implemented a naive channel implementation and
scheduler for coroutines in the Lua programming language, I can tell
you that getting the details right to match even basic channel
semantics is not straightforward, but a fun exercise nonetheless.
- Jim
roger peppe
> It sure matters to the scheduler, but does it really give you more
> expressive power? (as implied in Rob Pike's lectures). Here's the Leibovich
> Coroutine Conjecture:
>
> Given an evil scheduler, goroutines and coroutines are isomorphic.
using generators, how would you implement the pattern where a single goroutine
generates output for more than one channel?
to give a concrete example, how would you implement the following
code using python generators?
http://play.golang.org/p/lKBbS56f-n
package main
import "fmt"
func main() {
g0, g1 := generate("counting the number of some arbitrary values")
even, odd := count(g0, 'e'), count(g1, 'o')
for i := 0; i < 2; i++ {
select {
case x := <-even:
fmt.Printf("%d even 'e's\n", x)
case x := <-odd:
fmt.Printf("%d odd 'o's\n", x)
}
}
}
// count returns number of x's in found in c.
func count(c <-chan int, x int) (<-chan int) {
r := make(chan int)
go func() {
sum := 0
for i := range c {
if i == x {
sum++
}
}
r <- sum
}()
return r
}
// generate sends all even-indexed runes in s to the first
// returned channel, and all odd-indexed runes to the other
// returned channel.
func generate(s string) (<-chan int, <-chan int) {
even := make(chan int)
odd := make(chan int)
go func() {
i := 0
for _, r := range s {
if i % 2 == 0 {
even <- r
}else{
odd <- r
}
i++
}
close(even)
close(odd)
}()
return even, odd
}
Gustavo Niemeyer
> them relate to the scheduler.
The limitations relate to all of the things this thread already
pointed out. Buffering, scheduling, handling them as first class
values, etc.
> About the terminology, I must recommend the paper Coroutines in
> Java[1]. I think it's OK to call those coroutines, as the paper
> states:
If you go down that path, you can call a normal function as a more
limited form of coroutine as well. It's surely true, from a
theoretical standpoint, and if you abuse the system enough you can
even create more powerful coroutines on top of that. We tend to
specialize terminology over time precisely to more properly describe
the behavior of things.
That said, this is a rabbit hole. There's no right or wrong, and no
benefit in attempting to establish a shared point of view for either
of us.
Elazar Leibovich
using generators, how would you implement the pattern where a single goroutine
generates output for more than one channel?
to give a concrete example, how would you implement the following
code using python generators?
http://play.golang.org/p/lKBbS56f-n
#!/usr/bin/env python# coroutine equivalent of http://play.golang.org/p/lKBbS56f-n
def generate(s,even,odd):for i,c in enumerate(s):if i%2 == 0:even.send(c)else:odd.send(c)
def count(char):def count_(char):sum = 0while True:c = yieldif c == None:breakif c == char:sum += 1yield sumrv = count_(char)rv.next()return rv
def main():c1,c2 = count('e'),count('o')generate("counting the number of some arbitrary values",c1,c2)print("%d odd %s"%(c2.next(),'o'))print("%d even %s"%(c1.next(),'e'))
if __name__ == '__main__':main()
Jim Whitehead II
>
>
> On Fri, Dec 2, 2011 at 12:11 PM, Jim Whitehead II <jnwh...@gmail.com>
> wrote:
>>
>>
>>
>> There are certainly similarities between coroutines and channels, but
>> I do not believe it goes as deeply as an isomorphism (but I haven't
>> given that much thought). I also think you're massively
>> over-simplifying things by saying that "the limitations are in the
>> scheduler", because you wind up pushing the operational semantics of
>> channels into the scheduler yet claim you don't need to consider them.
>
>
> correctly.
>
> Seeing Rob Pike's lectures, I understand that he claims there that CSP can
> give you better expressibility, even if you don't care
> about multi-threading. He give examples of code which should run in a single
> thread, but is more expressible in terms of goroutines.
>
> What I meant to claim is, that if you do not care about multi-threading,
> the expressibility of CSP is equivalent to the expressibility of coroutines.
> If you don't care about multi-threading, then obviously you don't care what
> will your scheduler do, or who of the goroutines will get the CPU when.
>
> Given that, problems with multiple consumers or producer are definitely
> cases where you do care about multi-threading, so they are irrelevant to my
> claim. Indeed those kind of problems don't lend themselves nicely to the
> coroutines paradigm. This is maybe what I tried to express with the "evil
> scheduler". If you really need a scheduler, with coroutines you'll have to
> reimplement it. If your problem is not multi-threaded, then by definition
> you don't care about threads. Therefor you won't mind which scheduler do I
> use.
>
> I still think that goroutines won't help more than coroutines for
> single-threaded problems, and I'll still be glad to be proved wrong (say, a
> single-threaded problem whose solution is hard to express with coroutines,
> but easy with CSP).
Ah but you are using confusing terminology, and the way you're talking
here makes it a bit more easy to explain what is going on (and where
some of the confusion is coming from).
## CSP versus Go
First, the CSP process algebra is not the same as goroutines and
channels in Go, they are quite different in several ways. CSP uses
globally named channels that are not first class. CSP also includes
several ways of composing functions that just aren't a part of stock
Go, you'd need to implement them on your own.
The Go concurrency model is certainly derived from the process/channel
model that was advocated by Hoare, and appears quite close to the
language that appeared in its predecessor languages, as well as occam
(a much closer derivative of CSP). I may be splitting hairs here, but
I think it is an important distinction to make!
## Coroutines
Coroutines are a generalisation of subroutines that allow for the
suspension (yield) and the resumption (resume) at multiple points.
They are a fantastic abstraction that allows you to think about your
code in terms of simple sequential functions, but with some notion of
the "other", coroutines that themselves can be suspended and resumed.
A common extension of coroutines takes the yield/resume functionality
and bundle it together with a way to pass values to (and return values
from) the coroutines. This can be seen in the coroutine library for
Lua:
coroutine.yield(1,2,3) -- returns 1,2,3 to the corresponding resume call
coroutine.resume(1,2,3) -- returns 1,2,3 to the corresponding resume call
So coroutines know that they will be suspended, and they can
communicate with the 'other' without any extra machinery. There's also
no need for an explicit scheduler if everyone knows what everyone else
is going to do, but that's neither here nor there.
## Goroutines
A goroutine (by itself) is the execution of a method of function call
that is possibly executed alongside other goroutines within the same
address space. They have precisely one entry point, and although they
have an exit point, they cannot return values via this exit point.
In this way, goroutines are severely limited compared to goroutines.
They might be suspended by a scheduler, but they cannot choose to
suspend themselves other than breaking into the Go runtime. Even if a
goroutine can manage to suspend itself, it cannot resume another
goroutine. There is no way to pass information into, or get
information out of a goroutine without using references or other
trickery.
Enter the channel, which you talked about in your initial post.
Channels are a way to provide goroutines with a method of interacting
with the "other".
When using a *synchronous* channel, these send and receive sites seem
quite similar to the yield and resume calls you might see in a
coroutine. A send is a yield that exports some information, while a
receive is a resume that can import some information.
The concepts of coroutines, goroutines, and channels are certainly in
the same family of concepts and you can implement parts of one in the
others without much heartache. But there is a reason that they are
distinct concepts, and that is the context in which they exist.
So it really depends (to me) on what you're really asking.
Ian Lance Taylor
> Given an evil scheduler, goroutines and coroutines are isomorphic.
>
> All the examples given in the threads, makes different only to the
> scheduler. For example select statements on multiple goroutines, are
> equivalent to getting the value of the first coroutine, and hinting the
> evil scheduler to schedule the execution of the coroutines to make that the
> first coroutine computed.
Your scheduler has to be more than evil, it has to be omniscient. It
has to be able to look ahead to see which coroutine will complete first,
and arrange to select that one. Otherwise your scheduler can deadlock
in cases where the Go scheduler would not.
Also, can you implement channels of channels?
Ian
Elazar Leibovich
So it really depends (to me) on what you're really asking.
Rob 'Commander' Pike
What channels add is important, though: they allow [cg]oroutines to synchronize, schedule, and communicate values through a single mechanism. Without channels, [cg]oroutines must manage their own scheduling and data flow.
-rob
Jan Mercl
I'm going to give a lecture about Go. In this lecture I'll present Rob Pike's idea, that goroutines and channel allow you to express single-threaded ideas more clearly. He gives two excellent examples, calculating power series, and implementing lexers.
