Runtime Environments for GATE: Activation Records, Static vs Dynamic Scoping and Parameter Passing

Runtime-environment questions are output puzzles with one rule quietly changed. The same short program can print one value under static scoping and another under dynamic scoping. Change call by value to call by reference or value-result, and the answer moves again.

The cure is to trace bindings and updates, not guess from the syntax. First separate the control link from the access link. Then make every parameter-passing step explicit.

1. The activation record (stack frame)

Every active procedure or function call needs runtime storage. A stack-based implementation pushes an activation record, also called a stack frame, for the call and removes it when the call returns.

A typical record can contain:

• Return value space.

• Actual parameters or parameter information.

• A control link.

• An access link.

• Saved machine status, including the return address.

• Local variables.

• Temporary values created during expression evaluation.

The exact order is implementation-dependent, but the two links have distinct jobs.

The control link, also called the dynamic link, points to the activation record of the caller. It follows the runtime call chain. If main calls g and g calls f, the control links run from f to g to main.

The access link, also called the static link, points toward the activation record for the lexically enclosing scope. It follows the way procedures are nested in the source program, which may differ from the call chain.

Remember the one-line distinction: control says who called me; access says where I was written. Each active call owns exactly one frame, and that frame exists only until the call returns.

2. Static versus dynamic scoping

A free variable is used inside a block but declared elsewhere. The scoping rule tells the runtime which declaration that name denotes.

Under static scoping, also called lexical scoping, search the enclosing blocks in the source text. The binding can be determined from program structure. At runtime, access links help reach non-local variables in lexically enclosing activations.

Under dynamic scoping, search the active callers from the current function outward. The most recent live declaration in the call chain wins. Control links represent that chain.

C, Java and Python use static scoping, although their detailed name rules differ. Dynamic scoping remains examinable because it cleanly tests whether you understand source nesting versus runtime calling.

3. Worked example: the same program, two scoping rules

Consider this pseudocode:

x = 10

function f() {
    print(x)
}

function g() {
    x = 20
    f()
}

main() {
    g()
}

Under static scoping, inspect where f is written. It is at global scope, not inside g. The free x in f therefore resolves to global x = 10. The program prints 10.

Under dynamic scoping, inspect the live call chain:

main -> g -> f

Starting from f, the most recent active declaration of x is the local x = 20 in g. The program prints 20.

Nothing about the declarations or calls changed. Only the lookup rule changed. If you find yourself using g's local variable under static scope, you have followed the caller instead of the lexical enclosure.

4. Parameter passing: four conventions

Scoping chooses a binding. Parameter passing chooses how an actual argument and a formal parameter are connected.

Call by value

The formal receives a copy of the actual value. Assignments to the formal change only that copy. When the procedure returns, the copy is discarded.

Call by reference

The formal is an alias for the actual location. Reading either name reads the same location, and an assignment through the formal immediately changes the caller's variable.

Call by value-result

This is copy-in, copy-out. The actual value is copied into the formal at entry. The body works on the local formal. At return, the final formal value is copied back to the actual location. It can behave differently from reference when the body also accesses that actual variable directly.

Call by name

The argument expression is effectively re-evaluated in the caller's environment whenever the formal is used. It is associated with thunks and the classic Jensen's device. For an output question, substitute carefully on every read or write instead of treating it as value or reference.

5. Worked example: the same call, three answers

Let global a = 5, and use this pseudocode:

procedure p(x) {
    x = x + 1
    a = a + x
}

main() {
    p(a)
    print(a)
}

For call by value:

1. Copy a = 5 into local x, so x = 5.

2. Execute x = x + 1, giving x = 6; global a is still 5.

3. Execute a = a + x, giving a = 5 + 6 = 11.

4. Discard local x. The program prints 11.

For call by reference:

1. Make x an alias for a, whose value is 5.

2. Execute x = x + 1. Because x and a are the same location, both now denote 6.

3. Execute a = a + x. Both reads produce 6, so a = 6 + 6 = 12.

4. The program prints 12.

For call by value-result:

1. Copy a = 5 into local x, so x = 5.

2. Execute x = x + 1, giving local x = 6; global a remains 5.

3. Execute a = a + x, giving global a = 5 + 6 = 11.

4. On return, copy local x = 6 back into the actual a. This overwrites 11, so a = 6.

5. The program prints 6.

The final outputs are value 11, reference 12, and value-result 6. Value-result differs because the update through a occurs before a delayed copy-out overwrites it.

6. The traps GATE builds these on

• Swapping the links. Static scope follows lexical structure through access links. Dynamic scope follows callers through control links.

• Treating reference as delayed copy-out. A reference update reaches the actual immediately.

• Treating value-result as reference. Value-result uses a separate local during the call and copies back only at return.

• Forgetting direct aliases. In the worked procedure, the body accesses a both through the parameter route and directly.

• Using the caller under static scope. A call does not create a lexical enclosure.

• Counting completed recursive calls as live frames. Only calls that have started but not returned occupy the active call stack.

Write a small state table for output questions. Give each actual variable and local formal its own column, unless the convention explicitly makes them aliases.

7. How GATE tests this and the official pointer

Expect output prediction under stated scoping and parameter conventions, identification of control or access links, and maximum live activation-record counts for recursive calls. These questions are short but exact: one incorrect alias assumption changes the whole trace.

Runtime environments belong to Compiler Design in the GATE CS scope. Confirm the current syllabus and any mark-share information on the official GATE portal for your cycle. KnowledgeGate's practice bank contains about 700 Compiler Design questions for practising these traces. The GATE category places them in the wider exam plan.

Code generation is the next compiler connection. The syntax-directed translation and code optimization guide shows how translated operations eventually depend on runtime locations and temporaries.

8. The short version and your next step

One active call gets one activation record. The control link points to the caller, while the access link points toward lexical enclosure. Static and dynamic scoping print 10 and 20 in our first example. Value, reference and value-result print 11, 12 and 6 in the second.

Trace both examples again using named storage boxes. Then build the full Compiler Design sequence with GATE Guidance by Sanchit Sir and practise mixed output questions in the GATE test series. The rules stop feeling tricky once every binding and write has a visible destination.