+ When using static and dynamic chains, what language features would
force you to use a new link when entering a block, rather than only when
entering a function?
?
+ Static chains connect the set of stack frames in each dynamic
environment as a tree. Access to a particular stack frame in the static
environment means we must follow the links in the current chain, so access
is O(number of statically nested frames).
?
<top of 2nd column>
An alternative algorithm is to use a display, which is cheaper at each
access, but which is harder to keep correct as the static and dynamic
environments change. The idea is to keep an array (the display), whose
elements are copies of the static links for the current static environment
(i.e. the static chain that links together the currently accessible stack
frames). As these links are in an array rather than a list, access is O(1).
Using the examples above, draw the display required for each stack frame,
and so design an algorithm that will maintain the display correctly on
function entry and exit. There is more than one possibility (e.g. does each
stack frame have its own display, or is their one global display). List all
those you can think of, and try to analyse their relative merits. How would
you implement a function passed as a parameter?