Heads up: Dynamic environment now captured in continuations

1 view
Skip to first unread message

Bob Rogers

unread,
Oct 2, 2006, 8:54:22 PM10/2/06
to perl6-i...@perl.org
This weekend's project (committed as r14830) makes continuations
capture the dynamic environment so that they can restore it properly on
invocation. This makes it possible for multiple continuations to
coexist that return to different environments in the same context.

One word of caution, though: I had also wanted to move the
control_stack slot from the context to the interpreter, but found that
doing so breaks coroutines rather severely (see transcript below, using
slightly hacked signalling code). So this logical next step is on hold
for now. However, I strongly suspect that coroutines are still broken
in ways that are not detected by the test suite -- therefore, please let
me know if your favorite app develops a coroutine allergy.

-- Bob Rogers
http://rgrjr.dyndns.org/

------------------------------------------------------------------------
gmake -C compilers/tge
gmake[1]: Entering directory `/usr/src/parrot/compilers/tge'
../../parrot -o TGE/Rule.pbc --output-pbc TGE/Rule.pir
../../parrot ../../compilers/pge/pgc.pir --output=TGE/Parser.pir TGE/Parser.pg
attempt to access code outside of current code segment [2]
current instr.: 'parrot;PGE::P6Grammar;ws_corou' pc 114 (EVAL_2:47)
called from Sub 'parrot;PGE::Match;next' pc 540 (compilers/pge/PGE/Match.pir:209)
called from Sub 'parrot;PGE::P6Grammar;statement_corou' pc 246 (EVAL_5:104)
called from Sub 'parrot;PGE::P6Grammar;statement' pc 20 (EVAL_5:8)
called from Sub 'parrot;PGE::P6Grammar;compile_p6grammar' pc 333 (../../compilers/pge/pgc.pir:228)
called from Sub 'parrot;PGE::P6Grammar;main' pc 135 (../../compilers/pge/pgc.pir:111)
gmake[1]: *** [TGE/Parser.pir] Error 1
gmake[1]: Leaving directory `/usr/src/parrot/compilers/tge'
make: *** [compilers.dummy] Error 2

Francois Perrad

unread,
Oct 4, 2006, 2:55:34 AM10/4/06
to Bob Rogers, perl6-i...@perl.org
At 20:54 02/10/2006 -0400, Bob Rogers wrote:
> This weekend's project (committed as r14830) makes continuations
>capture the dynamic environment so that they can restore it properly on
>invocation. This makes it possible for multiple continuations to
>coexist that return to different environments in the same context.
>
> One word of caution, though: I had also wanted to move the
>control_stack slot from the context to the interpreter, but found that
>doing so breaks coroutines rather severely (see transcript below, using
>slightly hacked signalling code). So this logical next step is on hold
>for now. However, I strongly suspect that coroutines are still broken
>in ways that are not detected by the test suite -- therefore, please let
>me know if your favorite app develops a coroutine allergy.

I've tried without success to implement coroutine in language Lua.
See files :
languages/lua/pmc/luathread.pmc
languages/lua/lib/luacoroutine.pir
languages/lua/t/coroutine.t

Help is welcome.

François.

Bob Rogers

unread,
Oct 7, 2006, 6:52:29 PM10/7/06
to François PERRAD, perl6-i...@perl.org
From: François PERRAD <francoi...@gadz.org>
Date: Wed, 04 Oct 2006 08:55:34 +0200

I've tried without success to implement coroutine in language Lua . . .
Help is welcome.

François.

I am not surprised that you have had difficulty. I can't even get a
simple recursive coroutine to work in PIR. See the first attachment for
an attempt. I think this is a fundamental problem; I know nothing about
Lua, but I strongly suspect Parrot coroutines would have to be
redesigned to support what the Lua manual says about them [1].

But that's not a show-stopper; continuations alone are powerful
enough to do most of what you need. The second attachment is a demo
implementation based loosely on the Lua definitions of coroutine.create,
coroutine.resume, and coroutine.yield. The first third of the code
defines PIR near-equivalents to these, and the rest includes several
demos. The demo that runs by default (i.e. without editing the code) is
a solution to the "same fringe" problem [2] using a pair of recursive
coroutines to enumerate two trees simultaneously.

However, the abstraction is poor. This is partly because I was too
lazy to figure out whether an object-oriented solution would fail due to
the "continuation barrier" problem, and partly because I was too lazy to
make the "current coroutine" implicit, as it is in Lua [3]. Still, I
hope you find this useful. Probably it ought to get turned into an
example . . .

Also, the "[oops; got 4 and X]" lines in the output seem to suggest
that Parrot may be getting confused about parameters. The "4" is really
the length of one of the coro structures, which must be getting passed
as the first arg. Also, it fails with "too many args" if you don't
accept at least two values from the coroutine_yield. I suspect Parrot
is reusing some old parameter information; I'll try to nail this down if
I get a chance.

[1] http://www.lua.org/manual/5.1/manual.html#2.11

[2] http://www.nsl.com/papers/samefringe.htm, e.g.

[3] This also depends on how the "current coroutine" should be scoped.
Dynamic scoping seems reasonable, but that's not obvious from [1].

recursive-coroutine-1.pir
pir-coroutine-1.pir

Bob Rogers

unread,
Oct 8, 2006, 7:24:56 PM10/8/06
to François PERRAD, perl6-i...@perl.org
From: Bob Rogers <rogers...@rgrjr.dyndns.org>
Date: Sat, 7 Oct 2006 18:52:29 -0400

. . .

Also, the "[oops; got 4 and X]" lines in the output seem to suggest
that Parrot may be getting confused about parameters. The "4" is really
the length of one of the coro structures, which must be getting passed
as the first arg. Also, it fails with "too many args" if you don't
accept at least two values from the coroutine_yield. I suspect Parrot
is reusing some old parameter information; I'll try to nail this down if
I get a chance.

This turns out to have been a bug in my implementation; extensive
debugging shows that all parameter to all continuations are going to the
right places. Shame on me for having suspected Parrot. ;-}

A corrected version is attached.

-- Bob

pir-coroutine-2.pir

Bob Rogers

unread,
Oct 9, 2006, 9:30:34 PM10/9/06
to perl6-i...@perl.org
From: Bob Rogers <rogers...@rgrjr.dyndns.org>
Date: Mon, 2 Oct 2006 20:54:22 -0400

This weekend's project (committed as r14830) makes continuations
capture the dynamic environment so that they can restore it properly on
invocation. This makes it possible for multiple continuations to
coexist that return to different environments in the same context.

One word of caution, though: I had also wanted to move the
control_stack slot from the context to the interpreter, but found that

doing so breaks coroutines rather severely . . . So this logical


next step is on hold for now.

Done as r14876.

However, I strongly suspect that coroutines are still broken
in ways that are not detected by the test suite -- therefore, please let
me know if your favorite app develops a coroutine allergy.

This is still true, but I'm pretty sure I haven't made coroutines any
less functional.

-- Bob

Francois Perrad

unread,
Oct 10, 2006, 7:39:30 AM10/10/06
to Bob Rogers, perl6-i...@perl.org

Thank for your long response.

I included your code in languages/lua/lib/luacoroutine.pir (r14877).
I encountered 2 problems :
1) coroutine_yield needs a current coroutine (not surprising)
2) I want replace the LuaThread PMC by a PIR classe.
So, I create a classe :
$P0 = subclass 'FixedPMCArray', 'thread'
But when I replace in coroutine_create
coro = new .FixedPMCArray
coro = 4
by :
find_type $I0, 'thread'
coro = new $I0
coro = 4
some test of languages/lua/t/coroutine.t fail with the following
message :
FixedPMCArray: index out of bounds!

François.

Bob Rogers

unread,
Oct 10, 2006, 7:25:41 PM10/10/06
to François PERRAD, perl6-i...@perl.org
From: François PERRAD <francoi...@gadz.org>
Date: Tue, 10 Oct 2006 13:39:30 +0200

Thank for your long response.

I included your code in languages/lua/lib/luacoroutine.pir (r14877).
I encountered 2 problems :

1) coroutine_yield needs a current coroutine (not surprising)

Yes, this is the "implicit current coroutine" problem I mentioned. I
think this is best solved with a dynamically-bound variable, the value
of which Lua's "coroutine.running" can just return.

2) I want replace the LuaThread PMC by a PIR classe . . .

some test of languages/lua/t/coroutine.t fail with the following
message :
FixedPMCArray: index out of bounds!

François.

On Sunday, to see if it would work, I created a Parrot::Coroutine class,
and it works like a charm. I haven't committed it yet because it needs
a test case. This will be an extended version of the "same fringe" demo
but converted into a proper example; it's also an excellent workout for
closures.

So please stay tuned.

-- Bob

Bob Rogers

unread,
Oct 13, 2006, 10:21:18 PM10/13/06
to François PERRAD, perl6-i...@perl.org
Here's the Parrot::Coroutine patch; I will commit this if nobody
objects.

It seems to me that this should be mentioned in docs/compiler_faq.pod
as an alternative way to do coroutines . . . I will take a look at this.

In fact, it might be safer to deprecate Coroutine.pmc until it can be
redesigned. It would be a shame if somebody looked at only that and
concluded that Parrot doesn't really support coroutines after all.

pir-coroutine-class-1.patch

Leopold Toetsch

unread,
Oct 14, 2006, 7:22:07 AM10/14/06
to perl6-i...@perl.org
Am Samstag, 14. Oktober 2006 04:21 schrieb Bob Rogers:
>    Here's the Parrot::Coroutine patch; I will commit this if nobody
> objects.

Please note that you can extend existing PMCs with PIR methods.

>    It seems to me that this should be mentioned in docs/compiler_faq.pod
> as an alternative way to do coroutines . . . I will take a look at this.

I'd rather have some specs, how couroutines should behave before adding yet
another implementation. Then coroutine.pmc can be adjusted.

>    In fact, it might be safer to deprecate Coroutine.pmc until it can be
> redesigned.  It would be a shame if somebody looked at only that and
> concluded that Parrot doesn't really support coroutines after all.

Coroutines are e.g. used inside PGE and are working.

my 2c,
leo

Bob Rogers

unread,
Oct 14, 2006, 1:48:22 PM10/14/06
to Leopold Toetsch, perl6-i...@perl.org
From: Leopold Toetsch <l...@toetsch.at>
Date: Sat, 14 Oct 2006 13:22:07 +0200

Am Samstag, 14. Oktober 2006 04:21 schrieb Bob Rogers:

> ,b (B ,b (BHere's the Parrot::Coroutine patch; I will commit this if nobody
> objects.

Please note that you can extend existing PMCs with PIR methods.

True, but this is something different. Coroutine.pmc is limited in a
way that can't be cured by extension. The problem is that the C<yield>
instruction only works if used directly in the sub that is called as the
coroutine entry point. As a result, these coroutines can't recur, which
is why they can't even solve the "same fringe" problem, which is
believed to be the simplest problem that requires coroutines to be
solved efficiently. The only difference between C<yield> and C<return>
is that C<yield> records the next instruction afterwards.

> ,b (B ,b (BIt seems to me that this should be mentioned in docs/compiler_faq.pod


> as an alternative way to do coroutines . . . I will take a look at this.

I'd rather have some specs, how couroutines should behave before adding yet
another implementation. Then coroutine.pmc can be adjusted.

That was my original thought, too, but I see several arguments for
proceeding:

The first argument is that I think we are not yet ready to fix
Coroutine.pmc. In order to preserve the simplicity of the existing
C<yield> instruction, it is necessary to have an implicit "current
coroutine" that yield invokes. (The existing implementation uses the
current sub as the current coroutine, but that is precisely why it is
too limited.) IMHO, the only way to address this robustly is by
recording the current coroutine as part of the dynamic environment. My
preferred technique would be to use a global variable that is
dynamically bound; that way, we wouldn't need to invent a new mechanism.
As it is, fixing Coroutine.pmc will require API changes to coroutine
creation, so keeping C<yield> as-is will minimize the overall hassle of
converting to a new implementation.

So while we could redesign Coroutine.pmc now, I don't think we are
ready to reimplement it. In the mean time, having an alternative
implementation allows those who want a full implementation (hi,
Fran ,Ag (Bois!) to get on with it.

Beyond that, Parrot::Coroutine and its "same fringe" test case serve
a useful function for continuations. The test case gives them a good
workout, and the coroutine implementation provides an accessible example
of a nontrivial application of continuations that can be compared with
those of other languages.

> ,b (B ,b (BIn fact, it might be safer to deprecate Coroutine.pmc until it can be
> redesigned. ,b (BIt would be a shame if somebody looked at only that and


> concluded that Parrot doesn't really support coroutines after all.

Coroutines are e.g. used inside PGE and are working.

my 2c,
leo

True, but that's because PGE makes very limited use of coroutines, so
having a limited coroutine is not a handicap. In fact,
PGE::Match::ws_corou is just a loop with a single C<yield> instruction,
so in theory it should be straightforward to replace it with a closure
[1]. In practice, I haven't been able to do this; the attached patch
comes close, but still breaks a few test cases, no doubt because I do
not understand what PGE::Match::ws_corou is trying to do.

Indeed, it is not even clear to me why one would prefer a coroutine
(or even a closure) to keeping explicit state in the PGE::Match object
that is accessed and updated directly by the 'next' method. It would be
easier to examine and reset explicit state, for one thing. But perhaps
this is just a specialized version of the code generated by
PGE::Exp::Subrule, which I have not tried to understand at all.

I also have a further motivation in providing Parrot::Coroutine: I
have no personal interest in whether any coroutine implementation works
or not, but Coroutine.pmc pretends (badly) to be a continuation, and
that gets in the way of implementing dynamic environment features. From
my point of view, it would be ideal if PGE were rewritten to use
closures so that the current Coroutine.pmc could be dropped entirely, to
be reimplemented from scratch after the dust settles. But that is not
necessary, let alone realistic, so I am willing to do the extra work to
keep from breaking Coroutine.pmc any further. Still, I would like to be
able to offer Parrot::Coroutine as a workaround for the time being in
order to lessen the pressure to fix Coroutine.pmc immediately.

-- Bob

[1] In fact, all code that uses Coroutine.pmc can be replaced by a
closure, since C<yield> can only return to the immediate caller.
But the general case requires an additional state variable that
records which instruction yielded.

pge-ws-closure-1.patch

Leopold Toetsch

unread,
Oct 14, 2006, 4:34:33 PM10/14/06
to perl6-i...@perl.org, Bob Rogers
Am Samstag, 14. Oktober 2006 19:48 schrieb Bob Rogers:

> True, but this is something different.  Coroutine.pmc is limited in a
> way that can't be cured by extension.

[ and a lot more ]

Thanks for the detailed explanation. I now see the point of a
Parrot::Coroutine thingy.

OTOH I'd still like to have some proposals explaining all the planned use
cases (incl. HLL examples) what some more flexible coroutines could do. Some
ascii pictures of control flow would be nice to have too.

leo

Bob Rogers

unread,
Oct 14, 2006, 5:20:50 PM10/14/06
to Leopold Toetsch, perl6-i...@perl.org
From: Leopold Toetsch <l...@toetsch.at>
Date: Sat, 14 Oct 2006 22:34:33 +0200

Am Samstag, 14. Oktober 2006 19:48 schrieb Bob Rogers:

> True, but this is something different.  Coroutine.pmc is limited in a
> way that can't be cured by extension.

[ and a lot more ]

Thanks for the detailed explanation. I now see the point of a
Parrot::Coroutine thingy.

Great; committed as r14925.

OTOH I'd still like to have some proposals explaining all the planned use
cases (incl. HLL examples) what some more flexible coroutines could do. Some
ascii pictures of control flow would be nice to have too.

leo

This sounds more like a coroutine tutorial to me. I was hoping that the
'SEE ALSO' links in the source would cover that. Still, I agree it
would be good to have a detailed explanation of how coroutines work in
Parrot terms.

The problem is that those who don't understand continuations will
have a much harder time understanding coroutines. So an introduction to
Parrot coroutines probably belongs in the larger context of explaining
continuations in particular and advanced Parrot control structures in
general. In July, I started writing just such an introduction, but have
made no progress since, for two reasons: (a) I was waiting to fix some
Parrot misbehaviors first so that the examples would work, and (b)
coding is more fun anyway (and makes my fingers hurt less).

So I am planning on doing something like this eventually, it's just
taking more time than I would have liked.

-- Bob

Leopold Toetsch

unread,
Oct 14, 2006, 5:40:48 PM10/14/06
to perl6-i...@perl.org, Bob Rogers, Chip Salzenberg, Allison Randal
Am Samstag, 14. Oktober 2006 04:21 schrieb Bob Rogers:

A further note, while the patch has hit svn: this namespace

> +.namespace ["Parrot::Coroutine"]

is actually the absolute namespace:

[ 'parrot'; 'Parrot::Coroutine' ]

which isn't importable by a lot of HLLs.

My remark isn't specific to this patch, but just a general reminder regarding namespace usage and names. There are still no official specs, where parrot libs should be in the namespace hierarchy, OTOH hierachical namespaces are implemented and working.

Core's coroutine.pmc is using this absolute namespace

[ 'parrot'; 'Coroutine' ]

which is

.namespace ["Coroutine"]

under the default HLL 'parrot'.
And as already said several times, the HLL implications towards namespaces are looking really unhelpful to me.
leo

Leopold Toetsch

unread,
Oct 14, 2006, 5:47:13 PM10/14/06
to perl6-i...@perl.org
Am Samstag, 14. Oktober 2006 23:20 schrieb Bob Rogers:
> This sounds more like a coroutine tutorial to me.  I was hoping that the
> 'SEE ALSO' links in the source would cover that.  Still, I agree it
> would be good to have a detailed explanation of how coroutines work in
> Parrot terms.
>
>    The problem is that those who don't understand continuations will
> have a much harder time understanding coroutines.

I think re explanation more of some use cases like: if you yield from here
(this coro), you are back there, then, by doing foo, you are continuing where
you left off or elsewhere ;) ...

No continuation knowledge needed probably, just how can I do generators or
such. Just talking about the effect that's it.

Thanks,
leo

Bob Rogers

unread,
Oct 14, 2006, 5:59:26 PM10/14/06
to perl6-i...@perl.org
From: Leopold Toetsch <l...@toetsch.at>
Date: Sat, 14 Oct 2006 23:47:13 +0200

Thanks,
leo

Gotcha; you want a worked-out example or two. Yes, that would be a good
thing to add to Coroutine.pir. I'll put it on my list.

-- Bob

Francois Perrad

unread,
Oct 17, 2006, 4:47:02 AM10/17/06
to perl6-i...@perl.org, perl6-i...@perl.org
At 13:48 14/10/2006 -0400, Bob Rogers wrote:

> So while we could redesign Coroutine.pmc now, I don't think we are
>ready to reimplement it. In the mean time, having an alternative
>implementation allows those who want a full implementation (hi,

>Fran,Ag(Bois!) to get on with it.

I've removed the LuaThread PMC (in r14936).
Now, Lua doesn't depend of the deprecated Coroutine PMC.

François.


Leopold Toetsch

unread,
Oct 17, 2006, 2:00:04 PM10/17/06
to perl6-i...@perl.org
Am Dienstag, 17. Oktober 2006 10:47 schrieb François PERRAD:
> Now, Lua doesn't depend of the deprecated Coroutine PMC.

Coroutine PMC isn't deprecated, it's limited in its functionality.

leo

Francois Perrad

unread,
Oct 23, 2006, 12:51:03 PM10/23/06
to Bob Rogers, perl6-i...@perl.org

In languages/lua/lib/thread.pir, I create a Lua thread type by extension of
Parrot::Coroutine.
So I add a lot of methods for Lua type, but I think that 2 of these methods
could be integrated in Parrot::Coroutine :
- __clone
- __get_pointer (equivalent of get_pointer() in src/pmc/sub.pmc)

François.


Bob Rogers

unread,
Oct 24, 2006, 11:17:55 AM10/24/06
to François PERRAD, perl6-i...@perl.org
From: François PERRAD <francoi...@gadz.org>
Date: Mon, 23 Oct 2006 18:51:03 +0200

François.

The thread.pir methods you mention are stubs, so I'm not certain what
they should do.

* Should __clone copy the whole object state, or just the initial
sub, effectively resetting the coroutine to the start? Methinks the
latter, but I have little practical experience with coroutines.

* What should __get_pointer return? The address of the PMC? If so,
would that be better to implement on default.pmc?

In any case, I have had to limit my Parrot hacking lately to keep my
hands from hurting [1], so feel free to enhance Parrot::Coroutine as you
see fit. AFAIK, you're the only one using it at this point, so you
shouldn't need to worry about breaking anything else.

-- Bob

[1] FWIW, it's not a big deal, and I'm trying hard to keep it that way.

Reply all
Reply to author
Forward
0 new messages