Re: Compile-time binding
On Wed, May 28, 2003 at 06:35:31AM -0700, David Storrs wrote: > On Wed, May 28, 2003 at 04:41:36AM -0600, Luke Palmer wrote: > > I know it's compile-time binding, but... what's compile-time binding? > > Luke > > Well, perhaps I'm mistaken, but I had understood it to mean simply > [...] > > - Named variables have their addresses hardcoded during compilation > - Global variables given offset from start of global data area > - Local variables given offset from top of stack > - Object variables given offset from start of object data > - Normal function and method calls are hardcoded during compilation > - Normal functions have specific starting address in object file > - Object methods have specific starting address in object file > - Compiler is able to determine which function matches each call > > (The above shamelessly cribbed from: > http://www.cs.sbcc.net/~shouk/polyhi/tsld005.htm, because it's 9:34 AM > and my brain doesn't wake up for at least another half hour.) (Responding to my own post) I suppose I should explicitly state that P6 will probably implement things a little differently from the details described above (e.g., I don't know that we will have one-and-only one global data area), but the above describes the general concept. --Dks
Re: Cothreads
--- Dave Mitchell <[EMAIL PROTECTED]> wrote: > On Tue, May 27, 2003 at 02:05:57PM -0700, Michael Lazzaro wrote: > > If we could think about "threads" not in terms of forkyness, but > simply > > in terms of coroutines that can be called in parallel, it should be > > > possible to create an implementation of "threading" that had to do > a > > whole heck-of-a-lot less duplication of state, etc. Things > "outside" > > the scope of the thread group would automatically be shared(?), > things > > "inside" the thread group would not be shared unless explicitly > marked > > as such. > > > > Which, if I read it right, is what you proposed too, but with a > > slightly different syntax. > > > > That _might_ make threads a heck of a lot faster upon > creation/startup, > > and a lot less bulky in general. > > But underneath, these pretty coroutiney/virtual-threads still have > to to be implemented in terms of the underlying OS's real threads, so > parrot will have to start being really clever applying locks and > mutexes all over the place to all those outer bits that are > shared etc. On a single-CPU box, the OS level threads could easily be used to support blocking operations feeding back to async I/O, while all "real work" (execution of opcodes) was done in a single thread. Parrot could elect to implement threading on its own. In fact, if consistency of execution is a design objective, it probably should. > So while you may get a cleaner high-level interface to threading > behaviour, I don't think you're gonna gain speed and or bulkiness. It should be possible (if Parrot is in charge of threading) to guarantee pretty sweet behavior -- "context switches" only happen a "good moments" when it's easy to do. That should improve speed quite a bit. =Austin > Blaming Islam for 911 is like blaming Christianity for Oklahoma City. Replying to this tagline would likely start an incendiary discussion unlikely to be considered appropriate for the list. Are you sure you need to troll here?
Re: Cothreads
On Wed, May 28, 2003 at 07:58:37AM -0700, Austin Hastings wrote: > On a single-CPU box, the OS level threads could easily be used to > support blocking operations feeding back to async I/O, while all "real > work" (execution of opcodes) was done in a single thread. Parrot could > elect to implement threading on its own. In fact, if consistency of > execution is a design objective, it probably should. And on a multiple CPU box...? -- Never do today what you can put off till tomorrow.
Re: Cothreads
--- Dave Mitchell <[EMAIL PROTECTED]> wrote: > On Wed, May 28, 2003 at 07:58:37AM -0700, Austin Hastings wrote: > > On a single-CPU box, the OS level threads could easily be used to > > support blocking operations feeding back to async I/O, while all > "real > > work" (execution of opcodes) was done in a single thread. Parrot > could > > elect to implement threading on its own. In fact, if consistency of > > execution is a design objective, it probably should. > > And on a multiple CPU box...? Depends on whether of not you try taking advantage of the multiple CPUs. Now we get into OS-level threads vs. processes, and where the OS is going to support multiprocessing. But in the "most involved case" -- OS threads can span CPUs and still reference a single memory space -- the OS-thread to P6-thread mapping will have to do some sort of locking. My proposal called for locking at the expression level, as well as (of course) tunable locking for individual items. On the one hand, the required amount of locking will raise the cost of running Perl threads in a MP environment. But I think that can be minimised by the compiler knowing when it's in a threaded program. If the MP box with locking is slower than a like SP box, there should probably be a "just-one-user-thread-please" switch. (The MP could still be used to advantage for IO and OS operations by Parrot -- it's just that this particular user program is poorly designed for MP and thus requests C<#! /usr/bin/perl -just-one-user-thread>. =Austin
Re: Cothreads
"Jonathan Scott Duff" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> > If we could think about "threads" not in terms of forkyness, but simply
> > in terms of coroutines that can be called in parallel, it should be
> > possible to create an implementation of "threading" that had to do a
> > whole heck-of-a-lot less duplication of state, etc.
>
> See, this where I start to feel all Cozeny and wonder what the heck
> we're doing even thinking about how it's implemented.
I don't think this is an implementation issue: it is a user-level
distinction. Imagine the following algorithm
coro_sub_thingie tree_iter(FifoOutput $fifo: Tree $tree)
{
$fifo.cothread { tree_iter $tree.left };
$fifo.cothread { tree_iter $tree.right };
$fifo.emit $tree.node_value;
}
while < tree_iter $tree > { print }
(I've s/yield/emit/ to avoid mixing the control and data flow aspects)
This algorithm will work whether the "cothreads" are implemented as parallel
threads, or as coroutines. The difference is the scheduling policy. The
user-level difference is that one policy will produce a deterministic
ordering, whilst the other will be non-deterministic. We can provide a
common syntax to describe the dataflow constraints, and then find a way to
impose the sceduling policy that may, or may not, constrain the
control-flow.
My vision would be to enable concepts like threading and locking to go the
way of C -- it's there, but users typically use "structured" elements
that encapsulate the common patterns of use. Hoare's CSP is one such
abstraction; Shlaer-Mellor's wormhole abstraction is another. Other people
may prefer other abstractions -- but the safest code generally uses message
passing rather than shared variables (because messages don't require
user-level locking).
> What I want to
> know is how it looks from the user perspective. If, in order to
> understand threads, I have to first understand coroutines, I think
> that's a loss because it throws away (or at least morphs into an
> unrecognizable form) all of collect CS knowledge of what "threading"
> usually means. In other words, I think the idea of fork-like
> behaviour is important to threads.
Rather than understanding threads in terms of liberated coroutines, you
could instead try to understand coroutines in terms constrained threads ;-).
If a fork-like behavior is useful for threads, it may also be useful for
coroutines. But fork is a bit like goto -- its an unstructured primitive.
Dave.
Re: Cothreads [Philosophy]
On Tuesday, May 27, 2003, at 07:32 PM, Jonathan Scott Duff wrote: On Tue, May 27, 2003 at 02:05:57PM -0700, Michael Lazzaro wrote: If we could think about "threads" not in terms of forkyness, but simply in terms of coroutines that can be called in parallel, it should be possible to create an implementation of "threading" that had to do a whole heck-of-a-lot less duplication of state, etc. See, this where I start to feel all Cozeny and wonder what the heck we're doing even thinking about how it's implemented. What I want to know is how it looks from the user perspective. Sorry, yes, I'm not talking at all about implementation. I'm just talking about syntax/semantics of invoking them. Underneath, threads and coroutines may well be implemented by giant, man-eating woodchucks battling to the death on a rainy day under a popsicle-stick bridge, for all I care. :-) If, in order to understand threads, I have to first understand coroutines, I think that's a loss because it throws away (or at least morphs into an unrecognizable form) all of collect CS knowledge of what "threading" usually means. In other words, I think the idea of fork-like behaviour is important to threads. [Philosophy] Here's the possible defect in my brain that started my train of thought. I hadn't used coroutines in a long while, so when the topic came up I had to do a little reviewing to make sure I was on the same page. Reviewing done, I started thinking about how coroutines were a different concept from continuations, which were different from threads, and we already had closures, and at what point was the aggregation of all those things going to cause potential Perl6 converts to look at our hypothetical table-o-contents and say "WTF -- exactly how much 'Perl' am I gonna have to learn to be considered a 'good' Perl programmer?" Because _all_ those things are useful concepts, but in spite of the fact that they address very similar problem spaces -- allowing "program state" to be saved and resumed in less-than-strictly-linear ways -- they historically approach it in rather different ways. Whether you're sucking in a concept from a well-worn but sortof-crazy-aunt language like Lisp, or from a possibly-created-as-the-result-of-a-wager language like Icon, each concept largely reached its current fruition independent of the others. No currently-popular(?) language uses _all_ of them at the same time, or to be more precise, you don't see many programmers using _all_ those concepts simultaneously within a given application (and my gut tells me I'd not be keen to debug it if I saw it.) OK. So I get to thinking about coroutines. Coroutines are one of those things that Freak People Out, but once you get to use them, they're quite easy to understand, and damn useful. They're like blocking threads; you call them like a subroutine, they (eventually) return a result to you, and you go on your merry way. They are used _exactly_ as subroutines are used... the only difference is that, like a thread, you can _resume_ the subroutine from the point you last yield()ed, and continue on your way within the subroutine as if that yield() never happened. Again, like a suspended and resumed thread. True threads, on the other hand, are one of those things that everyone *thinks* they know, but which have so many issues with scheduling, blocking, data sharing and hiding, and general wiggyness that it's a lot harder to implement a well-engineered group of threads than most people are willing to admit. Much of that is intrinsic, by definition, to _any_ attempt at parallelization. But how much? Threads are a low-level interface to parallelization. But realistically, people use threads for a *very* narrow set of real-world concepts: (Concept 1) Creating event loops, listeners, etc., in which an event spawns an "action", which runs in parallel to anything else which is running and is independent of all those other things -- so whether it succeeds, fails, or just never ends, it doesn't affect the rest of the program. We'll call this the "subprocess" model. (Concept 2) Splitting multiple "lengthy" tasks to run in parallel, to allow calculations on one task to proceed even if another task is in a blocked (waiting) state, as frequently happens in I/O, or to allow multiple calculations to be run on multiple processors. We'll call this the "parallelization" model. Current popular thread semantics, I would argue, are entirely designed around (Concept 1), and are designed to be very similar to actual _process_ forking. Which at first glance is great, because if you understand process fork()ing you understand threading, but there are two problems with that. First, threads aren't processes, so the analogy breaks down upon more complicated inspection -- if you think of threads as processes, you're going to very quickly get burned by the fact that they aren't. Second, you don't _want_ them to be like proc
Re: Cothreads [Philosophy]
--- Michael Lazzaro <[EMAIL PROTECTED]> wrote:
>
> How, then, would you design an interface around (Concept 1) -- the
> listener/eventloop/subprocess model? Pseudocode for a top-level
> event
> loop might be something like:
>
> loop {
> sleep($fraction), next
>unless $e = get_event();
>
> process_event($e);
> }
>
What about this:
1. C always acts the same way -- stores args in CurThread.result
and gives up control to [?something?].
2. Using the keyword (probably function) C returns a Code object
that when called executes in serial, in the current thread context, and
causes C to transfer control back to the caller (essentially
call-cc) returning the result from yield.
3. Using the keyword (probably keyword - it's complex) C spins
off another thread of execution, causing yield to block.
4. Using C DTRT. In order to support arg-resetting, maybe a
simple call does no-arg-reset, while a resume passes new args. Or vice
versa.
E.g.,
sub fibs(?$a = 0, ?$b = 1) {
loop {
yield $b;
($a, $b) = ($b, $a+$b);
}
}
print fibs; # Error: use of yield without thread or coro context.
print coro fibs; # Coderefs autoderef into calls, right?
print thread fibs; # Magic Thread object treats "FETCH" as "wait".
Continuing:
Anyone can yield, so long as there's two active threads. Just one
thread produces an error/warning/exception/whatever.
Anyone can yield if there's a coro entry on the stack someplace.
If there's two active threads and a coro entry, the nearer (most
recently placed on the stack) wins.
There's an optional arg to yield to override this, as with C. Or
maybe yield is a method on both the Coroutine and Thread classes.
Either way, it can be made explicit.
Recursing doesn't create a new coro unless you say C.
Saying C is how you create a recursive coro.
-4,-2 s/coro/thread/g
Exampling:
sub traverse(Hash $tree) {
return unless $tree;
traverse $tree{left} if $tree{left};
yield $tree{node};
traverse $tree{right} if $tree{right};
}
my %hash is Tree;
my &cotrav := coro &traverse(%hash);
print $_ for ;
my &thtrav := thread &traverse(%hash);
print $_ for ;
=Austin
Re: Cothreads [Philosophy]
"Austin Hastings" <[EMAIL PROTECTED]> wrote:
> 1. C always acts the same way -- stores args in CurThread.result
> and gives up control to [?something?].
I think you want a fifo on the output there -- at least conceptually.
"Stores args in .result" might overly block the producer thread.
"gives up control to" -- the "something" would be the scheduler that's
associated with the fifo. When you have a fifo, you don't need to switch
control on every iteration. In fact, if you're a thread on a multi-cpu
machine, you might never yield control. But at the other end of the
spectrum, a coro would optimize out the fifo and switch contexts every time.
Has any given thought to how the pipeline syntax of A6 might interact with
this stuff? How would we attach multiple output fifos to a "cothread"?
Multiple inputs?
cothread foo is input($a,$b,$c) is output($x,$y,$z)
{
when $a { $x.yield $a+1 }
when $b & $c { $y.yield $b+$c; $z.yield $b-$c }
}
Dave.
Re: Cothreads [Philosophy]
You may evaluate for yourself whether thse comments are actually worth
two cents, but:
I want to be able to tell whether my program is threading or using some
other useful-but-not-what-I'd-do-in-a-hurry tool.
I don't want to learn a thousand different details that are only there
to make sure I know which tool I'm using.
So, if
sub x() is threaded {...}
I'll know by looking at the code. If I'm using a 3rd party module, it
had *better* tell me in the documentation if something I'm doing
requires that I know that I'm spawning threads, or any otherimportant
overhead from coro's or whatever. but if not, it had better handle
them efficiently and *quietly*.
At the top level, I'd prefer to be able to ask "hey, is this sub
threaded?" with something like C but otherwise,
I don't want to be bothered with it.
Regarding advocacy, I want to be able to point someone to a syntax
reference page and not have it intimidate them any more than it already
will
So I'd recommend
use threads;
sub x () is threaded {...}
and then I don't usually need to worry about it. I just say
x();
and hope that it doesn something useful, since it's a stupid name for a
sub. :)
In that vein, I like the idea of consolidating thread and coroutine
syntax. Hell, let's call them something else entirely, like "spawns" or
something, if it helps. I'd live if it uses keywords, I'd be happy if
it uses objects, but I like the idea of it being something simple,
however it's implemented.
my $t = thread.new(&x,[EMAIL PROTECTED]).someMethod;
foo();
bar();
print $t;
A bit ugly, and a bit confusing because of the seperation, but hey,
it's threaded. Add a few comments and enjoy the ride. :)
Paul
--- Michael Lazzaro <[EMAIL PROTECTED]> wrote:
>
> On Tuesday, May 27, 2003, at 07:32 PM, Jonathan Scott Duff wrote:
> > On Tue, May 27, 2003 at 02:05:57PM -0700, Michael Lazzaro wrote:
> >> If we could think about "threads" not in terms of forkyness, but
> >> simply
> >> in terms of coroutines that can be called in parallel, it should
> be
> >> possible to create an implementation of "threading" that had to do
> a
> >> whole heck-of-a-lot less duplication of state, etc.
> >
> > See, this where I start to feel all Cozeny and wonder what the heck
> > we're doing even thinking about how it's implemented. What I want
> to
> > know is how it looks from the user perspective.
>
> Sorry, yes, I'm not talking at all about implementation. I'm just
> talking about syntax/semantics of invoking them. Underneath, threads
>
> and coroutines may well be implemented by giant, man-eating
> woodchucks
> battling to the death on a rainy day under a popsicle-stick bridge,
> for
> all I care. :-)
>
>
> > If, in order to
> > understand threads, I have to first understand coroutines, I think
> > that's a loss because it throws away (or at least morphs into an
> > unrecognizable form) all of collect CS knowledge of what
> "threading"
> > usually means. In other words, I think the idea of fork-like
> > behaviour is important to threads.
>
> [Philosophy]
>
> Here's the possible defect in my brain that started my train of
> thought.
>
> I hadn't used coroutines in a long while, so when the topic came up I
>
> had to do a little reviewing to make sure I was on the same page.
> Reviewing done, I started thinking about how coroutines were a
> different concept from continuations, which were different from
> threads, and we already had closures, and at what point was the
> aggregation of all those things going to cause potential Perl6
> converts
> to look at our hypothetical table-o-contents and say "WTF -- exactly
> how much 'Perl' am I gonna have to learn to be considered a 'good'
> Perl
> programmer?"
>
> Because _all_ those things are useful concepts, but in spite of the
> fact that they address very similar problem spaces -- allowing
> "program
> state" to be saved and resumed in less-than-strictly-linear ways --
> they historically approach it in rather different ways. Whether
> you're
> sucking in a concept from a well-worn but sortof-crazy-aunt language
> like Lisp, or from a possibly-created-as-the-result-of-a-wager
> language
> like Icon, each concept largely reached its current fruition
> independent of the others. No currently-popular(?) language uses
> _all_
> of them at the same time, or to be more precise, you don't see many
> programmers using _all_ those concepts simultaneously within a given
> application (and my gut tells me I'd not be keen to debug it if I saw
>
> it.)
>
> OK. So I get to thinking about coroutines. Coroutines are one of
> those things that Freak People Out, but once you get to use them,
> they're quite easy to understand, and damn useful. They're like
> blocking threads; you call them like a subroutine, they (eventually)
> return a result to you, and you go on your merry way. They are used
> _exactly_ as subroutines are used... the only difference is that,
> like
> a thread
Re: Cothreads [Philosophy]
--- Dave Whipp <[EMAIL PROTECTED]> wrote:
> "Austin Hastings" <[EMAIL PROTECTED]> wrote:
> > 1. C always acts the same way -- stores args in
> CurThread.result
> > and gives up control to [?something?].
>
> I think you want a fifo on the output there -- at least conceptually.
> "Stores args in .result" might overly block the producer thread.
Why would it "overly" block? If you say C, I assume you I
to block -- else, why not use a shared var?
> "gives up control to" -- the "something" would be the scheduler
> that's associated with the fifo. When you have a fifo, you don't
> need to switch control on every iteration. In fact, if you're a
> thread on a multi-cpu machine, you might never yield control.
Of course you will -- *IF* you say C. Using a fifo is different
from being a coro. If you want to say
loop {
$res = compute();
@fifo.unshift $res;
}
that's fine -- but it has nothing to do with being a coro or a thread
(although it's kind of destined to be a thread...).
If you say C in a _thread_, then you're relinquishing control to
the scheduler and optionally setting the result of the thread. If the
scheduler is a round robin preempter, well, no big deal -- some time
goes by and you start again. If the scheduler considers yield to be
synonymous with snap, then the thread is snapped until someone
Cs it. (Frankly, I have no earthly idea why anyone would yield
in a preemptively scheduled thread, unless they are spinwaiting, in
which case they deserve whatever they get. But the behavior is
documented for both.)
> But at the other end of the spectrum, a coro would optimize out the
> fifo and switch contexts every time.
Exactly, save for the context switch: It's not a thread, but a
continuation. A coroutine executes in the same control sequence and the
same variable "environment" as its coroutine. (Look, reflexive noun!
Argh!) Even in a threaded environment, a simple coro should guarantee
sequence of execution with its caller.
That makes me think that the notion of a "cothread" is a valid one -- a
thread that runs in apparent parallel, but suspends completely when it
calls yield. Probably this requires implementing a new thread
scheduler, which can be implemented in perl, not core. This, at least,
should make Simon happy.
> Has any given thought to how the pipeline syntax of A6 might interact
> with this stuff? How would we attach multiple output fifos to a
> "cothread"? Multiple inputs?
>
> cothread foo is input($a,$b,$c) is output($x,$y,$z)
> {
> when $a { $x.yield $a+1 }
> when $b & $c { $y.yield $b+$c; $z.yield $b-$c }
> }
According to me:
my @a, @b, @c;
my @x, @y, @z;
sub foo {
loop {
given wait any(@a, all(@b, @c)) {
when @a { @x.unshift @a.pop; }
default { my $b = @b.pop; my $c = @c.pop;
@y.unshift $b + $c;
@z.unshift $b - $c; }
}
}
}
thread foo;
thread {
for (0..Inf) { ($_ % 7 ?? $_ % 3 ?? @a :: @b :: @c).push $_; }
};
thread {
loop {
wait @x;
print "X: ", @x.pop, "\n";
}
};
thread {
loop {
wait @y;
print "Y: ", @y.pop, "\n";
}
};
thread {
loop {
wait @z;
print "Z: ", @z.pop, "\n";
}
};
Re: Cothreads [Philosophy]
On Wednesday, May 28, 2003, at 01:01 PM, Austin Hastings wrote:
Exampling:
sub traverse(Hash $tree) {
return unless $tree;
traverse $tree{left} if $tree{left};
yield $tree{node};
traverse $tree{right} if $tree{right};
}
my %hash is Tree;
my &cotrav := coro &traverse(%hash);
print $_ for ;
my &thtrav := thread &traverse(%hash);
print $_ for ;
Hmm. I think that having _anything_ on the caller side that has to
change based on whether the called thing is a subroutine vs. a
coroutine probably defeats one of the most central purposes of
coroutines -- that nifty subroutine-like abstraction that makes it
"just work". Consider, under Damian's latest model:
for {...}
It doesn't matter whether foo() is a closure or function returning a
list, lazy list, or iterator, or is a coroutine returning it's .next
value. Which is excellent, and, I'd argue, the whole point; I'm not
sure that we can have any coroutine syntax that _doesn't_ do that, can
we?
But, as Luke pointed out, some of the other syntax required to make
that work is isn't particularly friendly:
coro pre_traverse(%data) {
yield %data{ value };
yield $_ for <&_.clone(%data{ left })>;
yield $_ for <&_.clone(%data{ right })>;
}
If I work backwards, the syntax I'd _want_ for something like that
would be much like Luke proposed:
sub pre_traverse(%data) is coroutine {
yield %data{ value };
pre_traverse( %data{ left } );
pre_traverse( %data{ right } );
}
... where the internal pre_traverses are yielding the _original_
pre_traverse. Whoa, though, that doesn't really work, because you'd
have to implicitly do the clone, which screws up the normal iterator
case! And I don't immediately know how to have a syntax do the right
thing in _both_ cases.
So, if I have to choose between the two, I think I'd rather iteration
be easy than recursion be easy. If lines like
yield $_ for <&_.clone(%data{ left })>;
are too scary, we might be able to make a keyword that does that, like:
sub pre_traverse(%data) is coroutine {
yield %data{ value };
delegate pre_traverse( %data{ left } );
delegate pre_traverse( %data{ right } );
}
Maybe. But in truth, that seems no more intuitive than the first.
(s/coroutine/thread/g for the same rough arguments, e.g. "why should
the caller care if what they're doing invokes parallelization, so long
as it does the right thing?")
MikeL
Re: Cothreads [Philosophy]
--- Michael Lazzaro <[EMAIL PROTECTED]> wrote:
>
> On Wednesday, May 28, 2003, at 01:01 PM, Austin Hastings wrote:
> > Exampling:
> >
> > sub traverse(Hash $tree) {
> > return unless $tree;
> >
> > traverse $tree{left} if $tree{left};
> > yield $tree{node};
> > traverse $tree{right} if $tree{right};
> > }
> >
> > my %hash is Tree;
> > my &cotrav := coro &traverse(%hash);
> > print $_ for ;
> >
> > my &thtrav := thread &traverse(%hash);
> > print $_ for ;
>
>
> Hmm. I think that having _anything_ on the caller side that has to
> change based on whether the called thing is a subroutine vs. a
> coroutine probably defeats one of the most central purposes of
> coroutines -- that nifty subroutine-like abstraction that makes it
> "just work". Consider, under Damian's latest model:
>
> for {...}
>
> It doesn't matter whether foo() is a closure or function returning a
> list, lazy list, or iterator, or is a coroutine returning it's .next
> value. Which is excellent, and, I'd argue, the whole point; I'm not
> sure that we can have any coroutine syntax that _doesn't_ do that,
> can we?
Given that I can say:
sub do_foo {...}
my &foo := coro &do_foo;
I can still provide the "transparent" behavior you're wanting.
> But, as Luke pointed out, some of the other syntax required to make
> that work is isn't particularly friendly:
>
> coro pre_traverse(%data) {
> yield %data{ value };
> yield $_ for <&_.clone(%data{ left })>;
> yield $_ for <&_.clone(%data{ right })>;
> }
> If I work backwards, the syntax I'd _want_ for something like that
> would be much like Luke proposed:
>
> sub pre_traverse(%data) is coroutine {
> yield %data{ value };
> pre_traverse( %data{ left } );
> pre_traverse( %data{ right } );
> }
>
> ... where the internal pre_traverses are yielding the _original_
> pre_traverse. Whoa, though, that doesn't really work, because you'd
> have to implicitly do the clone, which screws up the normal iterator
> case! And I don't immediately know how to have a syntax do the right
> thing in _both_ cases.
>
> So, if I have to choose between the two, I think I'd rather iteration
> be easy than recursion be easy. If lines like
>
> yield $_ for <&_.clone(%data{ left })>;
>
> are too scary, we might be able to make a keyword that does that,
> like:
>
> sub pre_traverse(%data) is coroutine {
> yield %data{ value };
> delegate pre_traverse( %data{ left } );
> delegate pre_traverse( %data{ right } );
> }
>
> Maybe. But in truth, that seems no more intuitive than the first.
Q: Can you "yield" from a subsubroutine?
If no, then yield=>coro at compile time. I don't care much for this
because it puts too much emphasis on remaining "in" the coroutine,
precluding me from distributing functionality. John MacDonald has given
several examples of this.
Q: If you recurse, does it automatically create a new coro context?
If Yes: We need a way to recurse in context. Perhaps by saying
&_.recurse(...) ?
If No: How do you create a new context?
Perhaps we need both: coro-as-verb to create a coro context on any
arbitrary function, and coro-as-type to declare contexts in advance.
>
> (s/coroutine/thread/g for the same rough arguments, e.g. "why should
> the caller care if what they're doing invokes parallelization, so
> long as it does the right thing?")
Global variables. Threads __never__ do the right thing.
=Austin
Re: Cothreads [Philosophy]
> But, as Luke pointed out, some of the other syntax required to make
> that work is isn't particularly friendly:
>
> coro pre_traverse(%data) {
> yield %data{ value };
> yield $_ for <&_.clone(%data{ left })>;
> yield $_ for <&_.clone(%data{ right })>;
> }
>
> If I work backwards, the syntax I'd _want_ for something like that
> would be much like Luke proposed:
>
> sub pre_traverse(%data) is coroutine {
> yield %data{ value };
> pre_traverse( %data{ left } );
> pre_traverse( %data{ right } );
> }
>
> ... where the internal pre_traverses are yielding the _original_
> pre_traverse. Whoa, though, that doesn't really work, because you'd
> have to implicitly do the clone, which screws up the normal iterator
> case! And I don't immediately know how to have a syntax do the right
> thing in _both_ cases.
>
> So, if I have to choose between the two, I think I'd rather iteration
> be easy than recursion be easy. If lines like
>
> yield $_ for <&_.clone(%data{ left })>;
>
> are too scary, we might be able to make a keyword that does that, like:
>
> sub pre_traverse(%data) is coroutine {
> yield %data{ value };
> delegate pre_traverse( %data{ left } );
> delegate pre_traverse( %data{ right } );
> }
>
> Maybe. But in truth, that seems no more intuitive than the first.
Well, at least it's not using all those fancy features that will scare
off non-gurus. But I think that instead of something declared coro
I a coroutine iterator, why not just make it one (which I
believe was Damian's original intent)?
for <&foo> {...}
A subroutine could gladly return one of these iterators in place of a
different kind of iterator (or iterable structure).
The problems come when passing arguments to it. For that, you can use
a coroutine factory, or you can do it this way:
for < coro { foo($a, $b) } > {...}
We might need some shorthand for that... but probably not.
This is interesting:
my $coro = coro { foo($a, $b) };
$coro();
Calls foo($a, $b) without becoming a coroutine. I don't know whether
this is useful or just strangely counter-intuitive.
Luke
Re: Cothreads [Philosophy]
> --- Michael Lazzaro <[EMAIL PROTECTED]> wrote:
> >
> > On Wednesday, May 28, 2003, at 01:01 PM, Austin Hastings wrote:
> > > Exampling:
> > >
> > > sub traverse(Hash $tree) {
> > > return unless $tree;
> > >
> > > traverse $tree{left} if $tree{left};
> > > yield $tree{node};
> > > traverse $tree{right} if $tree{right};
> > > }
> > >
> > > my %hash is Tree;
> > > my &cotrav := coro &traverse(%hash);
> > > print $_ for ;
> > >
> > > my &thtrav := thread &traverse(%hash);
> > > print $_ for ;
> >
> >
> > Hmm. I think that having _anything_ on the caller side that has to
> > change based on whether the called thing is a subroutine vs. a
> > coroutine probably defeats one of the most central purposes of
> > coroutines -- that nifty subroutine-like abstraction that makes it
> > "just work". Consider, under Damian's latest model:
> >
> > for {...}
> >
> > It doesn't matter whether foo() is a closure or function returning a
> > list, lazy list, or iterator, or is a coroutine returning it's .next
> > value. Which is excellent, and, I'd argue, the whole point; I'm not
> > sure that we can have any coroutine syntax that _doesn't_ do that,
> > can we?
>
> Given that I can say:
>
> sub do_foo {...}
> my &foo := coro &do_foo;
>
> I can still provide the "transparent" behavior you're wanting.
>
> > But, as Luke pointed out, some of the other syntax required to make
> > that work is isn't particularly friendly:
> >
> > coro pre_traverse(%data) {
> > yield %data{ value };
> > yield $_ for <&_.clone(%data{ left })>;
> > yield $_ for <&_.clone(%data{ right })>;
> > }
>
> > If I work backwards, the syntax I'd _want_ for something like that
> > would be much like Luke proposed:
> >
> > sub pre_traverse(%data) is coroutine {
> > yield %data{ value };
> > pre_traverse( %data{ left } );
> > pre_traverse( %data{ right } );
> > }
> >
> > ... where the internal pre_traverses are yielding the _original_
> > pre_traverse. Whoa, though, that doesn't really work, because you'd
> > have to implicitly do the clone, which screws up the normal iterator
> > case! And I don't immediately know how to have a syntax do the right
> > thing in _both_ cases.
> >
> > So, if I have to choose between the two, I think I'd rather iteration
> > be easy than recursion be easy. If lines like
> >
> > yield $_ for <&_.clone(%data{ left })>;
> >
> > are too scary, we might be able to make a keyword that does that,
> > like:
> >
> > sub pre_traverse(%data) is coroutine {
> > yield %data{ value };
> > delegate pre_traverse( %data{ left } );
> > delegate pre_traverse( %data{ right } );
> > }
> >
> > Maybe. But in truth, that seems no more intuitive than the first.
>
> Q: Can you "yield" from a subsubroutine?
>
> If no, then yield=>coro at compile time. I don't care much for this
> because it puts too much emphasis on remaining "in" the coroutine,
> precluding me from distributing functionality. John MacDonald has given
> several examples of this.
Agreed. I want to be able to distribute functionality. This is
isomorphic with recursion.
> Q: If you recurse, does it automatically create a new coro context?
>
> If Yes: We need a way to recurse in context. Perhaps by saying
> &_.recurse(...) ?
Obviously, that's not what I advocate.
> If No: How do you create a new context?
Like this:
# countcounter(4) yields 0 0 1 0 0 1 2 3
coro countcounter($n) {
for 0..$n-1 -> $c {
my $counter = coro { countcounter($c) };
yield $_ for <$counter>;
yield $c;
}
}
Yay for objects!
The only thing declaring countcounter as a coro gets you is the
ability to use &countcounter itself as an iterator... and some
documentation. Since it takes an argument, it would probably be just
as useful as a sub.
> > (s/coroutine/thread/g for the same rough arguments, e.g. "why should
> > the caller care if what they're doing invokes parallelization, so
> > long as it does the right thing?")
>
> Global variables. Threads __never__ do the right thing.
Hopefully Perl 6 will change that.
Luke
Re: Cothreads [Philosophy]
"Austin Hastings" <[EMAIL PROTECTED]> wrote
> --- Dave Whipp <[EMAIL PROTECTED]> wrote:
> > "Austin Hastings" <[EMAIL PROTECTED]> wrote:
> > > 1. C always acts the same way -- stores args in
> > CurThread.result
> > > and gives up control to [?something?].
> >
> > I think you want a fifo on the output there -- at least conceptually.
> > "Stores args in .result" might overly block the producer thread.
>
> Why would it "overly" block? If you say C, I assume you I
> to block -- else, why not use a shared var?
The lack of a fifo requires the producer and consumer to run in lockstep (or
else you start losing data). The both ends of the channel have somewhat
bursty temporal behavior, then this coupling can be undesirable. A fifo, by
introducing slack, allows the system run more smoothly.
For a nicer interface, I would prefer that the fifo be implicit. This way,
the producer produces a sequences of scalars, and the consumer consumes
them; but if the "thread" is being executed as a coroutine, then perl can
omit the fifo as an optimization.
As an aside, C does not guarentee to block until the consumer has
consumed the current value: it just guarentees to give the scheduler the
option to switch contexts. So unless you know that your scheduler is
scheduling you as a coroutine, then the lack of a fifo (explicit or
implicit) would likely cause problems.
And why not use a shared variable? Because they are evil, the spawn of
Satan, etc. They are a breeding ground for bugs. Implicit fifos -- aka
message queues -- encapsulate the locks, and thus are not so bug-friendly.
Most importantly, a message queue abstraction works efficiently, though
differently, for both coroutines and threads. They let me describe the
dataflow independently of control flow.
> thread {
> loop {
> wait @x;
> print "X: ", @x.pop, "\n";
> }
> };
I hope we'll be able to write that as:
thread @x
{
print "X: ", @x.pop, "\n";
}
though it would be nice to make the C implicit:
thread <@x>
{
print "X: $_\n";
}
Dave
Re: Cothreads [Philosophy]
On Wednesday, May 28, 2003, at 02:56 PM, Austin Hastings wrote:
(s/coroutine/thread/g for the same rough arguments, e.g. "why should
the caller care if what they're doing invokes parallelization, so
long as it does the right thing?")
Global variables. Threads __never__ do the right thing.
Heh. That's for sure.
I am enamored with the possibility of finding some sub-like syntax for
threads where variables are shared *solely* based on their scope,
because that is simply The Way It Should Work. If you're in a thread,
and refer to a var outside of the threaded block, it's shared; if you
refer to a lexical var within the thread, it's not shared. Much like
your April example, or John M's idea of C vs. C. So that if:
sub process_event (Event $e) is threaded { # (A) an
always-parallelized subroutine
my $z;
...
}
our $x;
loop {
our $y;
my $current_event = get_event()
or next;
process_event($current_event); # (B) creates a 'process_event'
thread for each event
}
$x and $y are shared between all active threads invoked by line (B),
the threads can't see the lexical $current_event at all, and the
lexical $e and $z are private to each individual C
thread. Bada-bing, Bada-boom, can't get much more intuitive than that.
OTOH, "threads" have proven historically easiest to manage when little
if any data is shared. OTOOH, threads that "share" everything but
their private lexical data would be faster/easier to create & run,
because they don't have to do mass copying of program state. OTOOOH,
they'd still need automatically generated locking when they _were_
accessing those shared vars. OTH, there's nothing wrong with that
-- that's what threads are supposed to do, and the vast majority of
speed-oriented threads don't *refer* to much shared data, and big
"event loop" threads do because, well, they have to.
MikeL
Re: Cothreads [Philosophy]
"Michael Lazzaro" <[EMAIL PROTECTED]> wrote in
> for {...}
>
> It doesn't matter whether foo() is a closure or function returning a
> list, lazy list, or iterator, or is a coroutine returning it's .next
> value. Which is excellent, and, I'd argue, the whole point; I'm not
> sure that we can have any coroutine syntax that _doesn't_ do that, can
> we?
>
> But, as Luke pointed out, some of the other syntax required to make
> that work is isn't particularly friendly:
...
> If I work backwards, the syntax I'd _want_ for something like that
> would be much like Luke proposed:
...
> ... where the internal pre_traverses are yielding the _original_
> pre_traverse. Whoa, though, that doesn't really work, because you'd
> have to implicitly do the clone, which screws up the normal iterator
> case! And I don't immediately know how to have a syntax do the right
> thing in _both_ cases.
I'll try not to repeat myself again...
I think that the problem you're having with the syntax is a result of
focusing on the control-flow aspect, rather than the dataflow. If you
describe it using data, then you get
sub pre_traverse(@out is rw, %data)
{
push @out, %data{ value };
pre_traverse( @out, %data{ left } );
pre_traverse( @out, %data{ right } );
}
This describes the data correctly, so now lets fix the execution model. I do
this in two steps: first I provide an implementation that works: then I
assume some magic happens...
The implementation that works is to put the recursive function inside a
thread, and then to implement @out using a tie (or, rather, a variable-type)
which has the semantics that constrain the execution so that only the
producer or consumer thread is running at a given time (this requires a pair
of semaphores, plus a bit of cooperation from the sub.
This would implement the ping-pong control flow that is desired, whilst
maintaining the dataflow of the recursive traversal.
The magic bit is to wrap it up in a keyword and assume that, given the
keyword, perl can optimse the threads onto continuations. If perl can't
optimise for some reason, it doesn't matter because the control flow will
still be correct. I'll write my coro using invocant syntax to supply the
fifo (which I will define to be, by default, a magic fifo of the type I just
described).
coro pre_traverse(@out: %data)
{
@out.push %data{value};
@out.pre_traverse %data{left};
@out.pre_traverse %data{right};
}
Finally, because the @out is an invocant (magically created by perl as the
handle to the coroutine)
coro pre_traverse(@out: %data)
{
.push %data{value};
.pre_traverse %data{left};
.pre_traverse %data{right};
}
So we get to a simple end-point: similar to the original but simpler because
I don't worry about describing the control flow, I don't need to worry about
cloning the execution context, yielding, etc. The Fifo (invocant) does all
that for my and, in addition, acts as the handle to the coro. So if I want
to do silly things with multiple, nested, interleaved, coroutines -- then
using different handles will avoid ambiguity.
> (s/coroutine/thread/g for the same rough arguments, e.g. "why should
> the caller care if what they're doing invokes parallelization, so long
> as it does the right thing?")
Indeed: why should be callee care, either?
Dave.
