7 ms·

Can people explain the fascination with Coroutines? I don't see what problem domain hits solutions that are best done with them all the time.

by gte910h 13y ago

jws 13y ago
all the time is strong. I find them useful when conjoining function A with produces a sequence of results and function B which consumes the sequence†. Without coroutines you either have to turn one of the functions inside out to use it as a callback or break into threads and pass data between them. With coroutines you can leave the functions in a more readable form and keep your cache footprint small by consuming the result as soon as it is produced. ␄ † I don't mean that I call A or B for each element of the sequence. A and B may have internal state and fill produce or consume the whole sequence in a single call. They could be organized to have a create function, a context structure, a "do one" call, and a destroy function… but that is a lot of noise and a lot of places for someone to make a mistake using them. A coroutine is cleaner.
- gte910h 13y ago
  Can I have an example here?
  - spc476 13y ago
    Here's a Lua-esque (since Lua supports coroutines) example. I want to run a simple TCP echo server, so the main code that handles a connection ideally would look like this: function echo(socket) local remote,data = socket:read() if remote == nil then -- no data socket:close() return end socket:write(remote,data) return echo(socket) -- Tail call, this is a goto end Normally, such code would need to be run in a separate process or thread but that's too much overhead. You can use an event-based method (say, with poll() or epoll()) but then the code becomes inverted (or involves callbacks---which in this case isn't too bad, but imagine trying to implement, say, SMTP). With coroutines, we can still use an event-based mainloop, but still keep the imperative style of the original function above. Our event loop would look something like: function mainloop() local events = select:events() for i = 1 , #events do local err,keepgoing = coroutine.resume(events[i].code,events[i].socket,events[i].remote) if not keepgoing then select:remove(events[i].socket) events[i].socket:close() end end return mainloop() end and we would need to change our function just a bit: function echo() local socket,remote = coroutine.yield(true) local data = socket:read() if data == nil then return false end socket:write(remote,data) return echo() end Oh, and don't forget the coroutine to accept new connections: function echoconnection() local socket = coroutine.yield(true) local connection,remote = socket:accept() select:insert(connection,{ read = true } ,{ code = echo,remote = remote }) return echoconnection() end You can, of course, rewrite it such that socket:read() does the call to coroutine.yield(), but here I wanted to make it more explicit (as well as a shorter example) to fully hide the implementation (this is based on a working implementation I have in about 224 lines of Lua, which also handles signals and hides the coroutine calls from the main functions---the first example in this post would run as-is in the fully-blown implementation).
    - 616c 13y ago
      Very cool stuff. I wanted to start learning Lua. Is there any way to see your code?
      - spc476 13y ago
        Well, it's finicky. You'll need to install several custom written Lua modules [1]. These have been tested under Linux and Solaris. You will definitely have to edit the Makefile to exclude building some of the modules like org.conman.tcc [2] because of dependency issues (TCC isn't for the faint of heart). If you are on another Unix system, you'll probably be able to get most of it built (at the least, you'll need org.conman.process, org.conman.net and org.conman.pollset). You will also need to install LPeg [3]. Once all those are installed, then you'll be able to run the code: http://pastebin.com/ZBq5gSbS http://pastebin.com/ZBq5gSbS Or you can just look at the code: http://pastebin.com/ZBq5gSbS http://pastebin.com/ZBq5gSbS The coroutine stuff is there, just well hidden. I will also link to a sample multiuser chat room (no security, very basic): http://pastebin.com/u6vSPc69 http://pastebin.com/u6vSPc69 [1] https://github.com/spc476/lua-conmanorg https://github.com/spc476/lua-conmanorg [2] It's a Lua interface to the TCC library, which is a C compiler-as-a-library. Not used in the same code I posted, but it is something I find immensely useful, but I would classify as "advanced." [3] http://www.inf.puc-rio.br/~roberto/lpeg/ http://www.inf.puc-rio.br/~roberto/lpeg/ This is the Lua Parsing Expression Grammar library. If you are familiar with compiler tools, think lex and yacc (or flex and bison).
zzzcpan 13y ago
I guess familiarity is the reason. Most people know how to make a function call, but learning other ways to do concurrency takes time and effort.
jerf 13y ago
As with so many programming techniques, there is nothing that can only be done with a coroutine approach, so bear in mind that any example that fits in a little text box probably also fits into a little text box with conventional functions. Practical differences only appear at scale. Further, "coroutine", like so many other programming terms, has suffered from a certain fuzziness. There's a reasonably precise term used by programming language researchers, which very few languages have. Things like Python's generators do not conform entirely to this definition, but you get people calling them coroutines anyhow, along with so many other things. So, rather than try to justify the exact PL-research definition, let me try to explain the interesting thing about the more sloppy, broad definition. In a nutshell: When you call a function, you pass in certain arguments. Then you start at the beginning, generating state or values in response to the input, before finally returning some more values. You then discard all the intermediate state the function generated. The idea here is that there are times when you may want to not discard the state, and/or you may want to be able to not start the function at the beginning. You may also want to pass fresh values into the middle of the function. One of the most clear examples of where this is useful is when you create a pipeline of functions within your code. Using "functions" that can get more input as they go along, and generate output without discarding all their intermediate state, makes it very easy to compose functions together into a pipeline that only know they are in a pipeline. You can take input from a user, apply a "coroutine" that then parses their input into numbers, feed that into a "coroutine" that groups them together into a run-length delimited format, then feed that into a coroutine that writes the results to a file. Each of these routines holds on to a little bit of state, instead of discarding it. Each of these routines is "pluggable"; you can take the same pipeline, pop the "user input" bit off the front, and read from a file, or stream from the network, and the same for all the little bits. You get a composable system of functions that all know just barely enough to function (which is what makes composition easy), instead of a set of functions that knows "A ha, I'm going to get this sort of linked list, traverse it, do 'my thing', and then return a new sort of linked list", which doesn't work on network streams, or hash tables, etc. This also is an easy way to operate on a "stream" without having to have the whole stream loaded into memory, and is more cache/memory-bandwidth friendly because you're only traversing it once. Of course, if you work at it enough, you can do this with conventional functions. But you're going to write a lot of boilerplate, you're going to get it wrong, and it probably still won't be as composable in the end. Or you'll end up manually re-implementing "coroutine"ish things yourself. This is only one example, but it's one of the clearer ones where having things able to retain state without being forced into the strict call hierarchy that conventional function stacks require is obviously a good idea. (Pendant note: I've tried to keep this comment very language agnostic. There's a world of difference between Haskell and Python here, for instance. I'm going for the essence of the pattern in general, not in a particular language.)
ufo 13y ago
The main benefit of coroutines is avoiding inversion of control flow. A classic example is iterators. Its very natural to write an iterator like for(i=0; i<10; i++){ yield i } But to program the same thing without coroutines you need to keep all the control flow state explicitly and write the logic inside out like a state machine: i = 0 int getNext(){ if(i >= 10){ return Done }else{ temp = i i = i + 1 return temp } } This inversion of control gets worse the more complicated your control flow is. For example if you have a recursive structure iterate_tree(t){ if(t.isLeaf){ yield t.value }else{ iterate_tree(t.left) yield t.key iterate_tree(t.right) } } then you suddenly need to also keep a bunch of stacks as your control flow state instead of just a single integer. I wont even try to write it because its just that ugly! --------- One way to prevent the inversion of control is to use internal iterators, where you pass a code block to the iterator: void iterate(callback){ for(i=0; i<10; i++){ callback(i) } } This works just fine sometimes but there are limitations: you cant't break out of the iteration at the middle and you cant interweave to iterations in parallel. Another situation where you see this kind of limitation is Javascript. Using callbacks to do async IO is better than writing everything inside out with all state in global variables (like you would do in C) but its a PITA to do simple things like chaining async calls one after the other inside a loop For example, with coroutines you could do something looking like foreach(url in list){ var x = await getUrl(url) console.log(x) } restOfTheCode(); while in regular JS you need to use recursive functions instead: function go(i){ if(i >= urls.length){ restOfTheCode(); }else{ getUrl(function(x){ print(x) go(i+1) }) } }
anonymoushn 13y ago
Some people think that async code phrased as though it was blocking code is easier to read, write, and modify. This is because the workflow for writing async code with callbacks is basically 1. Imagine the control flow you actually want. 2. Manually perform some subset of a CPS transform around the parts that would block. 3. Write the result of 2 and check it in. And then the workflow for updating it is a. Read the code. b. Attempt to reconstruct a mental model of the originally-desired control flow from the mess. c. goto 1. If you have some simulation/game in which many entities need to interact, you can use coroutines and write each entity's routine(s) imperatively. For example, BulletML lets you do this by embedding a suspendable domain-specific language in your project. If you check out http://www.youtube.com/watch?v=uK_YTyhj7T4 http://www.youtube.com/watch?v=uK_YTyhj7T4, every bullet that either fires other bullets or changes velocity has one or more functions attached to it, and they are all running concurrently. It might be even better to do this without using an extra language, though.
vidarh 13y ago
In addition to inversion of control mentioned elsewhere, consider situations where you could have used threads and synchronization points (mutexes etc.). In such situations co-routines can offer a much lighter weight alternative to full blown threads (for single core execution), as the points where control should switch can be explicitly known, and the "context switch" can often be done with far less data shuffling.
andrewcooke 13y ago
very informally, they're good for the kind of problem where it would be nice to structure your code as if you're using threads, but you have a simple sequence of actions so don't need the asynchronous aspect of threads or the worry that goes with them + mutable state. for example, in the matasano crypto challenge i needed to simulate a message protocol between various actors (and then break it). i could have written client and server as separate threaded entities, but it was simpler to just have them each be a coroutine. think of them like thread, state and bi-directional queue, in one easy package. another example is lazy sequences. you could start up a separate thread that generates the sequences, but then you need to talk to it, throttle it in some way, and close it down. using a generator (a simple co-routine) you can still have your code for generating the sequence in one clean place, but it's easier to call and control. if you've ever thought "it would be kinda cool if threads were simple, so i could structure my code like..." then you probably would have appreciated a coroutine. [update: blog post on the protocol bit - http://www.acooke.org/cute/UsingCorou0.html http://www.acooke.org/cute/UsingCorou0.html - although really it doesn't say much more than the above]
- tel 13y ago
  Cool, I've been expecting a chance to do coroutine-based modeling of crypto protocols in those challenges, but haven't been able to devote any time to going through them.

Can people explain the fascination with Coroutines? I don't see what problem domain hits solutions that are best done with them all the time.

by gte910h 13y ago

Can people explain the fascination with Coroutines? I don't see what problem domain hits solutions that are best done with them all the time.

jws 13y ago

all the time is strong. I find them useful when conjoining function A with produces a sequence of results and function B which consumes the sequence†. Without coroutines you either have to turn one of the functions inside out to use it as a callback or break into threads and pass data between them. With coroutines you can leave the functions in a more readable form and keep your cache footprint small by consuming the result as soon as it is produced. ␄ † I don't mean that I call A or B for each element of the sequence. A and B may have internal state and fill produce or consume the whole sequence in a single call. They could be organized to have a create function, a context structure, a "do one" call, and a destroy function… but that is a lot of noise and a lot of places for someone to make a mistake using them. A coroutine is cleaner.

gte910h 13y ago
Can I have an example here?
- spc476 13y ago
  Here's a Lua-esque (since Lua supports coroutines) example. I want to run a simple TCP echo server, so the main code that handles a connection ideally would look like this: function echo(socket) local remote,data = socket:read() if remote == nil then -- no data socket:close() return end socket:write(remote,data) return echo(socket) -- Tail call, this is a goto end Normally, such code would need to be run in a separate process or thread but that's too much overhead. You can use an event-based method (say, with poll() or epoll()) but then the code becomes inverted (or involves callbacks---which in this case isn't too bad, but imagine trying to implement, say, SMTP). With coroutines, we can still use an event-based mainloop, but still keep the imperative style of the original function above. Our event loop would look something like: function mainloop() local events = select:events() for i = 1 , #events do local err,keepgoing = coroutine.resume(events[i].code,events[i].socket,events[i].remote) if not keepgoing then select:remove(events[i].socket) events[i].socket:close() end end return mainloop() end and we would need to change our function just a bit: function echo() local socket,remote = coroutine.yield(true) local data = socket:read() if data == nil then return false end socket:write(remote,data) return echo() end Oh, and don't forget the coroutine to accept new connections: function echoconnection() local socket = coroutine.yield(true) local connection,remote = socket:accept() select:insert(connection,{ read = true } ,{ code = echo,remote = remote }) return echoconnection() end You can, of course, rewrite it such that socket:read() does the call to coroutine.yield(), but here I wanted to make it more explicit (as well as a shorter example) to fully hide the implementation (this is based on a working implementation I have in about 224 lines of Lua, which also handles signals and hides the coroutine calls from the main functions---the first example in this post would run as-is in the fully-blown implementation).
  - 616c 13y ago
    Very cool stuff. I wanted to start learning Lua. Is there any way to see your code?
    - spc476 13y ago
      Well, it's finicky. You'll need to install several custom written Lua modules [1]. These have been tested under Linux and Solaris. You will definitely have to edit the Makefile to exclude building some of the modules like org.conman.tcc [2] because of dependency issues (TCC isn't for the faint of heart). If you are on another Unix system, you'll probably be able to get most of it built (at the least, you'll need org.conman.process, org.conman.net and org.conman.pollset). You will also need to install LPeg [3]. Once all those are installed, then you'll be able to run the code: http://pastebin.com/ZBq5gSbS http://pastebin.com/ZBq5gSbS Or you can just look at the code: http://pastebin.com/ZBq5gSbS http://pastebin.com/ZBq5gSbS The coroutine stuff is there, just well hidden. I will also link to a sample multiuser chat room (no security, very basic): http://pastebin.com/u6vSPc69 http://pastebin.com/u6vSPc69 [1] https://github.com/spc476/lua-conmanorg https://github.com/spc476/lua-conmanorg [2] It's a Lua interface to the TCC library, which is a C compiler-as-a-library. Not used in the same code I posted, but it is something I find immensely useful, but I would classify as "advanced." [3] http://www.inf.puc-rio.br/~roberto/lpeg/ http://www.inf.puc-rio.br/~roberto/lpeg/ This is the Lua Parsing Expression Grammar library. If you are familiar with compiler tools, think lex and yacc (or flex and bison).

zzzcpan 13y ago

I guess familiarity is the reason. Most people know how to make a function call, but learning other ways to do concurrency takes time and effort.

jerf 13y ago

As with so many programming techniques, there is nothing that can only be done with a coroutine approach, so bear in mind that any example that fits in a little text box probably also fits into a little text box with conventional functions. Practical differences only appear at scale. Further, "coroutine", like so many other programming terms, has suffered from a certain fuzziness. There's a reasonably precise term used by programming language researchers, which very few languages have. Things like Python's generators do not conform entirely to this definition, but you get people calling them coroutines anyhow, along with so many other things. So, rather than try to justify the exact PL-research definition, let me try to explain the interesting thing about the more sloppy, broad definition. In a nutshell: When you call a function, you pass in certain arguments. Then you start at the beginning, generating state or values in response to the input, before finally returning some more values. You then discard all the intermediate state the function generated. The idea here is that there are times when you may want to not discard the state, and/or you may want to be able to not start the function at the beginning. You may also want to pass fresh values into the middle of the function. One of the most clear examples of where this is useful is when you create a pipeline of functions within your code. Using "functions" that can get more input as they go along, and generate output without discarding all their intermediate state, makes it very easy to compose functions together into a pipeline that only know they are in a pipeline. You can take input from a user, apply a "coroutine" that then parses their input into numbers, feed that into a "coroutine" that groups them together into a run-length delimited format, then feed that into a coroutine that writes the results to a file. Each of these routines holds on to a little bit of state, instead of discarding it. Each of these routines is "pluggable"; you can take the same pipeline, pop the "user input" bit off the front, and read from a file, or stream from the network, and the same for all the little bits. You get a composable system of functions that all know just barely enough to function (which is what makes composition easy), instead of a set of functions that knows "A ha, I'm going to get this sort of linked list, traverse it, do 'my thing', and then return a new sort of linked list", which doesn't work on network streams, or hash tables, etc. This also is an easy way to operate on a "stream" without having to have the whole stream loaded into memory, and is more cache/memory-bandwidth friendly because you're only traversing it once. Of course, if you work at it enough, you can do this with conventional functions. But you're going to write a lot of boilerplate, you're going to get it wrong, and it probably still won't be as composable in the end. Or you'll end up manually re-implementing "coroutine"ish things yourself. This is only one example, but it's one of the clearer ones where having things able to retain state without being forced into the strict call hierarchy that conventional function stacks require is obviously a good idea. (Pendant note: I've tried to keep this comment very language agnostic. There's a world of difference between Haskell and Python here, for instance. I'm going for the essence of the pattern in general, not in a particular language.)

ufo 13y ago

The main benefit of coroutines is avoiding inversion of control flow. A classic example is iterators. Its very natural to write an iterator like for(i=0; i<10; i++){ yield i } But to program the same thing without coroutines you need to keep all the control flow state explicitly and write the logic inside out like a state machine: i = 0 int getNext(){ if(i >= 10){ return Done }else{ temp = i i = i + 1 return temp } } This inversion of control gets worse the more complicated your control flow is. For example if you have a recursive structure iterate_tree(t){ if(t.isLeaf){ yield t.value }else{ iterate_tree(t.left) yield t.key iterate_tree(t.right) } } then you suddenly need to also keep a bunch of stacks as your control flow state instead of just a single integer. I wont even try to write it because its just that ugly! --------- One way to prevent the inversion of control is to use internal iterators, where you pass a code block to the iterator: void iterate(callback){ for(i=0; i<10; i++){ callback(i) } } This works just fine sometimes but there are limitations: you cant't break out of the iteration at the middle and you cant interweave to iterations in parallel. Another situation where you see this kind of limitation is Javascript. Using callbacks to do async IO is better than writing everything inside out with all state in global variables (like you would do in C) but its a PITA to do simple things like chaining async calls one after the other inside a loop For example, with coroutines you could do something looking like foreach(url in list){ var x = await getUrl(url) console.log(x) } restOfTheCode(); while in regular JS you need to use recursive functions instead: function go(i){ if(i >= urls.length){ restOfTheCode(); }else{ getUrl(function(x){ print(x) go(i+1) }) } }

anonymoushn 13y ago

Some people think that async code phrased as though it was blocking code is easier to read, write, and modify. This is because the workflow for writing async code with callbacks is basically 1. Imagine the control flow you actually want. 2. Manually perform some subset of a CPS transform around the parts that would block. 3. Write the result of 2 and check it in. And then the workflow for updating it is a. Read the code. b. Attempt to reconstruct a mental model of the originally-desired control flow from the mess. c. goto 1. If you have some simulation/game in which many entities need to interact, you can use coroutines and write each entity's routine(s) imperatively. For example, BulletML lets you do this by embedding a suspendable domain-specific language in your project. If you check out http://www.youtube.com/watch?v=uK_YTyhj7T4 http://www.youtube.com/watch?v=uK_YTyhj7T4, every bullet that either fires other bullets or changes velocity has one or more functions attached to it, and they are all running concurrently. It might be even better to do this without using an extra language, though.

vidarh 13y ago

In addition to inversion of control mentioned elsewhere, consider situations where you could have used threads and synchronization points (mutexes etc.). In such situations co-routines can offer a much lighter weight alternative to full blown threads (for single core execution), as the points where control should switch can be explicitly known, and the "context switch" can often be done with far less data shuffling.

andrewcooke 13y ago

very informally, they're good for the kind of problem where it would be nice to structure your code as if you're using threads, but you have a simple sequence of actions so don't need the asynchronous aspect of threads or the worry that goes with them + mutable state. for example, in the matasano crypto challenge i needed to simulate a message protocol between various actors (and then break it). i could have written client and server as separate threaded entities, but it was simpler to just have them each be a coroutine. think of them like thread, state and bi-directional queue, in one easy package. another example is lazy sequences. you could start up a separate thread that generates the sequences, but then you need to talk to it, throttle it in some way, and close it down. using a generator (a simple co-routine) you can still have your code for generating the sequence in one clean place, but it's easier to call and control. if you've ever thought "it would be kinda cool if threads were simple, so i could structure my code like..." then you probably would have appreciated a coroutine. [update: blog post on the protocol bit - http://www.acooke.org/cute/UsingCorou0.html http://www.acooke.org/cute/UsingCorou0.html - although really it doesn't say much more than the above]

tel 13y ago
Cool, I've been expecting a chance to do coroutine-based modeling of crypto protocols in those challenges, but haven't been able to devote any time to going through them.