A Functional Implementation of Dynamic Scope

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.

Dynamic Scope in Arc

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 ()

  (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.

Implementing Dynamic Scope

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)

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)
             (= *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))
                    (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.

Hidden Dynamic Parameter

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

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).

Implementing ccc

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.

The Implicit Runtime

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