pre-PATCH: lexicals
Jonathan Sillito
The patch looks good to me. Several weeks ago I
submitted a patch that overlaps this one, so if
you apply your patch then mine should just go
away. The approach I took was to make the pad
pmc be a pair of pointers, one to a hash and the
other to the parent pad, which makes taking a
closure quite efficient but makes some types of
look up slower. What do you think?
Anyway a few very minor comments about your patch:
store_lex(in STR, in PMC) does not seem to work
as I would expect it to, since it can not be
used to introduce a new lexicals, but I think I
can see your reasoning. Also I notice that it is
not used in any of the tests in t/op/lexicals.t.
In doc for new_pad: should the example be in PASM
instead of perl? I think it would be more clear
as it would show where the new_pad op fits etc.
In doc for store_lex(in STR, in PMC) there is a
reference to "if $1 is negative etc", which does
not belong.
--
Jonathan Sillito
On Sun, 15 Sep 2002, Sean O'Rourke wrote:
> I think the current lexical implementation won't do what we need. In
> particular, it can't support different levels of static nesting --
> everything is a single, flat scratchpad. This seems to make nested
> lexical scopes hard to implement correctly, particularly when %MY games
> can change them. The attached patch allows nested lexical scopes
> (implemented as an array of hashes), and changes the sub class (not
> coroutine yet) to use them. It doubtless needs some tidying, but I think
> the basic idea is sound.
>
> For those of you following along with me in the Dragon Book, it basically
> pushes the whole display onto the pad_stack whenever you push a new scope.
> Taking a closure just copies a pointer to the current display.
>
> The interface is what's in pdd06, but without the integer-indexed version
> of find_lex/fetch_lex, and with the names made the same. Pad-handling
> unfortunately leaks over into coroutines and subs: since invoking either
> will push a pad, Subs and Coroutines have to pop this pad before they
> return.
>
> new_pad(in INT)
> Create a new lexical scope pad with static nesting depth $1, and
> push it onto the lexical stack. Static depths 0 through $1 - 1,
> inclusive, are copied from the current static nesting. For
> example, say we have the following code:
>
> sub f($n) {
> sub g { ... }
> sub h { g() }
>
> if $n == 0 { h() }
> else { f($n - 1) }
> }
>
> f(1)
>
> Then the lex_stack will behave like this:
>
> action pad op state
> ------ ------ -----
> f(1) new_pad(0) [f]
> f(0) new_pad(0) [f] [f]
> h() new_pad(1) [h f] [f] [f]
> g() new_pad(1) [g f] [h f] [f] [f]
> g returns pop_pad [h f] [f] [f]
> h returns pop_pad [f] [f]
> f(0) returns pop_pad [f]
> f(1) returns pop_pad -
>
> pop_pad()
> Pop the current lexical scope pad off the stack
>
> store_lex(in STR, in PMC)
> Store object $2 as lexical symbol $1. $1 must have already been
> created at some static depth. If $1 is negative, count out from
> the current lexical scope; otherwise, count up from the
> outermost scope.
>
> store_lex(in INT, in STR, in PMC)
> Store object $3 as lexical $2 at depth $1. If [$1, $2] does not
> exist, it will be created. If $1 is negative, count out from the
> current lexical scope; otherwise, count up from the outermost
> scope.
>
> find_lex(out PMC, in STR)
> Find the lexical variable named $2 (at any depth) and store it
> in $1.
>
> find_lex(out PMC, in INT, in STR)
> Find the lexical variable named $3 at depth $2 and store it in
> $1.
>
> Anyways, feedback welcome.
>
> /s
>
Sean O'Rourke
> The patch looks good to me. Several weeks ago I
> submitted a patch that overlaps this one, so if
> you apply your patch then mine should just go
> away. The approach I took was to make the pad
> pmc be a pair of pointers, one to a hash and the
> other to the parent pad, which makes taking a
> closure quite efficient but makes some types of
> look up slower. What do you think?
I think I didn't look through the patch queue carefully enough ;). I
gather that it's accepted practice (or something like that) to use an
array of pointers instead of links to avoid having to do a traversal when
accessing outer scopes, so that's why I did things this way. Out of
curiosity, how were you planning to handle e.g. recursive functions?
Unless I'm misreading your patch, it always sets the parent static scope
to the parent dynamic scope, which often isn't what one wants.
> store_lex(in STR, in PMC) does not seem to work
> as I would expect it to, since it can not be
> used to introduce a new lexicals, but I think I
> can see your reasoning.
Yeah. I think that to create a new lexical, you should have to be
explicit about which scope you're using. This should probably be
documented, since others will likely share your "why the...? oh" reaction.
> Also I notice that it is not used in any of the tests in
> t/op/lexicals.t.
That's why this is a "pre-PATCH" ;). I just wanted to put some code with
the ideas to (a) prove to myself that it would do what I expected, and (b)
give others a chance to confirm or deny their expectations about whatever
documented semantics.
> In doc for new_pad: should the example be in PASM
> instead of perl? I think it would be more clear
> as it would show where the new_pad op fits etc.
The problem is that assembly doesn't have block structure, which is kind
of necessary for lexical scope. I was trying to show the correspondence
between typical nested block structure and its underlying pasm
implementation. I guess it would make people happier in the
language-neutrality department to use Algol or some sort of pseudo-code
for the example, but I was thinking in Perl as I wrote it up.
> In doc for store_lex(in STR, in PMC) there is a
> reference to "if $1 is negative etc", which does
> not belong.
Hoisted by my own copy-and-pasting, it seems.
/s
Juergen Boemmels
> I think the current lexical implementation won't do what we need. In
> particular, it can't support different levels of static nesting --
> everything is a single, flat scratchpad. This seems to make nested
> lexical scopes hard to implement correctly, particularly when %MY games
> can change them. The attached patch allows nested lexical scopes
> (implemented as an array of hashes), and changes the sub class (not
> coroutine yet) to use them. It doubtless needs some tidying, but I think
> the basic idea is sound.
There was a patch of Jonthan Sillito doing something similar. (#16797)
At the moment I try to use this to get functions working in Scheme. I
have something, that is somewhat working in gdb, but not ready yet.
> For those of you following along with me in the Dragon Book, it basically
> pushes the whole display onto the pad_stack whenever you push a new scope.
> Taking a closure just copies a pointer to the current display.
That was my idea, too.
> The interface is what's in pdd06, but without the integer-indexed version
> of find_lex/fetch_lex, and with the names made the same. Pad-handling
> unfortunately leaks over into coroutines and subs: since invoking either
> will push a pad, Subs and Coroutines have to pop this pad before they
> return.
The problem I had using this new/pop system arises when an internal
lexical scope leaks out of its surrounding scope i.e.
sub make_counter {
my $counter = shift;
return sub { my $val = shift; return $counter += $val ; }
}
$counter1 = make_counter (0);
$counter2 = make_counter (100);
print $counter1->(1);
print $counter2->(2);
print $counter1->(3);
When you call $counter1 you have to reinstall the scope of the function
definition (the one containing $counter), which is different from the
current scope, this has to be expanded by $val which gets bound 1,
modifing $counter and returning its value. Then the old scope is
reinstalled.
Next call $counter2. Again reinstall the scope of the definition. This
time its another one because $counter is bound to 100 and not to 1,
extend it bind 2 to $val, modify $counter and return.
Third call similar.
So the output will be 1, 102, 4.
My current implementation does something like this:
Function definition: Get the current scope and store it in the
function, along with the definition of the arguments, and the body of
the function.
Function invokation: Get the current scope and store it on the stack,
Set the scope to the value stored in the function, which can be
completely independend of the (formerly) current scope. Then extend
this scope by the arguments of the function. Run the body in this
scope. At last set the scope back to the value stored on the stack.
The stack can be a dedicated pad_stack, but it can also be the
user_stack. Maybe a dedicated stack is better because there are
dedicated ops for scope resolution.
> new_pad(in INT)
> Create a new lexical scope pad with static nesting depth $1, and
> push it onto the lexical stack. Static depths 0 through $1 - 1,
> inclusive, are copied from the current static nesting.
This is not enough. You need something like :
new_pad(in PMC)
Create a new lexical scope pad expanding the base scope
$1.
Push this scope on the lexical stack.
get_pad (out PMC)
Get the current lexical scope and store it in $1.
> For
> example, say we have the following code:
>
> sub f($n) {
> sub g { ... }
> sub h { g() }
>
> if $n == 0 { h() }
> else { f($n - 1) }
> }
>
> f(1)
>
> Then the lex_stack will behave like this:
>
> action pad op state
> ------ ------ -----
[...]
f(1) new_pad(NULL) [f]
sub g {} get_pad(->[f]) [f]
sub h {} get_pad(->[f]) [f]
f(0) new_pad(NULL) [f'] [f]
sub g {} get_pad(->[f']) [f'] [f]
sub h {} get_pad(->[f']) [f'] [f]
h() new_pad([f']) [h f'] [f'] [f]
g() new_pad([f']) [g f'] [h f'] [f'] [f]
g returns pop_pad [h f'] [f'] [f]
h returns pop_pad [f'] [f]
f(0) returns pop_pad [f]
f(1) returns pop_pad -
This example is essentaly unchanged.
But if you have the following code:
sub f ($n) {
return sub g { $n++; }
}
$f1 = f(1);
$f2 = f(2);
$f1->();
$f2->();
Then the lex_stack will behave like this.
action pad_op state
------ ------ -----
f(1) new_pad(NULL) [f]
sub g {} get_pad(->[f]) [f]
f returns pop_pad -
f(2) new_pad(NULL) [f']
sub g {} get_pad(->[f']) [f']
f returns pop_pad -
$f1->() new_pad([f]) [g f]
$f1 returns pop_pad -
$f2->() new_pad([f']) [g' f']
$f2 returns pop_pad -
> pop_pad()
> Pop the current lexical scope pad off the stack
>
> store_lex(in STR, in PMC)
> Store object $2 as lexical symbol $1. $1 must have already been
> created at some static depth.
Ok.
> If $1 is negative, count out from
> the current lexical scope; otherwise, count up from the
> outermost scope.
$1 is a string. Is "a" postive or negative?
You mean:
This symbol will be changed.
> store_lex(in INT, in STR, in PMC)
> Store object $3 as lexical $2 at depth $1. If [$1, $2] does not
> exist, it will be created. If $1 is negative, count out from the
> current lexical scope; otherwise, count up from the outermost
> scope.
>
> find_lex(out PMC, in STR)
> Find the lexical variable named $2 (at any depth) and store it
> in $1.
>
> find_lex(out PMC, in INT, in STR)
> Find the lexical variable named $3 at depth $2 and store it in
> $1.
>
> Anyways, feedback welcome.
Here is some.
boe
--
Juergen Boemmels boem...@physik.uni-kl.de
Fachbereich Physik Tel: ++49-(0)631-205-2817
Universitaet Kaiserslautern Fax: ++49-(0)631-205-3906
PGP Key fingerprint = 9F 56 54 3D 45 C1 32 6F 23 F6 C7 2F 85 93 DD 47
Jonathan Sillito
> From: Sean O'Rourke [mailto:soro...@cs.ucsd.edu]
>
> I think I didn't look through the patch queue carefully enough ;). I
> gather that it's accepted practice (or something like that) to use an
> array of pointers instead of links to avoid having to do a traversal when
> accessing outer scopes, so that's why I did things this way. Out of
> curiosity, how were you planning to handle e.g. recursive functions?
Umm, I am not sure ...
> Unless I'm misreading your patch, it always sets the parent static scope
> to the parent dynamic scope, which often isn't what one wants.
I see. So just to see if I understand things correctly, consider an example
in some made up language:
function get_counter(increment) {
var last = 0
function counter() {
last = last + increment
println last
}
return counter
}
x = get_counter(10)
y = get_counter(50)
x()
x()
y()
y()
this could be compiled to the following PASM (some error checking missing, I
guess):
new_pad 0
new P0, .Sub
set_addr I3, get_counter
set P0, I3
# invoke get_counter with one argument -> 10
saveall
new P5, .PerlInt
set P5, 10
invoke
# store returned closure as lexical "x"
store_lex 0, "x", P5
restoreall
# invoke get_counter with one argument -> 50
saveall
new P5, .PerlInt
set P5, 50
invoke
# store returned closure as lexical "y"
store_lex 0, "y", P5
restoreall
# invoke x twice
find_lex P0, "x"
saveall
invoke
restoreall
saveall
invoke
restoreall
# invoke y twice
find_lex P0, "y"
saveall
invoke
restoreall
saveall
invoke
restoreall
end
get_counter:
new_pad 1
# maybe should check that we were
# passed param?
# make param a lexical variable
store_lex 1, "increment", P5
# start with last == 0
new P1, .PerlInt
set P1, 0
store_lex 1, "last", P1
# return sub pmc in P5
new P5, .Sub
set_addr I5, counter
set P5, I5
pop_pad
pop_pad # extra pad needs to be popped
ret
counter:
# no new pad needed here since no lexicals
# are introduced
new P4, .PerlInt
set P4, 0
# do last = last + increment
find_lex P2, "last"
find_lex P3, "increment"
add P4, P2, P3
store_lex "last", P4
# print new last
print P4
print "\n"
pop_pad # extra pad needs to be popped
ret
with your patch in place, this works correctly and produces the output:
10
20
50
100
Is that how we want closures to work? Looks good to me, so I suggest you
apply your patch and we go from there; it certainly moves things forward.
--
Jonathan Sillito
Sean O'Rourke
> There was a patch of Jonthan Sillito doing something similar. (#16797)
Yes. I had missed it, but Mr. Sillito agrees that it doesn't quite do
what we need.
> At the moment I try to use this to get functions working in Scheme. I
> have something, that is somewhat working in gdb, but not ready yet.
Maybe we need a "pad pumpkin" to avoid these kinds of race conditions.
> The problem I had using this new/pop system arises when an internal
> lexical scope leaks out of its surrounding scope i.e.
>
> sub make_counter {
> my $counter = shift;
> return sub { my $val = shift; return $counter += $val ; }
> }
> $counter1 = make_counter (0);
> $counter2 = make_counter (100);
> print $counter1->(1);
> print $counter2->(2);
> print $counter1->(3);
>
> When you call $counter1 you have to reinstall the scope of the function
> definition (the one containing $counter), which is different from the
> current scope,
The way I have it, "invoke" implicitly pushes its saved pad, which leads
to an odd extra pop_pad at the end of anonymous subs, but works. Your
description (snipped) sounds spot-on to me.
> My current implementation does something like this:
>
> Function definition: Get the current scope and store it in the
> function, along with the definition of the arguments, and the body of
> the function.
Check.
> Function invokation: Get the current scope and store it on the stack,
Okay, the way I did it, it already is the top of the stack. Same thing, I
think.
> Set the scope to the value stored in the function, which can be
> completely independend of the (formerly) current scope. Then extend
> this scope by the arguments of the function.
And possibly its locals, right?
> Run the body in this scope. At last set the scope back to the value
> stored on the stack.
>
> The stack can be a dedicated pad_stack, but it can also be the
> user_stack. Maybe a dedicated stack is better because there are
> dedicated ops for scope resolution.
Actually, referencing the static scope as a multidimensional array might
work as well:
set P1, P0[2;"$foo"]
set P0[-1;"$bar"], 23
> > new_pad(in INT)
> > Create a new lexical scope pad with static nesting depth $1, and
> > push it onto the lexical stack. Static depths 0 through $1 - 1,
> > inclusive, are copied from the current static nesting.
>
> This is not enough. You need something like :
>
> new_pad(in PMC)
> Create a new lexical scope pad expanding the base scope
> $1.
> Push this scope on the lexical stack.
>
> get_pad (out PMC)
> Get the current lexical scope and store it in $1.
Not entirely. Currently, things that need the current scope get it
implicitly -- e.g. creating a new Sub captures the current scope. I'm not
sure this is a good idea or not, but it seemed at the time that it was
better (or more in line with the interface) not to have scopes running
around as free-range PMC's.
> > If $1 is negative, count out from
> > the current lexical scope; otherwise, count up from the
> > outermost scope.
>
> $1 is a string. Is "a" postive or negative?
"a" is positive, of course -- 10 in hex ;). This is a result of some
copy-and-paste documentation that was not removed.
> > Anyways, feedback welcome.
>
> Here is some.
Muchas gracias, senor
/s
Sean O'Rourke
Looks correct to me (and certainly much cleaner than the thing I created
in the test file), except possibly for the outermost lexical scope
(new_pad 0). Since there aren't any variables out there, it's probably
not necessary.
> Is that how we want closures to work? Looks good to me, so I suggest
> you apply your patch and we go from there; it certainly moves things
> forward.
As long as it's not "forward into that tree"...
/s
Juergen Boemmels
> > At the moment I try to use this to get functions working in Scheme. I
> > have something, that is somewhat working in gdb, but not ready yet.
>
> Maybe we need a "pad pumpkin" to avoid these kinds of race conditions.
My actual implementation is a hack using a patched version of Jonathans
patch.
> > The problem I had using this new/pop system arises when an internal
> > lexical scope leaks out of its surrounding scope i.e.
> >
> > sub make_counter {
> > my $counter = shift;
> > return sub { my $val = shift; return $counter += $val ; }
> > }
> > $counter1 = make_counter (0);
> > $counter2 = make_counter (100);
> > print $counter1->(1);
> > print $counter2->(2);
> > print $counter1->(3);
> >
> > When you call $counter1 you have to reinstall the scope of the function
> > definition (the one containing $counter), which is different from the
> > current scope,
>
> The way I have it, "invoke" implicitly pushes its saved pad, which leads
> to an odd extra pop_pad at the end of anonymous subs, but works. Your
> description (snipped) sounds spot-on to me.
You do something like push_pad implicitly in the Sub class, but
without a corresponding op in core.ops, when you invoke the Sub.
You also get the current lexical scope implicitly at Sub creation
time. This may be intentional so that the bytecode cant mess with the
lexical stack, but there are already. new_pad and pop_pad.
What would help me much in implementing scheme functions is a way to
get the current scope at bytecode level, and to extend an arbitary
scope.
Im currently thinking of the following ops
new_pad
create a completly new (empty) pad and push it onto the
pad_stack.
new_pad (in PMC)
create a new pad with $1 as parent, pushing this pad on the
stack.
get_pad (out PMC)
get the current pad, storing it in $1.
get_pad (out PMC, in INT)
get a pad corresponding to current scope at depth $2; store it
in $1. Negative values count from the outermost scope.
new_pad (in INT)
The same as get_pad P0, $1; new_pad P0.
(This is essentally the same you wrote).
store_lex (in STR, in PMC) and store_lex (in INT, in STR, in PMC)
the same way you do it.
> > My current implementation does something like this:
> >
> > Function definition: Get the current scope and store it in the
> > function, along with the definition of the arguments, and the body of
> > the function.
>
> Check.
>
> > Function invokation: Get the current scope and store it on the stack,
>
> Okay, the way I did it, it already is the top of the stack. Same thing, I
> think.
>
> > Set the scope to the value stored in the function, which can be
> > completely independend of the (formerly) current scope. Then extend
> > this scope by the arguments of the function.
>
> And possibly its locals, right?
In scheme locals are always some funny kind of lambda
(let ((<var1> <val1)(<var2> <val2>)...) <body>)
is the same as
((lambda (<var1> <var2> ...) <body>) <val1> <val2>)
In perl every
my $foo;
will translate to
new P0, .PerlUndef
store_lex 0,"$foo",P0
> > Run the body in this scope. At last set the scope back to the value
> > stored on the stack.
> >
> > The stack can be a dedicated pad_stack, but it can also be the
> > user_stack. Maybe a dedicated stack is better because there are
> > dedicated ops for scope resolution.
>
> Actually, referencing the static scope as a multidimensional array might
> work as well:
>
> set P1, P0[2;"$foo"]
> set P0[-1;"$bar"], 23
Good idea.
[...]
bye
juergen
Sean O'Rourke
> You do something like push_pad implicitly in the Sub class, but
> without a corresponding op in core.ops, when you invoke the Sub.
> You also get the current lexical scope implicitly at Sub creation
> time. This may be intentional so that the bytecode cant mess with the
> lexical stack, but there are already. new_pad and pop_pad.
Right. As I understand it, the idea is to have a very controlled
interface to lexical scopes. So you can create a shallower or deeper
scope based on the current one, or restore a previously-saved scope, but
not manipulate scopes in arbitrary ways.
I think if you need fully general pad-manipulation, we should go for
something like {push,peek,pop}_pad to manipulate the pad stack where each
pad will look sort of like arrays of hashes. That means you can implement
scope-chopping like so
pop_pad Px
set Ix, Px
dec Ix
set Px, Ix
push_pad Px
and scope extension using and "inc" instead of a "dec" in the above
sequence. To go a step further, we could just wrap stacks as limited
arrays, then have a "get_pad_stack" op, and use normal ops for the rest of
the manipulations. I'm leaning toward this because it lets people who
think of new and weird things they want to do with scopes implement them
without having to kludge around a limited set of pad ops.
{find,store}_lex could either remain unchanged, or be eliminated in favor
of all-the-time keyed access.
> > Actually, referencing the static scope as a multidimensional array might
> > work as well:
> >
> > set P1, P0[2;"$foo"]
> > set P0[-1;"$bar"], 23
The stubs are in there for some of these, and they look pretty
straightforward to implement.
/s
Piers Cawley
>> -----Original Message-----
>> From: Sean O'Rourke [mailto:soro...@cs.ucsd.edu]
>>
>> I think I didn't look through the patch queue carefully enough ;). I
>> gather that it's accepted practice (or something like that) to use an
>> array of pointers instead of links to avoid having to do a traversal when
>> accessing outer scopes, so that's why I did things this way. Out of
>> curiosity, how were you planning to handle e.g. recursive functions?
>
> Umm, I am not sure ...
>
>> Unless I'm misreading your patch, it always sets the parent static scope
>> to the parent dynamic scope, which often isn't what one wants.
>
> I see. So just to see if I understand things correctly, consider an example
> in some made up language:
>
> function get_counter(increment) {
> var last = 0
>
> function counter() {
> last = last + increment
> println last
> }
>
> return counter
> }
[...]
> get_counter:
> new_pad 1
Doesn't this violate the 'caller saves' principle, making it hard to
do tail call optimization? Would it make sense to move the creation of
a new pad into the Sub's invoke method?
[...]
--
Piers
"It is a truth universally acknowledged that a language in
possession of a rich syntax must be in need of a rewrite."
-- Jane Austen?
Jonathan Sillito
> From: Piers Cawley [mailto:pdca...@bofh.org.uk]
> "Jonathan Sillito" <sil...@cs.ubc.ca> writes:
> > get_counter:
> > new_pad 1
>
> Doesn't this violate the 'caller saves' principle, making it hard to
> do tail call optimization? Would it make sense to move the creation of
> a new pad into the Sub's invoke method?
>
I am not sure how this violates the 'caller saves' principle, unless you
mean that the caller should be saving its own scratch pad if necessary? I
did notice that this is in pdd03:
"The caller is responsible for preserving any environment it is
interested in keeping. This includes any and all registers, lexical
scoping and scratchpads, opcode libraries, and so forth."
I suppose scratchpads could be an exception, to this?
I have to think more about the tail call optimization. I am not sure how
putting the creation of the new pad into the sub's invoke method would help,
it still seems like it would be created each time the method was invoked
(which seems equivalent to putting a new_pad instruction at the top ... On
the other hand, if the instruction is left to the PASM for some subs it
could easily be optomized away by the compiler. Or maybe it could be
conditional?
get_counter:
new_pad 1
get_counter_no_new_pad:
# etc
Would this address the problem? Or am I missing somthing?
--
Jonathan Sillito
Dan Sugalski
> > -----Original Message-----
>> From: Piers Cawley [mailto:pdca...@bofh.org.uk]
>> "Jonathan Sillito" <sil...@cs.ubc.ca> writes:
>> > get_counter:
>> > new_pad 1
>>
>> Doesn't this violate the 'caller saves' principle, making it hard to
>> do tail call optimization? Would it make sense to move the creation of
>> a new pad into the Sub's invoke method?
>>
>
>I am not sure how this violates the 'caller saves' principle, unless you
>mean that the caller should be saving its own scratch pad if necessary? I
>did notice that this is in pdd03:
>
>"The caller is responsible for preserving any environment it is
>interested in keeping. This includes any and all registers, lexical
>scoping and scratchpads, opcode libraries, and so forth."
>
>I suppose scratchpads could be an exception, to this?
I'd rather it not be, but there are issues with tail recursion and
pads (amongst other things) anyway, since you're often several levels
of pad deep at any one time.
--
Dan
--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk