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

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,