Re: Q: access to subprogram

[dewar@cs.nyu.edu (Robert Dewar)]

Richard O'Keefe said

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

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.

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.

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.

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. However, Ada 95
adopted a consequence that allowed most useful uses of procedures
as parameters, but did not result in making displays inefficient.

By the way, over the years, many Pascal and Algol compilers have cheated.
YOu have to write a bit of a clever test program to see the difference
between properly restoring the full display environment and not bothering.

No one has forgotten anything here: this stuff is pretty well understood.
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.

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