peterr@utcsrgv.UUCP (Peter Rowley) (10/17/83)
I've been teaching some second year CS students about block-structured
languages and covered static links vs. displays. When two mechanisms
like this coexist, one expects to find a tradeoff between them, but I
am at a loss to explain the tradeoff (fortunately, the students didn't
ask!). As far as I can tell, a display takes only slightly more space
(one address per lexical level (the static link in the activation record
is replaced by the old display entry that the invocation set)) and is
always faster. So, what is the advantage to static links that I'm missing,
or why are they ever used? Non-technical reasons are welcome.
peter rowley, University of Toronto Department of C.S., Ontario Canada M5S 1A4
{cornell,watmath,ihnp4,floyd,allegra,ubc-vision,uw-beaver}!utcsrgv!peterr
{cwruecmp,duke,linus,decvax,research}!utzoo!utcsrgv!peterrmark@cbosgd.UUCP (Mark Horton) (10/18/83)
One advantage to static links is that, if you decide to put displays and/or links in registers (a very reasonable way to do it), if you use static links you need only 2 registers (global and static links), but if you use displays you must allocate N registers, where N is the deepest procedure nesting you can handle (or that occurs in the program, if your runtime system knows about the specific program).
kurt@fluke.UUCP (Kurt Guntheroth) (10/19/83)
[ Why are displays any better/faster/different than static links? ]
If your machine supports the right addressing modes, uplevel addressing is
faster with a display than it is with a static link.
To get to the activation record of the procedure n lexical levels above the
current function activation, you must perform n levels of indirection through
the static link. With a display, you simply indirect (once) through the display
at the lexical level you want.
--
Kurt Guntheroth
John Fluke Mfg. Co., Inc.
{uw-beaver,decvax!microsof,ucbvax!lbl-csam,allegra,ssc-vax}!fluke!kurtwhm@arizona.UUCP (Bill Mitchell) (10/20/83)
I believe that the primary advantage of static links is that they are
easier to implement and understand. This advantage is probably only of
worth from a pedagogical standpoint and thus one would hope to see
displays used in "real" language implementations.
The need for displays (or static links) is one of the several obvious
disadvantages of "block-structured" languages.
Bill Mitchell
whm.arizona@rand-relay
{kpno,mcnc,utah-cs}!arizona!whmbhaskar@fluke.UUCP (K.S. Bhaskar) (10/21/83)
I found displays to be much easier to understand than static links (many years
ago, I had to work through a complicated example to finally convince myself
that they work). As I see it, the only advantages of static links are (a) no
limit to the nesting of scope and (b) practicality. The first is obvious.
For the second, most programs tend to access mainly locals and globals, most
computers have a limited number of registers to expend on displays and have
efficient access to locals on the stackframe, so static links tend to be quite
sufficient.
Personally, after reading an article (I think it was by David Hanson a couple
of years ago), I became a convert to the idea that nested scoping is harmful.
Besides, it doesn't solve any of the real problems in programming -- I find
issues like classes, dynamic storage allocation, run-time binding, etc. to be
far more important in programming than static scoping.
One advantage of displays over static links not mentioned earlier is in
debugging a compiler that generates code that causes a program to throw up all
over itself and its stack.
{allegra,lbl-csam,microsoft,sb1,uw-beaver}!fluke!bhaskarmark@umcp-cs.UUCP (10/21/83)
Displays also have a slight runtime cost over static links during subroutine
call/return, and require the compiler developer to know how to use them.
--
spoken: mark weiser
UUCP: {seismo,allegra,brl-bmd}!umcp-cs!mark
CSNet: mark@umcp-cs
ARPA: mark.umcp-cs@CSNet-Relaychip@dartvax.UUCP (10/21/83)
To be brief, displays are better if you expect many references
to variables outside the current scope; other ways are better
if such references are rare.
The problem with displays is that they require some amount of
work for every procedure call and return. Analysis has
shown that most programs use only local variables and global
variables--variables declared in some intermediate nesting
are seldom referenced.
Probably the most efficient scheme to date is Tanenbaum's,
which keeps only a local and global stack frame pointer;
other frames are accessible through a static link.
Modern optimizing compilers rarely use the display mechanism,
since procedure calls are heavily used in current programming
practice, and must be quite fast.
See: "Implications of Structured Programming for Machine
Architecture", A.S. Tanenbaum, CACM, March 1978.
chip elliott ....decvax!dartvax!chip