Static vs. Dynamic Scope

Evaluating function calls ran this program and printed 40:

let scale = 10;

fn scaled(x: Int) -> Int = x * scale;

fn main() {
    let scale = 2;
    println(scaled(4));               // 40
}

scale is free in the body of scaled: nothing inside the function binds it. Two bindings of scale exist when the call happens. One is at the top of the program, where scaled was written, and holds 10. The other is in main, where scaled is called, and holds 2. Bridger’s rule for application runs the body in the environment the closure captured, so scale is 10. A language that ran the body in the caller’s environment instead would print 8.

A second program makes the difference sharper. twice applies a function to an argument two times, and add_x is a lambda whose body reads a name x from the block around it:

fn twice(f: fn(Int) -> Int, x: Int) -> Int = f(f(x));

fn main() {
    let x = 1;
    let add_x = |y: Int| y + x;
    println(twice(add_x, 10));        // 12
}

Bridger prints 12: add_x adds 1 each time it is called. Run add_x’s body in its caller’s environment and its caller is twice, whose parameter happens to be named x too. There x is 10, add_x(10) is 20, add_x(20) is 30, and the program prints 30. Rename twice’s parameter to n and the same rule prints 12 again.

The two programs raise these questions:

• Where does a free name in a function body get its value? From the environment where the function was written, or from the one where it is called?
• Is the answer a fact about the program text? If the caller’s environment decides, can anyone reading add_x say what it computes?
• What does each answer cost? What does it make easy, what does it break, and what does it do to a language that checks types before running?

The first implementation of Lisp gave the second answer to the first question, and its authors found out what that answer cost from a bug report.

Lisp’s free variables

McCarthy’s eval kept the environment as an association list, the a-list: a list of name/value pairs, handed to each evaluation and searched from the front when a variable was read. Applying a function paired its parameters with its arguments and put the pairs on the front of the a-list in hand, then evaluated the body with the longer list. A function passed as an argument was its λ-expression, a piece of list structure like any other, and when it was applied the a-list in hand was the one at the point of the call. Its free variables were looked up there.

In his “History of Lisp” (1979), McCarthy recalls the program that exposed this. James Slagle wrote a recursive search function that took, as one of its arguments, a function to call if the search failed, and in the recursive case passed a new λ-expression that mentioned the current call’s x. When that λ-expression ran, it was inside a deeper recursive call, and its x found the deeper call’s binding:

The difficulty was that when an inner recursion occurred, the value of car[x] wanted was the outer value, but the inner value was actually used. In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained.

I must confess that I regarded this difficulty as just a bug and expressed confidence that Steve Russell would soon fix it. He did fix it but by inventing the so-called FUNARG device that took the lexical environment along with the functional argument.

It is the twice program’s failure: a function finds a binding of the right name made by the wrong call. Russell’s repair was to make a functional argument carry its environment, a pair of the λ-expression and the a-list in force where it was written, which is a closure under another name. McCarthy adds that the problem “later showed up in Algol 60”, and that while the FUNARG device “worked well in the interpreter, comprehensiveness and speed seem to be opposed in compiled code, and this led to a succession of compromises.”

The repair did not change Lisp’s default. In the LISP 1.5 Programmer’s Manual, a programmer who wanted the environment kept wrote FUNCTION around the λ-expression, and the interpreter built a FUNARG from it; written plainly, under QUOTE, it was a bare λ-expression as before. The manual (§3.1) says when the difference does not matter: “QUOTE will work instead of FUNCTION, provided that there are no free variables present.” The compiler, described in the same manual, made a third arrangement. An ordinary variable of a compiled function got a storage location on the stack that “other functions cannot find”, so no other function could use it as a free variable at all; a variable meant to be read freely had to be declared SPECIAL, and “SPECIAL variables cannot be communicated between the interpreter and compiled functions.”

Joel Moses’s MIT memo “The Function of FUNCTION in LISP” (1970) set out the general problem. “An important point which must be realized about functional arguments (abbreviated FUNARGs) is that two different environments are involved in such cases”: the one where the function was made, which he calls the binding environment, and the one where it is applied, the activation environment. He treats a function passed down to another function as the easy case and a function returned as a value as the hard one, and the memo’s subtitle — Why the FUNARG Problem Should be Called the Environment Problem — gives his reason in a footnote: “One should also handle returns of functions”.

Two rules for a call

Bridger’s rule for application, E-App, evaluates the operator to a closure $⟨\lambda \vec{x}.e_b,{\rho }^{\prime }⟩$ and runs the body $e_b$ in ${\rho }^{\prime }[\vec{x}\mapsto \vec{v}]$: the captured environment, extended with the parameters. The caller’s environment $\rho$ is used to evaluate the operator and the arguments, and then set aside. Dynamic scope changes the third premise and nothing else:

$$\frac{\begin{array}{c}\rho ⊢⟨e_0,{\sigma }_0⟩\Downarrow ⟨\lambda \vec{x}.e_b,{\sigma }_0^{\prime }⟩\\ \rho ⊢⟨e_i,{\sigma }_{i-1}^{\prime }⟩\Downarrow ⟨v_i,{\sigma }_i^{\prime }⟩(1\le i\le n)\\ \rho [\vec{x}\mapsto \vec{v}]⊢⟨e_b,{\sigma }_n^{\prime }⟩\Downarrow ⟨r,{\sigma }^{\prime }⟩\end{array}}{\rho ⊢⟨e_0(e_1,\dots ,e_n),{\sigma }_0⟩\Downarrow ⟨\mathsf{Val}(\mathrm{unwrap}r),{\sigma }^{\prime }⟩}(\text{E-App-Dyn})$$

The body runs in $\rho [\vec{x}\mapsto \vec{v}]$, the environment of the call site with the parameters added. The operator’s value is a bare lambda, $\lambda \vec{x}.e_b$, with no environment beside it, because the rule would have no use for one. Under this rule E-Lam need not capture anything, and a function value is just its code. Landin’s remark that a closure’s environment part “would be unnecessary if λ-expressions containing free variables were prohibited” (closures) has a second case: the environment part is also unnecessary if free variables are looked up where the function is called.

Lexical scope described the alternative as resolving a free name “in the environment present where the code runs”. E-App-Dyn says exactly which environment that is. Each call extends its caller’s environment, which extends its own caller’s, back to main, so the environment a body runs in is a record of the calls that are in progress: the chain of active calls, each adding its parameters and its lets. A free name in a body finds the most recent binding of that name made by any call that has not yet returned.

Scope as a span of time

Under static scope, a binding’s scope is a region of text, as Part III defined it. Under dynamic scope, a binding made by let scale = 2 in main can be read by the body of scaled, which is nowhere inside main’s text, and by any other function that runs while main’s block is active and mentions scale. Where it can be read is no longer a region of text. When it can be read is fixed: from the let until the block that holds it ends. That is the dynamic extent that closures described, and a dynamically scoped binding is visible to any code, written anywhere, that runs during it. Common Lisp the Language builds the name from those two parts — “it is convenient to define dynamic scope to mean indefinite scope and dynamic extent” — and adds: “The term “dynamic scope” is a misnomer. Nevertheless it is both traditional and useful.“

The examples above show what follows from that.

A body’s meaning depends on its callers. Under E-App-Dyn, scaled multiplies by 2 when called from main, and by 10 when called from a function that binds no scale of its own, where the lookup reaches the top-level binding. Without the top-level binding, that second call gets stuck. Nothing in the text of scaled says which. Its behaviour is a property of the whole program and of the path by which control reaches it.

Renaming changes meaning. Under static scope, consistently renaming a bound name — a parameter and its uses — never changes what a program does. That is what the renaming clauses of Algol 60’s call by name were written to protect, and what de Bruijn’s indices build in by having no names to rename. Under E-App-Dyn, renaming twice’s parameter from x to n changed the program’s output from 30 to 12. The name a function gives its parameter, invisible from outside under static scope, becomes something every function it calls can see. Guy Steele and Gerald Sussman’s “The Art of the Interpreter” (1978) builds the same failure from a SCALE function that passes a lambda mentioning L to a MAPCAR whose own variable is named L, and concludes: “That the behavior of the SCALE program depends on the choice of names for its local variables is a violation of referential transparency.” A programmer writing twice has to know the free names of every function that might be passed to it, and a programmer writing add_x has to know the parameter names of every function it might be passed to.

A returned function loses its free names. make_adder under E-App-Dyn:

fn make_adder(k: Int) -> fn(Int) -> Int = |x: Int| x + k;

fn main() {
    let add5 = make_adder(5);
    println(add5(10));                // static: 15; dynamic: UnboundVariable k
}

k is bound for the dynamic extent of the call make_adder(5). When add5(10) runs, that call has returned, and the chain of active calls is main alone, which binds no k. Under dynamic scope a binding’s extent is the activation that made it, exactly as on a stack, and a function cannot carry a binding past it. The closures of the previous chapter, the adder, the counters, the account, have no dynamically scoped version.

A function passed down, to be called while its creator is still running, fares better. add_x’s creator is main, which is still running when twice calls it, so main’s x is in the chain. What goes wrong is that twice’s x is in the chain too, and nearer. The function finds a binding of the right name made by the wrong code.

Bridger’s answer

Bridger is statically scoped. There is no switch and no second mode: E-Lam records the defining environment, E-App runs the body there, and every free name in every function body is resolved the way Part III resolved the names in nested blocks. That was settled when first-class functions gave E-Lam its environment. There is nothing to build in this chapter; the Lambda and Call arms that run the programs of closures already implement it.

The decision is permanent for a reason in Part VI. The type checker built there checks a function body once, before the program runs, against the types of the names in scope where the body is written. A function’s free names are found in its definition’s environment, so their types are found in the definition’s types, and the checker can give scaled the type fn(Int) -> Int by reading it. Take away the top-level scale and give the program two callers:

fn scaled(x: Int) -> Int = x * scale;

fn a() -> Int {
    let scale = 2;
    scaled(4)
}

fn b() -> Int {
    let scale = true;
    scaled(4)
}

Under static scope scale is unbound in scaled. The M4 evaluator reports UnboundVariable at the first call, and Part VI’s checker rejects the program before anything runs. Under dynamic scope the program runs: a() returns 8, and b() gets stuck inside scaled’s body, multiplying an Int by a Bool. To check scaled before running it, a checker would have to know the type of scale in the body, and the body has none of its own: scale is an Int when the call comes through a and a Bool when it comes through b. Checking each body at each call site does not suffice either. scaled can be passed as a value and called from inside a function that never names it, and the chain of calls that reaches it is a fact about one run. Part VI’s checker gives each name one type for its whole scope, and under dynamic scope a free name has one type per path through the program.

The same property served Part III. Resolving names before the run replaced each name with the distance to its binding, computed from the text. Under dynamic scope the binding a free name finds depends on which calls are active, and the distance changes from call to call.

An experiment

The difference between the two rules is one environment in one arm of your evaluator. In a copy of your finished M4 interpreter, change the Call arm so that it extends the environment it was called with, instead of the closure’s captured environment, with the parameters. Then run:

• scaled from the start of this chapter, and watch 40 become 8;
• twice(add_x, 10), then rename twice’s parameter, and watch 30 become 12;
• the adder, counter, and account programs from closures, and find which still run;
• the two-caller program above, and try to write down a type for scale.

Then change it back. Bridger’s semantics is the captured environment, and nothing later in the book works under the other one.

The design space

Lisp after FUNARG

Gerald Sussman and Guy Steele’s “Scheme: An Interpreter for Extended Lambda Calculus” (1975) made capture the only behaviour: “SCHEME is essentially a full-funarg LISP. LAMBDA expressions need not be QUOTEd, FUNCTIONed, or *FUNCTIONed when passed as arguments or returned as values; they will evaluate to closures of themselves.” The memo lists what follows from closing every lambda in its “lexical” or “static” environment: “First, the axioms of lambda calculus are automatically preserved. Thus, referential transparency is enforced.” Richard Gabriel and Guy Steele’s “The Evolution of Lisp” calls Scheme “one of the first languages to have taken seriously the implications of lexical scoping (as opposed to local scoping, which had been in use in Lisp compilers for almost a decade) and first-class functions.” The local scoping of the compilers is the LISP 1.5 arrangement above: a variable no other function could see, with no closure to carry it anywhere.

Common Lisp (1984) made lexical scope the default and kept dynamic scope for variables declared special, an arrangement described below. Emacs Lisp stayed dynamically scoped longer. Emacs 24.1 (2012) added a variable, lexical-binding, that a file sets on its first line to choose lexical scope; Emacs 30.1 (2025) made the byte compiler warn about a file with no such line, and Emacs 31.1 (2026) warns when one is loaded. A file that says nothing still gets the old rule. The manual’s section on scoping rules puts it this way: “The old dynamic-only Emacs Lisp dialect is still the default in code loaded or evaluated from Lisp files that lack a dialect declaration. Eventually the modern dialect will be made the default.” Changing a language’s scope rule changes the meaning of every existing program that relies on the old one, and the change has been made one declared file at a time.

Implementing a dynamically scoped variable

Under dynamic scope, a variable’s current value is the most recent binding of its name made by an active call. Moses’s memo describes two ways to find it, and they are the two representations of environment representations. The deep access approach, “used in the classical “alist” implementation of LISP“, keeps the bindings in a chain and searches it: “The “deep access” approach forces one to search upward in the stack for the most recent value of the free variable.“ That is the chain of scopes, walked at every lookup. The shallow access approach keeps one cell per name holding its current value, and pays at the boundaries instead: “On entering such a function or block one usually saves the old value which is in the special cell on the stack … On leaving such a function or block one must remember to store the value saved in the stack in the special cell.” That is the flat map with its stack of shadowed bindings per name. LISP 1.5’s SPECIAL variables worked this way, and Moses calls the approach “favored in recent implementations of LISP.”

The costs fall where Part III found them: deep access pays at each lookup, shallow access at each call and return. What has no counterpart is resolving names before the run, which needs the binding to be fixed by the text. And a closure is hard to add to shallow access: a function that outlives its call needs the values its free variables had, and the cells hold only the values they have now.

Call-site resolution on purpose

Some names are meant to be read where code runs. Which output port print writes to, whether a search ignores case, how many digits a number prints with: each is a setting that a caller wants to change for everything it calls, for as long as the call lasts, without passing the setting as an argument through every function in between. The Emacs Lisp Reference Manual gives the case as its example:

(defun search-for-abc ()
  "Search for the string \"abc\", ignoring case differences."
  (let ((case-fold-search t))
    (re-search-forward "abc")))

case-fold-search is read deep inside re-search-forward, which search-for-abc did not write and cannot pass the setting to. The let changes it for the extent of the call, and when the let ends the old setting is back, however the body exited.

Languages that keep this behaviour mostly keep it as a marked exception to lexical scope. Common Lisp’s defvar and defparameter “establish name as a dynamic variable”, and by convention such names are written with asterisks, *print-base*, so a reader can tell them apart. Scheme’s parameter objects, introduced as SRFI 39 (2003) and part of R7RS under the heading “Dynamic bindings” (§4.2.6), are values created with make-parameter and rebound with parameterize; the Racket Guide says a parameterize “adjusts the value of a parameter during the whole time that the parameterize body is evaluated, even for uses of the parameter that are textually outside of the parameterize body”. Clojure’s vars are static unless tagged ^:dynamic. In each, an ordinary name is lexically scoped, and a name is dynamically scoped only when its declaration says so.

Perl kept both under two keywords. my declares a lexical variable; local, in the words of perlsub, “just gives temporary values to global (meaning package) variables. It does not create a local variable. This is known as dynamic scoping.” The Unix shells kept dynamic scope as the only rule for function locals. The Bash Reference Manual states it directly: “The value of a variable that a function sees depends on its value within its caller, if any, whether that caller is the global scope or another shell function.”

Exception handlers are found by the same rule, in languages that would never describe their variables that way. When a Java program throws, the Java Language Specification (§11.3) transfers control “to the nearest dynamically enclosing catch clause, if any, of a try statement that can handle the exception”, where a statement is dynamically enclosed by a catch if it is in the try block “or if the caller of the statement or expression is dynamically enclosed by the catch clause.” A method that throws does not know, and does not need to know, who will catch: the handler is whichever one the chain of active calls has installed most recently. That is E-App-Dyn’s lookup applied to handlers. Bridger has no exceptions; its Result values travel back through each caller as ordinary return values, and every function between the error and its handling says so in its type.

Typing a dynamically bound name

Part VI’s checker cannot give a dynamically scoped free name a type because the function’s type says nothing about it: scaled : fn(Int) -> Int mentions what scaled takes and returns, and the scale it reads from its caller is not among them. A type system can record that too. Jeffrey Lewis, Mark Shields, Erik Meijer, and John Launchbury’s “Implicit parameters: dynamic scoping with static types” (2000) did so for Haskell, and GHC implements it as the ImplicitParams extension. A dynamically bound name is written with a question mark, ?scale, and every function that reads one, or calls a function that does, carries it in its type. The GHC User’s Guide reads a type of the form (?x::t') => t as “this function uses a dynamically-bound variable ?x of type t’”. A caller binds ?scale for the duration of a call, and the checker confirms at every call that the binding is there and has the right type. Under that arrangement the name scaled reads from its caller is part of its interface, written in its type, and renaming it is a change to the interface.

Further reading

The FUNARG problem: McCarthy’s “History of Lisp” (1979) tells the Slagle story in its section on the move from LISP 1 to LISP 1.5 and points the reader to Moses for the rest. Moses’s “The Function of FUNCTION in LISP” (1970) takes up from there: the binding and activation environments, a function passed down against one returned, and the shallow and deep ways of finding a free variable’s value, with the stack and the a-list drawn out.

Dynamic and lexical scoping side by side: Steele and Sussman’s “The Art of the Interpreter” (1978) builds a sequence of small Lisp interpreters, changing one thing at a time. Part One runs the SCALE/MAPCAR example through a dynamically scoped evaluator, then closes each procedure in its environment by changing EVAL and APPLY, with the code for both on the page. Part Two returns to dynamic scoping as a way of decomposing a program’s state.

Scope and extent as separate ideas: chapter 3 of Common Lisp the Language defines lexical and indefinite scope, dynamic and indefinite extent, and names the constructs of Common Lisp that have each combination, including special variables.

Dynamic binding with static types: Lewis, Shields, Meijer, and Launchbury’s “Implicit parameters: dynamic scoping with static types” (2000) gives the type rules for dynamically bound names in Haskell, the design GHC’s ImplicitParams extension implements; the GHC User’s Guide section linked above shows it on a sort function whose comparison comes from its caller.

Concept checks