Re: Coroutine Question
On May 4, 2005 06:22 pm, Rod Adams wrote: > John Macdonald wrote: > > >On Wed, May 04, 2005 at 03:02:41PM -0500, Rod Adams wrote: > > > > > >>If there are good uses for coroutines that given/take does not address, > >>I'll gladly change my opinion. But I'd like to see some examples. > >>FWIW, I believe that Patrick's example of the PGE returning matches > >>could be written with given/take (if it was being written in P6). > >> > >> > > > >Um, I don't recall what given/take provides, so I may be only > >addressing the limitations of lazy lists... > > > > > First off, it's gather/take, not given/take. My mistake. Oops. > > Here goes my understanding of gather/take: > > "gather" takes a block as an argument, and returns a lazy list object. > Inside that block, one can issue "take" commands, which "push" one or > more values onto the list. However, since it's all lazy, it only > executes the block when someone needs something off the list that > currently isn't there. And even then, it only executes the block up > until enough "take"s have happened to get the requested value. If the > block exits, the list is ended. Strange. The names gather/take suggest accepting values rather than generating them (yet generating them onto the lizy list is what you describe this code as doing). I don't like the name "yield" either for the same reason - it suggests that the data only goes one way while the operation of transferrig control from one coroutine to another is a pair has the first producing a value to the other (but also being ready to accept a value in return when it gets resumed in turn). Whether a particular resume is passing data out, or accepting data in, or both, is a matter of what your code happen to need at that moment. > A simple example: > > sub grep ($test, [EMAIL PROTECTED]) { > gather { > for @values -> $x { > take $x if $x ~~ $test; > } > } > } > > Since the block in question is in effect a closure, and gets called > whenever a new value to the lazy list is requested, I believe it > provides all of the generator aspects of coroutines. It could access > various up-scoped/global variables, thereby changing it's behavior > midcourse, if needed. You can create several versions of the same > generator, all distinct, and with separate "states", and easily keep > them separate. To create a new list, you call the function. To resume a > list, you ask for a value from the list it hasn't already created. Asking for a value by scanning a lazy list provides no mechanism for sending information to the routine that will provide that value. For example, the parser for perl5 is written with contorted code because it needs just such a feedback mechanism - the parser has to turn characters into tokens differently depending upon the context. If it was written as a lazy list of tokens, there would have to be this feedback done somehow. (Is \1 one token or two? In a string, it is one token for the character with octal value 001 (or perhaps a part of the token that is the entire string containing that character as only a portion), in a substitute, it is one token that refers back to the first match, in open expression code, it is two tokens representing a refernce operator and the numeric value 1. (POD and here-strings are other forms that require feedback.) > Once you have some of these lazy list functions made, pipelining them > together is trivial via "==>" or "<==". > > >For many simple uses generators are exactly what you need, > >but they have limits. A more powerful coroutine mechanism can > >easily provide the simple forms (and, I would expect, without > >any serious loss of performance). > > > I'll ask again for a couple examples of the non-generator uses, mostly > out of curiosity, but also to better evaluate the proposals being kicked > around in this thread. > > -- Rod Adams > > >
Re: Coroutine Question
John Macdonald wrote: On Wed, May 04, 2005 at 03:02:41PM -0500, Rod Adams wrote: If there are good uses for coroutines that given/take does not address, I'll gladly change my opinion. But I'd like to see some examples. FWIW, I believe that Patrick's example of the PGE returning matches could be written with given/take (if it was being written in P6). Um, I don't recall what given/take provides, so I may be only addressing the limitations of lazy lists... First off, it's gather/take, not given/take. My mistake. Oops. Here goes my understanding of gather/take: "gather" takes a block as an argument, and returns a lazy list object. Inside that block, one can issue "take" commands, which "push" one or more values onto the list. However, since it's all lazy, it only executes the block when someone needs something off the list that currently isn't there. And even then, it only executes the block up until enough "take"s have happened to get the requested value. If the block exits, the list is ended. A simple example: sub grep ($test, [EMAIL PROTECTED]) { gather { for @values -> $x { take $x if $x ~~ $test; } } } Since the block in question is in effect a closure, and gets called whenever a new value to the lazy list is requested, I believe it provides all of the generator aspects of coroutines. It could access various up-scoped/global variables, thereby changing it's behavior midcourse, if needed. You can create several versions of the same generator, all distinct, and with separate "states", and easily keep them separate. To create a new list, you call the function. To resume a list, you ask for a value from the list it hasn't already created. Once you have some of these lazy list functions made, pipelining them together is trivial via "==>" or "<==". For many simple uses generators are exactly what you need, but they have limits. A more powerful coroutine mechanism can easily provide the simple forms (and, I would expect, without any serious loss of performance). I'll ask again for a couple examples of the non-generator uses, mostly out of curiosity, but also to better evaluate the proposals being kicked around in this thread. -- Rod Adams
Re: Coroutine Question
John Macdonald wrote a lovely summary of coroutines [omitted]. Then added: > I'd use "resume" instead of "coreturn" We've generally said we'd be using "yield". > and the interface for resume would allow values to be sent > in as well as out. Indeed. As John suggested, the "yield" keyword (or whatever we call it) will evaluate to the argument list that is passed when the coroutine is resumed. > sub byn(@base) is coroutine($count,@add) { > while(1) { > push(@base,@add); > return undef unless @base; > ($count, @add) = resume .call (splice @base, 0, $count ); > } > } Under the "stupid" proposal, that would be: sub byn(@base) { return coro ($count, [EMAIL PROTECTED] is copy) { # Anonymous coroutine while (1) { push @base, @add; return undef unless @base; ($count, @add) = yield splice @base, 0, $count; } } } > my $co = byn(1..10); > > print $co.resume(3); # 1 2 3 > print $co.resume(2,50..56)# 4 5 > print $co.resume(10); # 6 7 8 9 10 50 51 52 53 54 > print $co.resume(10); # 55 56 > print $co.resume(10); # (undef) > print $co.resume(10); # exception or undef Which would become: my $co = byn(1..10); print $co(3); # 1 2 3 print $co(2,50..56) # 4 5 print $co(10);# 6 7 8 9 10 50 51 52 53 54 print $co(10);# 55 56 print $co(10);# undef print $co(10);# exception Damian
Re: Coroutine Question
On Wed, May 04, 2005 at 03:02:41PM -0500, Rod Adams wrote: > John Macdonald wrote: > > >The most common (and what people sometimes believe the > >*only* usage) is as a generator - a coroutime which creates a > >sequence of values as its "chunk" and always returns control > >to its caller. (This retains part of the subordinate aspect > >of a subroutine. While it has the ability to resume operation > >from where it left off and so doesn't terminate as soon as it > >has a partial result to pass on, it has the subordinate trait > >of not caring who called it and not trying to exert any control > >over which coroutine is next given control after completing a > >"chunk"). > > > > > [Rest of lengthy, but good explanation of coroutines omitted] > > Question: > > Do we not get all of this loveliness from lazy lists and the given/take > syntax? Seems like that makes a pretty straightforward generator, and > even wraps it into a nice, complete object that people can play with. > > Now, I'm all in favor of TMTOWTDI, but in this case, if there are no > other decent uses of co-routines, I don't see the need for AWTDI. > Given/Take _does_ create a coroutine. > > > If there are good uses for coroutines that given/take does not address, > I'll gladly change my opinion. But I'd like to see some examples. > FWIW, I believe that Patrick's example of the PGE returning matches > could be written with given/take (if it was being written in P6). Um, I don't recall what given/take provides, so I may be only addressing the limitations of lazy lists... I mentioned Unix pipelines as an example. The same concept of a series of programs that treat each other as a data stream translates to coroutines: each is a "mainline" routine that treats the others as subroutines. Take a simple pipeline component, like say "tr". When it is used in the middle of a pipeline, it has command line arguments that specify how it is to transform its data and stdin and stdout are connected to other parts of the pipeline. It reads some data, transforms it, and then writes the result. Lather, rinse, repeat. A pipeline component program can be written easily because it keeps its own state for the entire run but doesn't have to worry about keeping track of any state for the other partsd of a pipeline. This is like a coroutine - since a coroutine does not return at each step it keeps its state and since it simply resumes other coroutines it does not need to keep track of their state at all. To change a coroutine into a subroutine means that the replacement subroutine has to be able, on each invokation, to recreate its state to match where it left off; either by using private state variables or by having the routine that calls it take over the task of managing its state. If pipeline components were instead like subroutines rather than coroutines, then whenever a process had computed some output data, instead of using a "write" to pass the data on to an existing coroutine-like process, it would have to create a new process to process this bit of data. Using coroutines allows you to create the same sort of pipelines within a single process; having each one written as its own "mainline" and thinking of the others as data sources and sinks that it reads from and writes to is very powerful. Lazy lists are similar to redirection of stdin from a file at the head of a pipeline. Its fine if you already have that data well specified. Try writing a perl shell program that uses coroutines instead of separate processes to handle pipelines and has a coroutine library to compose the pipelines; this would be a much more complicated programming task to write using subroutines instead of coroutines. The example of a compiler was also given - the parser runs over th input and turns it into tokens, the lexer takes tokens and parses them into an internal pseudo code form, the optimizer takes the pseudo code and shuffles it around into pseudocode that (one hopes) is better, the code generator takes the pseudocode and transforms it into Parrot machine code, the interpretor takes the Parrot machine code and executes it. They mostly connect together in a kind of pipeline; but there can be dynamic patches to that pipeline (a BEGIN block, for example, causes the interpretor to be pulled in as soon as that chunk if complete, and if that code includes a "use" it might cause a new pipeline of parser/lexer/etc to be set up to process an extra file right now, while keeping the original pipeline intact to be resumed in due course. (This example also fits with Luke's reservations about failing to distinguish clearly between crating and resuming a coroutine - how are you going to start a new parser if "calling" the parse subroutine will just resume the instance that is already running instead of creating a separate coroutime.) For many simple uses generators are exactly what you need, but they have limits. A more powerful coroutine mechanism can easily provide the s
Re: Coroutine Question
[Not back, just sufficiently irritated...] Luke Palmer wrote: in my proposal, when you call a coroutine, it returns an iterator (and doesn't call anything): my $example = example(); =$example; # 1 =$example; # 2 The thing this buys over the traditional (which I refer to as the "stupid") way, is that you can do this: my $example = example(); my $example2 = example(); =$example; # 1 =$example; # 2 =$example2; # 1 =$example; # 3 There is _no way_ to do that using the stupid way. Nonsense. You just return an anonymous coroutine: sub example { coro {...} } my $example = example(); my $example2 = example(); $example(); # 1 $example(); # 2 $example2(); # 1 $example(); # 3 Damian
Re: Coroutine Question
John Macdonald wrote: The most common (and what people sometimes believe the *only* usage) is as a generator - a coroutime which creates a sequence of values as its "chunk" and always returns control to its caller. (This retains part of the subordinate aspect of a subroutine. While it has the ability to resume operation from where it left off and so doesn't terminate as soon as it has a partial result to pass on, it has the subordinate trait of not caring who called it and not trying to exert any control over which coroutine is next given control after completing a "chunk"). [Rest of lengthy, but good explanation of coroutines omitted] Question: Do we not get all of this loveliness from lazy lists and the given/take syntax? Seems like that makes a pretty straightforward generator, and even wraps it into a nice, complete object that people can play with. Now, I'm all in favor of TMTOWTDI, but in this case, if there are no other decent uses of co-routines, I don't see the need for AWTDI. Given/Take _does_ create a coroutine. If there are good uses for coroutines that given/take does not address, I'll gladly change my opinion. But I'd like to see some examples. FWIW, I believe that Patrick's example of the PGE returning matches could be written with given/take (if it was being written in P6). -- Rod Adams
Re: Coroutine Question
On Wed, May 04, 2005 at 02:22:43PM -0400, John Macdonald wrote: > On Wed, May 04, 2005 at 10:43:22AM -0400, Aaron Sherman wrote: > > On Wed, 2005-05-04 at 10:07, Aaron Sherman wrote: > > > A coroutine is just a functional unit that can be re-started after a > > > previous return, so I would expect that in Perl, a coroutine would be > > > defined by the use of a variant of return > > A co(operating) routine is similar to a sub(ordinate) routine. > They are both a contained unit of code that can be invoked. > > A subroutine carries out its entire functionality completely > and then terminates before returning control back to the caller. > [...] > This can be used for a large variety of functions. > The most common (and what people sometimes believe the > *only* usage) is as a generator - a coroutime which creates a > sequence of values as its "chunk" and always returns control > to its caller. ... Notably, the grammar engine for Perl 6 rules is taking full advantage of Parrot coroutines. Invoking a rule (coroutine) causes the rule to continue until it completes a match, at which point it returns the results of the match to the caller. But the caller can later return control back to the rule/match so that the matching (and backtracking) continues from where it last finished. Pm
Re: Coroutine Question
On Wed, May 04, 2005 at 10:43:22AM -0400, Aaron Sherman wrote: > On Wed, 2005-05-04 at 10:07, Aaron Sherman wrote: > > On Wed, 2005-05-04 at 09:47, Joshua Gatcomb wrote: > > > > > So without asking for S17 in its entirety to be written, is it > > > possible to get a synopsis of how p6 will do coroutines? > > > > A coroutine is just a functional unit that can be re-started after a > > previous return, so I would expect that in Perl, a coroutine would be > > defined by the use of a variant of return A co(operating) routine is similar to a sub(ordinate) routine. They are both a contained unit of code that can be invoked. A subroutine carries out its entire functionality completely and then terminates before returning control back to the caller. A coroutine can break its functionality into many chunks. After completing a chunk, it returns control back to the caller (or passes control to a different coroutine instead) without terminating. At some later point, the caller (or some other coroutine) can resumes this coroutine and it will continue on from where it left off. From the point of view of this coroutine, it just executed a "subroutine" call in the middle of its execution. When used to it full limit, each coroutine treats the other(s) as a subroutine; each thinks it is the master and can run its code as it pleases, and call the other whenever and from wherever it likes. This can be used for a large variety of functions. The most common (and what people sometimes believe the *only* usage) is as a generator - a coroutime which creates a sequence of values as its "chunk" and always returns control to its caller. (This retains part of the subordinate aspect of a subroutine. While it has the ability to resume operation from where it left off and so doesn't terminate as soon as it has a partial result to pass on, it has the subordinate trait of not caring who called it and not trying to exert any control over which coroutine is next given control after completing a "chunk"). The mirror image simple case is a consumer - which accepts a sequence of values from another coroutine and processes them. (From the viewpoint of a generator coroutine, the mainline that invokes it acts is a consumer coroutine.) A read handle and a write handle are generator and consumer data contructs - they aren't coroutines because they don't have any code that "thinks" it has just called a "subroutine" to get the next data to write (or to process the previous data that was read). However, read and write coroutines are perfectly reasonable - a macro processor is a generator coroutine that uses an input file rather than a mathematical sequence as one facet of how it decides the next chunk to be generated and passed on; a code generator is a consumer coroutine that accepts parsed chunks and creates (and writes to a file perhaps) code from it. Controlling the flow of control is powerful - a bunch of coroutines can be set up to act like a Unix pipeline. The first coroutine will read and process input. Occassionally it will determine that it has a useful chunk to pass on to its successor, and pass control to that successor. The niddle coroutines on the chain will pass control to their predecessor whenever they need new "input" and to their successor when they have transformed that input into a unit of "output". The last coroutine will accept its input and process it, probably writing to the outside world in some way. Coroutines can permit even wider range in the control flow. Coroutines were used in Simula, which was a simulation and modelling language, and it allowed independent coroutines to each model a portion of the simulation and they would each be resumed at appropriate times, sometimes by a master scheduler which determined which major coroutine needed to be resumed next, but also sometimes by each other. A coroutine declaration should essentially declare 2 "subroutine" interfaces, describing the parameter and return value information. One is the function that gets called to create a new instance of the coroutine; the other defines the interface that is used to resume execution of an existing instance of that coroutine. The resume interface will look like a definition of a subroutine - describing the argument list and return values for the interface. Having special purpose coroutine declarations for simple generators and consumers would be possible and could hide the need (in more general cases) for the full double interface. The creation interface should (IMHO) return an object that can be resumed (using the resumtion interface), could be tested for various aspects of its state - .isalive (has it terminated by returning from the function), .caller (which coroutine last resumed it), probably others. The act of resuming another coroutine is simply calling its second interface with an appropriate set of arguments and expecting that resumption to return an appropriate set of values (when this coroutine is next re
Re: Coroutine Question
On Wed, 2005-05-04 at 10:07, Aaron Sherman wrote: > On Wed, 2005-05-04 at 09:47, Joshua Gatcomb wrote: > > > So without asking for S17 in its entirety to be written, is it > > possible to get a synopsis of how p6 will do coroutines? > > A coroutine is just a functional unit that can be re-started after a > previous return, so I would expect that in Perl, a coroutine would be > defined by the use of a variant of return Oh, I failed to comment on a few things (and given Luke's responses, this answer can be seen to dove-tail into what he said, though I don't think you need a coroutine trait most of the time). Here they are as questions with my expected default answers: Q: What does a coroutine return when exausted? A: It either explicitly "return"s something or falls off the end. This allows you to: sub ten() { for 1..10 -> $_ { coreturn $_ } return undef; } correctly terminating ten() when called in a loop. If you ever call coreturn, then dropping off the end of the routine probably implicitly returns undef rather than the last statement executed as normal. Why? As a default way to signal the caller that we're done. More sophisticated means (adding traits to the undef) might be employed. Q: What happens if you change parameters? A: Nothing. You would have to store the information about what parameters were active somewhere, and no matter where you choose (current lexical pad, parameters, coroutine itself, etc.), there are many cases that are non-obvious to the programmer, and this gets strange: while someco(@x) -> $_ { while someco(@x) -> $_ {...} } If you want to modify behavior based on parameter, return a closure that is a coroutine: sub someco(@p) { return -> { for @p -> $_ { coreturn $_ } } } my $co1 = someco(@x); while $co1.() -> $_ { my $co2 = someco(@x); while $co2.() -> $_ {...} } -- Aaron Sherman <[EMAIL PROTECTED]> Senior Systems Engineer and Toolsmith "It's the sound of a satellite saying, 'get me down!'" -Shriekback
Re: Coroutine Question
On 5/4/05, Luke Palmer <[EMAIL PROTECTED]> wrote: > On 5/4/05, Joshua Gatcomb <[EMAIL PROTECTED]> wrote: > > Ok - this isn't what I was expecting at all. That doesn't make it a > > bad thing. Given something that looks a lot more like a typical > > coroutine: > > > > sub example is coroutine { > > yield 1; > > yield 2; > > yield 3; > > } > > > > I would expect > > for 1 .. 5 { say example() } to print "1\n2\n3\n1\n\2" > > Ding! You just hit the disagreement point. You're on Damian's side. Not exactly. I am basing my expectation on the following link and then asking with all the different ways to define behavior - has a decision WRT p6 been made. http://www.sidhe.org/~dan/blog/archives/000178.html > Sorry for my language... it's just that if I were dropped into a > project that invented that abstraction for something it was doing, it > would be one of the first things I'd change. Totally unscalable > design. > > > If I got fancy and added a parameter > > > > sub example ( $num ) is coroutine { > > yield $num; > > yield $num + 1; > > yield $num - 2; > > } > > > > I would expect > > for 1 .. 5 { say example( 7 ) } to print "7\n8\n6\n7\n8"; > > And here is where it gets trickier: > > say example(7); # 7 > say example(7); # 8 > say example(8); # 8? 6? Exactly my point. There is more than one way to define the behavior (especially with parameter handling). That is why I included a reference and asked how p6 was going to do it. Personally, I don't care because I know people like you, Larry, Damian, et all will make a sound decision. What I want to know is if you have a decision already that isn't published in its entirety so I can start writing tests. Ok, I do care. Regardless of behavior, I would hope the syntax would somewhat resemble that of other languages. > > Luke > Cheers, Joshua Gatcomb a.k.a. L~R
Re: Coroutine Question
Hi, Joshua Gatcomb wrote: > On 5/4/05, Luke Palmer <[EMAIL PROTECTED]> wrote: >> On 5/4/05, Joshua Gatcomb <[EMAIL PROTECTED]> wrote: >> > So without asking for S17 in its entirety to be written, is it >> > possible to get a synopsis of how p6 will do coroutines? I ask >> > because after reading Dan's "What the heck is: a coroutine", it is >> > clear there is more than one way to dictate behavior. >> >> Well, one way is to use generating functions: >> >> my @a = gather { >> for 1..10 { >> say; >> take; >> } >> } > > Ok - this isn't what I was expecting at all. That doesn't make it a > bad thing. Given something that looks a lot more like a typical > coroutine: sub example(...) { my $index = 0; my @a:= gather { ...coroutine code here, use "take" to yield a result...; }; return { @a[$index++] }; } my $gen = example(...); say $gen(); say $gen(); say $gen(); (FWIW, I like something along the lines of "is coroutine" and then "yield" to yield a result, too, but I don't have a strong opinion on this.) --Ingo -- Linux, the choice of a GNU | Row, row, row your bits, gently down the generation on a dual AMD | stream... Athlon!|
Re: Coroutine Question
On 5/4/05, Luke Palmer <[EMAIL PROTECTED]> wrote: > On 5/4/05, Joshua Gatcomb <[EMAIL PROTECTED]> wrote: > > So without asking for S17 in its entirety to be written, is it > > possible to get a synopsis of how p6 will do coroutines? I ask > > because after reading Dan's "What the heck is: a coroutine", it is > > clear there is more than one way to dictate behavior. > > Well, one way is to use generating functions: > > my @a = gather { > for 1..10 { > say; > take; > } > } > > (Where that = might be spelled :=). Here, the code is not executed > until an element of @a is demanded. It is executed as many times as > necessary to fetch that element, and then stopped in its tracks. Ok - this isn't what I was expecting at all. That doesn't make it a bad thing. Given something that looks a lot more like a typical coroutine: sub example is coroutine { yield 1; yield 2; yield 3; } I would expect for 1 .. 5 { say example() } to print "1\n2\n3\n1\n\2" If I got fancy and added a parameter sub example ( $num ) is coroutine { yield $num; yield $num + 1; yield $num - 2; } I would expect for 1 .. 5 { say example( 7 ) } to print "7\n8\n6\n7\n8"; The questions I am really asking is: 1. Will coroutines be supported at all? 2. If yes, will they look like coroutines in other languages? 3. If yes, in what ways will they be behave (handling of parameters for instance)? 4. Finally, what is the proper syntax for declaring and calling coroutines? I am fine with a "we haven't got that far yet" answer. I was just hoping to write some tests to drive features. > > Luke - Hide quoted text - > Cheers, Joshua Gatcomb a.k.a. L~R
Re: Coroutine Question
On Wed, 2005-05-04 at 09:47, Joshua Gatcomb wrote: > So without asking for S17 in its entirety to be written, is it > possible to get a synopsis of how p6 will do coroutines? A coroutine is just a functional unit that can be re-started after a previous return, so I would expect that in Perl, a coroutine would be defined by the use of a variant of return, such as: sub generate_this() { for 1..10 -> $_ { coreturn $_; } } Of course, I'm pulling that out of my @ss, so YMMV. ;-) -- Aaron Sherman <[EMAIL PROTECTED]> Senior Systems Engineer and Toolsmith "It's the sound of a satellite saying, 'get me down!'" -Shriekback