GATE CS 1998 Q2.15 — Runtime Environments

The correct option is C.

In block-structured programming languages (such as Pascal), nested procedures can access variables declared in outer scopes (non-local variables). There are two primary techniques to implement this access:

• Static Links (Access Links): Accessing a non-local variable requires traversing a chain of pointers. If the variable is declared at a nesting depth $d$ levels shallower than the current procedure, we must traverse $d$ links, which takes $O(d)$ time.
• Display: To achieve faster, constant-time ($O(1)$) access to non-local variables, compilers use an auxiliary array of pointers called a display.

The $i$-th entry of the display array points to the activation record of the most recently active procedure at nesting depth $i$. Any non-local variable at nesting depth $i$ can be accessed directly in $O(1)$ time by dereferencing the pointer at index $i$ of the display, followed by the local offset.

Why other options are incorrect:

• Stack: Used to store activation records in a Last-In-First-Out (LIFO) order, but does not directly provide $O(1)$ access to non-local variables in nested scopes.
• Heap: Used for dynamic memory allocation (e.g., objects, lifetime extending beyond procedure calls).
• Activation Tree: A conceptual tree representing the entry and exit of control among various activation records during execution. It is not a data structure used for variable access.