<p>How to implement dynamic scoping?</p>
<p>Dynamic scoping is useful for forms of dependency injection, error handling and alternatives to thread local storage.</p>
<p>Some examples of dynamic scoping include <a href="https://react.dev/reference/react/useContext" rel="noreferrer">React's useContext</a> and <a href="https://openjdk.org/jeps/429" rel="noreferrer">Java's proposed scoped values</a>.</p>
<p>The <a href="https://wiki.c2.com/?DynamicScoping" rel="noreferrer">C2 wiki</a> mentions <a href="https://wiki.c2.com/?DeepBinding" rel="noreferrer">deep binding</a> and <a href="https://wiki.c2.com/?ShallowBinding" rel="noreferrer">shallow binding</a> as common implementation techniques.</p>
<p>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.</p>
<p>Dynamic scoping seems strangely awkward to implement despite having in some ways nicer semantics.</p>

<implementation><optimization><scoping>
How to implement dynamic scoping?
<blockquote>
<p>Dynamic scoping seems strangely awkward to implement despite having in some ways nicer semantics.</p>
</blockquote>
<p>Dynamic scope is arguably <em>easier</em> 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.</p>
<p>The issue is really that no sensible language wants to have <em>only</em> dynamic scope, because lexical scope is much better suited for problem-solving, and people are used to it. (See my related answer <a href="https://languagedesign.stackexchange.com/a/264/89">here</a>.) 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.</p>
<p>Assuming you don't want to use <em>only</em> dynamic scope, then probably you want names to be lexically scoped by default, and so you need some way to allow certain variables to &quot;opt in&quot; to dynamic scoping. A good option is to automatically pass dynamically scoped variables <em>down</em> the call stack when a function which uses one of these variables is called, instead of searching <em>up</em> 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.</p>
<p>The result is how &quot;implicit&quot; variables in <a href="https://docs.scala-lang.org/tour/implicit-parameters.html" rel="noreferrer">Scala</a> and in my own language <a href="https://kaya3.github.io/papyri/" rel="noreferrer">Papyri</a> work. Here's an example of a hypothetical syntax which demonstrates this:</p>
<pre class="lang-py prettyprint-override"><code>def foo(implicit x):
    print(&quot;Hello,&quot;, x)

def bar():
    implicit x = &quot;Andrew&quot;
    foo()
</code></pre>
<p>At the call to <code>foo()</code>, we check whether it has any <code>implicit</code> parameters ─ in this case, <code>x</code> is one. The argument value for <code>x</code> 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:</p>
<ul>
<li>In a statically typed compiled language, the <code>implicit</code> parameters would be known at compile-time, so the call could be <a href="https://en.wikipedia.org/wiki/Syntactic_sugar" rel="noreferrer">desugared</a> into one which passes the arguments explicitly, and there would be no need for anything different to happen at runtime.</li>
<li>Otherwise, the <code>implicit</code> parameters would be known from <code>foo</code>'s signature at runtime, and the resolution of those names would happen at the call-site before <code>foo</code> is invoked.</li>
</ul>
<p>Note also that in this hypothetical syntax, the variable <code>x</code> in the caller's scope is labelled as <code>implicit</code> when it is declared, i.e. <code>bar</code> has to &quot;consent&quot; to this variable being passed to the function <code>foo</code>. This is a good idea because it means a change to the signature of <code>foo</code> can't result in <code>foo</code> having access to one of <code>bar</code>'s local variables which <code>bar</code> didn't intend to expose. However, this is just a safety measure and it's not strictly needed for the feature to work.</p>

CC BY-SA 4.0
2023-05-19T03:18:38.223Z
2023-05-19T06:43:52.217Z
2023-05-19T06:43:52.217Z
kaya3
CC BY-SA 4.0
2023-05-24T00:46:08.153Z
I guess I should clarify main awkwardness with dynamic scope is implementing it fast. Maybe you could do something with a JIT like with GraalVM or rpython? It's simpler if you can implement it slowly definitely.
Ms. Molly Stewart-Gallus
CC BY-SA 4.0
2023-07-07T22:52:57.310Z
I'm pretty sure it inherently needs to happen at runtime, unless you're willing to specialize the function code for each caller. So it will definitely incur runtime overhead.
Karl Knechtel
CC BY-SA 4.0
2023-07-08T09:39:05.460Z
Generally speaking, it cannot be fast, because you cannot optimize out the runtime part unless you add regions where dynamic scoping is not allowed at all. Essentially dual to sealed classes in OOP dynamic dispatch.
feldentm
<p>Consider the following program that uses a mixture of lexical and dynamic scoping. (Anything following a semicolon is a line comment.)</p>
<pre><code>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.
</code></pre>
<p>If you call the tag <code>myTag</code>, the program will output these values:</p>
<pre><code>5
3
5
</code></pre>
<p>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.</p>

CC BY-SA 4.0
2023-05-19T01:47:24.403Z
2023-05-19T01:47:24.403Z
Isaiah
# How to implement dynamic scoping?
Posted by: username_0 on 2023-05-19
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](https://react.dev/reference/react/useContext) and [Java's proposed scoped values](https://openjdk.org/jeps/429).

The [C2 wiki](https://wiki.c2.com/?DynamicScoping) mentions [deep binding](https://wiki.c2.com/?DeepBinding) and [shallow binding](https://wiki.c2.com/?ShallowBinding) 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.
**Tags:** implementation optimization scoping
---
## 2 answers
### Answer by username_1 on 2023-05-19. Score: 6
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.
> **Comments:**
> **username_0** (2023-05-24): I guess I should clarify main awkwardness with dynamic scope is implementing it fast. Maybe you could do something with a JIT like with GraalVM or rpython? It's simpler if you can implement it slowly definitely.  
> **username_2** (2023-07-07): I'm pretty sure it inherently needs to happen at runtime, unless you're willing to specialize the function code for each caller. So it will definitely incur runtime overhead.  
> **username_3** (2023-07-08): Generally speaking, it cannot be fast, because you cannot optimize out the runtime part unless you add regions where dynamic scoping is not allowed at all. Essentially dual to sealed classes in OOP dynamic dispatch.  
---
### Answer by username_4 on 2023-05-19. Score: 4
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.
---
