Re: Stack frames & static predecessors

Gene <gene.ressler@gmail.com> writes:


> John's note on displays great. A display is conventionally an array
> of pointers to stack frames of lexically enclosing scopes. Another
> technique connects successive lexically enclosing scopes in a linked
> list (actually a child-to-parent-connected tree if you look at it
> globally). For this purpose, each scope contains a pointer called a
> "static link" (vice the dynamic link, which always points to the next
> lexically enclosing scope, regardless of its lexical nesting).
    ^^^^^^^^^ I think that's a typo -- you meant "dynamically"
That is, the dynamic link points to the caller's stack frame.
The static link points to the stack frame of the procedure
that statically encloses the callee.


> Displays can access any scope with at most one dereference. Static
> link chains need one dereference per scope, a small performance
> penalty.


Right, but for many languages and programming styles, the number of
links traversed is typically small -- an average of approximately one
link. Furthermore, multiple references to the same outer scope can be
optimized (I'm thinking of a loop that references an outer variable --
you only need to chase down the chain once).


You also need to consider the overhead of managing the display.


>...But static link chains make function/procedure pointers and
> arguments simpler.


Yes. Simpler and more efficient.


>...Pointers to functions/procedures that access variables outside
>their body scopes are really structures (sometimes called thunks)
>containing the usual code pointer plus pointers to enclosing scopes.
>For a linked list only the end of the chain is needed; for displays,
>something fancier.


Right. The length of the display is the max nesting depth, which is not
known until link time (unless you arbitrarily limit nesting depth).


- Bob

Return to the comp.compilers page.
Search the comp.compilers archives again.