The surviving call stack, from oldest to newest, is main, p, r, s, q. A dynamic link identifies the caller's stack frame, whereas a static link identifies the current activation of the lexically enclosing procedure. These need not identify the same stack frame.

Figure 1.
The call stack during `q`, with dynamic links on the left and static links on the right; arrows point to older stack frames
. **Details**.

The dynamic chain is

q ⟶ s ⟶ r ⟶ p ⟶ main .

(1)

The individual static links are

q ⟶ p, s ⟶ r, r ⟶ p, p ⟶ main .

(2)

main has no enclosing procedure; its links can be null. The p stack frame contains t=3 and x=3, and the q stack frame contains y=3. Return addresses are code addresses, not links to another stack frame. In particular, q returns dynamically to s while obtaining x statically from p.

b

 0  0

Solution

 0  0

We specify a small stack machine instruction convention because the paper does not prescribe instruction spellings or numeric stack frame offsets. PUSHFP pushes the current frame pointer. LOAD k replaces a stack-top frame address by the value at fixed offset k in that frame. Let SL be the static link offset, X the offset of p's x, and Y the offset of q's parameter y. ADD pops two integers and pushes their sum. RETVAL returns the stack-top value, removes the current activation and restores the caller through the usual calling convention.

PUSHFP       ; address of q's frame
LOAD SL      ; q's static link: address of p's frame
LOAD X       ; value of p.x
PUSHFP       ; address of q's frame, above x
LOAD Y       ; q's local parameter y
ADD          ; x + y
RETVAL       ; return the sum to s

One static link traversal suffices for x, despite three intervening calls in the dynamic chain. y is local to q. In this execution the two loads produce

3

and

3

, so the returned integer is

6

c

 0  0

Solution

 0  0

Continue the instruction convention above. The current stack frame is now s's. Its static chain passes through r to p; q is declared directly inside p, so the new q activation must receive a static link to that same p stack frame. Let T be the offset of p's parameter t.

Define CALL q,1 to expect, above the pre-existing evaluation stack, the static link for q followed by its one argument. It consumes these, creates q's stack frame with its dynamic link pointing to the current s activation, and leaves one return value when q returns. This explicit convention avoids dependence on a particular real instruction set architecture.

PUSHFP       ; s
LOAD SL      ; r
LOAD SL      ; p, the required static parent of q
DUP          ; preserve p for CALL while also using it to read t
LOAD T       ; replace the duplicate p address by p.t
CALL q,1     ; q(p.t), with static parent p and dynamic caller s
RETVAL       ; return q's result from s to r

Immediately before CALL, the evaluation stack ends in p-frame, 3. Two static link traversals find both the argument's environment and the environment to pass to q. In terms of the hidden argument and ordinary argument,

SL_{q} = frame_{p}, y = t = 3.

(1)

An implementation that places the hidden static link after the ordinary argument could use a different ordering of these same operations.

d

 0  0

Solution

 0  0

Use mathematical induction on the sequence of call and return events. The invariant concerns the static chain of the currently executing activation: every stack frame on that chain is the most recent surviving activation of the procedure it represents. It need not hold for the saved chain of an arbitrary suspended caller while a recursive callee is running.

Initially only main is active, so the claim holds. Suppose it holds just before a direct call to a procedure

R

, whose lexical parent is

P

. Without procedural parameters, visibility of

R

means that its declaration lies in the current procedure or in a lexically enclosing procedure. Therefore the activation of

P

needed for the call is on the caller's static chain. By the induction hypothesis, it is the newest surviving activation of

P

Create a new activation of

R

whose static link points to this

P

activation. The inherited chain is a suffix of the caller's chain, so its stack frames still represent the newest surviving activations of their procedures. Adding

R

does not make any of those inherited activations out of date:

R

cannot be its own lexical ancestor. The new

R

activation itself is plainly the newest activation of

R

. This covers recursive calls too: an older activation of

R

may survive on the dynamic chain, but is absent from the new activation's static chain.

On return, the callee and every call it made have finished. The caller's saved stack frame and static chain are restored. Any temporarily newer activation of a procedure represented on that chain has returned, so each restored activation is again the most recent surviving one. Thus return preserves the invariant as well.

The claim holds for the executing procedure's static chain throughout every execution using direct calls under lexical scope. Equivalently, writing

P_{F}

for the procedure represented by a stack frame

F

F \in staticChain_{executing} ⟹ F = newestSurviving (P_{F}) .

(1)

e

 0  0

Solution

 0  0

Searching the dynamic chain would require identifying the procedure associated with each visited stack frame. More seriously, the search length is bounded by the number

h

of active calls, not by lexical nesting depth. Recursion in procedures unrelated to the desired enclosing declaration can make

h

arbitrarily large. Thus a single nonlocal variable access can take

O (h)

time complexity, whereas a conventional static chain access needs only

d

traversals for lexical distance

d

Instead give each procedure

P

a known global pointer cell current[P]. On entry to

P

, save its previous value in the new stack frame and set current[P] to the new frame pointer. On return, restore the saved value. A nonlocal variable declared in

P

is then loaded using current[P] and its known frame offset. The proof in part (d) justifies that lookup in the absence of procedural parameters. This is a procedure-indexed version of a display for lexical scope; a conventional display for lexical scope can instead use lexical levels as indices.

With

m

procedures and

h

active calls, the procedure-indexed table needs

O (m)

additional global words and one saved previous pointer per active stack frame, hence

O (h)

activation storage. The saved word can replace the conventional per-frame static link if that link is no longer needed. A conventional static chain has one pointer per active stack frame and no such

m

-entry table. Both schemes retain ordinary dynamic links and return information.

The table gives constant-time nonlocal access and constant-time save/restore work on each entry/return, independently of lexical distance. Conventional static chain access costs

O (d)

per access, and establishing the callee's static link may also require following an appropriate portion of the caller's chain. For a fixed program

d

is statically bounded, but it still affects generated instruction counts. These costs assume constant-cost pointer operations and omit shared ordinary call overhead. For the procedure-indexed table,

T_{access} = O (1), T_{entry/return} = O (1), S_{environment} = O (m + h) .

(1)

f

 0  0

Solution

 0  0

No: a procedural parameter can carry an older lexical environment past a newer recursive activation. Here is typed, Pascal-like pseudocode; a function-valued parameter is represented by a programming closure, comprising code and its defining environment.

procedure dummy(): integer;
begin return 0 end;

procedure P(n: integer; f: procedure(): integer): integer;
    var x: integer;
    procedure Q(): integer;
    begin return x end;
begin
    x := n;
    if n = 1 then return P(2, Q)
             else return f()
end;

begin print P(1, dummy) end.

Call the first P activation

P_{1}

. It sets its own x to

1

and passes the programming closure

(Q, P_{1})

into a recursive activation

P_{2}

. That activation sets its own x to

2

and calls its parameter f. The resulting activation of Q has its static link pointing to

P_{1}

, because that is where the passed procedure was defined. Its dynamic link points to

P_{2}

, because that is where it was called.

During this call the dynamic chain contains Q, P2, P1, main, while Q's static chain contains Q, P1, main. The newest surviving activation of P is

P_{2}

, but the static chain deliberately uses

P_{1}

. Correct lexical scope therefore prints

1

; blindly consulting current[P] would produce

2

. Both enclosing activations remain alive, so no issue of a returned procedure or dangling pointer is involved.

The failed step in part (d) is precisely the assumption that the callee's lexical environment is a suffix of the direct caller's static chain. A passed programming closure can specify a different, still surviving environment. An implementation supporting such calls must preserve that environment; a table implementation requires additional environment installation and restoration rather than merely consulting newest activations.

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 2

a

Solution

b

Solution

c

Solution

d

Solution

e

Solution

f

Solution

 Ancestors (9)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 2

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion