baskett@decwrl.UUCP (Forest Baskett) (10/22/83)
Displays are always faster than static links (except in pathological cases) provided the compiler exercises a little bit of intelligence when generating code for procedure entry and exit. The previous discussions make clear that displays are faster for referencing non-locals/non-globals but some of them suggest that procedure calling suffers more from displays than from static links. In fact, the reverse is usually true. Here's why. Most procedures do not do non-local/non-golbal referencing so if we could find a way to call and return from those procedures without any action related to lexical scoping, we would, 99% of the time, be on the same footing as languages without lexical scoping (e.g., C). The display enables us to do that if the compiler cooperates. If I'm a procedure and I have local variables that some other proceudre is going to access (notice that this other procedure must be defined inside me), then when I am entered, I must save the display pointer to my lexical level that existed at entry and replace it with a pointer to my locals. When I exit, I need to restore the old display pointer. Now here's the flip side. If I'm a procedure and NO OTHER procedure references my locals (the usual case), then I can blithly DO NOTHING about the display pointer to my lexical level. I can leave it along, not touch it, not execute any instructions associated with it. When I exit, everything will be fine, no matter who I've called in the meantime. (This is an inductive argument.) Can the compiler easily tell if no other procedures reference my locals? Well, some compilers actually can and most compilers can be fixed so that they can. Remember that the only procedures that can reference my locals are those that are defined INSIDE me. Thus when the compiler gets to the point of generating code for my body, it will have seen all the procedures that have any chance of referencing my locals. If it watches for non-local/non-global references as it processes those procedures and marks the current procedure being compiled at a lexical level that does experience a non-local/non-global reference, then when it gets to my body there will be a flag that tells it whether to bother with the display or not on my entry and exit sequences. A less demanding but almost as effective strategy is to just key off the presence or absence of enclosed procedures. If there are no procedures defined inside me (a very common case), then I don't need to do display maintenance. I've used this trick on several compilers now and it works and is very effective. I can't imagine ever using static links. I don't know where this trick comes from but I'm pretty sure it's pretty old. I have a very foggy recollection of Edsgar Dijkstra telling Burroughs Corporation how to do it for their Algol 60 compiler. It's too bad it doesn't ever seem to be mentioned in compiler books. Forest Baskett ...!decwrl!baskett
bhaskar@fluke.UUCP (K.S. Bhaskar) (10/25/83)
yes, i also used the display optimization technique mentioned in an
interpreter that i wrote some years ago, and, like all hackers, i
(re-)invented it from scratch! actually, maybe i am missing something, but
with any machine with a reasonable stack architecture (which eliminates only
one major line of machines), saving and restoring a display should actually
take less work than setting up a static link, since displays are global and
the static scope level of a procedure is known at compile-time and is constant.
{allegra,lbl-csam,microsoft,sb1,uw-beaver}!fluke!bhaskarmjl@ritcv.UUCP (Mike Lutz) (10/26/83)
I sent a note to utcsrgv!peterr on this subject, showing one case where I think static links are a win over saving the previous value of for display level 'N' in the activation record of a procedure called at level 'N'. (Whew -- sorry about the run-on sentence.) The problem arises when formal procedure parameters are supported in the language. In such cases, when a procedure is passed as an argument, the actu- al information passed must include the entry point to the procedure's code, its lexical level, and some encoding of the accessing environment at the time of the call. It is this last requirement which motivates the use of static links. With static links, all that need be passed is a pointer to the sur- rounding parent's activation record; when the procedure is eventually invoked, the display can then be reconstructed by traversing the static link chain be- ginning at this point. Without the static chain, the entire display up to and including the parent's lexical level must be passed. One must, of course, evaluate the cost/benefit ratio in light of the expected frequency of such constructions. It is worth noting that there are program- ming styles that attempt to provide a modicum of information hiding in block structured languages by using procedure parameters. If anyone has a solution to this problem that is both space efficient and doesn't require static links, I'd like to know about it. Mike Lutz ritcv!mjl
paulh@tektronix.UUCP (Paul Hoefling) (11/03/83)
> actually, maybe i am missing something, but > with any machine with a reasonable stack architecture (which eliminates only > one major line of machines), saving and restoring a display should actually > take less work than setting up a static link, since displays are global and > the static scope level of a procedure is known at compile-time and is constant. There is one minor problem with this statement, the static scope level of all procedures is known at compile time *only* if the entire program is compiled at once (ala standard Pascal) with a language that allows separate compilation, this ain't necessarily so... Happy computing... Paul Hoefling (...!teklabs!tektronix!paulh - usenet) (paulh at tektronix - csnet) (AB00PLH on Cyber)