Dynamic and Static scoping and recursion

Question

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?

Answer 1

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.

Answer 2

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))
=> #<closure-1>

(funcall F 5)
=> (let ((a 5)) (lambda () a))
=> #<closure-2>

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.