From: Allison Randal <[EMAIL PROTECTED]>
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?
. . .
> 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.
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
[1]
http://groups.google.com/group/perl.perl6.internals/browse_frm/thread/b5d7279ce4a0729e/fd8d67b5569fbce2?#fd8d67b5569fbce2
