Static vs dynamic scoping; tracing program output under each; access links and displays (brief)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• What does the control link of an activation record point to? from Lesson 5.2
• How many basic blocks does code with leaders 1, 4, 6, 7, 9 have? from Lesson 4.4
• Which phase detects the use of an undeclared variable, and with which table? from Lesson 0.1.3

1 · The Story

📖

Two Rameshes

The script of Mr. Patel’s evening contains a short tribute written by Mrs. Shah: “Thank you, Ramesh”. In the script, Mrs. Shah’s section sits inside the chapter about the Surat office, whose manager is Ramesh Mehta.

On the night, Mrs. Shah reads the tribute while she is a guest on the Mumbai panel, whose host is also called Ramesh, Ramesh Iyer.

Which Ramesh is thanked? If names are looked up in the script, the tribute means the Ramesh of the enclosing Surat chapter, wherever it is read. If names are looked up in the room, it means whichever Ramesh most recently took the floor before her: Ramesh Iyer. Translation House decides that its booklets always follow the script, because a reader can check the script without knowing who invited whom on the night.

2 · Predict First

🤔

What does this print under static scoping, and under dynamic scoping?

int x = 10;
int f() { return x; }
int g() { int x = 20; return f(); }
main() { print(g()); print(f()); }

Write your guess down. The answer is in the vault.

3 · Core Concept

Scope

The scope of a declaration is the part of the program where that declaration is the one a name refers to. A name used in a procedure but not declared there is a non-local name; the scope rule says which declaration it refers to.

Static (lexical) scoping

A non-local name refers to the declaration in the nearest enclosing block or procedure in the program text, regardless of who called the procedure at run time. Used by C, Java, Pascal, Python and almost every modern language. The binding can be decided at compile time.

Dynamic scoping

A non-local name refers to the declaration in the most recently called, still active procedure that declares it: search the callers, newest first, along the control links. Used by early Lisp, some shells, and as an option in some languages. The binding depends on the call chain at run time.

How to trace (method)

• For every use of a non-local name, decide which declaration it refers to:

• static: look outward in the text (enclosing procedure, then global);

• dynamic: look at the call chain at that moment (the caller, its caller, …).

• Assignments to a non-local change that declaration’s variable; later reads of the same declaration see the change.

• Keep a small table of each variable’s current value as you simulate.

Access links (static scoping, nested procedures)

When procedures can be nested (Pascal, ML), each activation record holds an access link (the static link of Lesson 5.2) to the record of the lexically enclosing procedure’s most recent activation. If a procedure at nesting depth nₚ uses a name declared at depth nₐ, the code follows nₚ − nₐ access links to find it. Under dynamic scoping, the search instead follows control links.

Displays (brief)

A display is an array d where d[i] points to the record of the most recent active procedure at nesting depth i. A non-local at depth i is found in one step through d[i]. On a call to a procedure at depth i, its record saves the old d[i] and d[i] is set to the new record; on return the old value is restored.

Story → compiler term

4 · Visual

Stack snapshot inside r for the nested program in Example 3 (captured by running it). r (depth 3) reaches z in q by 1 access link, y in p by 2, x in the global record by 3.

5 · Worked Examples

Example 1 Easy

Trace under both rules:

int x = 1;
void show() { print(x); }
void change() { x = 2; }
void test() { int x = 3; change(); show(); }
main() { test(); show(); }

Solution

Static: change() and show() are declared at global level, so their x is the global x. test calls change (global x = 2), then show prints the global x: 2. main’s show prints 2. Output 2 | 2.

Dynamic: inside test, the most recent active declaration of x is test’s (3). change sets test’s x to 2; show prints test’s x: 2. Then main’s show finds only the global x, still 1. Output 2 | 1. Two Rameshes, two answers.

Example 2 Medium

What does this print under each rule?

int n = 5;
int f(int k) { return k * n; }
int g() { int n = 2; return f(3) + n; }
main() { int n = 10; print(g(), f(1)); }

Solution

Static: f always uses the global n = 5: f(3) = 15, plus g’s own n = 2 gives 17; f(1) = 5. Output 17 5.

Dynamic: f(3) is called from g, whose n = 2: f(3) = 6, + 2 = 8. f(1) is called from main, whose n = 10: 10. Output 8 10.

Example 3 GATE

Nested procedures (allowed in this course’s little language as in Pascal):

int x = 1;
void p() { int x = 2; void q() { print(x); } void r() { int x = 3; q(); } r(); }
main() { p(); }

What is printed under static and under dynamic scoping?

Solution

Static: q is nested in p, so q’s x is p’s x = 2, even though q is called from r, which has its own x = 3. Output 2. Dynamic: the most recent active x when q runs is r’s: 3.

6 · Shortcuts

⚡

Static: where is the procedure written? Dynamic: who called it? Decide that once per procedure, then simulate. Valid when: any scoping trace.

⚡

Access links to follow = nesting depth of the user − nesting depth of the declaration. Valid when: questions on access links with nested procedures.

7 · GATE Traps

⚠️

• Under dynamic scoping an assignment to a non-local can change a caller’s local variable, which later output may reveal.
• Under static scoping the call chain is irrelevant for name lookup.
• A local declaration with the same name hides the outer one inside its scope (both rules).
• Access links follow the program text; control links follow the call chain.
• C does not allow nested functions; questions with nesting use Pascal-like syntax.

8 · Memory Hook

🧠

Static scope reads the script; dynamic scope looks around the room.

9 · Connect the Dots

A procedure also receives values through its parameters. Is it given a copy, the variable itself, or the unevaluated expression? The next lesson traces programs under four parameter-passing rules.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ2 marksTrace

What does this print (two prints) under dynamic scoping?

int a = 1; int b = 2;
void p() { a = a + b; }
void q() { int b = 5; p(); print(a, b); }
main() { q(); print(a, b); }

• (A) 3 5, 3 2
• (B) 6 5, 6 2
• (C) 3 5, 6 2
• (D) 6 5, 3 2

Q2MCQ2 marksTrace

Same program under static scoping: the output is

• (A) 3 5, 3 2
• (B) 6 5, 6 2
• (C) 3 2, 3 2
• (D) 6 5, 3 2

Q3NAT2 marksAccess links

Procedure r at nesting depth 3 uses a variable declared in procedure p at nesting depth 1. How many access links are followed?

Numerical answer: ________

Q4MCQ1 markDefinition

Under dynamic scoping, a non-local name refers to the declaration in:

• (A) the nearest enclosing procedure in the program text
• (B) the most recently called active procedure that declares it
• (C) the global scope only
• (D) the first procedure in the file

Q5MSQ1 markFacts

Which are true?

• (A) Static scoping can be resolved at compile time.
• (B) A display gives constant-time access to non-locals.
• (C) Dynamic scoping follows access links.
• (D) C uses static scoping.

11 · Rule Card

• Scope: region where a declaration applies; non-local = used but not declared locally.
• Static: nearest enclosing declaration in the text (compile time).
• Dynamic: most recent active caller that declares it (run time, control links).
• Access link → record of the lexically enclosing procedure; hops = depth(user) − depth(declaration).
• Display d[i] → most recent record at depth i; save/restore d[i] on call/return.

12 · Concept Ledger

scopenon-local namestatic (lexical) scopingdynamic scopingaccess link (static link)nesting depthdisplay

13 · Answer Vault