Path: utzoo!mnetor!uunet!husc6!hao!boulder!michael@boulder.Colorado.EDU
From: michael@boulder.Colorado.EDU (Michael Schmidt)
Newsgroups: comp.lang.misc
Subject: Re: Displays (Was:  Var scoping in Wirth-type languages)
Message-ID: <4808@sigi.Colorado.EDU>
Date: 12 Mar 88 20:09:14 GMT
References: <3821@ihlpf.ATT.COM> <2791@enea.se> <3949@ihlpf.ATT.COM> <7562@sol.ARPA> <4426@june.cs.washington.edu> <7629@sol.ARPA>
Sender: news@sigi.Colorado.EDU
Reply-To: michael@boulder.Colorado.EDU (Michael Schmidt)
Organization: Uni-GH Paderborn, FB17/Informatik
Lines: 81
Summary: Wrong, guys, display is really unnecessary
In-reply-to: crowl@cs.rochester.edu (Lawrence Crowl)

Posting-Front-End: Gnews 1.1


In article <7629@sol.ARPA>, crowl@cs (Lawrence Crowl) writes:
>In article <4426@june.cs.washington.edu> pardo@uw-june.UUCP
>(David Keppel) writes:
>)(Paraphrasing) from compilers class:
>)
>)    "Displays are a really great idea, but are too expensive to
>)    implement to be useful for Algol-class languages."
>)
>)Where "too expensive" is measured in terms of the cost of maintaining
>)one over each procedure call versus the performance penalty for scanning
>)up the dynamic links.
>
>Displays require one more load-to-register to implement than do static chains.

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?

>(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.

>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.

Take a look in the PhD thesis of Lynn Carter, Univ. of Colorado,
1980. He analysed pascal programs and found out, that of all
references to variables 56.47% are for global ones (under unix in
bss or data memory, no chain involved), 36.66% to local ones
(obviously no chain involved) and 5.97 to local-1 ones (one step
in the chain). All others accounted for 0.9% and I think that is
not so much.

In article <758@cresswell.quintus.UUCP>, ok@quintus (Richard A. O'Keefe) writes:
>You don't even need a full display.  Just retain a pointer to each level of
>the display you actually need.  E.g.
>	
>program main(..); var x;
>    procedure one(...); var y;
>	procedure two(...); var z;
>	    procedure three(...);
>		begin {use x and y but not z}
>		end;
>
>-->
>	    procedure three(...);
>		var one_ptr: ^frame of one;
>		begin
>		    one_ptr := self^.parent^.parent;
>		    {use global^.x and one_ptr^.y}
>		end;
>
>Any Pascal compiler which searches the static chain on every non-local
>variable reference is a toy.

See above. Non local variable don't really exist.

But, that is nothing other than keeping a local display per
activation record. But for that you have to maintain a static
chain.

I really see no possibility to implement pascal without static
chain.

	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