From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,99ab4bb580fc34cd X-Google-Attributes: gid103376,public From: ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) Subject: Re: Q: access to subprogram Date: 1996/07/10 Message-ID: <4rvnbr$amu@goanna.cs.rmit.edu.au> X-Deja-AN: 167538947 references: <4rb9dp$qe6@news1.delphi.com> <4re2ng$t7u@wdl1.wdl.loral.com> <4rqbo9$b02@goanna.cs.rmit.edu.au> organization: Comp Sci, RMIT, Melbourne, Australia nntp-posting-user: ok newsgroups: comp.lang.ada Date: 1996-07-10T00:00:00+00:00 List-Id: I wrote, apropos of the claim that using displays made it hard to implement procedures as (non-generic) parameters: "This puzzles me mightily. Burroughs Algol for the B6700 used a single global display (actually a dedicated bank of 32 registers; reduced to 16 on later models). In fact, all languages on that machine did, including Fortran, PL/I, and Pascal. Now Algol, Fortran, PL/I, and Pascal all allow procedures to be passed as parameters, and in Algol, PL/I, and Pascal those procedures can be nested." dewar@cs.nyu.edu (Robert Dewar) writes: >If it puzzles you, you should probably go back and reread a good book >explaining all this. I strongly recommend the (admittedly somewhat >obsolete) book by Gries, the treatment of displays is very clear here. I am getting just a little bit tired of insults. I *have* Gries. I've read it. I've even worked on a Pascal compiler (that admittedly was never deployed) that used a display. In fact, getting procedures as (non-generic) parameters right was the show-stopper that prevented the compiler being deployed (by the time we fixed the design, a better *finished* compiler was available). >The whole point of using a single global display is that you only need >to change (at most) one element at a time). The general use of procedure >parameters in Pascal or Algol, if done right, clearly violates this, and >requires entire sections of displays to be saved and restored. Exactly so. *BUT* it can be implemented without any *distributed* cost. The parent of a procedure that will be passed as a parameter keeps a copy of the relevant section of the display; such a child is passed as a pair (pointer to copy of display, pointer to wrapper procedure), and the wrapper procedure saves the current section, resets the display, calls the real child, restores the display, and returns the child's result. If the child is not called directly (the usual case) it can be integrated in the "wrapper". And another minor optimisation turns the "parent is at lex level 1" common case into exactly the same thing as passing a static link. >Maybe the 6700 hardware took care of it, but there is no magic, if it >was done right, then it requires saving and restoring chunks of displays >(or worse still replicating them in stack frames). This is indeed less >efficient than static displays. It can be implemented with distributed overhead (as the B6700 did, if I recall correctly) with a static link as well as a dynamic link and a return address in every (non-leaf) frame. But it can *also* be implemented with "lumped" overhead so that the overhead for programs or procedures NOT using this facility is ZERO. The overhead for a procedure at lexical level N is roughly 6N memory references per indirect call. This is less efficient than the single static link approach, but (a) it can be retrofitted into a single global display system, in such a way that existing library units that do not use the facility generate EXACTLY the same code as before, and (b) doing it this way is INFINITELY more efficient than not doing it at all! In any case, this display resetting is precisely a context switch, and guess what: Ada has tasking, necessitating either a display per task or a display reset per context switch _anyway_. In fact, one of the claimed advantages for the way the B6700 did it was that it unified the treatment of tasks and procedures in an approach that was very simple to use and to generate code for. >Steelman specifically excluded procedure parameters. One of the stated >reasons was to allow the use of simple mechanisms (i.e. displays) to >handle uplevel references. Ada 83 followed this design choice, and >Ada 95 did not. A reasonable change, but the inevitable possible >consequences was that displays would not fit well. I am sorely puzzled that I have to say this: procedures as formal parameters *can* be implemented without *distributed* overhead in a static display architecture; the result is less efficient than alternative architectures might have been, but it is MORE efficient than not doing it. >No one has forgotten anything here: this stuff is pretty well understood. Not as well as it might be, apparently. >The one thing that Gries misses, which is critical for the efficiency of >handling displays, is that you do NOT need to modify the display if the >procedure you are calling has no nested procedures. This is a common case, >and is missed by most (all?) text books and is absolutely critical for >efficiency comparisons. I felt so strongly about this issue that I started writing an article on variants of the BCPL and Algol models. I actually wrote some notes about this particular optimisation yesterday, and read your article at 5:40+ today. It's >In other words, the usual invariant for level N of a global display is >that it points to the most recent level N procedure on the dynamic >invocation scheme. >The modification is that the invariant adds "that contains nested >procedures" after the word procedure in this invariant. >(I am also assuming that the frame pointer is separate from the display, >as is typical practice). What you are describing is what I've called "the hybrid BCPL/display model" in which the value that would have been in D[n] is actually in the L register. To summarise: if an Ada 83 compiler used a simplified single static display model in which every procedure entry/exit changes/restores a single display element, and in which activation records are not threaded with static links, then procedures (and functions) as (non-generic) formal parameters in the style of Fortran, Algol 60, Pascal, PL/I, Simula 67, ... COULD have been implemented with *no* distributed cost; calling the parent of a passed-procedure would have overhead; calling a formal procedure parameter would have overhead; but these overheads would only be incurred in programs using the new feature. This means that the implementation argument against the feature is bogus. -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.