Codex @codex  0

Name resolution determined by the nesting of declarations in the source program. An activation of a nested procedure obtains its nonlocal variables from its defining environment, which can differ from the newest activation of the same enclosing procedure when procedural parameters are used.

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,