Re: Add nested-function support in a language the based on a stack-machine

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>George Neuner <gneuner2@comcast.net> writes:
>>I'd really like to see that paper to find out what they are comparing
>>to display [and using what language].
>
>The language was probably Algol or one of it's direct offspring.
>
>Anyway, if I get around to it, I will search for a reference to the
>paper in our library, but if someone else can supply the reference,
>that would be cool.


I looked in some older compiler books, but did not find a reference to
such a paper. What I found:


* Aho and Ullman (1977) only mention displays as ways to implement
    static scoping.


* Aho, Sethi, Ullman (1986) also mention access links (static links).


* Fischer and Leblanc (1988) discuss both, and say the following:


    |For example, a study of reference patterns in a wide variety of
    |Simula 67 programs (Magnusson 1982) found that fully 80% if all
    |references were to variables at the outermost level or to local
    |variables. Another 17% of the references were to the block
    |immediately surrounding the local one. [...] Thus few references
    |will actually require following the static chain, and most of those
    |will require only one level of such indirection.


    |Magnussen, K. 1982. "Identifier references in Simula 67 programs."
    |Simula Newsletter 10(2):


    They do not write about performance disadvantages of displays,
    though.


I also looked if I could find Wirth's response to Cohen's paper, and I
found it:


<https://dl.acm.org/citation.cfm?id=214521> (probably behind a paywall
for many).


And there he gave the reason for not using a display for accessing
non-local variables:


  |Upon closer analysis, we decided to discard the use of a display
  |that was already in our first Pascal compiler (1969). The reason
  |was that (1) the display requires updating for every procedure call
  |and return (!) that causes a change of context, and (2) variables at
  |intermediate levels (neither local nor global) are referenced quite
  |rarely. As a result, the maintenance of a display turned out to be
  |more costly than the inefficient access of nonlocal variables via a
  |static link.


So apparently there was no influential paper in the 60s or 70s that
damned the display. Wirth and his collaborators discovered the
performance disadvantages of displays by original research, but
apparently did not publish this piece of knowledge before 1991.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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