Path: utzoo!mnetor!uunet!mcvax!enea!tut!santra!news
From: news@santra.UUCP (news)
Newsgroups: comp.lang.misc
Subject: Re: Displays (Was:  Var scoping in Wirth-type languages)
Message-ID: <11151@santra.UUCP>
Date: 14 Mar 88 22:26:21 GMT
References: <3821@ihlpf.ATT.COM> <2791@enea.se> <3949@ihlpf.ATT.COM> <7562@sol.ARPA> <4426@june.cs.washington.edu> <7629@sol.ARPA> <4808@sigi.Colorado.EDU>
Reply-To: s30780a@puukko.UUCP (Johan Myreen)
Organization: Helsinki University of Technology, Finland
Lines: 95

In article <4808@sigi.Colorado.EDU> michael@boulder.Colorado.EDU (Michael Schmidt) writes:
>In article <7629@sol.ARPA>, crowl@cs (Lawrence Crowl) writes:

>>Displays require one more load-to-register to implement than do static chains.

I think displays are much more efficient than static chains, for the
following resons:

- When calling a procedure of nesting depth N, you only have to do three
things:

1) Push the value of display element N on the stack. This value is
pointer to the activation record of the last called procedure of
nesting depth N. 

2) Save the address of the newly created activation record in display
element N.

3) Upon return from the procedure, pop the saved value of the display
element. 

Note also, that not even these steps are required if the variables of
the called procedure are not accessed by procedures at nesting depth >
N.
Non-local variables are accessed from the called procedure by
looking in the activation record pointed to by the appropriate display
element. 

Using static chains the computer may have to do a lot more work at run
time.  First, calling a procedure at nesting level N from a procedure
at nesting level M > N involves following M-N+1 access links to find
out the activation record of the enclosing procedure. 
Second, accessing a variable at nesting level N from a procedure at
nesting level M > N also means that you have to follow M-N access
links to reach the activation record of the outer procedure.


>That would be nice. But, it is wrong, unfortunately (as long as
>we have nested procedures and functional parameters, and I like
>this!). How would you implement the correct display, when a
>procedure of depth k calls a functional parameter of say k+n. At
>this moment you have no garanty that the static predecessor or
>the predecessor of the predecessor of the called procedure is in
>the display at all. So you have to reconstruct the display and
>restore it again at return time. How would you do this without
>static chain?

You are right, this can't be done with a display. But as the
subject line says "Wirth-type languages" I can't resist mentioning
that this has been "fixed" :-) in Modula-2. Quoting from "Programming in
Modula-2" (2.ed, p. 79): "... procedures that are assigned to variables
or are passed as parameters, must not be declared local to any
procedure."


>>(Assuming you have enough registers to implement the display.  Most new
>>processors do.)
>
>Well, I always thought, that the MC68020 is a fairly new
>processor. It has not more than 6 address register available for
>it (may be only 5). So if you have a nesting depth of six (not
>very common, but may happen), you have to be very carefull (and
>slow) with address computations.

I don't understand why it is necessary to implement the display using
registers. A display element and an access links in the static chain
are essentially the same thing: a pointer to an activation record on
the stack. But the display has the advantage that its elements always
point directly to the wanted activation record, and not to an
activation record that contains a pointer to another activation record
that may point to the activation record with the sought variable, or
it may point to an activation record that contains a pointer to still
another activation record that...

Also, the display can be allocated in static memory, with fixed
addresses.

>>To convince me that displays are not worth the cost, you must show
>>me hard data indicating that non-local references are not much used.
>
>[hard data omitted]

But there is no cost, if you don't use non-local references. See above.

>
>	Michael Schmidt
>--
>Michael Schmidt, Universitaet-GH Paderborn, FB 17, Warburger Str.100,
>                 D-4790 Paderborn, West Germany
>z.Zt.: University of Colorado, Boulder
>Mail: michael@boulder.UUCP    or    michael@boulder.Colorado.EDU

Johan Myreen
s30780a@puukko.hut.fi
...!mcvax!santra!puukko!s30780a