Runtime Environment Practice Questions

Frame Pointer (FP) / Base Pointer (BP): Points to a FIXED reference location within the current activation record (typically the saved old FP or the first parameter). Since FP stays fixed during execution, all local variables and parameters can be accessed via fixed positive/negative offsets from FP (e.g., FP-8, FP+4). This is stable even when SP changes.

Stack Pointer (SP): Always points to the TOP of the runtime stack. It changes dynamically as values are pushed/popped (e.g., for VLAs, temporary values, or function calls). After the function prologue, SP is decremented to allocate locals.

Why both? If only SP were used, offsets to locals would change every time something is pushed/popped, making code generation complex. FP provides a stable anchor. Option A correctly describes this.

Analysis for each strategy:

Call by Value: ALL arguments are evaluated BEFORE the call. Evaluating loop() causes infinite recursion → program does NOT terminate.

Call by Name: Arguments are substituted textually but evaluated only when USED. first(42, loop()) returns 'a' (= 42) without ever using b. Since loop() is never used, it is never evaluated → program TERMINATES and prints 42.

Call by Need: Same as Call by Name for this case - b (= loop()) is never used, so it is never evaluated → program TERMINATES and prints 42.

Call by Reference: loop() would be evaluated to get an address to pass → infinite recursion → does NOT terminate.

Answer: B - Call by Name and Call by Need both terminate; Call by Value and Call by Reference do not.

An activation record contains:
A: Return value slot - space reserved for the function's return value.
B: Actual parameters - values/references passed by the caller.
C: Local variables - all variables declared inside the procedure.
D: Saved registers - includes return address (PC), saved frame pointer, and other caller-saved registers.
F: Control link (dynamic link) - points to the activation record of the calling procedure (used to restore the stack on return).
G: Access link (static link) - points to the nearest enclosing scope's activation record (used for non-local variable access in statically scoped languages).
E is FALSE - source code is never stored in the activation record; it lives in the code/text segment.

A dangling reference (dangling pointer) is a pointer/reference that points to memory that is no longer valid - i.e., memory that has been deallocated (freed from heap) or whose lifetime has ended (e.g., a pointer to a local variable after the function returns and the activation record is popped from stack).

Example 1 (heap): int *p = malloc(4); free(p); p = 5; ← dangling
Example 2 (stack): int f() { int x=5; return &x; } ← returns pointer to local variable (dangling after return)

Option B is a null pointer dereference. Option C is an uninitialized pointer. Option D is valid (local variable of currently executing function is on the live stack).

CALLER responsibilities:
A: TRUE - Caller evaluates arguments and pushes them onto the stack (or loads into registers per ABI).
B: TRUE - Caller saves the return address (next instruction after call) and transfers control via CALL instruction.
D: TRUE - Caller-saved registers are saved by the caller before the call and restored by the caller after return.
E: TRUE - After the callee returns, the caller pops (or adjusts SP past) the parameters it pushed (caller-cleanup convention, as in C cdecl).

CALLEE responsibilities:
C: FALSE for caller - The callee allocates space for its own local variables by decrementing SP inside its prologue. The caller does NOT allocate the callee's locals.

Additional callee tasks: save callee-saved registers, set up frame pointer, allocate local variable space, restore everything in epilogue.

A: TRUE - One vtable per CLASS (shared by all instances). The vtable is a compile-time constant array of function pointers for that class's virtual methods.

B: TRUE - Every object of a class with virtual functions has a hidden vptr (virtual pointer) as its first member, pointing to the class's vtable. Added by the compiler automatically.

C: TRUE - Virtual call: obj->vfunc() compiles to: ((vptr) + offset)(obj). Step 1: dereference obj to get vptr; Step 2: index into vtable to get function pointer; Step 3: call. This is 2 memory dereferences (vptr load + vtable index).

D: FALSE - Non-virtual functions are resolved at COMPILE TIME (static dispatch). Their addresses are directly embedded in the call instruction - no vtable lookup needed.

E: TRUE - This is the entire purpose of vtables: runtime polymorphism. A base class pointer to a derived object uses the vptr of the derived object → calls the derived class's overriding method.

A: TRUE - Fixed parts (return addr, control/access links, saved registers, fixed-size locals) are laid out at compile time with known offsets.
B: TRUE - One common approach is to allocate VLAs on the heap and store a pointer in the fixed activation record frame.
C: TRUE - Another approach (C99 alloca-like): push the VLA onto the stack by decrementing SP by n*element_size at runtime; store the base address in a pointer in the fixed frame.
D: FALSE - Compile-time worst-case estimates are not feasible for true VLAs (n is not known at compile time).
E: TRUE - The frame pointer (FP/BP) is essential for VLAs. Since SP moves dynamically (when VLAs are allocated on stack), local variable offsets are computed relative to FP (which stays fixed during the procedure's execution), not SP.

f(n) makes 2 recursive calls to f(n-1), forming a complete binary tree.
Number of nodes in a complete binary tree of height h = 2^(h+1) - 1.

For f(3): calls f(2) twice; each f(2) calls f(1) twice; each f(1) calls f(0) twice; f(0) just returns.

Level 0 (root): f(3) → 1 node
Level 1: f(2), f(2) → 2 nodes
Level 2: f(1), f(1), f(1), f(1) → 4 nodes
Level 3: f(0)×8 → 8 nodes

Total = 1 + 2 + 4 + 8 = 15 nodes.

Formula: For f(n) with 2 recursive calls each decreasing n by 1, total nodes = 2^(n+1) - 1 = 2^4 - 1 = 15.

Aliasing occurs when two or more names refer to the same memory location.

Call by Reference: If the caller passes the same variable as two different arguments (e.g., swap(a, a) or f(x, x)), both formal parameters point to the same memory location → aliasing. Example: void f(int &p, int &q) - if called as f(x, x), then p and q are aliases.

Call by Value: Copies are made - no aliasing possible.
Call by Value-Result: Copies are made at call time; results written back at return - no runtime aliasing during execution, though write-back may cause unexpected results.
Call by Name: Uses textual substitution - can cause complex aliasing but not in the direct sense of two formals pointing to same location.

Answer: B - Call by reference.

Trace execution carefully (a is a GLOBAL variable, so all calls share it):

Call P(3): a = 0 + 3 = 3. x=3 > 1, so call P(2).
Call P(2): a = 3 + 2 = 5. x=2 > 1, so call P(1).
Call P(1): a = 5 + 1 = 6. x=1 NOT > 1, no recursion. printf → prints 6. Returns.
Back in P(2): printf → prints a = 6. Returns.
Back in P(3): printf → prints a = 6. Returns.

Output: 6 6 6

Key insight: 'a' is global, so when P(1) increments a to 6, and then P(2) and P(3) print a AFTER their recursive calls return, they all see the SAME global a = 6. The printf in each frame executes AFTER the recursive call completes. Answer: A.

Free blocks: [0-99]=100B, [300-349]=50B, [650-799]=150B. Total free = 300B.

A: TRUE - Although 300B total is free, no single CONTIGUOUS block ≥ 120B exists. The largest is 150B at [650-799]. Wait - 150B ≥ 120B, so the request CAN be satisfied from [650-799]. Let me reread: [650-799]=150B ≥ 120B → request CAN be satisfied. So A is FALSE in this case. Let me re-examine: First-fit would check [0-99]=100 < 120 (skip), [300-349]=50 < 120 (skip), [650-799]=150 ≥ 120 ✓ → allocated. So request IS satisfiable. Correcting: A is FALSE, D is FALSE (100<120), B is TRUE (scattered free blocks = external fragmentation), C is TRUE (best-fit picks 150B as it's smallest fitting), E is TRUE (compaction merges free blocks).

FINAL: B: TRUE (scattered free memory = external fragmentation), C: TRUE (best fit picks 150B block - smallest block ≥ 120), E: TRUE (compaction would merge free blocks into contiguous memory). F: FALSE (internal fragmentation = wasted space WITHIN allocated blocks; this scenario shows external fragmentation).

When procedure $p$ begins, $s$ is called $[p\to s].$ $s$ is enclosed within $p.$ So, any undeclared variable found inside $s$ will be searched for inside the body within which it is enclosed i.e., function $p$ (static scoping rules). So access link is from s to p . Now, $s$ is visited and $s$ calls $q$ $[p\to s \to q].$ $q$ is visited and begin execution. Any undeclared variable found inside $q$ will be searched inside the enclosing function i.e. $p$ again. So, access link is from q to p . Now, $q$ calls $r$ $[p \to s \to q \to r].$ $r$ is visited. $r$ begins execution and any undeclared variable found is searched in the enclosing function i.e., $q$ here. So, access link is from r to q . $r$ calls $q$ $[p\to s \to q \to r \to q]:$ This is the sequence of calls which is already given in the question. We have already seen access links for $q.$ So, it becomes

arr is a local array declared inside createArray(), so it is allocated on the STACK in createArray()'s activation record. When createArray() returns, its activation record is POPPED from the stack - the memory that arr occupied is reclaimed and may be overwritten by subsequent function calls or interrupt handlers.

The pointer p returned by createArray() now points to this reclaimed (invalid) stack memory - this is a DANGLING POINTER. Accessing p[0] after the function returns is undefined behavior in C.

Fix: Allocate arr on the heap: int *arr = malloc(5 * sizeof(int)); - heap memory persists until explicitly freed, so the pointer remains valid after the function returns.

Static (Lexical) Scoping: Variable resolution is based on where the function is DEFINED in source code. P() is defined at the global level where x = 10. So P() prints 10 under static scoping.

Dynamic Scoping: Variable resolution is based on the CALL CHAIN at runtime. At the time P() is called, the most recently bound 'x' in the call stack is x = 20 (declared in Q(), which called P()). So P() prints 20 under dynamic scoping.

Answer: Static → 10, Dynamic → 20. Option C.

In STATIC allocation (used in early FORTRAN), each procedure has exactly ONE activation record allocated at compile time at a fixed memory location. There is no stack.

When B calls itself recursively:

• The new call to B overwrites the SAME statically allocated activation record for B
• The original call's local variables, return address, etc. are DESTROYED
• When the recursive call returns and the original call tries to resume, its data is corrupted

This is WHY early FORTRAN did NOT support recursion - the static allocation model fundamentally cannot support multiple simultaneous activations of the same procedure.

Modern languages solve this with STACK allocation - each call pushes a NEW activation record, supporting arbitrary recursion depth.

Trace the full execution:
main() calls A() and B().
A() calls B() and C().
B() (inside A) calls C() and D().
C() (inside B inside A) calls D() → D() = 1 node
C() (inside A) calls D() → D() = 1 node
B() (from main) calls C() and D().
C() (inside B from main) calls D() → D() = 1 node

Count all activation nodes:
main(1) → A(1) → B(1) → C(1) → D(1)
→ D(1)
→ C(1) → D(1)
→ B(1) → C(1) → D(1)
→ D(1)

Nodes: main=1, A=1, B=2, C=3, D=5 → but let's recount carefully:

• main: 1
• A (called by main): 1
  • B (called by A): 1
    • C (called by B→A): 1
      • D (called by C→B→A): 1
    • D (called by B→A): 1
  • C (called by A): 1
    • D (called by C→A): 1
• B (called by main): 1
  • C (called by B→main): 1
    • D (called by C→B→main): 1
  • D (called by B→main): 1
    Total = 1+1+1+1+1+1+1+1+1+1+1+1 = 12 nodes. Answer = 12.

Parameter passing strategies compared:

Call by Value: Evaluate BEFORE call; pass value. Evaluated exactly once regardless of usage.
Call by Name: Substitute expression textually; re-evaluated EVERY time parameter is used. (Like macros)
Call by Need (Lazy): Evaluate AT MOST ONCE - on FIRST USE. The result is MEMOIZED (cached). Subsequent uses of the parameter reuse the cached value WITHOUT re-evaluation.

Key distinction from Call by Name: Call by Name may evaluate multiple times (inefficient if used many times); Call by Need evaluates at most once (efficient - combines laziness with memoization).

Example: if f(x) uses x twice, Call by Name evaluates the argument twice; Call by Need evaluates it once and caches the result for the second use.

Haskell uses Call by Need as its default evaluation strategy.

The correct execution sequence is given in the above figure. inside main() we have $3$ function call as $f_1(),f_2(),f_3()$. $f_1(),f_3()$ will return but $f_2()$ will take $x=2$ and evaluate it. when $X=2$ it will call $f_3()$ and else part. in next time when $x$ value became $1$ again it will call $f_3()$ and if part of given code. after that, it will return. Option (A) is correct.

Each procedure call pushes one activation record onto the runtime stack. The call sequence is: main (or A) → B → C → D. At the deepest point (inside D), the stack contains activation records for A, B, C, and D simultaneously. Maximum stack depth = 4 activation records. This models the dynamic call chain and each frame is popped when the respective procedure returns.