Re: Q: access to subprogram

[ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe)]

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.