Dynamically scoped variables (a.k.a parameters, a.k.a. implicit variables) are usually described as being implemented by imperatively mutating global state (for example, see parameter objects).
Here I explore implementing implicit variables with a functional implementation, by adding a hidden parameter to functions and function calls. A demo (slow but sufficient to run tests) can be found on github: github.com/awwx/arc-implicit.
While Arc3.1 doesn’t explicitly expose Racket’s parameters, it does make use of them. For example the standard ports are dynamically scoped. I can say:
(def f1 ()
(prn "f1"))
(def f2 ()
(f1))
(def f3 ()
(tostring (f2)))
and calling (f3) returns the
string "f1\n". tostring redirects the
standard output port to a string during the execution of its body,
and the execution of the functions its body calls.
In a language without exceptions or continuations, I might
implement call-w/stdout by storing the current value of
the standard output port in a global variable such
as *stdout and doing something like:
(def call-w/stdout (port f)
(let orig *stdout
(= *stdout port)
(let rv (f)
(= *stdout orig)
rv)))
When we have exceptions in our language, we also need to restore the
original value of *stdout when an exception is thrown.
(def call-w/stdout (port f)
(let orig *stdout
(after (do (= *stdout port)
(f))
(= *stdout orig))))
An equivalent implementation in a language that has try
... finally such as JavaScript looks like:
function callWithStdout(port, f) {
var orig = gStdout;
try {
gStdout = port;
return f();
} finally {
gStdout = orig;
}
}
With continuations the implementation gets even more complicated
because when a captured continuation is reinvoked we want the
dynamic environment to be restored as well. Arc3.1
doesn’t directly expose Racket’s dynamic-wind, but if
it did our implementation might look like:
(def call-w/stdout (port f)
(let orig *stdout
(dynamic-wind (fn () (= *stdout port))
f
(fn () (= *stdout orig)))))
Real implementations of dynamically scoped variables don’t use a separate global variable for each dynamic variable, of course. Here’s an implementation that uses a single global variable to hold all the dynamic bindings: Parameter Objects (in Scheme and Racket, dynamically scoped variables are called “parameters”).
With make-parameter and parameterize
implemented and stdout a parameter,
call-w/stdout becomes:
(def call-w/stdout (port f)
(parameterize stdout port (f)))
While one of the things I like about Arc is that it doesn’t pedantically try to force me into writing functional code when an imperative style would be more straightforward, implementing dynamic variables a.k.a parameters by setting and resetting a global variable seems a bit ugly to me.
I don’t mind using global variables for things that are actually global but I dislike using global variables for local state.
One of the ideas of Arc is that the implementation can serve as the language spec [Arc Tutorial]. The imperative approach to implementing dynamic scope strikes me as being particularly far from that ideal. I have some sense of how I think dynamic variables work, and I can inspect the implementation to see if it looks like it’s doing what I think it should, but I don’t get the sense that I understand dynamic scope from looking at the implementation.
It gets even worse when we look at how we might
implement dynamic-wind. The usual approach is more
imperatively modified global state. (See for
example
Continuations
in the Chez Scheme manual). To understand how parameters interact
with continuations, we need to look at an imperatively modified
global state implementation of parameters wrapped around an
imperatively modified global state implementation
of dynamic-wind.
I personally like to call dynamically scoped variables “implicit variables”, because it’s as if the variable were being passed implicitly to each called function. For example, if we were to pass “stdout” to every function, my example would then look like:
(def f1 (stdout)
(prn stdout "f1"))
(def f2 (stdout)
(f1 stdout))
(def f3 (stdout)
(tostring (f2 stdout)))
and tostring as a macro could in effect expand into
a let which gave a new binding for stdout:
(def f3 (stdout)
(let stdout (outstring)
(f2 stdout)
(inside stdout)))
In this language, stdout is a simple lexical variable
(which happens to be passed around a lot). There’s no confusion
about how stdout would interact with continuations
here, because it isn’t any different than any other lexical
variable. For example, suppose f1
called foo which might capture a continuation:
(def f1 (stdout)
(foo stdout)
(prn stdout "f1"))
If the function foo did capture a continutation and
that continuation was invoked so that foo returned
again later, what should stdout be
when prn is called again? Just what it is. The
original value of stdout passed to f1
which hasn’t changed.
We don’t need to restore stdout to the value that it
had when the continuation was captured because
however foo might choose to pass stdout to
the function it calls, that doesn’t affect stdout as a
lexical parameter of f1. It still has its original
value.
So then I thought, what if I actually did implement implicit variables (a.k.a parameters, a.k.a. dynamically scoped variables) using a hidden parameter passed to every function?
I could transform every function definition
(fn (a b c) ...)
to have an additional parameter
(fn ($dyn a b c) ...)
and every function call
(foo 1 2 3)
to include the hidden parameter:
(foo $dyn 1 2 3)
My compilation stages can now start with:
L0 ---------------> L1 ------------------> L2
macro expansion implicit expansion
L0 is a dialect of Arc which not only has parameters, continuations, complex function arguments, etc., like Arc3.1 does, but also stores global variables in an Arc table and allows macros to be expanded with values as well as with names.
L1 is a more primitive language. It doesn’t have global variables
(those were implemented by the macro expander) or complex function
parameters (macro expanded) or macros (all expanded by the macro
expander). Functions, conditionals, lexical variable assignments,
and quotation are represented by primitives
$fn, $if, $assign,
and $quote. It does have implicit variables and
continuations.
L2 is an even more primitive language, not having implicit
variables (those got implemented by adding a hidden
$dyn parameter to every function definition and
every function call), but it does still rely on the target runtime
for continuations and tail calls.
From L2 I can go in two directions. Like with my Arc Macro Expander, I could cross-compile to a runtime that didn’t implement Arc yet (but which does have continuations and tail calls). I can also transform L2 back into Arc3.1, which isn’t particularly efficient, but does let me easily run tests to see if the implicit code transformation is working.
L2 -----------> Arc3.1
unprimitive
In the L2 (implicit language) runtime, each builtin function is now
called with the hidden $dyn parameter:
(+ $dyn 3 4)
As Arc globals are stored in an Arc table, it’s easy enough to construct an initial set of globals containing the builtin functions:
(= ir (obj + (fn ($dyn . args) (apply + args))
- (fn ($dyn . args) (apply - args))
...))
(Since error handlers are dynamically scoped, if I wanted to do a complete implementation I’d trap Racket errors and then invoke the error handler found in the dynamic environment. Being lazy and not needing it for the demo I skipped doing that part).
It’s instructive to look at the implementation of ccc
in the implicit runtime. At the user language
level ccc is called with a single
argument, f, and at the implicit runtime implementation
level it also gets passed the hidden $dyn parameter:
(= ir!ccc
(fn ($dyn f)
...))
We need to call the real ccc, which takes a single
parameter, a function which is also called with a single parameter,
the continuation:
(= ir!ccc
(fn ($dyn f)
(ccc (fn (c)
...))))
We then need to call the user function f with the
continuation, and being a user function, f also takes
the hidden $dyn parameter. We only have one dynamic
environment available to give it, so we have no choice but to use
the $dyn we have:
(= ir!ccc
(fn ($dyn f)
(ccc (fn (c)
(f $dyn (fn ...))))))
The user function gets called with a continuation. At the user
language level, the user will call the continuation with a single
argument, the value to return from the captured continuation. Since
that function call will include the hidden $dyn
parameter, the continution function we supply has to have both
parameters:
(= ir!ccc
(fn ($dyn f)
(ccc (fn (c)
(f $dyn (fn ($dyn2 v)
...))))))
Now we have two dynamic environments, the dynamic environment at the
time the continuation was captured ($dyn), and the
dynamic environment at the time the continuation is invoked
($dyn2). Which one is the continuation invoked with?
We don’t actually have a choice here either. The real
continuation c is only called with a single argument
(the value for the continuation to return). There’s no place
for $dyn2 to go.
(= ir!ccc
(fn ($dyn f)
(ccc (fn (c)
(f $dyn (fn ($dyn2 v)
(c v)))))))
So if we implement implicit variables using this hidden parameter approach, we’re inexorably led to invoked continuations having the dynamic environment of the captured continuation, not the dynamic environment of the code calling the continuation.
Which isn’t surprising since it was by design that as a
lexical variable, the hidden $dyn parameter couldn’t be
affected by continuations. But it’s still neat to see it fit
together.
We can check this with a test:
(with (a (parameter)
c1 nil
x 0)
(parameterize a 123
(ccc (fn (c)
(= c1 c)
nil)) ; 1
(test (a) 123)) ; 2
(++ x)
(if (is x 1)
(parameterize a 456 ; 3
(c1 nil)))) ; 4
The test at 2 gets run twice. The first time when ccc
returns at 1, and naturally the value of the
parameter a is 123 as parameterized above.
Later a is parameterized to 456. If c1
were a regular function call, a would have the value of
456 during that execution, but since c1 is a captured
continuation the dynamic environment is also restored, and at
2 a is 123 again.
The test runs the same way in both Arc3.1
(extended with Racket’s implementation of
parameter and parameterize and in the
implicit language implementation of the demo.
A small complication is that in Arc values such as tables, lists and
strings can also be called. If I had written a target runtime, it
would be easy enough to have ar-apply (or its
equivalent) accept the additional hidden parameter. For the demo
running on top of Arc3.1, the quick and easy thing to do
was to have function calls actually expand into a call
to implicit-call... i.e., rather than having (+ 3
4) just expand into (+ $dyn 3 4), instead have
it expand into (implicit-call + $dyn 3
4). implicit-call then handles dropping
the $dyn parameter when calling non-function values.
In a more serious implementation, the extra layer of indirection can
be avoided by having the runtime accept the $dyn
parameter for calls to non-functions.
Another complication is calling macros from the macro expander.
When the macro expander is loaded into L2, it naturally calls macros
with the hidden $dyn because all function calls made at
the L2 level have the extra parameter added. The macro expander
neither knows nor cares whether implicit variables are implemented
with Racket parameters or with $dyn, it just needs to
call the macro function:
(apply (rep m) args)
However since the macro expander is written in Arc, to bootstrap
into running the L2 language we need to first load the macro
expander into Arc3.1 so that we have something running to
cross-compile to L2. In this scenario the macro expander is calling
macros loaded into L2, but is itself running in Arc3.1,
so it needs to explicitly pass the $dyn parameter that
the L2 macro function expect. To do this I add a compilation option
to specify the dynamic environment to pass into the macro:
(apply (rep m) compile!xcompile-dyn args)
The demo implementation can be found on github: github.com/awwx/arc-implicit