The idea: where does a free name come from?
In program P1, show() prints x but does not declare it. Inside show, x is a free name: its meaning has to come from somewhere else. There are two rules. Static scoping (also called lexical scoping) looks where show is written: next to the global x = 1. Dynamic scoping looks where show is called from: run() just declared its own x = 2 and then called show. So the same program prints 1, 1 under one rule and 2, 1 under the other (Demo 1 and Demo 2).
Frames, dynamic links and static links
Each call pushes an activation record (a frame) on the run-time stack. It holds the parameters and the local variables. Every frame also has a dynamic link (the control link) to the caller's frame. The return uses it, and dynamic scoping searches along it.
A language with static scoping and nested procedures, like Pascal, Ada or ALGOL, gives each frame a second pointer: the static link (the access link). It points to the frame of the procedure that encloses the callee in the source. In P2, inner is written inside outer but called by caller. Its dynamic link goes to caller and its static link goes to outer. The two links point to different frames (Demo 3).
To set the static link, the caller follows its own static chain. If the callee is written k levels further out than the caller, that takes k hops. In P2, caller and inner are both written inside outer, so caller follows its own static link once to reach outer.
Lookup: the static chain vs the call chain
A free name is found by walking a chain of frames and stopping at the first frame that has it:
- Static scoping walks the static chain. In P2, inner finds outer's
x = 10in 1 hop and never looks at caller's x (Demo 3). - Dynamic scoping walks the call chain, newest frame first. In P2, inner finds caller's
x = 20in 1 hop (Demo 4).
Recursion shows the difference in the chains, even when the answer is the same. In P3, outer calls count(2), which calls count(1), which calls count(0). All three count frames have a static link to outer, because count is written inside outer. So count(0) finds x = 10 in 1 hop and skips the 2 count frames in between (Demo 5). Dynamic scoping searches count(1), count(2) and then outer: 3 hops for the same 10 (Demo 6). With deep recursion the call chain grows but the static chain does not.
The symbol table as a stack of scopes
Under static scoping the compiler can answer every lookup before the program runs, because the answer depends only on the source. It keeps a symbol table organised as a stack of scopes:
- On entering a procedure body, push a new scope, already holding the parameters.
- For each declaration, insert the name in the top scope. A procedure's name goes into the enclosing scope before its body is read, so the body can call itself.
- For each use, look up from the top scope down. The first match wins. Record how many scopes down it was.
- At the end of the body, pop the scope. Its names are gone.
In P2 the compiler pushes 4 scopes (main, outer, inner, caller) and pops 4. The stack is never more than 3 deep, because inner's scope is popped before caller's is pushed. At print x it finds x in outer, 1 level up (Demo 7). The generated code then says "follow 1 static link, then take x". That is the number of hops Demo 3 took at run time. Real compilers often store each name as a pair (levels up, offset in the frame).
Shadowing
When an inner scope declares a name that an outer scope also has, the inner one shadows (hides) the outer one inside its scope. In P2, outer's x = 10 hides the global x, and caller's x = 20 hides outer's x. The canvas marks a hidden name "(hidden)". Lookup always stops at the first match, so a hidden name is never reached from inside. It comes back into view when the inner scope is popped. At run time, var x = 2 in run() makes a new variable in run's frame; the global x stays 1.
Which languages do which
| Rule | Languages | Cost of a lookup |
|---|---|---|
| Static scoping | C, Java, Pascal, Ada, Python, JavaScript, Scheme, Go and almost every modern language | Known at compile time: k hops plus an offset |
| Dynamic scoping | Early Lisp, Emacs Lisp by default, Bash and other shells (variables seen by called functions), Perl's local | A search at run time, as deep as the call chain |
Static scoping won because you can read a procedure and know what each name means without knowing who will call it. Under dynamic scoping, renaming a local variable in one procedure can change what another procedure prints.
See also the compiler pipeline (where the symbol table is used), recursion to an explicit stack and recursive factorial (what frames hold), LL(1) parsing (the parser that walks the source) and compiler vs interpreter.
See also Parameter passing modes for what fills a frame when a procedure is called: a copy, an address or a thunk.
See also closures and currying, where a function keeps its defining environment alive in the heap after the frame that made it is popped.
See also Hindley-Milner type inference, where the environment of names in scope carries types, and a let-bound name gets a fresh copy of its type at each use.
What the page leaves out
The page uses one name, x, and three tiny programs. It leaves out how parameters are passed (by value, by reference and so on), the display (an array of pointers that replaces the static chain), shallow binding (a central table per name instead of searching frames), closures that outlive their frame and need heap-allocated environments, frame offsets and the machine code for a hop, block scopes inside a procedure, and hash tables per scope in a real symbol table.