Coroutine calling convention

[Luke Palmer]

After reading Dan's recent blog entry, I realized how (semantically)
ugly coroutines are, with all the different ways of calling them, and
dealing with parameters, etc.

There's a couple problems as far as what's easy with the approaches
described there. For instance, you can't really have a coroutine that
everyone can call with the same state, because it would either start
over, or create a new one.

It's very hard to maintain several coroutine states of the same
coroutine in the same scope. You have to do tricky stuff with
closures, or some other such workaround.

So, since they are generally used as iterators, why not steal the
iterator semantics for them? This clears up most of the issues:

sub range($start, $end) is coroutine {
for $start .. $end { yield $_ }
}

my $iter = range(1,10); # Doesn't actually run range's code.
for <$iter> {
print "Got $_"
}

So calling a function declared as a coroutine wouldn't run anything at
all. It would return an iterator, that when advanced would run until
the first C<yield>.

A problem that I see is that this breaks the "encapsulation" of
continuing a coroutine being equivalent to just calling a function.
However, coroutines are stateful, so it should be explicit that you're
using an existing state rather than starting a new one (as in the case
of a function call).

Luke

[Luke Palmer]

> On Fri, May 02, 2003 at 07:09:02AM -0600, Luke Palmer wrote:
>
> > [whatsit about an iterator interface to coroutines]

> I don't like this. Iterators can be implemented in terms of
> continuations which can be implemented in terms of coroutines.
> (Actually, what Dan has described in his blog entry is a
> continuation in my book; I'd be glad if someone show me that I am
> wrong)

You probably have your terms switched around, then. The general way
it's thought of (when the thinkers invloved keep their heads by the
end :) is that coroutines are implemented in terms of continuations.
But if you were sufficiently clever, I suppose you could do it the
other way around, too.

A continuation is an object that closes over the entire stack and the
execution point (see Dan's other blog entry on continuations). A
coroutine is a convenience feature that allows you to temporarily
suspend the execution of a function to return a value, and then pick
up where you left off when told to do so (usually returning more
values in a similar manner).

> So what you suggest is essentially a needless limitation. Even
> perl5 coroutines (Coro and Coro::*) can do more at this point!

I don't quite understand. What is limited about it? Can you give an
example?

Luke

> \Anton.

[Anton Berezin]

On Fri, May 02, 2003 at 07:09:02AM -0600, Luke Palmer wrote:

I don't like this. Iterators can be implemented in terms of

continuations which can be implemented in terms of coroutines.
(Actually, what Dan has described in his blog entry is a continuation in
my book; I'd be glad if someone show me that I am wrong)

So what you suggest is essentially a needless limitation. Even perl5

coroutines (Coro and Coro::*) can do more at this point!

\Anton.
--
Perl is strongly typed, it just has very few types. -- Dan Sugalski

[Luke Palmer]

> > > So what you suggest is essentially a needless limitation. Even
> > > perl5 coroutines (Coro and Coro::*) can do more at this point!
> >
> > I don't quite understand. What is limited about it? Can you give
> > an example?
>

> And the point being...
>
> What you suggest looks nice, and there is very little which can be
> misunderstood in this approach. But! You essentially limit the
> semantics to Dan's case 1, with a possibility to explicitly achieve
> case 2 behavior (by making two `iterators'). It is not possible to
> implement case 3 at all.

(For those of you without immediate access to Dan's blog, case 1 is to
ignore arguments on subsequent calls until the function thinks it's
done, case 2 is to start a new coroutine when you call with different
arguments, and case 3 is to change already-bound arguments in the
middle of the call)

I think case 3 is so wierd (and dangerous) that it deserves a special
name. That's why you put the coroutine in the iterator I<object>:

my $iter = coroutine_func(1, 2, 3);
print <$iter>;
$iter->rebind(3, 2, 1);
print <$iter>;

There are some other benefits of having it in an object: it's possible
to terminate it in the middle of its execution:

$iter->terminate;
# or
undef $iter; # Let GC get it

It's possible to pass it around, rather than having it manditorily
stay in one scope. I think this is a more important benefit than
avoiding the initialization step. It's encapsulated in the iterator
interface, so you can use it where people might expect a filehandle or
any other kind of iterator. And finally, it makes it easy to tie to
various objects.

But then, I haven't yet seen any tolerable alternatives. I don't
consider the semantics that Dan describes at all tolerable (despite
that being the traditional way to do it), unless there's a piece of
the interface I'm missing.

> On the other hand, if the coroutine semantics were to correspond to
> case 3, then case 1 is trivially implemented (by copying), but there
> is no way to achieve case 2 behavior.
>
> In my opinion, the ability to implement/to choose from all three
> cases would be neat, neat, neat. How? Dunno.

See above :)

> Another thing which I don't like about your proposal is that it is
> too explicit, and involves a preparation/initialization step.

Obviously you haven't spent enough time with Perl 6 :)

sub foobar() is coroutine {...}

for <foobar> {
# do stuff with each yielded value
}

You don't have to put the iterator in a variable if you don't want
to. That might turn out to be a subtle trap, eg:

$val1 = <foobar>;
$val2 = <foobar>; # Starts a new instance!

But it's not really that subtle. You typed the function's name twice,
so it will be I<started> twice.

As I scour google for uses of coroutines, they really are mostly
iterators, except they're just not implemented that way. One is for a
"pipe" sort of mechanism (stream iterator), another for iterating
depth-first over a tree. Another is for solving the towers of hanoi
with a recursive algorithm, which is really just iterating over
another (implicit) tree.

I'm biased, of course, because I've always felt that iterators were
underrepresented in Perl 5. Iterators, especially generic ones, are
very useful tools, and I<the toolbox> barely supported them.

Sorry for babbling.

Luke

[Anton Berezin]

Luke,

On Fri, May 02, 2003 at 09:39:26AM -0600, Luke Palmer wrote:
> > On Fri, May 02, 2003 at 07:09:02AM -0600, Luke Palmer wrote:
> >
> > > [whatsit about an iterator interface to coroutines]
>
> > I don't like this. Iterators can be implemented in terms of
> > continuations which can be implemented in terms of coroutines.
> > (Actually, what Dan has described in his blog entry is a
> > continuation in my book; I'd be glad if someone show me that I am
> > wrong)

> You probably have your terms switched around, then. The general way
> it's thought of (when the thinkers invloved keep their heads by the
> end :) is that coroutines are implemented in terms of continuations.
> But if you were sufficiently clever, I suppose you could do it the
> other way around, too.

> A continuation is an object that closes over the entire stack and the
> execution point (see Dan's other blog entry on continuations). A
> coroutine is a convenience feature that allows you to temporarily
> suspend the execution of a function to return a value, and then pick
> up where you left off when told to do so (usually returning more
> values in a similar manner).

:-) There really seems to be a lot of confusion over terminology on
this list. I'll admit that my only source was what perl5 Coro module
does, and there coroutines and continuations are indeed switched around,
comparing to what you describe.

Anyway, that's beyond the point.

> > So what you suggest is essentially a needless limitation. Even
> > perl5 coroutines (Coro and Coro::*) can do more at this point!
>
> I don't quite understand. What is limited about it? Can you give an
> example?

And the point being...

What you suggest looks nice, and there is very little which can be
misunderstood in this approach. But! You essentially limit the
semantics to Dan's case 1, with a possibility to explicitly achieve case
2 behavior (by making two `iterators'). It is not possible to implement
case 3 at all.

On the other hand, if the coroutine semantics were to correspond to case

3, then case 1 is trivially implemented (by copying), but there is no
way to achieve case 2 behavior.

In my opinion, the ability to implement/to choose from all three cases
would be neat, neat, neat. How? Dunno.

Another thing which I don't like about your proposal is that it is too

explicit, and involves a preparation/initialization step.

$Anton.
--
Our marketing people are so good they can solve technical problems.

[Damian Conway]

Does it have to be either/or?

FWIW, my view is that the correct interface for re-calling to a
co-routine with different arguments is that the previous C<yield>
should evaluate to the subsequent call's argument list.

In other words, when you jump back into a subroutine (just after the previous
C<yield>) that C<yield> appears to evaluate to the new argument list with
which you jumped back in:

*@args_of_next_call := yield $previous_yielded_value;

The point is, when implementing a particular co-routine, you can
choose to ignore the arg lists of each subsequent re-call:

sub next_fib (Int $a is copy, Int $b is copy) {
yield $a;
yield $b;
loop { ($a, $b) = ($b, $a+$b); yield $b }
}

or choose to update internal data using the subsequent arg lists:

sub next_fib (Int $a is copy, Int $b is copy) {
($a, $b) = yield $a;
($a, $b) = yield $b;
loop { ($a, $b) = ($b, $a+$b); ($a, $b) = yield $b }
}

And with a modest amount of extra effort, you can even implement the
"different-args-means-different-iterator" semantics:

sub next_fib (Int $a, Int $b) {
my sub fibber (Int $a is copy, Int $b is copy) is cached {
return {
yield $a;
yield $b;
loop { ($a, $b) = ($b, $a+$b); yield $b }
}
}
return fibber($a,$b).();
}

TMTOWTContinueI :-)

Damian

[Piers Cawley]

Luke Palmer <fibo...@babylonia.flatirons.org> writes:

What's limited? The fact that the caller now has to know that it's
calling a coroutine rather than just another function. Stripping off
that layer of encapsulation can be thought of as stripping off the
entire rationale for using a coroutine in the first place.

--
Piers

[Piers Cawley]

Damian Conway <dam...@conway.org> writes:

> Does it have to be either/or?
>
> FWIW, my view is that the correct interface for re-calling to a
> co-routine with different arguments is that the previous C<yield>
> should evaluate to the subsequent call's argument list.
>
> In other words, when you jump back into a subroutine (just after the
> previous C<yield>) that C<yield> appears to evaluate to the new
> argument list with which you jumped back in:
>
> *@args_of_next_call := yield $previous_yielded_value;
>
>
> The point is, when implementing a particular co-routine, you can
> choose to ignore the arg lists of each subsequent re-call:
>
> sub next_fib (Int $a is copy, Int $b is copy) {
> yield $a;
> yield $b;
> loop { ($a, $b) = ($b, $a+$b); yield $b }
> }
>
> or choose to update internal data using the subsequent arg lists:
>
> sub next_fib (Int $a is copy, Int $b is copy) {
> ($a, $b) = yield $a;
> ($a, $b) = yield $b;
> loop { ($a, $b) = ($b, $a+$b); ($a, $b) = yield $b }
> }

Neat. Very. It 'feels' like taking a continuation too, which makes
sense as it's probably what's happening underneath the covers
anyway:

sub yield(*@args) {
my $caller = get_caller_as_coro;
callcc { $caller.set_entry_point($^cnt);
return *@args }
CATCH return { throw $@ }
}

Where C<caller_as_coro> conditionally wraps the caller up in a
Coroutine hook along the lines of:

-> *@args { my $ep = $.entry_point;
undef($.entry_point);
return $ep ?? $ep(*@args) :: &.the_sub(*@args) }

With a few wrinkles to catch the case where the C<yield> is the last
expression in the block.

Looking at this, it occurs to me that it might be handy to be able to
declare 'blocklike' subroutines that don't return to their caller, but
to their caller's caller. I *think* the C<CATCH return { throw $@ }>
approch will do the right thing, but being able to do:

sub foo (...) is Blocklike {...}

or something to generate 'return transparent' Subroutines would be
quite handy.

--
Piers

[Luke Palmer]

> >> So what you suggest is essentially a needless limitation. Even
> >> perl5 coroutines (Coro and Coro::*) can do more at this point!
> >
> > I don't quite understand. What is limited about it? Can you give an
> > example?
>
> What's limited? The fact that the caller now has to know that it's
> calling a coroutine rather than just another function. Stripping off
> that layer of encapsulation can be thought of as stripping off the
> entire rationale for using a coroutine in the first place.

Exactly! A coroutine should not be thought of as a function, because
it maintains state!

But I think it's time for some examples. I'll use Damian's version of
the "other way," because it's the best I've seen so far (not that it
doesn't suffer the same problems I've been trying to address).

Let me note that with the iterator method, you have to declare subs as
coroutines, and with the traditional method, you don't. There's
something to be said for both sides.

First, let me say this:

sub fibonacci($a) is coroutine {...}

sub next_fib($a) {
state $coro = ENTER { fibonacci($a) };
if my $ret = <$coro> {
$ret
}
else {
$coro = fibonacci($a);
<$coro>
}
}

So there shouldn't be any complaints about raw capability.

But now the examples that I said I'd do. I tried to be fair by coding
it the best way with regard to each paradigm.

# I have fibonacci() and next_fib(), and I want to print each
# number in the order it was generated mod 2**29

while my $fib = next_fib(50) { # How do I know when it's done?
print $fib % 2**29;
}

for <fibonacci(50)> {
print $_ % 2**29;
}

============

# I have decompress(), next_decompressed(), words(), and
# next_word(), and I want to print each word from the decompressed
# stream in sequence. The decompression functions return one
# character at a time.

sub decompress($stream) is coroutine {...}
sub next_decompressed($stream) {...}
sub words($stream) is coroutine {...}
sub next_word($stream) {...}

# Traditional

# Mmm... parameterized types
class DecompressWrapper($.stream) is Stream {
method READ() {
next_decompressed($.stream)
}
}

my $pipe is DecompressWrapper($*IN);
while my $word = next_word($pipe) {
print $word;
}

# Iterator

for <words decompress $*IN> {
print;
}

============

Basically, the idea I'm trying to get across is that coroutines are
seldom used only once as a function call. The traditional method
encapsulates them in the function call syntax, but that's not what
they are. They create sequences and are often used as such, so it's
better to unify their interface with sequences' interfaces, rather
than with static function call interfaces.

The traditional method reminds me too much of Perl 5's C<pos>. C<pos>
is yucky, because you can only have one iterator into a string at a
time, without saving out the values and setting them each time you
want to match. I banged my head on the wall over and over when I was
trying to extract a section of code, and then perform matches on its
insides, because stupid C<pos> kept resetting behind my back.

Everyone is saying that this proposal is too "explicit." Yep. That's
the point. The last thing we need is another implicit iterator that's
very tricky to work with for the harder cases. It looks great for
simple uses, but when things get more complicated, Perl turns out to
be too dumb to manage What You Mean by itself.

And again, it's not breaking encapsulation, it's encapsulating
coroutines into a different interface, where, IMO, it belongs more. I
think this is one of my better ideas, so I'll keep advocating it until
I see that the alternative is better (or until someone of authority
says "we're doing it traditionally, now shut up").

I would really like to see examples of where the traditional method
makes things easier than the iterator method.

Luke

[Luke Palmer]

> > Everyone is saying that this proposal is too "explicit." Yep. That's
> > the point. The last thing we need is another implicit iterator that's
> > very tricky to work with for the harder cases. It looks great for
> > simple uses, but when things get more complicated, Perl turns out to
> > be too dumb to manage What You Mean by itself.
>

> Let me try another angle. We are supposed to have continuations,
> coroutines, and iterators. What is the difference between coroutines
> with an iterator syntax that you suggest and the `real' iterators?

Umm, nothing. That or filehandles, array & hash iterators,
coroutines, etc. depending on which way you look at it.

Iterator is an interface. Anything that provides a <> operator (a
.next method), maybe an C<is Iterator> declaration, depending on our
object model, is an iterator.

Coroutines, on the other hand, are an implementation. They involve
closing on the stack and saving their position until they're told to
awaken again.

Mmmm... abstraction.

It looks like the biggest conflict point is that of
encapsulation/opacity. The traditional approach keeps coroutines
under the guise of ordinary sub calls, whereas my approach masks them
as sequences.

I'm probably not going to shut up until I see an example where it's
easier and/or clearer to do something traditionally than with
iterators. And trust me, I have been trying to come up with one.

Luke

[Luke Palmer]

I said:
> And again, it's not breaking encapsulation, it's encapsulating
> coroutines into a different interface, where, IMO, it belongs more. I
> think this is one of my better ideas, so I'll keep advocating it until
> I see that the alternative is better (or until someone of authority
> says "we're doing it traditionally, now shut up").

Well, that's probably not true. I'll likely be quiet about it when I
have nothing more to contribute to the discussion. I've clearly
expressed my views, and pounding them harder and harder isn't going to
do much. We have a competent design team, and if my idea isn't used,
there's going to be a good reason for it (but we probably won't know
what it is :).

What I'm doing right now, for anyone interested, is trying to come up
with a way that elegantly supports both styles.

Luke

[Anton Berezin]

On Mon, May 05, 2003 at 01:10:48PM -0600, Luke Palmer wrote:

[skipping nice examples]

> Basically, the idea I'm trying to get across is that coroutines are
> seldom used only once as a function call. The traditional method
> encapsulates them in the function call syntax, but that's not what
> they are. They create sequences and are often used as such, so it's
> better to unify their interface with sequences' interfaces, rather
> than with static function call interfaces.

> Everyone is saying that this proposal is too "explicit." Yep. That's

> the point. The last thing we need is another implicit iterator that's
> very tricky to work with for the harder cases. It looks great for
> simple uses, but when things get more complicated, Perl turns out to
> be too dumb to manage What You Mean by itself.

Let me try another angle. We are supposed to have continuations,

coroutines, and iterators. What is the difference between coroutines
with an iterator syntax that you suggest and the `real' iterators?

*Anton.
--
You shouldn't be intimidated by this issue at all, since Perl is your
friend. -- Apache mod_perl guide

[John Macdonald]

fibo...@babylonia.flatirons.org (Luke Palmer) wrote in message news:<ygcptmw...@babylonia.flatirons.org>...

> Mmmm... abstraction.
>
> It looks like the biggest conflict point is that of
> encapsulation/opacity. The traditional approach keeps coroutines
> under the guise of ordinary sub calls, whereas my approach masks them
> as sequences.
>
> I'm probably not going to shut up until I see an example where it's
> easier and/or clearer to do something traditionally than with
> iterators. And trust me, I have been trying to come up with one.
>
> Luke

The view I have of coroutines dates back to how I learned them (in the
70's) using a subroutine package on top of the B programming language.
In that view, a coroutine is much like an object with a few simple
methods. Creating the coroutine specifies the subroutine and
arguments that are to be initially called and return a magic cookie
(an object). In normal operation, a coroutine is invoked with the
function call:

$result = resume( $coroutine, $argument );

This statement a value bi-directionally - a value is passed here from
the coroutine that is calling resume to the one that is being resumed,
and another value will be passed later back to this coroutine by
whateven coroutine resumes it. It can get used, for example, in a
producer-consumer relationship:

sub producer {
my( $next ) = @_;
detach();
while( ... ) {
...
# compute $value
$value = resume( $next, $value );
}
$next->resume(undef);
}

sub consumer {
my $value = detach();
my $prev = coroutine->caller;
while( $value = resume( $prev, $value ) ) {
# do something with $value
...
}
}

sub main {
my $cons = create( \&consumer );
my $prod = create( \&producer, $cons );
$prod->resume;
}

That can be extended to a pipeline of filters. Add the function
filter and change main and there is no change requied for producer and
consumer:

sub filter { # sample filter - doubles every line,
# no return value from cons to prod
my $next = @_;
my $value = detach();
my $prev = caller();
while( $value ) {
$next->resume( $value );
$next->resume( $value );
$value = $prev->resume;
}
}

sub main {
my $cons = create( \&consumer );
my $filt = create( \&filter, $cons );
my $prod = create( \&producer, $filt );
$prod->resume;
}

There are a number of significant differences from what the current
perl6 design shows:

Creating and resuming a different operations. The initial creation
provides an argument list and is done by a creator. (The operation
detach is actually a resume, but it resumes the coroutine that created
or more recently attach()ed this coroutine.)

The caller function tells you which coroutine resume'd you - the
filter function uses it to set up the backward link on the pipeline.
A routine might use the caller function after every resume, for
example, if new elements might be inserted dynamically into the
pipeline, rather than just once at tha start as I showed above.

When the top-level function (the one that was named in the create
call) returns, it essentially does a detach call, normally that
returns it to the creator. (There was a destroy function that the
creator could call to clean up the memory allocation - this was a
language that didn't hide memory management issues for you. In fact,
one of the arguments to create was an option integer value to specify
the size of stack to allocate for the coroutine - the default value
would work if there weren't too deep a level of nested calls, or too
large an amount of stack allocated variable space.)

This "chain of coroutines in a pipeline" is quite useful (the Filter
modules provide it for perl5 source massaging). The producer-consumer
relationship is also useful - each considers the other a function that
can be called to produce (or consume) the next chunk of data. They
are a pair of iterator - one generating value and the other accepting
and using values. (A filter coroutine is a read iterator to one of
its neighbours and a write iterator to the other.) But iterators are
normally only in a language as a creator of a sequence of values, not
also as an acceptor of a sequence.