Dynamic variable scoping
Bob Rogers
community, I am about to make my third annual attempt to implement
Parrot support for what Common Lisp calls "special variable binding."
Most of the rest of the world calls it "dynamic binding" or "dynamic
scoping" [1]; after last fall's email discussion [2], I am hoping that
"dynamic variable scoping" will capture the, ah, scope of this
particular project in a way that is satisfactory to everyone.
In the aforementioned thread [2], we seem to have reached a number of
conclusions about what "dynamic variable scoping" should mean. I have
summarized these below, to be sure we're all on the same page. If I
don't hear objections in the next week, I will start updating the
proposal.
FWIW, I am (re-)starting this project a few weeks earlier than I did
last year, so I am supremely confident that I will have the third
implementation ready by Christmas. At which time, if tradition holds,
the Powers That Be will veto it. ;-)
-- Bob Rogers
http://rgrjr.dyndns.org/
Project summary:
1. The dynamic variable scoping mechanism will address only global
variables, not registers or slots in aggreggates (e.g. arrays).
2. This mechanism will do binding, rather than assignment, where
"binding" is defined thus: "A binding replaces the PMC stored in the
namespace or lexical pad with another PMC [3]."
3. It may be possible to use dynamic variable scoping to implement
Perl 5 "local" and Perl 6 "temporization" in the case of binding of
global variables. However, full implementation of these features would
have to go far beyond this, so support for "temporization" is not a
design goal.
4. Dynamic variable binding state must be stored on the dynamic
environment stack, so that dynamic values are available to called subs,
and can be captured and restored by continuations. This in turn
requires new instructions to manipulate dynamic bindings on the dynamic
environment stack.
5. Dynamic variable bindings must be visible only within that
thread. Besides being useful in its own right, this makes it possible
to use thread-scoped dynamic variables to implement thread-scoped
dynamic control structures (e.g. coroutines, Lisp CATCH/THROW).
6. The implementation should not multiply PMC classes beyond
necessity.
References:
[1] http://en.wikipedia.org/wiki/Dynamic_variable_scoping#Dynamic_scoping
[3] Quoting Allison's message of 7-Dec-2006 from thread [2].
Allison Randal
> In what seems to have become an autumn tradition in the Parrot
> community, I am about to make my third annual attempt to implement
> Parrot support for what Common Lisp calls "special variable binding."
>
> FWIW, I am (re-)starting this project a few weeks earlier than I did
> last year, so I am supremely confident that I will have the third
> implementation ready by Christmas. At which time, if tradition holds,
> the Powers That Be will veto it. ;-)
How about starting by describing the problem you want to solve in 4
sentences? Laziness is a virtue... also a good way to get stuff done.
Allison
Allison Randal
the most likely solution is to create a LispSpecialVar PMC. In the same
way that a MultiSub acts like a sub but internally stores a list of
subs, the LispSpecialVar would act like an ordinary variable to Parrot
internals and to all other languages, but would internally store a stack
of previous dynamic bindings.
Likewise, the behavior at the point when a PMC is shared across threads
is determined by the 'share' and 'share_ro' vtable functions, and so
easily implemented within a LispSpecialVar PMC.
Allison
Bob Rogers
Date: Mon, 22 Oct 2007 19:16:37 -0700
Bob Rogers wrote:
> In what seems to have become an autumn tradition in the Parrot
> community, I am about to make my third annual attempt to implement
> Parrot support for what Common Lisp calls "special variable binding."
[...]
How about starting by describing the problem you want to solve in 4
sentences? Laziness is a virtue... also a good way to get stuff done.
Allison
All I am talking about is the equivalent of what "local $var" provides
for Perl 5, i.e. dynamically-scoped binding of scalar "package
variables."
================
From: Allison Randal <all...@perl.org>
Date: Mon, 22 Oct 2007 20:43:47 -0700
If the problem is simply "implement Common Lisp special variables", then
the most likely solution is to create a LispSpecialVar PMC. In the same
way that a MultiSub acts like a sub but internally stores a list of
subs, the LispSpecialVar would act like an ordinary variable to Parrot
internals and to all other languages, but would internally store a stack
of previous dynamic bindings.
How would continuations capture dynamic bindings, then? How would
stack-unwinding know which dynamic bindings to unmake?
-- Bob
Allison Randal
>
> All I am talking about is the equivalent of what "local $var" provides
> for Perl 5, i.e. dynamically-scoped binding of scalar "package
> variables."
Perl 5 locals and Perl 6 temps are quite different than Lisp special
variables. I don't immediately see a way to explain this any more
clearly than I explained it last time.
> If the problem is simply "implement Common Lisp special variables", then
> the most likely solution is to create a LispSpecialVar PMC. In the same
> way that a MultiSub acts like a sub but internally stores a list of
> subs, the LispSpecialVar would act like an ordinary variable to Parrot
> internals and to all other languages, but would internally store a stack
> of previous dynamic bindings.
>
> How would continuations capture dynamic bindings, then?
What information do the continuations need to capture? i.e. what do they
need to restore when invoked?
In general, continuations capture globals, but don't capture the values
of the globals. Invoking a continuation doesn't restore the value of a
global.
> How would
> stack-unwinding know which dynamic bindings to unmake?
A LET has a scope (a beginning and an end), so you generate the binding
code at the beginning and the corresponding unbinding code at the end.
Allison
Bob Rogers
Date: Tue, 23 Oct 2007 23:11:51 -0700
Bob Rogers wrote:
>
> All I am talking about is the equivalent of what "local $var" provides
> for Perl 5, i.e. dynamically-scoped binding of scalar "package
> variables."
Perl 5 locals and Perl 6 temps are quite different than Lisp special
variables. I don't immediately see a way to explain this any more
clearly than I explained it last time.
You did explain it clearly; that's why I said "scalar package variables"
(and didn't mention "temp" except to disavow it). AFAICS, these have
semantics nearly identical [1] to Lisp special variables, and I don't
see anything in last fall's discussion to the contrary.
Much of that discussion was spent curing my ignorance of the
difference between binding and assignment, and how that applies to
"temp", plus other discussion related to localizing/temping registers
and structure members, but I thought I stated clearly that I was not
going to consider such things.
> If the problem is simply "implement Common Lisp special variables", then
> the most likely solution is to create a LispSpecialVar PMC. In the same
> way that a MultiSub acts like a sub but internally stores a list of
> subs, the LispSpecialVar would act like an ordinary variable to Parrot
> internals and to all other languages, but would internally store a stack
> of previous dynamic bindings.
>
> How would continuations capture dynamic bindings, then?
What information do the continuations need to capture? i.e. what do they
need to restore when invoked?
In general, continuations capture globals, but don't capture the values
of the globals. Invoking a continuation doesn't restore the value of a
global.
In a nutshell, a "special" binding changes the dynamic environment, in
the same sort of way that pushing an error handler does -- both are
inherited by subs called in that environment. Exiting from that
environment, by whatever means, must return to the previous environment
at the point where the continuation was taken.
In fact, if Parrot were to provide an implementation of dynamically
scoped global variables in which invoking a continuation did *not* fully
restore them, then I would not be able to use such an implementation.
If I tried to, the nonlocal transfer-of-control features of Lisp
(implemented with continuations) would break [2]. This should not
surprise anyone. (Does it??)
One such nonlocal transfer-of-control feature is "catch/throw". Here
is some Lisp code (albeit somewhat contrived) that illustrates the
matter:
(defun main ()
(format t "*print-base* is ~D.~%" *print-base*)
(let ((*print-base* 16)) ;; Because I want output in hex.
(format t "*print-base* is now ~D.~%" *print-base*)
(catch 'done
(let ((*print-base* 2)) ;; Well, I really want it in binary.
(format t "*print-base* is now ~D.~%" *print-base*)
(dotimes (i 16)
(format t "~S~%" (generate-row i 0))))
(format t "We never get here.~%"))
(format t "*print-base* is still ~D.~%" *print-base*)))
(defun generate-row (i j)
(cond ((> i 5)
;; Gratuitous nonlocal exit.
(throw 'done nil))
((>= j i)
nil)
(t
(let ((*print-base* j))
;; Since nothing is printed in this dynamic scope,
;; the only effect is to create a binding that must
;; be popped when exiting this frame (or throwing
;; through it).
(cons (* i j) (generate-row i (1+ j)))))))
*print-base* is a global variable that controls the output radix in the
obvious way, and it's initial default value is 10 (decimal); all of the
numbers in the source code are decimal. This global is rebound twice in
the "main" function, and once in the generate-row function.
The special "throw" operator transfers control to the innermost
"catch" with a matching tag, unwinding the dynamic environment to the
point of the catch, where "dynamic environment" means the state of all
error handlers and dynamic variable bindings [3].
The output looks like this (where "PARROT" just happens to be the
name of the package I'm in):
PARROT> (main)
*print-base* is 10.
*print-base* is now 16.
*print-base* is now 2.
NIL
(0)
(0 10)
(0 11 110)
(0 100 1000 1100)
(0 101 1010 1111 10100)
*print-base* is still 16.
NIL
PARROT>
On the sixth time through the loop, "throw" has to unwind out of 6 stack
frames (and the *print-base* bindings in 5 of them) to get back to the
"catch", but must unwind only the innermost of the two *print-base*
bindings in "main". As I said above, "catch" and "throw" (along with
the lexically-scoped nonlocal transfer-of-control primitives of Lisp)
are implemented in Kea-CL using continuations; indeed, I don't see how I
could do otherwise. If each dynamic variable binding is stored as an
entry on interp->dynamic_env (as I did in last fall's attempt), then
invoking the continuation automatically restores these bindings to the
right place -- and ditto for exception handlers, which are basically
continuations.
> How would
> stack-unwinding know which dynamic bindings to unmake?
A LET has a scope (a beginning and an end), so you generate the binding
code at the beginning and the corresponding unbinding code at the end.
Allison
That works fine when the LET is exited normally, and such unbinding code
is needed for that case. But what if an error or nonlocal exit causes
the unbinding code to be skipped? How would Parrot figure out which
bindings need attention, and what values to restore?
From re-reviewing our earlier correspondence, I get the impression
that you have a particular implementation in mind, one which doesn't
seem to work for my use case. Perhaps you should describe the use case
for your implementation, and then we can decide whether to combine them.
-- Bob
[1] The differences don't matter at this level of discussion, it just
means I'll need a little extra mechanism for Lisp.
[2] In fact, catch/throw only works now without an implementation of
dynamic variable scoping because I kludge around it with
C<pushaction>, as mentioned on 7-Dec-06 in last fall's thread, and
continuations (now) do the right thing (mostly) with C<pushaction>.
[3] Plus, strictly speaking, a few other things that don't matter in
practical terms, because they are typically implemented using
dynamically bound globals, so they don't require special handling.
(In Kea-CL, even catch & throw are implemented using a dynamically
bound global.)
Allison Randal
>
> From re-reviewing our earlier correspondence, I get the impression
> that you have a particular implementation in mind, one which doesn't
> seem to work for my use case. Perhaps you should describe the use case
> for your implementation, and then we can decide whether to combine them.
I have an implementation in mind for dynamically scoped variables in
general. It's similar to the implementation of lexicals (may even use
the same LexPad structures), but instead of linking along the chain of
lexical scopes outward, it links along the chain of return continuations
backward. This would allow for capture by return continuations, and so
restoration on return invocation. It would also allow for declaring a
dynamic variable in one scope that masks-without-modifying a variable in
a previous dynamic scope (much like inner lexicals).
I'm just trying to get a clear definition of the problem you're solving,
so I can lay solution and problem side-by-side and see if they match. It
may be that I need to just spec and implement dynamically scoped
variables, then let you try using it and see if you need anything more.
Allison
Bob Rogers
Date: Fri, 02 Nov 2007 15:24:40 -0400
Bob Rogers wrote:
> From re-reviewing our earlier correspondence, I get the impression
> that you have a particular implementation in mind, one which doesn't
> seem to work for my use case. Perhaps you should describe the use case
> for your implementation, and then we can decide whether to combine them.
I have an implementation in mind for dynamically scoped variables in
general. It's similar to the implementation of lexicals (may even use
the same LexPad structures), but instead of linking along the chain of
lexical scopes outward, it links along the chain of return continuations
backward. This would allow for capture by return continuations, and so
restoration on return invocation. It would also allow for declaring a
dynamic variable in one scope that masks-without-modifying a variable in
a previous dynamic scope (much like inner lexicals).
At this level of description, and except for the mention of LexPad
structures, that sounds like the basic mechanism I had in mind.
At the time you implied that you would rather see "one data structure
per scope" instead of one per binding; I imagine this was an allusion to
something LexPad-like. But I have trouble visualizing how one of these
per scope can achieve the necessary granularity, given that contexts
won't bind all of their dynamic variables at once. How would
continuations and called contexts figure out which subset of bindings
are in scope?
I'm just trying to get a clear definition of the problem you're solving,
so I can lay solution and problem side-by-side and see if they match. It
may be that I need to just spec and implement dynamically scoped
variables, then let you try using it and see if you need anything more.
Allison
I should be able to tell you that after reading the spec, shouldn't I?
(And if not, why not? ;-)
-- Bob