problems with Static Chaining in a compiler

Question

One criticism of using the static chain to access nonlocal variables is that references to variables in scopes beyond the static parent cost more than references to locals. The static chain must be followed, one link per enclosing scope from the reference to the declaration. Fortunately, in practice, references to distant nonlocal variables are rare, so this is not a serious problem. Another criticism of the static-chain approach is that it is difficult for a programmer working on a time-critical program to estimate the costs of nonlocal references, because the cost of each reference depends on the depth of nesting between the reference and the scope of declaration. Further complicating this problem is that subsequent code modifications may change nesting depths, thereby changing the timing of some references, both in the changed code and possibly in code far from the changes.

Are there any more potential problems with this approach?

Answer 1

Excluded two problems are: A nonlocal reference is slow if the number of scopes between the reference and the declaration of the referenced variable is large. Time-critical code is difficult, because the costs of nonlocal references are not equal, and can change with code upgrades and fixes.

However, the static chain must be modified for each subprogram call and return. The action required at a subprogram call is complex. Although the correct parent scope is easily determined at compile time, the most recent activation record instance of the parent scope must be found at the time of the call. The long walk through the static chain would be an overhead. Some alternatives to static chains have been developed, most notably an approach that uses an auxiliary data structure called a display (Static chain is better, unless the display can be kept in registers). However, none of the alternatives has been found to be superior to the static-chain method, which is still the most widely, used approach. Also, deep access which also superior in dynamic scoping acts in a similar way in creating the dynamic link.

Answer 2

This question sounds damn familiar (homework-esque if you will) so I'm going to take a cautious approach in answering and tell where to focus your search.

Static Chaining implements Static Scoping. One is a concept, the other is how that concept is implemented. I recommend using algebra's associative property and going from there. :)

And just in case Static Scoping needs a little additional clarification: http://hoolihan.net/blog-tim/2009/02/17/static-vs-dynamic-scope/

Answer 3

This seems like much ado about little.

I had to implement this for the Modula-3 C backend.

So I have observations:

• You can amortize the cost. If an "uplevel local" is accessed frequently in a function, you can cache its address in a local/register. I did not implement this.
• This is exceedingly rare stuff.
  • Programming languages supporting this are rare (Modula-3. Modula-2? Pascal? Not any of C, C++, Rust, Go..)
  • Within those languages, nested functions are fairly rare.
  • Within those nested functions, access to uplevel locals is furthermore rare.
  • And then rarely performance sensitive.

So it never really matters.

I don't understand what is "display" vs. "static chain". Aren't these the same thing?