Re: Subprogram types vs. "limited access" (was Re: Do we need "Mission-Critical" software? Was: What to Do?

[Robert Dewar <robert_dewar@my-deja.com>]

In article <f5L76.231$Br5.104407@homer.alpha.net>,
  "Randy Brukardt" <randy@rrsoftware.com> wrote:

> The Intel processors include some instructions that were
> intended to be used to manage displays, but they are slower
> than the equivalent regular instructions, so no one uses
> them.

That's misleading. When people talk about displays, they almost
always mean single global displays, whih are updated as each
procedure is called.

The Intel hardware scheme uses local displays, where each
procedure constructs a new copy of the display in its local
stack frame for its own use. This is a very bad method of
doing things period, regardless of whether it is done in
hardware or software.

Many compiler text books still present this entirely poor
way of doing things, and most likely some fellow at Intel
had a compiler course where the instructor stressed this
bad method, and that's how it got into the hardware. The
instruction involved (ENTER with a non-zero level) is
indeed completely useless.

> Unless closures are needed (certainly the normal case)
> displays are quite efficient.

Actually in Ada 83, where pointers to procedures did not exist
(part of the reason for their exclusion in Steelman was an
awareness of this issue), displays are very efficient, much
more efficient than static links. Why?

Because the situation is as follows:

1) with static links, no overhead is required for calls to top
level procedures, but if you call a nested procedure, link
mucking is ALWAYS required.

2) with a display, if you do things right (it requires noticing
a rather special case not discussed in any text book I know of)
then calling a procedure that has no nested procedures has no
overhead, and it is only when a call to a procedure containing
nested procedures is made that display mucking is needed.

Clearly if you have no nested procedures, both methods become
completely efficient. If ther ARE nested procedures, behavior
2) is much more attractive than behavior 1) since dynamically
more calls are to leaf procedures.

> There are a couple of obscure cases in generics that
> require handling closures, so Janus/Ada at least already has
> support for doing that. Those cases are (of course) quite
> expensive.

I suspect that is an artifact of shared generics in Janus/Ada,
I know of no such obscure cases in the Alsys implementation
which used displays throughout.

Personally, I would immediately choose static links if I
decided on shared generics. Furthermore in Ada 95, static
links are really the only approach that makes sense. The
only reason the language was restricted (some would say
crippled, but not me :-) so that displays work was loud
objections from the Alsys and RR folks that their compilers
could not be adapted easily to Ada 95 unless this was the
case.

Note that it is the use of static links that makes the
very useful 'Unrestricted_Access attribute easy to implement
in GNAT.

Robert Dewar

(*) the trick in display management is the following:

The display is used for up level references, but for references
to the current stack frame, you simply use the stack pointer
or the frame pointer as the case may be.

This means you do NOT adjust the current display entry unless
someone might use it. The ONLY case in which someone might use
the entry is if you call one of your own nested procedures, and
if you don't have any nested procedures, then you don't need
to worry about this case.

The normal invariant for a display is that the N'th level entry
is the stack frame of the most recently invoked N'th level
subprogram.

With this (very important) modification, the invariant for
the display is that the N'th level entry is the stack frame of
the most recently invoked N'th level subprogram NOT having
any nested subprograms.


Sent via Deja.com
http://www.deja.com/