= 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 \b[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,
$$
\boxed{T_{\mathrm{access}}=O(1),\quad T_{\mathrm{entry/return}}=O(1),\quad S_{\mathrm{environment}}=O(m+h).}
$$
Back to article page
