RFC: Proposal for dynamic binding
Bob Rogers
a proposal for dynamic binding in Parrot. Please give this a read, when
you have a chance, and let me know what you think. (For those who would
rather not patch their Parrot in order to read it, I also have it up on
my site at http://rgrjr.dyndns.org/perl/pddXX_dynbind.html .)
The patch also adds an implementation of global variable binding,
which is probably a third to a half of the total effort. I started the
implementation in order to help me clarify the issues; it is included
here as an illustration of what the doc really means.
All feedback eagerly anticipated,
-- Bob Rogers
http://rgrjr.dyndns.org/
Bob Rogers
Date: Sun, 12 Nov 2006 21:56:04 -0500
The attached patch adds a docs/pdds/pddXX_dynbind.pod file . . .
Ahem, this patch should have been called "dynbind-deep-vars-2.patch"
instead of "dynbind-shallow-vars-2.patch". I hope this is the only
place I have made this mistake, but I corrected just this error in the
POD last weekend, so it seems like a faint hope. Sorry for the
confusion.
-- Bob
Leopold Toetsch
> +There are two techniques for implementing dynamic binding. These are
> +traditionally called deep binding and shallow binding [2].
Can you please consider the impacts of a third variant using STM, which is
already implemented:
$ cat stm.pir
.sub main :main
$P0 = new .Integer
$P0 = 42
$P1 = new .STMRef, $P0 # localalize $P0
stm_start # 2nd line
$P1 = 45
print $P1
print "\n"
stm_abort # un-local ;)
print $P1
print "\n"
.end
$ ./parrot stm.pir
45
42
Thanks,
leo
Bob Rogers
Date: Mon, 13 Nov 2006 21:19:26 +0100
Am Montag, 13. November 2006 03:56 schrieb Bob Rogers:
> +There are two techniques for implementing dynamic binding. These are
> +traditionally called deep binding and shallow binding [2].
Can you please consider the impacts of a third variant using STM, which is
already implemented . . .
Thanks,
leo
Well, I see that STM transactions nest, but they don't seem to roll back
in case of an error. In the test case below, you can see that the
innermost temporary binding is not undone when control transfers to the
error handler. In this particular case I could put the "stm_abort" in
the error handler, but in general I wouldn't know how many nested
transactions to unwind. I'm sure it would work to put an "stm_abort" in
a pushaction sub wherever I do "stm_start", but if I was going to go
that way, I might as well put "set_global" there instead; that would
also save me the trouble of deciding whether I needed to change the
stored PMC to an STMRef. But either way, full continuations (and
therefore coroutines) would still not work properly, as the actions
would be run repeatedly. Or am I missing something about STM?
In general, I would expect invoking a continuation to restore the
dynamic bindings in effect when the continuation was taken. For an
example, see the "coroutines, GC" test case added to t/op/globals.t by
the patch; there are two coroutines which each bind the same variable to
different values, but yielding from one and re-invoking the other
flip-flops between the same two bindings. Note that there are still
only two bindings; changes to the binding made in one environment would
persist until the next cycle. I don't have any language implementation
models to cite, but this behavior strikes me as Clearly The Right Thing:
Dynamic bindings should be visible only from the point of binding and
downward.
IIUC, stm_start and stm_abort assume a single linear series of
changes for a given interpreter, where all 'start ... commit/abort'
pairs nest properly. If so, this works for stack-based interpreters
(and could be made to work for limited continuations that are restricted
to returning down the stack), but not for full continuations. If STM
transactions were made part of the dynamic environment, then that would
be a different story, but in that case STM transaction nesting would be
nonlinear, and I have no clue whether doing so would require a small
change to the STM code or a major rewrite. Or it might break STM in
other ways; I do not at all grok STM (and reading the code is not going
to get me there in a hurry).
Or perhaps we should give up on full continuations, since STM seems
to be yet another feature that breaks/is broken by them. Seriously.
-- Bob
------------------------------------------------------------------------
rogers@rgrjr> cat hacks/stm3.pir
.sub main :main
push_eh handler
$P0 = new .Integer
$P0 = 42
$P1 = new .STMRef, $P0 # localalize $P0
stm_start # 2nd line
$P1 = 45
print $P1
print "\n"
foo($P1)
print $P1
print "\n"
stm_abort # un-local ;)
print $P1
print "\n"
end
handler:
.local pmc e
.local string s
.get_results (e, s)
print "Error: "
print s
print "\n"
print $P1
print "\n"
.end
.sub foo
.param pmc var
print "in foo\n"
stm_start # 2nd level
var = 49
print var
print "\n"
## oops; we got an error.
$P3 = new .Exception
$P3[0] = 'oops'
throw $P3
print "leaving foo normally\n"
stm_abort # un-local ;)
.end
rogers@rgrjr> ./parrot hacks/stm3.pir
45
in foo
49
Error: oops
49
rogers@rgrjr>
Allison Randal
> The attached patch adds a docs/pdds/pddXX_dynbind.pod file, which is
> a proposal for dynamic binding in Parrot. Please give this a read, when
> you have a chance, and let me know what you think. (For those who would
> rather not patch their Parrot in order to read it, I also have it up on
> my site at http://rgrjr.dyndns.org/perl/pddXX_dynbind.html .)
Thanks very much for putting this proposal together. You've worked
through a number of important issues. In general, you've got the right
idea. A few observations:
- It's not stack unwinding/rewinding, so let's not call it stack
unwinding/rewinding. Need a new phrase.
- "Store once" Locations isn't really a good fit for the dynamic nature
of Parrot.
- Overall, I want the implementation of dynamic binding to be tied in
more closely with the implementation of globals and lexicals.
Particularly lexicals. They're already operating under the same scope
constraints as locals. They already have storage for named variables
relevant to a particular scope, and the mechanism for handling scopes
within scopes.
- I like the idea of "thread locals": global variables shared across
threads, but with a local value in one particular thread. I'll have to
mull that one over some more. It seems fundamentally different from
"scope locals", to the point of deserving a different way of interacting
with the feature (perhaps more closely tied to the concurrency model
than to variable storage).
- We keep adding hacks to get around the fact that Parrot doesn't
handle scopes smaller than a compilation unit particularly well. If we
tackled that quirk, dynamic binding would likely fall out more
naturally, not to mention exception handlers, lexical variables, etc.
Allison
Bob Rogers
Date: Thu, 16 Nov 2006 17:29:57 -0800
Bob Rogers wrote:
> The attached patch adds a docs/pdds/pddXX_dynbind.pod file, which is
> a proposal for dynamic binding in Parrot. Please give this a read, when
> you have a chance, and let me know what you think. (For those who would
> rather not patch their Parrot in order to read it, I also have it up on
> my site at http://rgrjr.dyndns.org/perl/pddXX_dynbind.html .)
Thanks very much for putting this proposal together. You've worked
through a number of important issues. In general, you've got the right
idea. A few observations:
- It's not stack unwinding/rewinding, so let's not call it stack
unwinding/rewinding. Need a new phrase.
When I first brought the topic up, I called it "rezipping" -- and I
still like the word, as it's visually very appropriate. It even lends
itself to "zip up" and "zip down" for describing the parts of the
detailed algorithm. But then I rewrote it all to use "unwinding" and
"rewinding" because I thought it would be a bad idea to introduce new
jargon where it wasn't really needed. So I'm certainly amenable to
alternatives.
- "Store once" Locations isn't really a good fit for the dynamic nature
of Parrot.
You're absolutely right; this is too stringent. I was trying to prevent
Locations from being stored into while in use as a dynamic binding, as
that could have effects outside the normal dynamic scope. That might
cause hard-to-debug problems in user code, but avoiding such problems is
not worth the price. I will change this paragraph to read:
Locations slots should never be changed while the Location is in
use by Parrot as a dynamic binding. Doing so can have
unintended side effects outside the normal scope of the binding,
especially if there are other bindings of the same location in
effect.
But with continuations, you never know when a binding that is out of
scope might come back in again . . .
- Overall, I want the implementation of dynamic binding to be tied in
more closely with the implementation of globals and lexicals.
Particularly lexicals. They're already operating under the same scope
constraints as locals. They already have storage for named variables
relevant to a particular scope, and the mechanism for handling scopes
within scopes.
I'm afraid I don't follow you, particularly the "operating under the
same scope constraints" part. It seems to me that lexical variables are
orthogonal to dynamic/global variables, and dynamic binding is purely a
feature of globals. And lexicals are necessarily simpler, because all
possible references are available to the compiler. So nested scopes are
handled by the compiler simply by using a different register. Globals
and dynamic bindings, because they must be visible to code in multiple
compilation units, must necessarily use different mechanisms.
- I like the idea of "thread locals": global variables shared across
threads, but with a local value in one particular thread. I'll have to
mull that one over some more. It seems fundamentally different from
"scope locals", to the point of deserving a different way of interacting
with the feature (perhaps more closely tied to the concurrency model
than to variable storage).
By "local value" I assume you mean "local binding," which (in the
version I posted) would indeed be per-thread. But in what sense are
"global variables shared across threads"? Without the binding, all you
have is the name, which isn't terribly variable.
And "scope locals" -- aren't all variables local to their scope by
definition, even if that scope happens to be universal?
So I'm pretty sure I must be misunderstanding something . . .
- We keep adding hacks to get around the fact that Parrot doesn't
handle scopes smaller than a compilation unit particularly well. If we
tackled that quirk, dynamic binding would likely fall out more
naturally, not to mention exception handlers, lexical variables, etc.
Allison
I'm afraid I don't follow this, either. "Scope" is mostly an HLL
concept; what would Parrot need to do to support them better? Or are
you talking about debugger annotation for variable lifetime?
-- Bob
Bob Rogers
Date: Mon, 13 Nov 2006 23:02:30 -0500
From: Leopold Toetsch <l...@toetsch.at>
Date: Mon, 13 Nov 2006 21:19:26 +0100
Am Montag, 13. November 2006 03:56 schrieb Bob Rogers:
> +There are two techniques for implementing dynamic binding. These are
> +traditionally called deep binding and shallow binding [2].
Can you please consider the impacts of a third variant using STM, which is
already implemented . . .
Thanks,
leo
Well, I see that STM transactions nest, but they don't seem to roll back
in case of an error . . .
I see now [1] that the Parrot implementation is incomplete with respect
to error handling. Throwing an error that unwinds past the transaction
should indeed do one of two things [3]:
1. If the transaction is still valid, then the error is a real one;
the transaction must be aborted so that the enclosing handler can deal
with the error.
2. Otherwise, the transaction is in an inconsistent state, which may
in fact have been the cause of this error. The transaction must
therefore be retried *instead* of entering the error handler. (I think
retrying is what C<stm_wait> is supposed to do, but a comment in
Parrot_STM_wait says "Not yet implemented. Right now just aborts.")
This all just means that invoking a continuation that unwinds past an
C<stm_start> must take care to check the transaction state, and wait or
abort the transaction as appropriate.
So C<stm_start> must push something onto the dynamic environment so
that rezipping/unwinding/whatever-we-call-it can take notice and do the
right thing. I am pretty sure this needs to be a Continuation subclass
that (a) points to the C<stm_start> instruction so that the transaction
can be retried, and (b) identifies the transaction that was opened by
the C<stm_start> so we check the right one for validity. Once that is
done, C<stm_wait> won't need a label; it can just find the most recent
transaction object in the dynamic environment. This also makes it
possible to decompose a single atomic STM operation into multiple
closures transparently [4].
Have I got this right so far?
. . . I might as well put "set_global" there instead; that would
also save me the trouble of deciding whether I needed to change the
stored PMC to an STMRef. But either way, full continuations (and
therefore coroutines) would still not work properly, as the actions
would be run repeatedly. Or am I missing something about STM?
I also notice that one cannot assign to an STMRef outside of a
transaction; the following code throws an "STM_begin_update outside
transaction" error:
.sub main :main
$P0 = new .Integer
$P0 = 42
$P1 = new .STMRef, $P0
$P1 = 45
print $P1
print "\n"
.end
So that means that I can't simply initialize all global variables to use
STMRef; I must use C<set_global> to interpose an STMRef object when I
want to bind it dynamically, thus:
## begin dynamic scope
$P0 = get_global ['Some'; 'Place'], '$global'
$I0 = isa $P0, "STMRef"
$P1 = $P0
if $I0 goto have_stmref
$P1 = new .STMRef, $P0
set_global ['Some'; 'Place'], '$global', $P1
have_stmref:
stm_start
## ... dynamic binding of $Some::Place::global is in scope here.
$P1 = 'new value'
stm_abort
if $I0 goto had_stmref
set_global ['Some'; 'Place'], '$global', $P0
had_stmref:
## end dynamic scope.
But of course this kludge is subject to race conditions, plus the same
sort of interleaved execution problems as naive shallow binding, not to
mention being broken with respect to continuations (including
exceptions). So it appears that I would have to bind the variable
dynamically before I can bind it dynamically!
The race conditions, interleaved execution, and exit continuation
problems could presumably be solved by adding an instruction that put an
entry on the dynamic environment so that rezipping could un-wrap the
global . . . but this begins to look suspiciously like my original
proposal. And even so, it would still not be possible to have one
thread bind a global dynamically while another sets its global value --
the global-setting thread would get that same "STM_begin_update outside
transaction" error.
FWIW, the code above can't work as written. The following code
snippet:
.sub main :main
$P0 = new .Integer
$P0 = 42
$P1 = new .STMRef, $P0
$I1 = isa $P1, "STMRef"
if $I1 goto it_is
print "not "
it_is:
print "an STMRef.\n"
.end
prints "not an STMRef." Presumably, this is because "isa" is actually
operating on the referenced value, and not the STMRef container.
In general, I would expect invoking a continuation to restore the
dynamic bindings in effect when the continuation was taken. For an
example, see the "coroutines, GC" test case . . .
Coroutines are an interesting special case. Rezipping out of a
transaction (by yielding from code inside it) obviously shouldn't abort
it, because we would normally expect to re-enter that context later.
But if the coroutine is never re-entered, then the transaction is never
cleanly terminated. Is this a problem, and if so, what should be done?
Rezipping via a general continuation class is more ambiguous. Should
the transaction be aborted, or not? Providing Parrot with more
Continuation subclasses that are explicitly associated with "abort" or
"suspend" semantics should help here.
Then again, one could argue that atomic STM operations should be
small, self-contained, and limited to reversible memory operations, and
therefore shouldn't involve anything hairy enough to require full
continuations. That is reasonable, but IMHO limiting; we should strive
to avoid artificial barriers to composing Parrot features.
And all of this is besides the point for dynamic binding. Rezipping
a dynamic binding is straightforward, and does not depend on the
Continuation class. Using STM makes the whole business unnecessarily
complicated.
IIUC, stm_start and stm_abort assume a single linear series of
changes for a given interpreter, where all 'start ... commit/abort'
pairs nest properly . . .
Consider a nested transaction composed of two primitive operations. The
primitive could be something that updates a shared hash table. It might
be written as a stand-alone STM operation, such as this:
.sub mutate_table
.param pmc table
...
stm_start
## random table munging
...
stm_commit
.end
Callers can invoke mutate_table with the knowledge that all updating is
protected by a transaction. If two tables need to be updated
simultaneously, they can be combined in an outer transaction:
.sub mutate_two_tables
...
stm_start
mutate_table(table1)
mutate_table(table2)
stm_commit
.end
The normal sequence of events (i.e. assuming no other thread causes an
inconsistency) would be:
stm_start (outer)
stm_start (table1)
# table1 munging
stm_commit (table1)
stm_start (table2)
# table2 munging
stm_commit (table2)
stm_commit (outer)
Other threads will not see the effect of either update until the final
(outer) commit. IIUC, this is achieved [5] by merging the committed
inner transactions into the outer transaction. This ability, IMHO, is
the essence of STM: Robust composability without breaking abstractions.
Now let's consider what happens if we use STM transactions to
implement dynamic binding. In outline, we would compile Perl 5 code
that looks like this:
sub test {
local $foo = 42;
...;
}
to something like the "dynamic scope" code shown above, with the key
global modification wrapped in stm_start and stm_abort. But that means
that if we have *any* dynamic binding in scope, *all* nested STM
operations would be thrown away. For the following code:
sub test {
local $foo = 42;
...;
mutate_table($table1);
}
the sequence of events would be
stm_start (binding)
stm_start (table1)
# table1 munging
stm_commit (table1)
stm_abort (binding)
The stm_abort would throw away the table-munging work done by the
stm_commit before it. And the author of the "test" sub is not likely to
understand why; the "local" could even be in a different module far
removed from the STM hackery.
In summary, I think dynamic binding needs a different mechanism from
STM for the following reasons:
1. Parrot STM is currently incomplete with respect to error
handling.
2. Even when this is fixed, there will still be other issues with
continuations that would limit an STM-based implementation.
3. Initial wrapping of globals that need to be dynamically bound in
STMRef objects is problematic, and breaks other threads that want to
treat the global as a global.
4. Dynamic binding would not be composable with STM: An application
that used the former would not be able to use the latter.
-- Bob
[1] I have now read exactly one paper [2] on the subject, which
officially makes me dangerous.
[2] Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy,
"Composable memory transactions". ACM Conference on Principles and
Practice of Parallel Programming 2005 (PPoPP'05).
http://research.microsoft.com/Users/simonpj/papers/stm/stm.pdf
[3] Ibid., p9.
[4] It may also eliminate the need for an explicit closure stack in
runtime/parrot/library/STM.pir, but I can't claim to understand why
it's there in the first place.
[5] Based on my reading of Section 6 of [2], and *not* on the Parrot
code, which uses data structures that I find harder to follow.
Bob Rogers
Date: Sun, 12 Nov 2006 21:56:04 -0500
The attached patch adds a docs/pdds/pddXX_dynbind.pod file, which is
a proposal for dynamic binding in Parrot . . .
I have made some minor updates to the doc which are available here:
http://rgrjr.dyndns.org/perl/pddXX_dynbind.html
The changes are to use "rezip" instead of "rewind," add a brief
discussion of the relation of dynamic binding to STM, remove the awkward
C<RegisterBinding> concept, clarify the risk of mutating locations in
use on the dynamic environment, and fix a misstatement of the effect
tailcalling by replacing it with an expanded discussion.
I haven't changed the code, so I won't bother to post an updated
patch.
-- Bob
Allison Randal
>
> - Overall, I want the implementation of dynamic binding to be tied in
> more closely with the implementation of globals and lexicals.
> Particularly lexicals. They're already operating under the same scope
> constraints as locals. They already have storage for named variables
> relevant to a particular scope, and the mechanism for handling scopes
> within scopes.
>
> I'm afraid I don't follow you, particularly the "operating under the
> same scope constraints" part. It seems to me that lexical variables are
> orthogonal to dynamic/global variables, and dynamic binding is purely a
> feature of globals. And lexicals are necessarily simpler, because all
> possible references are available to the compiler. So nested scopes are
> handled by the compiler simply by using a different register. Globals
> and dynamic bindings, because they must be visible to code in multiple
> compilation units, must necessarily use different mechanisms.
The proposal starts off talking about Perl 5's 'local' and Perl 6's
'temp'. They are lexical in nature (though they're more feature-rich
than simple lexicals). They only exist within a specific lexical scope,
and "roll back" on exiting that scope.
Why would dynamic binding only apply to globals? Perl 5's 'local'
doesn't apply to lexicals, but Perl 6's 'temp' will.
> - I like the idea of "thread locals": global variables shared across
> threads, but with a local value in one particular thread. I'll have to
> mull that one over some more. It seems fundamentally different from
> "scope locals", to the point of deserving a different way of interacting
> with the feature (perhaps more closely tied to the concurrency model
> than to variable storage).
>
> By "local value" I assume you mean "local binding," which (in the
> version I posted) would indeed be per-thread. But in what sense are
> "global variables shared across threads"? Without the binding, all you
> have is the name, which isn't terribly variable.
>
> And "scope locals" -- aren't all variables local to their scope by
> definition, even if that scope happens to be universal?
>
> So I'm pretty sure I must be misunderstanding something . . .
Your proposal mixes two ideas. One is the idea of 'local'/'temp', the
other is thread-level dynamic bindings. (I called these two concepts
"scope locals" and "thread locals", but "scoped locals" is probably a
better term for the first set.)
A more explicit phrasing of my comment about "local value" is: "In the
case of a global variable shared across threads, this proposal would
make it possible to have a version of the variable local to one specific
thread, so changes to that variable within that thread do not affect the
variable's value in the other threads." I consider this to be the most
interesting idea put forth in the proposal.
While I'm not accepting the currently proposed implementation, this idea
is likely to make it in. Possibly as a lightweight use of STM, possibly
as part of the new concurrency model(s), or possibly as a variation on
scoped locals.
> - We keep adding hacks to get around the fact that Parrot doesn't
> handle scopes smaller than a compilation unit particularly well. If we
> tackled that quirk, dynamic binding would likely fall out more
> naturally, not to mention exception handlers, lexical variables, etc.
>
> I'm afraid I don't follow this, either. "Scope" is mostly an HLL
> concept; what would Parrot need to do to support them better? Or are
> you talking about debugger annotation for variable lifetime?
It's true that scope is an HLL concept, but the whole idea of Parrot is
to provide tools for implementing HLLs. Parrot's concept of scope is
still quite primitive, and not very helpful to compiler writers.
Allison
Bob Rogers
Date: Sun, 26 Nov 2006 18:14:28 -0800
Bob Rogers wrote:
>
> - Overall, I want the implementation of dynamic binding to be tied in
> more closely with the implementation of globals and lexicals.
> Particularly lexicals. They're already operating under the same scope
> constraints as locals. They already have storage for named variables
> relevant to a particular scope, and the mechanism for handling scopes
> within scopes.
>
> I'm afraid I don't follow you, particularly the "operating under the
> same scope constraints" part. It seems to me that lexical variables are
> orthogonal to dynamic/global variables, and dynamic binding is purely a
> feature of globals. And lexicals are necessarily simpler, because all
> possible references are available to the compiler. So nested scopes are
> handled by the compiler simply by using a different register. Globals
> and dynamic bindings, because they must be visible to code in multiple
> compilation units, must necessarily use different mechanisms.
The proposal starts off talking about Perl 5's 'local' and Perl 6's
'temp'. They are lexical in nature (though they're more feature-rich
than simple lexicals). They only exist within a specific lexical scope,
and "roll back" on exiting that scope.
They do "roll back" on block exit, but that is a statement about
lifetime, not scope. The whole point of dynamic binding is that such
bindings are visible outside of the sub where they are bound, which by
definition makes them "not lexical" in scope. Do you disagree?
Why would dynamic binding only apply to globals? Perl 5's 'local'
doesn't apply to lexicals, but Perl 6's 'temp' will.
Because I have been assuming that these language constructs *always*
introduce a new binding, which is trivial for lexicals, as I've already
said: Just allocate a new register and you're done. The extra
mechanism is only needed for globals because only global bindings are
potentially visible outside the compilation unit that creates the
binding (but I've said that, too).
But then, prompted by your response, I took another look at S04 and
found the following statement near the end of the first section:
C<temp> and C<let> temporize or hypotheticalize the value or
the variable depending on whether you do assignment or
binding.
This could mean that "temp" and "let" might not always create new
bindings, which would mean that a "rollback" mechanism could indeed be
needed for lexicals. I assume this statement can be defactored into the
following four:
C<temp> temporizes the value if you do assignment.
C<temp> temporizes the variable if you do binding.
C<let> hypotheticalizes the value if you do assignment.
C<let> hypotheticalizes the variable if you do binding.
But I'm not at all sure what "assignment" vs "binding" means here, since
it appears to refer to syntax that is not shown. I'm also unsure that I
understand the difference between temporizing/hypotheticalizing values
vs. variables; is this a question of morphing a PMC vs. replacing it in
its container?
My apologies if these are Perl 6 FAQs, or the answers turn out to be
irrelevant to Parrot; I figure I ought to know in order to understand
what mechanisms Parrot needs to provide.
> - I like the idea of "thread locals": global variables shared across
> threads, but with a local value in one particular thread. I'll have to
> mull that one over some more. It seems fundamentally different from
> "scope locals", to the point of deserving a different way of interacting
> with the feature (perhaps more closely tied to the concurrency model
> than to variable storage).
>
> By "local value" I assume you mean "local binding," which (in the
> version I posted) would indeed be per-thread. But in what sense are
> "global variables shared across threads"? Without the binding, all you
> have is the name, which isn't terribly variable.
>
> And "scope locals" -- aren't all variables local to their scope by
> definition, even if that scope happens to be universal?
>
> So I'm pretty sure I must be misunderstanding something . . .
Your proposal mixes two ideas. One is the idea of 'local'/'temp', the
other is thread-level dynamic bindings. (I called these two concepts
"scope locals" and "thread locals", but "scoped locals" is probably a
better term for the first set.)
Perhaps, but I did mix them deliberately. After considering several
alternatives, I decided that it was most useful to define "dynamic
scope" as being thread-local.
A more explicit phrasing of my comment about "local value" is: "In the
case of a global variable shared across threads, this proposal would
make it possible to have a version of the variable local to one specific
thread, so changes to that variable within that thread do not affect the
variable's value in the other threads." I consider this to be the most
interesting idea put forth in the proposal.
For the record, the concept is far from original. That's essentially
how dynamic bindings behaved on the Lisp Machine of yore, though the
mechanism proposed is different.
Besides, dynamic binding is not supposed to be interesting; it's
supposed to be cheap, simple, and boring, so that it can be used to
implement the *really* interesting stuff. ;-}
However, your use of the phrase "a version of the variable" makes me
wonder if I understand you properly. Does this mean "a variable
binding"? If so, why avoid this well-established terminology? And in
any case, I still don't understand in what sense such a variable could
be "shared across threads" if the binding is not? It seems to me that
sharing only the variable name is not sharing the variable.
While I'm not accepting the currently proposed implementation, this idea
is likely to make it in. Possibly as a lightweight use of STM, possibly
as part of the new concurrency model(s), or possibly as a variation on
scoped locals.
Could you be more specific about the proposed implementation? What
issues do you have with it? Is it worth fixing, or should I give up?
> - We keep adding hacks to get around the fact that Parrot doesn't
> handle scopes smaller than a compilation unit particularly well. If we
> tackled that quirk, dynamic binding would likely fall out more
> naturally, not to mention exception handlers, lexical variables, etc.
>
> I'm afraid I don't follow this, either. "Scope" is mostly an HLL
> concept; what would Parrot need to do to support them better? Or are
> you talking about debugger annotation for variable lifetime?
It's true that scope is an HLL concept, but the whole idea of Parrot is
to provide tools for implementing HLLs. Parrot's concept of scope is
still quite primitive, and not very helpful to compiler writers.
Allison
Then I'm still in the dark -- or perhaps just lucky. As a compiler
writer, the only thing I find "unhelpful" about Parrot in terms of
scoping is its lack of dynamic binding. Hence, the patch.
-- Bob
Allison Randal
> Allison Randal wrote:
>
> The proposal starts off talking about Perl 5's 'local' and Perl 6's
> 'temp'. They are lexical in nature (though they're more feature-rich
> than simple lexicals). They only exist within a specific lexical scope,
> and "roll back" on exiting that scope.
>
> They do "roll back" on block exit, but that is a statement about
> lifetime, not scope. The whole point of dynamic binding is that such
> bindings are visible outside of the sub where they are bound, which by
> definition makes them "not lexical" in scope. Do you disagree?
The whole point of 'temp' and 'local' is that the bindings aren't
visible outside the scope where they're defined (whether that scope is a
sub, block, etc).
> Why would dynamic binding only apply to globals? Perl 5's 'local'
> doesn't apply to lexicals, but Perl 6's 'temp' will.
>
> Because I have been assuming that these language constructs *always*
> introduce a new binding, which is trivial for lexicals, as I've already
> said: Just allocate a new register and you're done. The extra
> mechanism is only needed for globals because only global bindings are
> potentially visible outside the compilation unit that creates the
> binding (but I've said that, too).
Also not a valid assumption for 'temp' and 'local'.
> But then, prompted by your response, I took another look at S04 and
> found the following statement near the end of the first section:
>
> C<temp> and C<let> temporize or hypotheticalize the value or
> the variable depending on whether you do assignment or
> binding.
>
> This could mean that "temp" and "let" might not always create new
> bindings, which would mean that a "rollback" mechanism could indeed be
> needed for lexicals. I assume this statement can be defactored into the
> following four:
>
> C<temp> temporizes the value if you do assignment.
> C<temp> temporizes the variable if you do binding.
> C<let> hypotheticalizes the value if you do assignment.
> C<let> hypotheticalizes the variable if you do binding.
>
> But I'm not at all sure what "assignment" vs "binding" means here, since
> it appears to refer to syntax that is not shown. I'm also unsure that I
> understand the difference between temporizing/hypotheticalizing values
> vs. variables; is this a question of morphing a PMC vs. replacing it in
> its container?
To put it in Parrot terms: An assignment passes the value of one PMC to
an existing PMC and lets the receiving PMC decide what to do with the
value. A binding replaces the PMC stored in the namespace or lexical pad
with another PMC.
> A more explicit phrasing of my comment about "local value" is: "In the
> case of a global variable shared across threads, this proposal would
> make it possible to have a version of the variable local to one specific
> thread, so changes to that variable within that thread do not affect the
> variable's value in the other threads." I consider this to be the most
> interesting idea put forth in the proposal.
>
> For the record, the concept is far from original. That's essentially
> how dynamic bindings behaved on the Lisp Machine of yore, though the
> mechanism proposed is different.
>
> Besides, dynamic binding is not supposed to be interesting; it's
> supposed to be cheap, simple, and boring, so that it can be used to
> implement the *really* interesting stuff. ;-}
Aye, but it's a new idea for Parrot.
> However, your use of the phrase "a version of the variable" makes me
> wonder if I understand you properly. Does this mean "a variable
> binding"? If so, why avoid this well-established terminology?
Just being explicit. Many a conversation has gone wrong because two
people are using the same words to mean different things.
> And in
> any case, I still don't understand in what sense such a variable could
> be "shared across threads" if the binding is not? It seems to me that
> sharing only the variable name is not sharing the variable.
The variable is still shared if you can "unbind" it at some point and
then have access to the shared value. The shared value is stored
somewhere in thread.
> Could you be more specific about the proposed implementation? What
> issues do you have with it? Is it worth fixing, or should I give up?
Mainly, I don't see the proposal as it stands as a solution for 'temp'
and 'local'. Dynamic binding as you define it (what I'm calling
thread-locals), is a completely different problem. The proposal needs a
description of the problem it is solving, instead of describing one
problem and solving a different one.
Also, the particular implementation suggested -- the Location class
hierarchy of abstract and instantiable classes, the stack of stored
values -- is more heavy weight than the underlying concept merits. I see
thread-locals as a feature to integrate into the sharing architecture of
the core concurrency model.
So yeah, the proposal is worth working on, if you're interested in
pushing the idea to the next level. If you're not interested in going
there, you have raised an interesting idea, so many thanks!
> As a compiler
> writer, the only thing I find "unhelpful" about Parrot in terms of
> scoping is its lack of dynamic binding.
That would be useful information. What are the practical problems you're
working on that would be made easier with thread-locals? How will the
feature be used by HLLs? How will it be used in Parrot's internal code
(compiler tools, etc)?
Allison
Bob Rogers
Date: Wed, 06 Dec 2006 20:09:09 -0800
Bob Rogers wrote:
> Allison Randal wrote:
>
> The proposal starts off talking about Perl 5's 'local' and Perl 6's
> 'temp'. They are lexical in nature (though they're more feature-rich
> than simple lexicals). They only exist within a specific lexical scope,
> and "roll back" on exiting that scope.
>
> They do "roll back" on block exit, but that is a statement about
> lifetime, not scope. The whole point of dynamic binding is that such
> bindings are visible outside of the sub where they are bound, which by
> definition makes them "not lexical" in scope. Do you disagree?
The whole point of 'temp' and 'local' is that the bindings aren't
visible outside the scope where they're defined (whether that scope is a
sub, block, etc).
Please run the following Perl 5 example:
#! /usr/bin/perl -w
#
# Illustration of "local" binding scope. This is an
# "uncompiled" version of the "binding at two call levels" test
# case from t/op/globals.t in the patch. The order of the three
# subs is immaterial. -- rgr, 7-Dec-06.
package Foo::Bar;
use strict;
use vars qw($foo);
sub main {
$foo = "Outer value\n";
show_value();
test1();
show_value();
}
sub test1 {
local $foo = "Inner value\n";
show_value();
}
sub show_value {
print $foo;
}
main();
The variable $foo has global scope, but "local $foo" introduces a new
binding of $foo that is most definitely visible outside of the lexical
environment where it is created. Running this code prints
Outer value
Inner value
Outer value
illustrating that show_value has access to this binding. According to
perlsub (but with underlining changed to caps):
A "local" modifies its listed variables to be "local" to the enclosing
block, "eval", or "do FILE"--and to ANY SUBROUTINE CALLED FROM WITHIN
THAT BLOCK. A "local" just gives temporary values to global (meaning
package) variables. It does NOT create a local variable. This is
known as dynamic scoping. Lexical scoping is done with "my", which
works more like C's auto declarations.
This is also my definition of "dynamic scoping". Were you not aware of
this behavior of "local", or are we talking about different things
entirely?
> . . .
>
> But I'm not at all sure what "assignment" vs "binding" means here, since
> it appears to refer to syntax that is not shown. I'm also unsure that I
> understand the difference between temporizing/hypotheticalizing values
> vs. variables; is this a question of morphing a PMC vs. replacing it in
> its container?
To put it in Parrot terms: An assignment passes the value of one PMC to
an existing PMC and lets the receiving PMC decide what to do with the
value. A binding replaces the PMC stored in the namespace or lexical pad
with another PMC.
OK, I think I've got it. In that case, we probably need C<temp_global>
and C<temp_location> ops in that case. And certainly some new
C<BoundLocation> classes . . .
But I'm still unclear how this distinction is made in a Perl 6
program. If you write
temp $foo = 37;
is this assignment or binding? And in either case, how do you specify
the other? Larry? (Not that understanding this is likely to be
necessary for getting Parrot to do the right thing.)
> . . .
>
> And in
> any case, I still don't understand in what sense such a variable could
> be "shared across threads" if the binding is not? It seems to me that
> sharing only the variable name is not sharing the variable.
The variable is still shared if you can "unbind" it at some point and
then have access to the shared value. The shared value is stored
somewhere in thread.
OK, I think I see; the shadowed binding is still "shared" in that sense.
(Though I'm still not fond of this terminology.)
> Could you be more specific about the proposed implementation? What
> issues do you have with it? Is it worth fixing, or should I give up?
Mainly, I don't see the proposal as it stands as a solution for 'temp'
and 'local'. Dynamic binding as you define it (what I'm calling
thread-locals), is a completely different problem. The proposal needs a
description of the problem it is solving, instead of describing one
problem and solving a different one.
Does the Perl 5 example above convince you that it is the same problem?
Or at least a subset, given that I didn't follow the "assignment
vs. binding" thing?
Also, the particular implementation suggested -- the Location class
hierarchy of abstract and instantiable classes, the stack of stored
values -- is more heavy weight than the underlying concept merits.
If you can think of a lighter-weight approach, I'm all ears. I proposed
something fairly lightweight nearly a year ago [1], with nearly the same
functionality, though it only addressed globals. Leo quite reasonably
objected that it didn't fully implement Perl 5 "local", and I agreed
that it was too particular to globals to be generalized, so I withdrew
it. The new approach attempts to address that limitation by introducing
PMC classes to support structure and variable binding distinctly in an
extensible way [2]. Now it appears that I need to be both (a) more
complete, to handle assignment as opposed to just binding, and (b)
lighter in weight. Please pick just one. ;-}
I see thread-locals as a feature to integrate into the sharing
architecture of the core concurrency model.
So yeah, the proposal is worth working on, if you're interested in
pushing the idea to the next level. If you're not interested in going
there, you have raised an interesting idea, so many thanks!
I would like to see this implemented, so I'm willing to go back to the
drawing board for a third go. Before I do, though, I would just like to
be reasonably sure that I'm aimed in the right direction.
> As a compiler
> writer, the only thing I find "unhelpful" about Parrot in terms of
> scoping is its lack of dynamic binding.
That would be useful information. What are the practical problems
you're working on that would be made easier with thread-locals? How
will the feature be used by HLLs? How will it be used in Parrot's
internal code (compiler tools, etc)?
Allison
Oh, I have lots of ideas:
1. First and foremost, I need for my compiler to support this basic
CL feature. (Right now, it kludges around this with C<pushaction>, but
the implementation is really gross.) Here is a CL version of the Perl
program above; it is almost identical, modulo syntax changes.
;;; Illustration of Common Lisp "special" bindings. This is an
;;; "uncompiled" version of the "binding at two call levels"
;;; test case from t/op/globals.t in the patch. The order of
;;; the three subs is immaterial. -- rgr, 7-Dec-06.
(defpackage foobar)
(in-package :foobar)
(defvar foo)
(defun main ()
(setq foo "Outer value")
(show-value)
(test1)
(show-value))
(defun test1 ()
(let ((foo "Inner value"))
(show-value)))
(defun show-value ()
(format t "~A~%" foo))
(main)
Besides being an important feature in its own right (CL I/O depends
heavily upon dynamic binding), it is traditionally used to implement
nonlexical features such as CATCH and THROW [3], which typically
communicate via a dynamically-bound alist of CATCH tags. Not having
dynamic binding has effectively stalled my compiler project for about
six months now.
2. I have an implementation strategy for bringing C<throw> up to
PDD23 that relies on dynamic binding -- and here the per-thread aspect
becomes important. How does one keep track of bound handlers as they
are tried in such a way that they are not in scope when invoked, yet are
still restored if and when a continuation exits? The following Perl 5
pseudocode should give the flavor of it:
sub throw {
my $exception = shift;
local @BOUND_HANDLERS = @BOUND_HANDLERS;
while (@BOUND_HANDLERS) {
pop(@BOUND_HANDLERS)->($exception);
}
# still unhandled . . .
}
This cannot be implemented in C as written since invoking the handler
via an inferior runloop would make it impossible for the handler to call
an exit continuation (or BE an exit continuation). Fortunately, the
rebinding of @BOUND_HANDLERS makes it easy to rewrite this as a tail
recursion, given suitable C-calling magic in the continuation. It also
serves the purpose of keeping each handler out of its own scope, while
restoring the handler state appropriately if a handler exits.
3. When the PDD23 dust settles, it will then be possible to finish
STM with respect to error handling. (Well, I suppose it's possible now,
but I assume it will be easier later.)
4. As currently implemented, the Coroutine class requires all
C<yield> instructions to be in the initial coroutine sub (indeed, this
IS the coroutine), which is limiting. To fix this, Coroutine should be
redone as a variant of a Continuation, which probably requires minor API
changes to the way in which coroutines are created. However, the
C<yield> interface can remain the same as long as there is a "current
coroutine" concept which is dynamically scoped -- an ideal application
for a dynamic variable binding (again, thread-local).
And I'm sure I'll think of more as soon as I send this . . .
Your faithful Dynamic Environmentalist,
-- Bob
[2] This extensibility is important to me because CL requires that I be
able to bind a variable (named by a symbol) that is not in any
namespace (package). That should be easy enough to handle with a
new LispBinding class that takes a symbol. The details are still
fuzzy . . .
[3] http://www.lispworks.com/documentation/HyperSpec/Body/s_catch.htm#catch
Allison Randal
>
> This is also my definition of "dynamic scoping". Were you not aware of
> this behavior of "local", or are we talking about different things
> entirely?
I was talking about the lifetime of the temporization not static vs.
dynamic scoping.
But, this does help me better understand what you're getting at. The
proposal only mentions "dynamic scope" three times, but reading through
it again now I can see that the whole proposal is a literal
implementation of a classic textbook definition of dynamic scope.
[For reference, Wikipedia says: "In dynamic scoping, each identifier has
a global stack of bindings. Introducing a local variable with name x
pushes a binding onto the global x stack (which may have been empty),
which is popped off when the control flow leaves the scope. Evaluating x
in any context always yields the top binding."]
> But I'm still unclear how this distinction is made in a Perl 6
> program. If you write
>
> temp $foo = 37;
>
> is this assignment or binding? And in either case, how do you specify
> the other? Larry? (Not that understanding this is likely to be
> necessary for getting Parrot to do the right thing.)
That's assignment. Binding would be:
temp $foo := 37;
> > Could you be more specific about the proposed implementation? What
> > issues do you have with it? Is it worth fixing, or should I give up?
>
> Mainly, I don't see the proposal as it stands as a solution for 'temp'
> and 'local'. Dynamic binding as you define it (what I'm calling
> thread-locals), is a completely different problem. The proposal needs a
> description of the problem it is solving, instead of describing one
> problem and solving a different one.
>
> Does the Perl 5 example above convince you that it is the same problem?
> Or at least a subset, given that I didn't follow the "assignment
> vs. binding" thing?
We're now talking about 3 different things: dynamic binding, dynamic
scoping, and temporization. Dynamic binding is any association of a
value with an identifier, when that association is made at runtime. It's
much broader than what we're talking about here. So, let's stop using
that term.
On dynamic scoping and temporization, I agree that they're related
problems, in that some definitions of temporization use dynamic scoping.
But either feature can be used without the other, so it's better to
separate the implementation of dynamic scoping from the implementation
of temporization.
> Also, the particular implementation suggested -- the Location class
> hierarchy of abstract and instantiable classes, the stack of stored
> values -- is more heavy weight than the underlying concept merits.
>
> If you can think of a lighter-weight approach, I'm all ears. I proposed
> something fairly lightweight nearly a year ago [1], with nearly the same
> functionality, though it only addressed globals. Leo quite reasonably
> objected that it didn't fully implement Perl 5 "local", and I agreed
> that it was too particular to globals to be generalized, so I withdrew
> it. The new approach attempts to address that limitation by introducing
> PMC classes to support structure and variable binding distinctly in an
> extensible way [2]. Now it appears that I need to be both (a) more
> complete, to handle assignment as opposed to just binding, and (b)
> lighter in weight. Please pick just one. ;-}
Lighter weight, by separating out the problems into separate components.
Assignment and binding are relevant to temporization, not to dynamic
scoping.
> I would like to see this implemented, so I'm willing to go back to the
> drawing board for a third go. Before I do, though, I would just like to
> be reasonably sure that I'm aimed in the right direction.
Step one: Write a proposal for implementing dynamic scope and remove all
references to temporization.
Bonus: Try one data structure per scope, that tracks the dynamically
scoped items in that scope. This data structure can be captured by a
continuation. Don't create the data structure unless there are
dynamically scoped items declared in the scope. Try making the interface
as simple as the lexical C<.lex>.
> Oh, I have lots of ideas:
>
> 1. First and foremost, I need for my compiler to support this basic
> CL feature. (Right now, it kludges around this with C<pushaction>, but
> the implementation is really gross.)
Agreed that using C<pushaction> for this is a kludge. We can do better.
> Here is a CL version of the Perl
> program above; it is almost identical, modulo syntax changes.
>
> ;;; Illustration of Common Lisp "special" bindings. This is an
> ;;; "uncompiled" version of the "binding at two call levels"
> ;;; test case from t/op/globals.t in the patch. The order of
> ;;; the three subs is immaterial. -- rgr, 7-Dec-06.
>
> (defpackage foobar)
>
> (in-package :foobar)
>
> (defvar foo)
>
> (defun main ()
> (setq foo "Outer value")
> (show-value)
> (test1)
> (show-value))
>
> (defun test1 ()
> (let ((foo "Inner value"))
> (show-value)))
>
> (defun show-value ()
> (format t "~A~%" foo))
>
> (main)
The important point here is that C<defvar> is a declaration to create a
dynamically scoped variable (or "special variable" as they call it). In
the Perl example, it's the C<local> that makes 'foo' behave dynamically
scoped, and it will return to being an ordinary global as soon as that
C<local> declaration goes out of scope. In both cases, dynamic scoping
is a property of the variable, in much the same way that lexical scoping
is a property of a variable.
> Besides being an important feature in its own right (CL I/O depends
> heavily upon dynamic binding), it is traditionally used to implement
> nonlexical features such as CATCH and THROW [3], which typically
> communicate via a dynamically-bound alist of CATCH tags. Not having
> dynamic binding has effectively stalled my compiler project for about
> six months now.
Since we've apparently been using "dynamic binding" to mean two
completely different things, I'll try to translate. CATCH and THROW in
CL rely on a dynamically scoped list variable. And, extrapolating: at
each dynamic scope is (potentially) a list of catch tags. When throw is
looking for the catch tags that match the throw tag, it first searches
the current top-most list of catch tags in the dynamically scoped
variable. If it fails to find a match in the top-most list, does it
traverse back through the stack of dynamic values for the list? That is,
is there a reason you need to implement exception handling using custom
data structures rather than relying on Parrot's exceptions?
> 2. I have an implementation strategy for bringing C<throw> up to
> PDD23 that relies on dynamic binding -- and here the per-thread aspect
> becomes important. How does one keep track of bound handlers as they
> are tried in such a way that they are not in scope when invoked, yet are
> still restored if and when a continuation exits? The following Perl 5
> pseudocode should give the flavor of it:
>
> sub throw {
> my $exception = shift;
>
> local @BOUND_HANDLERS = @BOUND_HANDLERS;
> while (@BOUND_HANDLERS) {
> pop(@BOUND_HANDLERS)->($exception);
> }
> # still unhandled . . .
> }
>
> This cannot be implemented in C as written since invoking the handler
> via an inferior runloop would make it impossible for the handler to call
> an exit continuation (or BE an exit continuation). Fortunately, the
> rebinding of @BOUND_HANDLERS makes it easy to rewrite this as a tail
> recursion, given suitable C-calling magic in the continuation. It also
> serves the purpose of keeping each handler out of its own scope, while
> restoring the handler state appropriately if a handler exits.
Sounds like a topic for a separate proposal. Not really enough here to
evaluate.
> 4. As currently implemented, the Coroutine class requires all
> C<yield> instructions to be in the initial coroutine sub (indeed, this
> IS the coroutine), which is limiting. To fix this, Coroutine should be
> redone as a variant of a Continuation, which probably requires minor API
> changes to the way in which coroutines are created. However, the
> C<yield> interface can remain the same as long as there is a "current
> coroutine" concept which is dynamically scoped -- an ideal application
> for a dynamic variable binding (again, thread-local).
What do you mean by allowing a C<yield> instruction outside the
coroutine sub? That sounds about like a C<return> instruction outside of
a subroutine/compilation unit. I'm not convinced this is a problem that
needs to be fixed, but if you have more thoughts on it you might put
them in another separate proposal.
Allison
Bob Rogers
Date: Sat, 09 Dec 2006 21:55:35 -0800
Bob Rogers wrote:
> This is also my definition of "dynamic scoping". Were you not aware of
> this behavior of "local", or are we talking about different things
> entirely?
I was talking about the lifetime of the temporization not static vs.
dynamic scoping.
OK, then I think we agree. (Your original statement was ambiguous about
whether you were talking about scope or lifetime, but then your next
statement used the word "scope.")
But, this does help me better understand what you're getting at. The
proposal only mentions "dynamic scope" three times, but reading through
it again now I can see that the whole proposal is a literal
implementation of a classic textbook definition of dynamic scope.
Yes. But I've been calling it "dynamic binding" because it's the
variable binding that has dynamic scope. I'm willing to adopt your
terminology, but you'll have to bear with me, because I've been saying
"dynamic binding" for quite a while now. But what would you have me use
for the verb, if not "to bind"?
[For reference, Wikipedia says: "In dynamic scoping, each identifier has
a global stack of bindings. Introducing a local variable with name x
pushes a binding onto the global x stack (which may have been empty),
which is popped off when the control flow leaves the scope. Evaluating x
in any context always yields the top binding."]
I saw this, too. I assume this is just a conceptual simplification for
teaching purposes; it would be silly to create a literal stack for each
variable when only a handful of them will ever be rebound this way at
any given time. None of the compilers I'm aware of do it this way.
> But I'm still unclear how this distinction is made in a Perl 6
> program. If you write
>
> temp $foo = 37;
>
> is this assignment or binding? And in either case, how do you specify
> the other? Larry? (Not that understanding this is likely to be
> necessary for getting Parrot to do the right thing.)
That's assignment. Binding would be:
temp $foo := 37;
Great; thanks.
> > Could you be more specific about the proposed implementation? What
> > issues do you have with it? Is it worth fixing, or should I give up?
>
> Mainly, I don't see the proposal as it stands as a solution for 'temp'
> and 'local'. Dynamic binding as you define it (what I'm calling
> thread-locals), is a completely different problem. The proposal needs a
> description of the problem it is solving, instead of describing one
> problem and solving a different one.
>
> Does the Perl 5 example above convince you that it is the same problem?
> Or at least a subset, given that I didn't follow the "assignment
> vs. binding" thing?
We're now talking about 3 different things: dynamic binding, dynamic
scoping, and temporization. Dynamic binding is any association of a
value with an identifier, when that association is made at runtime. It's
much broader than what we're talking about here. So, let's stop using
that term.
Now I'm confused again. Isn't that exactly what we're talking about,
but generalized to include binding of non-variables?
On dynamic scoping and temporization, I agree that they're related
problems, in that some definitions of temporization use dynamic scoping.
But either feature can be used without the other, so it's better to
separate the implementation of dynamic scoping from the implementation
of temporization.
OK.
> Also, the particular implementation suggested -- the Location class
> hierarchy of abstract and instantiable classes, the stack of stored
> values -- is more heavy weight than the underlying concept merits.
>
> If you can think of a lighter-weight approach, I'm all ears. I proposed
> something fairly lightweight nearly a year ago, with nearly the same
> functionality, though it only addressed globals. Leo quite reasonably
> objected that it didn't fully implement Perl 5 "local", and I agreed
> that it was too particular to globals to be generalized, so I withdrew
> it. The new approach attempts to address that limitation by introducing
> PMC classes to support structure and variable binding distinctly in an
> extensible way. Now it appears that I need to be both (a) more
> complete, to handle assignment as opposed to just binding, and (b)
> lighter in weight. Please pick just one. ;-}
Lighter weight, by separating out the problems into separate components.
Assignment and binding are relevant to temporization, not to dynamic
scoping.
??? Do you mean "The assignment versus binding distinction is relevant
to temporization, not ..."? If so, I'm perfectly happy to ignore it.
> I would like to see this implemented, so I'm willing to go back to the
> drawing board for a third go. Before I do, though, I would just like to
> be reasonably sure that I'm aimed in the right direction.
Step one: Write a proposal for implementing dynamic scope and remove all
references to temporization.
OK. I assume "dynamic scope" can include Perl 5 "local" as applied to
variables; does it exclude "local" applied to structure locations?
Bonus: Try one data structure per scope, that tracks the dynamically
scoped items in that scope. This data structure can be captured by a
continuation. Don't create the data structure unless there are
dynamically scoped items declared in the scope. Try making the interface
as simple as the lexical C<.lex>.
What is the purpose of this "one data structure per scope"? I certainly
understand why it works to have one data structure per sub for C<.lex>,
despite the fact that each variable may be introduced in a different
block. But dynamically-scoped variables need more fine-grained
handling. For concreteness, here is another Perl 5 example:
sub foo {
# [span 1]
{
local $bar = compute_bar();
# [span 2]
{
local $baz = compute_baz();
# [span 3]
}
# [span 4]
}
# [span 5]
}
To belabor the obvious, the extents of the two "local" bindings divide
the sub into five spans, with different dynamic environments going from
one to the next. These dynamic environments must be established and
disestablished individually, so that "compute_bar()" does not see a new
"$baz" binding in scope, but "compute_baz()" does see the new "$bar".
The current proposal deals with this by using opcodes that add and
subtract from the dynamic environment. I think you are saying that you
would prefer that I do this declaratively using one data structure per
sub (or per block?). To me, this seems harder, especially since values
from "compute_bar()" and "compute_baz()" must be supplied somehow. Am I
missing something?
. . .
I would cavil that dynamic scoping is a property of the binding; I can
rewrite this example without the C<defvar>. It is a minor point, but I
mention it in the hope of foiling future misunderstandings.
> Besides being an important feature in its own right (CL I/O depends
> heavily upon dynamic binding), it is traditionally used to implement
> nonlexical features such as CATCH and THROW, which typically
> communicate via a dynamically-bound alist of CATCH tags. Not having
> dynamic binding has effectively stalled my compiler project for about
> six months now.
Since we've apparently been using "dynamic binding" to mean two
completely different things, I'll try to translate. CATCH and THROW in
CL rely on a dynamically scoped list variable. And, extrapolating: at
each dynamic scope is (potentially) a list of catch tags. When throw is
looking for the catch tags that match the throw tag, it first searches
the current top-most list of catch tags in the dynamically scoped
variable. If it fails to find a match in the top-most list, does it
traverse back through the stack of dynamic values for the list?
Not necessary; at any given time, the list contains all valid CATCH
tags. The translation process does something like this (omitting
details of how results from the continuation are handled):
(catch <tag> <body>)
=>
(let ((*catch-bindings* (cons (cons <tag> (%make-continuation))
*catch-bindings*)))
(declare (special *catch-bindings*))
<body>)
So each shadowed binding of *catch-bindings* contains a tail of all of
the newer bindings.
That is, is there a reason you need to implement exception handling
using custom data structures rather than relying on Parrot's
exceptions?
I am not suggesting that Parrot's exceptions be changed or replaced. I
was only pointing out a different mechanism for keeping track of the
handlers that are currently in scope, using a dynamically-scoped
variable and a Pair (or some kind of array, but using a Pair would be
more efficient).
> 2. I have an implementation strategy for bringing C<throw> up to
> PDD23 that relies on dynamic binding . . .
Sounds like a topic for a separate proposal. Not really enough here to
evaluate.
Yes. By all means, let's stick to one proposal at a time.
> 4. As currently implemented, the Coroutine class requires all
> C<yield> instructions to be in the initial coroutine sub (indeed, this
> IS the coroutine), which is limiting. To fix this, Coroutine should be
> redone as a variant of a Continuation, which probably requires minor API
> changes to the way in which coroutines are created. However, the
> C<yield> interface can remain the same as long as there is a "current
> coroutine" concept which is dynamically scoped -- an ideal application
> for a dynamic variable binding (again, thread-local).
What do you mean by allowing a C<yield> instruction outside the
coroutine sub? That sounds about like a C<return> instruction
outside of a subroutine/compilation unit. I'm not convinced this is
a problem that needs to be fixed, but if you have more thoughts on it
you might put them in another separate proposal.
Allison
The problem was described in the "Coroutines in Lua" thread [1], but
I'll summarize. The gist is that the current design of Parrot can't
support the Lua coroutine API. In fact, I was not able to implement a
solution to the "same fringe problem" using the Coroutine PMC. Since
(AFAIK) this is the smallest problem for which the coroutine solution is
both efficient and significantly simpler than any known alternatives,
that argues strongly that the Parrot PMC implementation is broken.
But I'll save the implementation details for a proper proposal.
-- Bob