"Runtime Environments" — Practice

Question 1

Which pointer in an activation record is used to locate non-local variables?

Accepted Answer

B

Question 2

Why can a language using only static allocation not support recursion?

Accepted Answer

B

Question 3

Which garbage collection technique fails to reclaim cyclic structures?

Accepted Answer

C

Question 4

A procedure swap(a, b) executes: temp = a; a = b; b = temp. It is called as swap(x, arr[x]) with x = 1 and arr = [10, 20, 30] using zero-based indexing. Give the outcome under call by reference and call by name.

Accepted Answer

Under call by reference, both parameters are bound to their arguments at the moment of the call. Parameter a aliases x, and parameter b aliases arr[1], the element selected by x's value of 1, which is 20.

The binding of b is fixed at call time, so it refers to arr[1] throughout regardless of later changes to x.

Execution: temp becomes 1, the value of a. Then a is set to b, so x becomes 20. Then b is set to temp, so arr[1] becomes 1.

Final state: x is 20 and arr is [10, 1, 30].

Under call by name, the argument expressions are substituted textually and re-evaluated at every use. Parameter a stands for x, and parameter b stands for arr[x] evaluated afresh each time.

Execution: temp becomes 1. Then a is set to b, meaning x is set to arr[x], which with x equal to 1 gives arr[1] equal to 20, so x becomes 20. Then b is set to temp, meaning arr[x] is set to 1 — but x is now 20, so this writes to arr[20], which is out of bounds.

Final state: x is 20, arr[1] is unchanged at 20, and the program has written past the end of the array.

The divergence is entirely due to re-evaluation. Reference captures the location once; name recomputes it after x has changed, which is exactly what makes call by name unpredictable and why no mainstream language uses it.

Question 5

A global x is 5. Procedure P prints x. Procedure Q declares a local x equal to 15 and calls P. Procedure R declares a local x equal to 25 and calls Q. Main calls R. What does P print under static and under dynamic scope?

Accepted Answer

Under static scope, P's reference to x is resolved by examining the program text. P declares no x of its own, so the compiler looks at the enclosing scopes in the text. Assuming P is declared at the outermost level alongside Q and R, the nearest enclosing declaration is the global x.

P therefore prints 5, and it prints 5 no matter who calls it. The resolution is fixed before the program runs, and the compiler can emit a direct reference to the global's fixed address.

Under dynamic scope, P searches the chain of active activations for the most recent declaration of x still alive.

The call chain at the moment P executes is main, then R, then Q, then P. Searching outward from P, the first activation declaring x is Q, whose local x is 15.

P therefore prints 15. Note that R's x of 25 is also active but is further out in the chain, so Q's declaration shadows it.

The two answers differ because static scope reads the program text and dynamic scope reads the call stack. Changing which procedure calls P changes the dynamic answer and leaves the static one untouched.

This is precisely why static scope dominates. A reader of P can determine what x means by looking at the enclosing text, without enumerating every possible caller, and the compiler can resolve the name to a fixed location so the access costs nothing at run time. Dynamic scope requires searching the chain on every access.

Question 6

Procedures are nested as A containing B containing C, and also A containing D. If D calls C, how is C's access link set, and how does C reach a variable declared in A?

Accepted Answer

Establish the nesting depths first. A is at depth 1, B and D are both at depth 2, and C is at depth 3.

When D calls C, the access link of C's new frame must point to the most recent activation of C's immediate lexical parent, which is B — not D, even though D made the call.

The caller computes this from the depth difference. D is at depth 2 and C is at depth 3, so C is nested one level deeper than D. Since D is not C's lexical parent, D cannot supply its own frame. It must follow its own access link chain to reach depth 2 minus 1, that is depth 1, and then the runtime finds the appropriate depth-2 activation of B.

In practice this case reveals a problem: if B has no active activation at all, C cannot legally be called from D, because C's non-locals in B would have no storage. Languages permitting this pass C as a closure carrying its defining environment, which is exactly what an access link records.

For reaching a variable in A: A is at depth 1 and C is at depth 3, so the variable is two levels out.

C follows its access link to B's frame, then B's access link to A's frame, then applies the compile-time offset of the variable within A's frame. Two dereferences plus one offset.

With a display instead, A is at depth 1, so C reads display entry 1 directly and applies the offset — one lookup regardless of the depth gap. The cost is that every procedure entry must save the display entry for its own depth and restore it on exit.

Question 7

Compare reference counting and mark-and-sweep on cycle handling, pause behaviour, fragmentation and cost distribution, and state when each is preferable.

Accepted Answer

On cycles, reference counting fails and mark-and-sweep succeeds. Reference counting asks whether anything points at an object; in a cycle the answer is permanently yes, so the memory is never reclaimed. Mark-and-sweep asks whether the object is reachable from the roots, and an isolated cycle is never reached during traversal, so it is swept correctly.

On pause behaviour, the two are opposites. Reference counting reclaims an object the moment its last reference disappears, so memory is returned promptly and there is no stop-the-world phase. Mark-and-sweep does nothing until the heap fills, then pauses the program for a time proportional to the live data plus the heap size. For interactive or real-time systems that pause is the dominant objection.

On fragmentation, reference counting frees objects individually and leaves holes, and mark-and-sweep does the same during its sweep phase. Neither compacts. A copying collector solves this by moving live objects into a contiguous half of the heap, which makes subsequent allocation a pointer bump, at the cost of leaving half the heap unused.

On cost distribution, reference counting charges every pointer assignment with an increment and a decrement, so the overhead is spread thinly across normal execution and is paid even when no garbage exists. Mark-and-sweep charges nothing during execution and everything at collection time.

Reference counting is preferable where predictable latency matters and cycles are rare or manually broken with weak references, which is why it appears in systems programming and in some scripting runtimes. Mark-and-sweep, usually generational and copying, is preferable where throughput matters and cyclic data is common, which is why managed language runtimes use it.

Question 8

Trace the control and access links for the call chain where P contains Q, main calls P, P calls R, and R calls Q. State each link and explain why they differ.

Accepted Answer

Establish the lexical structure first. Q is nested inside P. R is at the outer level alongside P, so R is not nested inside P and Q is not nested inside R.

The call chain at run time is main, then P, then R, then Q, so four frames sit on the stack in that order.

Control links follow the call order exactly, since each points to the frame of whoever invoked it.

P's control link points to main's frame. R's control link points to P's frame. Q's control link points to R's frame.

Access links follow the lexical nesting, since each points to the most recent activation of the immediately enclosing procedure.

P is declared at the outer level, so its access link points to the global environment. R is likewise at the outer level, so its access link also points to the global environment. Q is declared inside P, so its access link points to P's frame.

The divergence is at Q. Its control link points to R and its access link points to P, and the two are different frames.

The reason matters. If Q references a variable declared in P, following the control link would reach R's frame, where that variable does not exist and where some unrelated local occupies the same offset. The read would silently return the wrong value.

Following the access link reaches P's frame, which is where the variable actually lives, and where the compile-time offset is valid.

The general rule is that the control link answers where to return and the access link answers where non-locals live. They coincide only when a procedure is called from its immediate lexical parent, which is why the two-pointer design is necessary rather than redundant.

Question 9

Explain why call by value-result can give two different answers for the same program, and why call by reference cannot.

Accepted Answer

Call by value-result copies each argument into the parameter on entry and copies the parameter back to the argument on exit. Between those two moments the parameter is an independent local variable, and the caller's storage is untouched.

The ambiguity appears when two parameters are bound to the same caller variable, which happens whenever the same variable is passed twice.

Suppose a procedure takes two parameters and modifies both, and is called with the same variable x for each. On entry both parameters receive copies of x's value. During execution the procedure sets the first to 5 and the second to 8, working on independent copies.

On exit both must be written back to x. If the write-back proceeds left to right, x receives 5 and then 8, ending at 8. If right to left, x receives 8 and then 5, ending at 5.

Most language definitions leave the write-back order unspecified, so both outcomes are legal and a program can behave differently on two conforming compilers. That is exactly why value-result is regarded as fragile and why languages using it usually forbid aliased arguments.

Call by reference has no such ambiguity because there are no copies at all. Both parameters are aliases for x itself, so every assignment takes effect immediately and in program order. The first statement sets x to 5, and the second reads the current value of x, which is now 5, and computes from it.

The result is determined entirely by the statement order within the procedure, which the language does specify. No write-back phase exists, so no ordering question arises.

The contrast is instructive: reference has one storage location and immediate effects, while value-result has three locations and deferred effects, and the deferral is what admits ambiguity.

Practice — "Runtime Environments"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities