Allowing push/pop across sub calls
Bob Rogers
news is that it also breaks PGE, albeit in a small way. Six of the
"<after>" tests (mostly, but not exclusively, involving "<!after>") in
t/compilers/pge/p6rules/builtins.t seem to go into an infinite loop. I
have been unable to figure this out, so I'm hoping it will be easy for
someone who understands PGE. (Maybe there's something in PGE that
assumes that returning from a sub restores the state of the user stack?)
When (and if) that happens, we can decide whether this patch is worth
doing. TIA,
-- Bob Rogers
http://rgrjr.dyndns.org/
Patrick R. Michaud
Content-Description: message body text
I'll take a look and see if I can figure out what's going on from
the PGE side.
Pm
Patrick R. Michaud
Content-Description: message body text
> news is that it also breaks PGE, albeit in a small way. Six of the
> "<after>" tests (mostly, but not exclusively, involving "<!after>") in
> t/compilers/pge/p6rules/builtins.t seem to go into an infinite loop. I
> have been unable to figure this out, so I'm hoping it will be easy for
> someone who understands PGE. (Maybe there's something in PGE that
> assumes that returning from a sub restores the state of the user stack?)
Surprisingly, the following rule infinite loops when applied to
a target string of "cb":
<!after c>b
Perhaps equally surprisingly, neither the code generated for the
above rule nor the <after> subrule itself make use of either the
"push" or "pop" opcodes.
Still looking...
Pm
Patrick R. Michaud
Content-Description: message body text
> news is that it also breaks PGE, albeit in a small way. Six of the
> "<after>" tests (mostly, but not exclusively, involving "<!after>") in
> t/compilers/pge/p6rules/builtins.t seem to go into an infinite loop. I
> have been unable to figure this out, so I'm hoping it will be easy for
> someone who understands PGE. (Maybe there's something in PGE that
> assumes that returning from a sub restores the state of the user stack?)
Okay, looking at a debug trace further it appears that the user
stack is indeed not behaving the way PGE expects it to. This
could be from a shortcoming in my understanding of how things
will work, so the detailed explanation of PGE's expectations
is below.
PGE does not expect that a sub will restore the state of the user
stack, but it does expect that *coroutines* get their own copy of
the user stack, and that calling/returning from a coroutine will
not affect the current user stack. This expectation comes from
two sources-- first, it's claimed at the bottom of page 165 in
"Perl 6 and Parrot Essentials", and the docs/pmc/subs.pmc file
says that coroutines get a COW copy of the user stack.
As I said, I'll be the first to admit that my understanding of
how the user stack is supposed to work may be incorrect.
Based on the trace I just looked at, it appears that a save opcode
executed inside a coroutine -- the coroutine generated to handle
the <after c> subrule -- is indeed affecting the results of a
restore in the caller and causing an infinite loop. In particular,
I'm seeing the following sequence...
save I1 I1=1
...
(invoke coroutine)
...
save I1 I1=0
...
(yield from coroutine back to caller)
...
restore I1
inc I1 I1=0 ( should be I1=1 ?)
So, with this patch applied, user stacks in coroutines don't
appear to be working the way I would expect them to.
Any clarification from others would be very helpful here.
On somewhat related note, I'm probably going to eliminate PGE's
use of the user stack altogether and replacing it with an Array
object that is used as a stack via push/pop opcodes. Leo has
commented that this may be faster than the save/restore ops, and
it will also make it much easier for PGE to implement <cut>,
<commit>, and other related ops, since it can instantly erase
parts of the backtracking state by clearing the array.
However, I'd still like to be sure I understand how the user
stack works in coroutines, so any answers or guidance on this
would be greatly appreciated.
Hope this helps,
Pm
Patrick R. Michaud
> Based on the trace I just looked at, it appears that a save opcode
> executed inside a coroutine -- the coroutine generated to handle
> the <after c> subrule -- is indeed affecting the results of a
> restore in the caller and causing an infinite loop. In particular,
> I'm seeing the following sequence...
Just in case it makes a difference, I should also note that
the call to the coroutine is nested inside of a couple of other
sub invocations. So, a more complete picture goes something like:
...
save I1 (trace shows I1=1)
invoke PGE::Rule::after
invoke "[c]$" subrule
invoke coroutine for "[c]$" subrule
I1 = 0
save I1 (trace shows I1=0)
...
yield from "[c]$" coroutine
return from "[c]$" subrule
return from PGE::Rule::after
restore I1
inc I1 (trace shows I1=0 (!))
Pm
Leopold Toetsch
On Feb 23, 2006, at 5:06, Patrick R. Michaud wrote:
>
> PGE does not expect that a sub will restore the state of the user
> stack, but it does expect that *coroutines* get their own copy of
> the user stack, and that calling/returning from a coroutine will
> not affect the current user stack. This expectation comes from
> two sources-- first, it's claimed at the bottom of page 165 in
> "Perl 6 and Parrot Essentials", and the docs/pmc/subs.pmc file
> says that coroutines get a COW copy of the user stack.
Moving the user stack from context (which is distinct for a coroutine)
to the interpreter needs definitely more code:
a) create or copy user stack on coroutine creation, store it in the
coro structure
b) swap user stacks on yield/reinvocation
>
> As I said, I'll be the first to admit that my understanding of
> how the user stack is supposed to work may be incorrect.
Well, there are two issues involved with the user stack:
* do we really need it / want it / keep it [1]
* if so, how are the semantics across sub calls or for coros
[1] the stacks are rather inefficient and big structures:
one stack entry occupies 12 words (96 bytes on 32-bit)
using a local ResizableIntegerArray is by far more efficient
leo
Patrick R. Michaud
>
> On Feb 23, 2006, at 5:06, Patrick R. Michaud wrote:
> >PGE does not expect that a sub will restore the state of the user
> >stack, but it does expect that *coroutines* get their own copy of
> >the user stack, and that calling/returning from a coroutine will
> >not affect the current user stack.
> Well, there are two issues involved with the user stack:
> * do we really need it / want it / keep it [1]
> * if so, how are the semantics across sub calls or for coros
I've just committed an update (r11722) that eliminates PGE's
use of save/restore opcodes in the code it generates -- indeed,
PGE no longer has any save or restore opcodes and thus doesn't
need the user stack at all.
Also, with these changes, the patch that started this thread
now seems to work (all tests pass on my system, including PGE tests).
Since I don't really understand the details of what it is doing, I'll
leave it to someone else to decide its fate. :-)
My intuition says that if we keep the user stack around, then
coroutines should continue to get their own user stack, and
any manipulation of the user stack by a coroutine should not
affect the user stack of the caller. But with this latest update
to PGE I'm completely happy to leave that discussion for the future... :-)
Hope this helps, and thanks,
Pm
Leopold Toetsch
On Feb 24, 2006, at 0:23, Patrick R. Michaud wrote:
>> [...]
>> Well, there are two issues involved with the user stack:
>> * do we really need it / want it / keep it [1]
>> * if so, how are the semantics across sub calls or for coros
>
> I've just committed an update (r11722) that eliminates PGE's
> use of save/restore opcodes in the code it generates -- indeed,
> PGE no longer has any save or restore opcodes and thus doesn't
> need the user stack at all.
That's indeed an (indirect) answer to the 'do we really need it' part ;)
leo
Bob Rogers
Date: Wed, 22 Feb 2006 22:06:22 -0600
. . .
PGE does not expect that a sub will restore the state of the user
stack, but it does expect that *coroutines* get their own copy of
the user stack, and that calling/returning from a coroutine will
not affect the current user stack. This expectation comes from
two sources-- first, it's claimed at the bottom of page 165 in
"Perl 6 and Parrot Essentials", and the docs/pmc/subs.pmc file
says that coroutines get a COW copy of the user stack.
Are you talking about the table under "Items in the Subs Context"? I
had forgotten that existed. Is it still prescriptive? Because most of
the "C" items are in fact "X", if I understand correctly.
Based on the trace I just looked at, it appears that a save opcode
executed inside a coroutine -- the coroutine generated to handle
the <after c> subrule -- is indeed affecting the results of a
restore in the caller and causing an infinite loop. In particular,
I'm seeing the following sequence...
So, with this patch applied, user stacks in coroutines don't
appear to be working the way I would expect them to.
Yes, what you're seeing is what I thought I had implemented. I had
realized that coroutines would be affected this way, but it didn't even
occur to me that PGE might rely on this. In particular, I didn't think
it was specified behavior. In any case, thanks for figuring this out.
FWIW, the current stack implementation only works for you (unless I
am much mistaken) since all of the push/pop ops within each coroutine
happen in the same sub. Otherwise, the change of context would work
against you.
From: Leopold Toetsch <l...@toetsch.at>
Date: Thu, 23 Feb 2006 10:37:00 +0100
. . .
Moving the user stack from context (which is distinct for a coroutine)
to the interpreter needs definitely more code:
a) create or copy user stack on coroutine creation, store it in the
coro structure
b) swap user stacks on yield/reinvocation
Yes. Given such ops as C<rotate_up>, it seems to me that copying the
stack on creation, or creating it empty, would be cleaner than a
solution that shared stack entries.
> As I said, I'll be the first to admit that my understanding of
> how the user stack is supposed to work may be incorrect.
Well, there are two issues involved with the user stack:
* do we really need it / want it / keep it [1]
* if so, how are the semantics across sub calls or for coros
[1] the stacks are rather inefficient and big structures:
one stack entry occupies 12 words (96 bytes on 32-bit)
using a local ResizableIntegerArray is by far more efficient
leo
Yes, and compilers/humans that want to use stacks can scope such stacks
arbitrarily (i.e. globally, per-coroutine, per-sub, whatever) simply by
stuffing the array in an appropriately-scoped variable.
From: "Patrick R. Michaud" <pmic...@pobox.com>
Date: Thu, 23 Feb 2006 17:23:19 -0600
I've just committed an update (r11722) that eliminates PGE's
use of save/restore opcodes in the code it generates -- indeed,
PGE no longer has any save or restore opcodes and thus doesn't
need the user stack at all.
Also, with these changes, the patch that started this thread now
seems to work (all tests pass on my system, including PGE tests)
. . .
Works for me, too.
leo
I myself have no real interest in keeping the user stack, having no
particular use for it. The real point of this exercise (besides, IMHO,
making stacks more stack-like) was as a warm-up for dynamic bindings. I
intend to argue (in my long-overdue dynamic binding proposal) that the
control_stack needs to be moved into the interpreter, since it must be
saved/restored by continuations and coroutines, much as you say above
for the user stack. While considering this, though, I realized that
moving the user_stack would also have benefits.
I do think this patch adds something useful, for those who want a
stack. But if the choice is to have per-coroutine stacks, or flush the
feature altogether, then there's no point to it.
-- Bob
Chip Salzenberg
> On Feb 24, 2006, at 0:23, Patrick R. Michaud wrote:
> >>[...]
> >use of save/restore opcodes in the code it generates -- indeed,
> >PGE no longer has any save or restore opcodes and thus doesn't
> >need the user stack at all.
>
> That's indeed an (indirect) answer to the 'do we really need it' part ;)
Is there any other client of the user stack that can't be easily replaced by
some kind of *Array? It'd be nice to lop off such a low-value feature.
--
Chip Salzenberg <ch...@pobox.com>
Will Coleda
current implementation has over "just using a PMC" is that you don't
have to go out and get the global PMC you're storing things in.
We already have at least one language implementation that used to
work just fine using the stack, but has been crippled with various
deprecations over the last few years.
Would it be difficult and/or desirable to change our user stack
implementation to:
1) Automatically create a global ResizablePMCArray and put it in a
well known location.
2) Provide some PIR sugar so that if a particular token (e.g.
$USERSTACK, .USERSTACK) is mentioned as an argument, it is fetched
from the global and put into a local register. (and thereafter, the
local register is used, as long as it's in the same sub.)
3) eliminate the special cased opcodes for dealing with the user stack.
This would also allow more direct manipulation of the stack for
nefarious purposes. (Though, you could just call that "introspection"
and chalk it up to a feature.)
This is predicated on the assumption that *someone* wants the user
stack, though.
On Mar 1, 2006, at 7:40 AM, Bob Rogers wrote:
> I can think of two more strikes against it:
>
> 1. In error handling code, it's a pain to restore the stack state.
> You have to (a) take note of the depth before starting, and (b)
> emit EH
> code to pop back to that level. This is made more difficult by the
> fact
> that . . .
>
> 2. Stack entries are "strongly typed," i.e. you have to know the
> INSP type of the thing you pushed in order to pop it, or you get an
> error. This is in stark contrast to the new calling protocol,
> which is
> willing to convert.
>
> Neither of these are fatal, but both make the user stack harder to
> use than it could be. IMHO, it seems easier to flush it than to
> fix it.
>
> -- Bob
>
Patrick R. Michaud
As Will Coleda mentioned, the only real advantage of the user stack
over an *Array seems to be that each subroutine wanting to manipulate the
stack doesn't have to first look up a global symbol in order to do it.
Intuitively, it would seem that a user stack, with its specialized parrot
opcodes, ought to be significantly faster than simply using another
array-ish object as a stack. It was this sort of (incorrect) thinking
that led me to use it over an array in the first place. Since that
is apparently not the case, I don't see any real use for keeping the
user stack.
(In PGE's case, using an array instead of the userstack is also
superior for a number of other reasons, mostly having to do with
being able to manipulate large parts of the stack in a single
operation.)
Pm
Leopold Toetsch
On Mar 1, 2006, at 14:46, Will Coleda wrote:
> We already have at least one language implementation that used to work
> just fine using the stack, but has been crippled with various
> deprecations over the last few years.
If you are speaking of forth here, then no. That was broken by design.
It jumped directly into evaled code. To get that working it just turned
off bounds checking for the runloops (i.e. if the program counter is
inside the current code segment limits).
leo