How to implement dynamic scoping?

Question

How to implement dynamic scoping?

Dynamic scoping is useful for forms of dependency injection, error handling and alternatives to thread local storage.

Some examples of dynamic scoping include React's useContext and Java's proposed scoped values.

The C2 wiki mentions deep binding and shallow binding as common implementation techniques.

Interruptible multithreading seems to place some hard constraints on implementation. In theory cooperative multitasking like in JS could be easier but I can't figure it out.

Dynamic scoping seems strangely awkward to implement despite having in some ways nicer semantics.

Answer 1

Dynamic scoping seems strangely awkward to implement despite having in some ways nicer semantics.

Dynamic scope is arguably easier to implement than lexical scope ─ it means instead of building a tree structure of lexical scopes and searching that, you resolve names at runtime by searching the call stack for a stack frame where the name exists.

The issue is really that no sensible language wants to have only dynamic scope, because lexical scope is much better suited for problem-solving, and people are used to it. (See my related answer here.) So if your choice is between either just lexical scope, or both lexical scope and dynamic scope, then the latter is indeed more work to implement.

Assuming you don't want to use only dynamic scope, then probably you want names to be lexically scoped by default, and so you need some way to allow certain variables to "opt in" to dynamic scoping. A good option is to automatically pass dynamically scoped variables down the call stack when a function which uses one of these variables is called, instead of searching up the call stack when one of these variables is used. This way, there is no change to how names are resolved, instead the only change is in how parameters are passed.

The result is how "implicit" variables in Scala and in my own language Papyri work. Here's an example of a hypothetical syntax which demonstrates this:

def foo(implicit x):
    print("Hello,", x)

def bar():
    implicit x = "Andrew"
    foo()

At the call to foo(), we check whether it has any implicit parameters ─ in this case, x is one. The argument value for x is found by resolving the same name in the caller's scope, and then passed to the function in the same way any other argument would be passed. This could be done either in a compiled or an interpreted language:

• In a statically typed compiled language, the implicit parameters would be known at compile-time, so the call could be desugared into one which passes the arguments explicitly, and there would be no need for anything different to happen at runtime.
• Otherwise, the implicit parameters would be known from foo's signature at runtime, and the resolution of those names would happen at the call-site before foo is invoked.

Note also that in this hypothetical syntax, the variable x in the caller's scope is labelled as implicit when it is declared, i.e. bar has to "consent" to this variable being passed to the function foo. This is a good idea because it means a change to the signature of foo can't result in foo having access to one of bar's local variables which bar didn't intend to expose. However, this is just a safety measure and it's not strictly needed for the feature to work.

Answer 2

Consider the following program that uses a mixture of lexical and dynamic scoping. (Anything following a semicolon is a line comment.)

myTag()
    new x ; x is now in scope
    set x=5
    do printX()
    do tag2()
    do printX()
    quit ; x is now out of scope
printX()
    write !,x ; Even though x is not a parameter, it can be assumed from deeper scopes.
    quit
tag2()
    new x ; This declares a new x variable that shadows the old one.
    set x=3
    do printX()
    quit ; Upon encountering the quit, the new x goes out of scope. The old x is still in scope.

If you call the tag myTag, the program will output these values:

5
3
5

One easy way to implement the scoping rules for this program (especially in an interpreter! is to keep a stack of tables of variables. When you see a variable get new'ed, you add it to the table for the current (topmost) scope. When you call a tag, you can push a new table of variables onto the stack, and when a tag ends, you just have to pop the top of the stack to delete all the variables declared in that scope. Then, to implement the dynamic scoping rules, you just have to walk back through your stack to find the variable. If it was declared in the current scope, then you are done. Otherwise, you just have to keep walking back until you find it. If you don't find it, then it doesn't exist, and you can either issue an error or do something else.