<p>So I learned the concept of lexical and dynamic scoping in programming languages. But I am not quite sure about the behaviour of these concepts in recursion(or even not recursion, but two different functions shadowing global variable).</p>
<p>If we consider some example pseudocode program below:</p>
<pre><code>int b = 1;

int rec (int a) {
  print b;
  if (a&lt;1) return 0;
  b = 2;
  print b;
  rec (a-1);
}

rec(1);
</code></pre>
<p>When the inner scope in recursion executes <code>print b</code>, will it refer to the outer recursion function's outer scope or global variable? (For both lexical and dynamic) It is quite hard to come up with an example, that fully shows my question, but I hope you can help me build a mental model of how scoping works. Or is the thing I am concerned about completely implementation-specific (putting aside the fact that I am using a local variable before its assignment)?</p>
<p>Did I even correctly understand the concept of scoping? Is it defined on parsing or on the execution of the program?</p>

<scoping><recursion>
Dynamic and Static scoping and recursion
CC BY-SA 4.0
2023-07-30T10:22:29.397Z
If you mean for the function to declare its own variable named `b`, this would be clearer if you wrote `int b = 2;`. Otherwise the assignment `b = 2` looks like it is intended to modify the global variable.
kaya3
CC BY-SA 4.0
2023-07-30T16:39:37.250Z
The second programming language I designed (a DSL for writing image filters) used dynamic scoping.  It was interesting to play with, but I don't think it's a good idea for a general purpose language.
occipita
CC BY-SA 4.0
2023-07-31T13:39:22.537Z
@kaya3-supportthestrike the question is exactly about what happens when `b` *isn't* local - i.e. what "lexical scoping" and "dynamic scoping" imply for how non-local scope is resolved; equivalently, what "enclosing scope" means in those cases. At least, that's how I understood it.
Karl Knechtel
CC BY-SA 4.0
2023-07-31T14:30:45.207Z
@KarlKnechtel If there is only one variable named `b` then the question of which variable the name `b` resolves to is trivial, and doesn't depend on the scoping rules (unless `b` is used out of scope, but that's not the case here for either lexical or dynamic scope).
kaya3
<h3>Scope and extent</h3>
<p>In Lisp there is both lexical and dynamic scoping, and the language relies on two concepts to explain bindings:</p>
<ul>
<li><p><em>scope</em> which is related to <em>space</em></p>
<p>Where can you refer to this binding?</p>
</li>
<li><p><em>extent</em> which is related to <em>time</em></p>
<p>How long does this binding hold?</p>
</li>
</ul>
<h3>Lexical scope</h3>
<p>For example, the following is a let-over-lambda that creates a closure:</p>
<pre><code>(let ((a 5))
  (lambda (b)
    (+ a b)))
</code></pre>
<p>Both <code>a</code> and <code>b</code> are <em>lexically</em> scoped, meaning that you can refer to <code>a</code> only under the body of the <code>let</code>, and you can refer to <code>b</code> only inside the <code>lambda</code>.</p>
<p>If you store the resulting closure in memory, you can call it whenever you want: the <em>extent</em> is <em>indefinite</em>. Everytime you call the closure, the binding for <code>a</code> will refer to the variable introduced by the lexically surrounding <code>let</code>.</p>
<p>Consider this expression, let's name it <code>F</code>:</p>
<pre><code>(lambda (a) (lambda () a))
</code></pre>
<p>Here it is a function that accepts an <code>a</code>, and builds a closure that constantly returns <code>a</code>. If you call it twice with different bindings, you produce two different closures, as-if you did the following:</p>
<pre><code>(funcall F 3)
=&gt; (let ((a 3)) (lambda () a))
=&gt; #&lt;closure-1&gt;

(funcall F 5)
=&gt; (let ((a 5)) (lambda () a))
=&gt; #&lt;closure-2&gt;
</code></pre>
<p>In each case <code>a</code> lexically refers to a binding visible in the surrounding code, but with different values.</p>
<h3>Dynamic scope</h3>
<p>&quot;Dynamic variables&quot; (<em>special variables</em> in Lisp) however have:</p>
<ul>
<li>an <em>indefinite scope</em>, because you can refer to the variables from anywhere in the code</li>
<li><em>dynamic extent</em>: you can access the binding only while it is being defined; the binding is established while entering a block, and undone when exiting it.</li>
</ul>
<p>For example, in Lisp special variables are written with <em>asterisks</em> around them (so-called &quot;earmuffs&quot;), like <code>*standard-output*</code> which is the current output stream.</p>
<p>When you call:</p>
<pre><code>(write &quot;abc&quot;)
</code></pre>
<p>There is an optional parameter, the stream, which is bound by default to <code>*standard-output*</code>, so this is as-if you wrote:</p>
<pre><code>(write &quot;abc&quot; *standard-output*)
</code></pre>
<p>If you want to temporarily redirect the standard output, you can rebind it:</p>
<pre><code>(let ((*standard-output* ...))
  (write &quot;abc&quot;))
</code></pre>
<p>Here, the <code>...</code> is some other stream, for example a network socket or something else. While the binding is active, the standard output is redirected. When the <code>let</code> exits, the variable reverts to its previous value. That's why the extent is dynamic. Notably:</p>
<pre><code>(let ((*standard-output* ...))
  (lambda ()
    (write &quot;abc&quot;)))
</code></pre>
<p>In the above example, the binding is only available while the <code>let</code> body is being evaluated, but the closure that is eventually returned won't capture this binding. Later, if you call the closure, it will print using the binding for <code>*standard-output*</code> that is available during the call, not at closure creation time.</p>
<p>The scope is indefinite because the variable is accessible from everywhere, even if there is no apparent binding (there is a global scope for special variables).</p>
<h3>Recursion</h3>
<p>There is no special case for recursion: a new binding shadows an existing one, which is true for both lexical and dynamic scoping. When you invoke a function recursively, the call is executed inside the existing extent of the caller, so you have access to dynamic bindings and can temporarily shadow them. Let's define a special variable named <code>*depth*</code>:</p>
<pre><code>(defvar *depth* 0)
</code></pre>
<p>You can use it to detect when some recursion is going too deep; each rebinding is only visible at its level an below, the variable is never modified, only rebound to another value.</p>
<pre><code>(defun visit (tree)
  (let ((*depth* (+ 1 *depth*)))
    (when (&gt; *depth* 10)
      (error &quot;Too deep&quot;))
    (when (consp tree)
      (visit (car tree))
      (visit (cdr tree)))))
</code></pre>
<p>The alternative is to change the signature of <code>visit</code> to have <code>depth</code> as an additional parameter, in which case you only need lexical scoping, each function call has a different binding for the variable in a given invocation of the function:</p>
<pre><code>(defun visit (tree &amp;optional (depth 0))
  (when (consp tree)
    (visit (car tree) (+ 1 depth))
    (visit (cdr tree) (+ 1 depth))))
</code></pre>
<p>Note that if, however, you assign the binding to a different value, then you can have side-effects. For the special variable <code>*depth*</code>, if you increment it using <code>(setq *depth* (1+ *depth*))</code> then you will modifiy the nearest binding by side-effects.</p>
<p>For dynamic scoping, the outermost binding is the <em>global scope</em>, that's the level at which your <code>b</code> variable is introduced: it is a global variable, that is modified with <code>b = 2</code> inside the function. In that case, you can try to look at the sequence of events from a global point of view:</p>
<ul>
<li><code>b</code> is assigned 1</li>
<li><code>rec</code> is called with <code>a == 1</code></li>
<li>then global variable <code>b</code> is assigned 2</li>
<li>the recursive call enters <code>rec</code> with <code>a == 0</code></li>
<li>trying to access <code>b</code> here means you are reading the current value of <code>b</code> in the global scope, which is 2.</li>
</ul>
<p>Note that: if your <code>b = 2</code> was a <em>binding</em>, and not an <em>assignment</em>, for exemple if you declared: <code>let b == 2 in ...</code> or something that syntactically is different from an assignment, then the situation would be the same: inside the recursive call to <code>rec</code>, the binding is still in effect until the code returns from the block that introduced the binding in the caller.</p>
<h3>Conclusion</h3>
<p>I hope this clarifies things, dynamic scope is about havine a push/pop behavior at runtime, when the code is being executed. Lexical scope is static and is directly given by how the code is written, before executing it.</p>

CC BY-SA 4.0
2023-07-30T22:02:18.917Z
2023-07-31T17:38:13.363Z
2023-07-31T17:38:13.363Z
coredump
<p>I'll assume that <code>b = 2;</code> is meant to be a declaration of a new variable, rather than an assignment to an existing one (because otherwise this is trivial). Let's try a different pseudocode program to illustrate, using two different functions instead of self-recursion:</p>
<pre class="lang-none prettyprint-override"><code>let b = 0
let c = 1
def f:
    let b = c + 1
    print(b)
    g()
def g:
    let c = b + 1
    print(c)
    f()
f()
</code></pre>
<p>In a <em>lexically-scoped</em> model, when <code>f</code> refers to <code>c</code> it can only be the global (or nothing — some languages don't have implicit access to global scopes). Any variable name can only refer to the nearest one &quot;outside&quot; the current scope. In <code>g</code>, <code>b</code> can only be the global, so <code>b+1</code> is always 1. This program would print 2 from <code>f</code> and 1 from <code>g</code>, alternating over and over: 2 1 2 1 2 ...</p>
<p>We would look at the scope of <code>f</code> as &quot;nested&quot; inside the global scope. Whenever <code>f</code> refers to a variable, it's the one inside the nearest surrounding scope with the right name. This is <strong>determined statically, when the code is written</strong>.</p>
<p>In a <em>dynamically-scoped</em> model, when <code>f</code> refers to <code>c</code> it means the most recently-seen thing named <code>c</code> that existed inside a function that called <code>f</code>, or called something else that then called <code>f</code> (the nearest one in the call stack). So:</p>
<ul>
<li>For the first <code>f()</code> call, the most recent <code>c</code> is the one in the global scope with value 1, so it will set its own <code>b</code> to 2, and print it out.</li>
<li>It then runs <code>g()</code>, and when <code>g</code> talks about <code>b</code> it will find the <code>b</code> from that execution of the <code>f</code> function. <code>c</code> will be set to 3, and printed out.</li>
<li>We then call <code>f()</code> again from inside <code>g</code>. This time, when it says <code>c</code>, it will be taken as referring to <em>the <code>c</code> that was just inside <code>g</code></em>. <code>b</code> will be set to 4, and printed out. <strong>It's a different <code>c</code> than the first time, defined in a different place!</strong></li>
<li>We call <code>g()</code> again, then <code>f()</code>, each time printing out the next number: <code>b</code> and <code>c</code> identify different variables in each invocation of the function. This program would print out 2 3 4 5 6 7 ...</li>
</ul>
<p>Under <strong>dynamic scoping</strong>, we always find the nearest definition in the run-time call stack. This is <strong>determined at run time, by what other functions are in the chain that called this one</strong> — and it can be different for different invocations that reached the function via different routes.</p>
<hr />
<p>In a self-recursive case, with lexical scoping each function has its own independent copy of any local variables, and has the same surrounding scope — here, the global one. With dynamic scoping, each instance of the function will have access to the variables from the caller, but since it presumably creates new variables of the same name itself it <em>probably</em> can't see them — but this is a language design choice.</p>
<p>Your pseudocode could mean several different things, depending not only on whether it has lexical or dynamic scoping but on language-defined rules about which names are visible, when variable declarations take effect, and whether you can shadow variables you're already using. These are all implementation-dependent, and mostly not directly related to the lexical/dynamic scoping issue.</p>
<hr />
<p><strong>Dynamic scoping is quite uncommon in real languages</strong>. Having a variable name refer to something different every time gets confusing, and it's possible to &quot;poison&quot; the execution by inadvertently introducing a new variable inside a caller that wasn't expected. Similarly, any function that you call has access to <em>all</em> your state, potentially including the ability to mutate it - there's no protection from other code you run. The most likely place for you to encounter dynamic scoping by default currently is probably Unix shell languages, where it's a common cause of problems, but can't be changed without breaking backwards compatibility.</p>
<p>A more interesting bit of lexical scoping is nested scopes. Many languages create a lot of scopes, not just for function bodies but for the bodies of loops and conditionals, for functions defined inside other functions, for classes and their methods, and so on. With lexical scoping, each of these has its own set of variables, which nobody else can ever access. Often, this lets you have multiple things with the same name inside &quot;sibling&quot; scopes, all independent from each other, and sometimes it lets you &quot;shadow&quot; names defined in surrounding scopes with a new definition for just an interior scope. Many languages have some places where lexical lookup stops, or stops by default: they don't allow implicit access to &quot;global&quot; variables, or require any variable from outside to be imported explicitly. These are choices made by individual languages.</p>
<p>Most contemporary real-world languages with a concept of scope use lexical scoping. A few have limited dynamic scoping as well that code can opt into, bringing in a specific variable or a variable of a specific type from the caller. Two popular languages with this sort of feature include Scala and Perl, and some Lisp versions.</p>

CC BY-SA 4.0
2023-07-30T10:11:18.583Z
2023-07-30T20:50:07.343Z
2023-07-30T20:50:07.343Z
Michael Homer
CC BY-SA 4.0
2023-07-31T19:22:52.820Z
The most harmful and obscure issue with dynamic scoping is that combined with function pointers or references, it can happen that a variable is not accessible at all. Because the function execution escaped the statically enclosing variable.
feldentm
# Dynamic and Static scoping and recursion
Posted by: username_0 on 2023-07-30
So I learned the concept of lexical and dynamic scoping in programming languages. But I am not quite sure about the behaviour of these concepts in recursion(or even not recursion, but two different functions shadowing global variable).
If we consider some example pseudocode program below:
int b = 1;

int rec (int a) {
  print b;
  if (a<1) return 0;
  b = 2;
  print b;
  rec (a-1);
}

rec(1);

When the inner scope in recursion executes print b, will it refer to the outer recursion function's outer scope or global variable? (For both lexical and dynamic) It is quite hard to come up with an example, that fully shows my question, but I hope you can help me build a mental model of how scoping works. Or is the thing I am concerned about completely implementation-specific (putting aside the fact that I am using a local variable before its assignment)?
Did I even correctly understand the concept of scoping? Is it defined on parsing or on the execution of the program?
**Tags:** scoping recursion
> **Comments:**
> **username_1**: If you mean for the function to declare its own variable named `b`, this would be clearer if you wrote `int b = 2;`. Otherwise the assignment `b = 2` looks like it is intended to modify the global variable.  
> **username_2**: The second programming language I designed (a DSL for writing image filters) used dynamic scoping.  It was interesting to play with, but I don't think it's a good idea for a general purpose language.  
> **username_3**: @kaya3-supportthestrike the question is exactly about what happens when `b` *isn't* local - i.e. what "lexical scoping" and "dynamic scoping" imply for how non-local scope is resolved; equivalently, what "enclosing scope" means in those cases. At least, that's how I understood it.  
> **username_1**: @KarlKnechtel If there is only one variable named `b` then the question of which variable the name `b` resolves to is trivial, and doesn't depend on the scoping rules (unless `b` is used out of scope, but that's not the case here for either lexical or dynamic scope).  
---
## 2 answers
### Answer by username_5 on 2023-07-30. Score: 13 | Accepted answer
I'll assume that b = 2; is meant to be a declaration of a new variable, rather than an assignment to an existing one (because otherwise this is trivial). Let's try a different pseudocode program to illustrate, using two different functions instead of self-recursion:
let b = 0
let c = 1
def f:
    let b = c + 1
    print(b)
    g()
def g:
    let c = b + 1
    print(c)
    f()
f()

In a lexically-scoped model, when f refers to c it can only be the global (or nothing — some languages don't have implicit access to global scopes). Any variable name can only refer to the nearest one "outside" the current scope. In g, b can only be the global, so b+1 is always 1. This program would print 2 from f and 1 from g, alternating over and over: 2 1 2 1 2 ...
We would look at the scope of f as "nested" inside the global scope. Whenever f refers to a variable, it's the one inside the nearest surrounding scope with the right name. This is determined statically, when the code is written.
In a dynamically-scoped model, when f refers to c it means the most recently-seen thing named c that existed inside a function that called f, or called something else that then called f (the nearest one in the call stack). So:

For the first f() call, the most recent c is the one in the global scope with value 1, so it will set its own b to 2, and print it out.
It then runs g(), and when g talks about b it will find the b from that execution of the f function. c will be set to 3, and printed out.
We then call f() again from inside g. This time, when it says c, it will be taken as referring to the c that was just inside g. b will be set to 4, and printed out. It's a different c than the first time, defined in a different place!
We call g() again, then f(), each time printing out the next number: b and c identify different variables in each invocation of the function. This program would print out 2 3 4 5 6 7 ...

Under dynamic scoping, we always find the nearest definition in the run-time call stack. This is determined at run time, by what other functions are in the chain that called this one — and it can be different for different invocations that reached the function via different routes.

In a self-recursive case, with lexical scoping each function has its own independent copy of any local variables, and has the same surrounding scope — here, the global one. With dynamic scoping, each instance of the function will have access to the variables from the caller, but since it presumably creates new variables of the same name itself it probably can't see them — but this is a language design choice.
Your pseudocode could mean several different things, depending not only on whether it has lexical or dynamic scoping but on language-defined rules about which names are visible, when variable declarations take effect, and whether you can shadow variables you're already using. These are all implementation-dependent, and mostly not directly related to the lexical/dynamic scoping issue.

Dynamic scoping is quite uncommon in real languages. Having a variable name refer to something different every time gets confusing, and it's possible to "poison" the execution by inadvertently introducing a new variable inside a caller that wasn't expected. Similarly, any function that you call has access to all your state, potentially including the ability to mutate it - there's no protection from other code you run. The most likely place for you to encounter dynamic scoping by default currently is probably Unix shell languages, where it's a common cause of problems, but can't be changed without breaking backwards compatibility.
A more interesting bit of lexical scoping is nested scopes. Many languages create a lot of scopes, not just for function bodies but for the bodies of loops and conditionals, for functions defined inside other functions, for classes and their methods, and so on. With lexical scoping, each of these has its own set of variables, which nobody else can ever access. Often, this lets you have multiple things with the same name inside "sibling" scopes, all independent from each other, and sometimes it lets you "shadow" names defined in surrounding scopes with a new definition for just an interior scope. Many languages have some places where lexical lookup stops, or stops by default: they don't allow implicit access to "global" variables, or require any variable from outside to be imported explicitly. These are choices made by individual languages.
Most contemporary real-world languages with a concept of scope use lexical scoping. A few have limited dynamic scoping as well that code can opt into, bringing in a specific variable or a variable of a specific type from the caller. Two popular languages with this sort of feature include Scala and Perl, and some Lisp versions.
> **Comments:**
> **username_6** (2023-07-31): The most harmful and obscure issue with dynamic scoping is that combined with function pointers or references, it can happen that a variable is not accessible at all. Because the function execution escaped the statically enclosing variable.  
---
### Answer by username_4 on 2023-07-30. Score: 6
Scope and extent
In Lisp there is both lexical and dynamic scoping, and the language relies on two concepts to explain bindings:

scope which is related to space
Where can you refer to this binding?

extent which is related to time
How long does this binding hold?


Lexical scope
For example, the following is a let-over-lambda that creates a closure:
(let ((a 5))
  (lambda (b)
    (+ a b)))

Both a and b are lexically scoped, meaning that you can refer to a only under the body of the let, and you can refer to b only inside the lambda.
If you store the resulting closure in memory, you can call it whenever you want: the extent is indefinite. Everytime you call the closure, the binding for a will refer to the variable introduced by the lexically surrounding let.
Consider this expression, let's name it F:
(lambda (a) (lambda () a))

Here it is a function that accepts an a, and builds a closure that constantly returns a. If you call it twice with different bindings, you produce two different closures, as-if you did the following:
(funcall F 3)
=> (let ((a 3)) (lambda () a))
=> #

(funcall F 5)
=> (let ((a 5)) (lambda () a))
=> #

In each case a lexically refers to a binding visible in the surrounding code, but with different values.
Dynamic scope
"Dynamic variables" (special variables in Lisp) however have:

an indefinite scope, because you can refer to the variables from anywhere in the code
dynamic extent: you can access the binding only while it is being defined; the binding is established while entering a block, and undone when exiting it.

For example, in Lisp special variables are written with asterisks around them (so-called "earmuffs"), like *standard-output* which is the current output stream.
When you call:
(write "abc")

There is an optional parameter, the stream, which is bound by default to *standard-output*, so this is as-if you wrote:
(write "abc" *standard-output*)

If you want to temporarily redirect the standard output, you can rebind it:
(let ((*standard-output* ...))
  (write "abc"))

Here, the ... is some other stream, for example a network socket or something else. While the binding is active, the standard output is redirected. When the let exits, the variable reverts to its previous value. That's why the extent is dynamic. Notably:
(let ((*standard-output* ...))
  (lambda ()
    (write "abc")))

In the above example, the binding is only available while the let body is being evaluated, but the closure that is eventually returned won't capture this binding. Later, if you call the closure, it will print using the binding for *standard-output* that is available during the call, not at closure creation time.
The scope is indefinite because the variable is accessible from everywhere, even if there is no apparent binding (there is a global scope for special variables).
Recursion
There is no special case for recursion: a new binding shadows an existing one, which is true for both lexical and dynamic scoping. When you invoke a function recursively, the call is executed inside the existing extent of the caller, so you have access to dynamic bindings and can temporarily shadow them. Let's define a special variable named *depth*:
(defvar *depth* 0)

You can use it to detect when some recursion is going too deep; each rebinding is only visible at its level an below, the variable is never modified, only rebound to another value.
(defun visit (tree)
  (let ((*depth* (+ 1 *depth*)))
    (when (> *depth* 10)
      (error "Too deep"))
    (when (consp tree)
      (visit (car tree))
      (visit (cdr tree)))))

The alternative is to change the signature of visit to have depth as an additional parameter, in which case you only need lexical scoping, each function call has a different binding for the variable in a given invocation of the function:
(defun visit (tree &optional (depth 0))
  (when (consp tree)
    (visit (car tree) (+ 1 depth))
    (visit (cdr tree) (+ 1 depth))))

Note that if, however, you assign the binding to a different value, then you can have side-effects. For the special variable *depth*, if you increment it using (setq *depth* (1+ *depth*)) then you will modifiy the nearest binding by side-effects.
For dynamic scoping, the outermost binding is the global scope, that's the level at which your b variable is introduced: it is a global variable, that is modified with b = 2 inside the function. In that case, you can try to look at the sequence of events from a global point of view:

b is assigned 1
rec is called with a == 1
then global variable b is assigned 2
the recursive call enters rec with a == 0
trying to access b here means you are reading the current value of b in the global scope, which is 2.

Note that: if your b = 2 was a binding, and not an assignment, for exemple if you declared: let b == 2 in ... or something that syntactically is different from an assignment, then the situation would be the same: inside the recursive call to rec, the binding is still in effect until the code returns from the block that introduced the binding in the caller.
Conclusion
I hope this clarifies things, dynamic scope is about havine a push/pop behavior at runtime, when the code is being executed. Lexical scope is static and is directly given by how the code is written, before executing it.
---
