Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 61 ยท Code Generation and Runtimes

Static (Lexical) vs Dynamic Scoping

Compare static (lexical) and dynamic scoping with a runnable interpreter: the same program gives different answers, closures break, and binding costs differ.

Every time a function uses a name that is not its own parameter or local variable, the language has to answer one question: which variable does that name mean? There are two possible answers. With static scoping (also called lexical scoping) the answer depends on where the function is written in the source text. With dynamic scoping it depends on who called the function at run time and which variables that caller had in scope.

Nearly all modern languages are lexically scoped, and the symbol table and static links you have already seen implement it. Dynamic scoping still matters: you meet it in shell scripts, in Lisp's "special variables", in Perl's local, and in patterns like thread-local settings. This lesson builds one small interpreter that can run in either mode, so you can see exactly where the two rules differ.

The same program, two answers

Consider this program, written in a pseudocode that looks like most languages:

TEXT
x = 1

function show():
    return x

function test():
    x = 2          # a new local variable named x
    return show()

print test()

What does it print? Inside show, the name x is not a parameter or a local, so it is a free variable and must be resolved somewhere else.

  • Static scoping looks at the text around show. It is written at the top level, so its free x is the global x, which is 1. The local x inside test is invisible to show, because show is not written inside test. The program prints 1.
  • Dynamic scoping looks at the call chain. show was called by test, and test has a variable x equal to 2, so that one is found first. The program prints 2.
flowchart LR
    subgraph Static["Static: follow the text"]
        S1["show: free x"] --> S2["defined at top level"] --> S3["global x = 1"]
    end
    subgraph Dynamic["Dynamic: follow the calls"]
        D1["show: free x"] --> D2["called by test"] --> D3["test's x = 2"]
    end

Static scoping resolves a free name along the lines of the source. Dynamic scoping resolves it along the call stack.

The big practical difference is when the answer is known. With static scoping the compiler can resolve every name before the program runs and even replace it by an offset or a number of static links. With dynamic scoping the answer can change from one call to the next, so the name must be looked up at run time.

One interpreter, a switch for the rule

The interpreter below evaluates a tiny expression language written as nested tuples. An environment is a chain of dictionaries (one per scope), exactly like the scope chain from the symbols lesson. The entire difference between the two rules is one line: when a function is called, what is the parent of the new environment?

  • Lexical: the environment where the function was defined (stored with the function, which is a closure).
  • Dynamic: the environment of the caller.
Python Run one program under both rules

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output is 1 for lexical and 2 for dynamic, matching the pseudocode. Notice that the function value carries defined_in. That stored environment is the whole mechanism of closures: a lexically scoped function remembers its birthplace. A dynamically scoped function has no use for it.

Where dynamic scoping breaks: returned functions

Dynamic scoping has a notorious weakness, historically called the funarg problem (functional argument problem). A function that is created in one place and called in another does not carry the variables it was written next to.

Here is the classic "make an adder" function. make_adder(n) returns a function that adds n to its argument. Under static scoping the returned function remembers n. Under dynamic scoping, when you call it later, n is no longer anywhere in the call chain.

Python The funarg problem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Lexical scoping prints 15. Dynamic scoping fails with unbound variable 'n': by the time add10(5) runs, the call to make_adder has finished, and its parameter n has disappeared from the call chain. This is exactly why Scheme, ALGOL-family languages and every mainstream language today chose lexical scoping: it makes functions self-contained values that you can store, pass around and return.

Implementing dynamic scoping

If dynamic scoping is so awkward, why implement it? Some uses are natural: a variable like "the current output stream", "the current locale" or "the verbosity level" that you want to change for a whole call tree without passing it as a parameter. The compiler needs a different mechanism from static links. There are two classic ones.

Technique How it works Lookup cost Entering/leaving a binding
Deep binding Keep a stack (an association list) of (name, value) pairs. A lookup searches from the top of the stack. grows with the depth of the stack push and pop one pair
Shallow binding Each name has a single global value cell. A new binding saves the old value and overwrites the cell; leaving restores it. constant: read the cell save and restore

The program below implements both and checks that they agree. It then counts how many pairs deep binding has to inspect for one lookup. In a real language implementation, shallow binding is the usual choice when reads are frequent.

Python Deep binding vs shallow binding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both implementations print the same text: the color and indent set by section are visible in emit, a function it calls, and are restored when section returns. The deep version had to scan past the three junk entries to find color, so its cost depends on how many unrelated bindings sit on top. The shallow version reads one cell every time, but pays when it binds and unbinds.

Who uses which

Language Rule for ordinary variables Notes
C, C++, Java, C#, Go, Rust, Swift static resolved at compile time
Python, JavaScript, Ruby, Lua, Scheme, Haskell static closures capture the defining environment
Common Lisp static, plus dynamic for defvar ("special") variables you choose per variable; special names are written *like-this*
Perl my is static; local is dynamic local saves and restores a global for the dynamic extent of a block
Bash dynamic for local variables a function called from another function sees the caller's locals
Emacs Lisp historically dynamic; static with lexical-binding enabled many older files still rely on the dynamic rule

Even in lexically scoped languages you will find dynamically scoped features built on purpose: thread-local variables, Python's contextvars, an "implicit context" parameter, or an exception handler (the nearest catch up the call stack is found dynamically). The lesson is not that dynamic binding is bad but that it must be explicit, because as a default it makes it hard to reason about a function without knowing all of its callers.

A related but different idea is static type checking versus dynamic typing. Scoping decides which variable a name means. Typing decides which values a variable may hold. A language can be lexically scoped and dynamically typed (Python) or the other way around in principle, so keep the two questions apart.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a statically scoped language, how is a free variable in a function resolved?

    Static (lexical) scoping depends only on the program text, so a compiler can resolve the name before the program runs.
  2. 2. In the interpreter, which single line makes the difference between lexical and dynamic scoping?

    A lexical call chains the new environment to where the function was defined. A dynamic call chains it to the caller's environment.
  3. 3. Why does make_adder(10)(5) fail under dynamic scoping?

    make_adder has already returned, so its binding of n is gone. Only a closure that remembers its defining environment, as in lexical scoping, can still see n.
  4. 4. What is the main advantage of shallow binding over deep binding?

    Shallow binding reads a single cell. The price is paid when a binding starts or ends, because the old value must be saved and restored.
  5. 5. Which of these is a deliberately dynamic feature in an otherwise lexically scoped language?

    Perl's local temporarily replaces a global for the dynamic extent of the block, so called functions see the new value.

Summary

  • Static (lexical) scoping resolves a name from the structure of the source; dynamic scoping resolves it from the chain of callers at run time.
  • The same program can print different results: a free variable in a function sees its defining scope under static rules and the caller's variables under dynamic rules.
  • Closures work because a lexically scoped function stores its defining environment; without that, returned functions lose their variables (the funarg problem).
  • Dynamic scoping is implemented with deep binding (a stack of pairs, slow lookups) or shallow binding (one cell per name, save and restore on entry and exit).
  • Nearly every mainstream language is lexically scoped and offers dynamic behavior only through explicit features such as special variables, local, thread-locals or context objects.

Next: Code Generation Basics