Runtime environments

Runtime storage organization

Definition. A running program commonly uses code/text, static or global data, a run-time stack, and a heap. Static data has a fixed lifetime; stack storage supports nested procedure activations; heap objects can outlive a call and have dynamic lifetimes.

Example. A local integer may live in an activation record, while an object allocated with new may live in the heap.

Exam point. “Stack allocated” describes lifetime and allocation discipline, not necessarily the physical direction of address growth.

Solved examples

Example 1 — classify objects. A program has a global table, local variable x in f, and dynamically allocated node p.

1. The global table has program-wide lifetime and belongs to static/global storage.
2. x is created when f is called and removed when that activation returns: stack frame.
3. The node's lifetime is controlled by allocation/deallocation, not f's return: heap.
4. Storage classes: static, stack, heap respectively.

Activation records

Definition. An activation record, or frame, stores information for one procedure call: parameters, return value or address, saved registers, local variables, temporaries, and links. Exact fields and order depend on the calling convention and compiler.

Example. Recursive calls to factorial create distinct frames for n=4,3,2,1.

Exam point. Each recursive call has its own locals and return point, even though all calls execute the same code.

Solved examples

Example 1 — recursive depth. Function f calls itself once with n−1 until n=0. For f(4), how many active frames exist at maximum?

1. Calls are f(4), f(3), f(2), f(1), f(0).
2. The base call f(0) is active while all previous calls wait.
3. Maximum simultaneous frames is five.
4. Answer: 5 frames.

Example 2 — return addresses. Why must f(4)'s frame preserve a return location while f(3) executes?

1. f(4) is suspended at its recursive call.
2. When f(3) returns, control must resume immediately after that call in f(4).
3. The return address identifies that instruction.
4. Each activation stores its own continuation.

Stack allocation and calling sequence

Definition. A call sequence passes arguments, saves caller state as required, creates a frame, transfers control, and records a return address. A return sequence places the result, restores saved state, removes the frame, and resumes the caller. Caller-save and callee-save conventions divide register preservation responsibility.

Example. A caller-save register is saved by a caller if its value is needed after a call that may overwrite it.

Exam point. The exact frame layout is convention-dependent; reason from the stated convention.

Solved examples

Example 1 — stack state. Main calls f, then f calls g. Show the conceptual active stack.

Stack top	Activation	Suspended caller
top	g	f
below	f	main
bottom	main	—

1. Main's frame remains while f executes.
2. f's frame remains while g executes.
3. Returning from g pops g, then returning from f pops f.
4. The return order is last-in, first-out.

Example 2 — caller save. Register R holds a live value in caller P. P calls Q, which may overwrite R.

1. P needs the old value after Q returns.
2. Under caller-save convention, P stores R before the call.
3. After return, P restores R if needed.
4. If P does not need the old value, it need not save it.

Access to nonlocal variables

Definition. In lexically nested procedures, a nonlocal variable belongs to an enclosing lexical scope. A static (access) link points to the frame of the lexically enclosing procedure; following a fixed number of static links reaches the declaration environment. A dynamic (control) link points to the caller's frame.

Example. A procedure nested two lexical levels below the declaration follows two static links to reach an outer variable.

Exam point. Static links reflect source nesting; dynamic links reflect the run-time call chain, and those chains can differ.

Solved examples

Example 1 — follow static links. Procedure P at level 1 declares x. Q is nested in P at level 2; R is nested in Q at level 3. R references x.

1. R's frame has a static link to Q's frame.
2. Q's frame has a static link to P's frame.
3. Follow two links and access x at P's frame offset.
4. Static-link distance is 2.

Example 2 — distinguish links. Main calls P, then a separate top-level Q. Q references a variable declared in Main.

1. Dynamic link from Q points to P because P called Q.
2. Static link from Q points to Main because Main is its lexical parent.
3. The links differ: dynamic→P, static→Main.

Displays

Definition. A display is an array of pointers to the most recent activation record at each lexical nesting level. It can provide constant-time access to a nonlocal variable's level, while calls must save and restore the display entry for the callee's level.

Example. A reference to a level-1 variable indexes display[1] and adds the variable's known offset.