Run-Time Environments & Activation Records: Stacks, Trees & Procedure Calls

Core Concepts: Activation Records and Runtime Stacks

1. What is an Activation Record?

An activation record (AR), also called a stack frame, is a block of memory allocated on the runtime stack whenever a procedure (function/subroutine) is called. It stores:

• Control information (return address, saved registers)
• Access links (pointers to parent/child frames)
• Local variables (temporaries, parameters)
• Return value (if any)

Why a stack?

• LIFO (Last-In-First-Out) ensures proper nesting of calls.
• Dynamic allocation (no fixed size) handles recursion and variable scopes.
• Efficient access (top of stack is fastest).

2. Components of an Activation Record

In the Real World

1. eSewa’s Payment Flow

   • Activation Records: Each step (selectService → enterAmount → verifyOTP) gets its own AR.
   • Access Links: verifyOTP() accesses transactionID from enterAmount()’s AR.
   • Stack Trace: If OTP fails, the system unwinds the stack to return to selectService().

2. Pathao’s Ride-Matching Algorithm

   • Recursion: findNearestDriver() calls itself for each driver in the pool (activation tree branches).
   • Saved Machine Status: Preserves driver location before calculating fare.

3. Kathmandu Traffic Routes (Simulated)

   • Activation Tree: Each intersection (Thapathali → Koteshwor) is a procedure call.
   • Control Links: If a route fails (e.g., RingRoad jammed), the system backtracks to the parent node (KTM_CBD).

3. Activation Tree: Visualizing Procedure Calls

An activation tree shows the hierarchy of procedure calls. Each node is an AR, and edges represent caller-callee relationships.

flowchart TD
    A["Main()"] --> B["calculateTax()"]
    A --> C["processOrder()"]
    C --> D["validatePayment()"]
    C --> E["updateInventory()"]
    E --> F["checkStock()"]
    F --> G["checkStock()"] <!-- Recursive call -->

Key Observations:

• Depth = Nesting level (e.g., checkStock() called from updateInventory()).
• Recursion creates sibling nodes (e.g., checkStock() calling itself).
• Leaf nodes are procedures that don’t call others (e.g., validatePayment()).

4. Caller vs. Callee: Who Does What?

Example: Nepali Bank Loan Calculation

def calculateEMI(principal, rate, years):
    monthly_rate = rate / 12
    n = years * 12
    emi = (principal * monthly_rate * (1 + monthly_rate)**n) / ((1 + monthly_rate)**n - 1)
    return emi

# Caller: Main program
principal = 1000000
rate = 0.08
years = 5
emi = calculateEMI(principal, rate, years)  # AR pushed

Stack Trace:

1. Caller (main) pushes principal, rate, years and jumps to calculateEMI().
2. Callee (calculateEMI) allocates its AR, computes emi, then returns to main.
3. Stack Unwinds: calculateEMI()’s AR is popped; main uses the returned emi.

5. Handling Recursion in Activation Records

Recursion creates multiple ARs for the same procedure in the stack. Each recursive call gets its own frame.

Example: Factorial Calculation

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)  # Recursive call

Stack Growth for factorial(3):

AR Contents at Each Step:

Key Point:

• The access link forms a chain to the original caller.
• Tail recursion (optimized) can reuse the same AR.

6. Three-Address Code and Activation Records

Compilers generate intermediate code (e.g., three-address code) that maps to AR operations. Example:

n = (a + b) * (c - d)
for i = 0; i < n; i++:
    for j = 0; j < n; j++:
        x = n + i + j

Three-Address Code:

t1 = a + b
t2 = c - d
n = t1 * t2
i = 0
L1: if i >= n goto L3
    j = 0
L2: if j >= n goto L4
    t3 = n + i
    t4 = t3 + j
    x = t4
    j = j + 1
    goto L2
L4: i = i + 1
    goto L1
L3: exit

Stack Behavior:

1. Loop variables (i, j) are stored in the AR of the loop’s scope.
2. Temporaries (t1, t2) are allocated in the AR of the expression evaluation.
3. Recursive calls (if any) would push new ARs.

7. Symbol Table and Activation Records

The symbol table tracks variables, but activation records manage their runtime scope.

Example: Scope Conflict

x = 10
def outer():
    x = 20
    def inner():
        x = 30  # Shadows outer’s x
        print(x)  # Uses inner’s AR
    inner()
    print(x)  # Uses outer’s AR

AR Hierarchy:

outer()’s AR → inner()’s AR (child)

• inner()’s x hides outer()’s x until inner() returns.

Exam Tip

1. Draw the Stack: Always show the state after each operation (push/pop/call/return).
   • Example: For factorial(3), draw the stack before and after each recursive call.
2. Label All Components: In activation records, explicitly mark:
   • Access link (parent pointer).
   • Control link (for recursion).
   • Saved registers (e.g., PC, SP).
3. Real-World Mapping: Relate to Nepali apps:
   • eSewa: Procedure calls = payment steps.
   • Pathao: Recursion = driver matching.
4. Three-Address Code: For loops/nested calls, show how temporaries map to ARs.
5. Common Pitfalls:
   • Forgetting to restore registers on return.
   • Incorrect access link setup in recursive calls.
   • Mismatched parameter passing (e.g., passing by value vs. reference).

Practice Question with Solution

Question: Draw the activation tree and stack frames for the following calls:

def main():
    a = 10
    b = callA(a)
    print(b)

def callA(x):
    y = x * 2
    z = callB(y)
    return z

def callB(w):
    return w + 5

Solution:

1. Activation Tree:
2. Stack Frames:
   • After callA(a):

     [main()’s AR]
       - a = 10
       - b = ?
     [callA()’s AR]
       - x = 10 (passed by value)
       - y = ?
     

   • After callB(y):

     [main()’s AR]
     [callA()’s AR]
       - y = 20 (10 * 2)
     [callB()’s AR]
       - w = 20
       - return value = 25 (20 + 5)
     

   • After return:
     • callB()’s AR is popped; callA() gets z = 25.
     • callA()’s AR is popped; main() gets b = 25.

Key Formulas (If Applicable)

For runtime stack growth, the maximum depth is: $$\text{Max Depth}=\text{Maximum Nesting Level}+\text{Recursion Depth}$$ Example: factorial(5) with 2 nested loops → Depth = 5 (recursion) + 2 (loops) = 7.