GATE CSE 1998 | Question: 2.15

Question

Faster access to non-local variables is achieved using an array of pointers to activation records called a 

• A. stack
• B. heap
• C. display
• D. activation tree

Comments

@ShouvikSVK

Thanks :)

---

Link from Shouvik is not working

Updated :

https://www.cse.iitk.ac.in/users/swarnendu/courses/spring2024-cs335/runtime-environments.pdf
Page 63-67

---

@P0535_Yedidyah_Sagar Thanks Bro.

Answer 1

Correct Option: C

Properties of displays    

1. Use a pointer array to store the activation records along the static chain.
2. Fast access for non-local but may be complicated to maintain.
3. Calling a subprogram in the same level – simply replace and restore.
4. Calling a subprogram in the higher level – add an entry and may need to save the old pointers.
5. Calling a subprogram in the lower level – shrink the pointer and restore it when the subprogram returns.

http://users.dickinson.edu/~wahlst/356/ch10.pdf

Comments

If a variable or a code or block or anything, that is not in my function but in other function, Then my function will use "access link" of Activation record to access them.

Displays are an optimization technique that replaces access links. There are implemented as an array (of pointer) in this array each entry points to one of the activation records.
The size of the array is the maximum nesting depth in the program

use: if disp is the display, then disp[i] points to the activation record associated with the current
scope at nesting depth i.

Now if function j wants to access something that is in function i then
Step-1: go to the activation record pointed to by disp[i]
Step-2: find the nonlocal via an offset in this activation record

---

@sachin can you please provide some reference for display. I know nothing about them. But i'm seeing few question about them. Thank You.

---

@Hemant-Ullman 2ed compilers

---

adding info to above comment ullman page 432

---

nice point sachin sir

---

thnx @Sachin Mittal 1 sir

---

Is this part in syllabus now?

Answer 2

The data structure used to enable efficient access to non-local variables in block-structured languages that support nested procedures (such as Pascal or Ada) is the display. A display is an array of pointers to activation records, where each entry corresponds to a static nesting level. If the maximum static depth of nesting in a program is $ d $, then the display is an array $ \text{display}[0 \ldots d] $ such that:

$$
\text{display}[i] = \text{pointer to the activation record of the most recent invocation at static level } i.
$$

When a procedure executing at static level $ k $ needs to access a variable defined at an outer static level $ i < k $, it retrieves the variable using:

$$
\text{display}[i] + \text{offset of variable}.
$$

This mechanism provides $ O(1) $ access time to non-local variables, regardless of how deeply nested the current procedure is in the call chain.

Consider the following program structure:

1. Program $ \text{Main} $ (static level 0) declares variable $ a $.
2. Procedure $ P $ (static level 1) declares variable $ b $.
3. Procedure $ Q $, nested inside $ P $ (static level 2), executes the statement $ a := a + b $.

During execution of $ Q $, the display contains:

• $ \text{display}[0] $ pointing to $ \text{Main} $'s activation record,
• $ \text{display}[1] $ pointing to $ P $'s activation record,
• $ \text{display}[2] $ pointing to $ Q $'s own activation record.

Thus, $ Q $ accesses $ a $ via $ \text{display}[0] $ and $ b $ via $ \text{display}[1] $, without traversing a static link chain.

Other options are unsuitable:

• The stack holds activation records but does not by itself support direct indexed access to outer scopes.
• The heap is used for dynamically allocated data, not for lexical scoping.
• The activation tree is a conceptual model of procedure calls, not a runtime data structure.

Therefore, the correct answer is:

$$
\color{hotpink} \boxed{\text{C. display}}
$$