Re: Q: access to subprogram

Re: Q: access to subprogram

[Robert A Duff]

In article <4rb9dp$qe6@news1.delphi.com>,  <tmoran@bix.com> wrote:
>Could someone please explain
>  "subprogram must not be deeper than access type".

Here, "deeper" means more nested within a subprogram or block_stm or
task_body.  Nested within a subprogram is the usual problem.

>I want package utilities to offer
>  type p is access procedure(x:in integer);
>and
>  procedure do_stuff(how : in p);
>
>But if my main program 'with utilities' and
>  procedure this_is_how(x:in integer);
>..
>  utilities.do_stuff(this_is_how'access);

Right, that's illegal.  You need to put This_Is_How in a library
package; then it will work.  The main subprogram is a subprogram, and
therefore represents a deeper level of nesting.  You can't take 'Access
of something *inside* a subprogram, and let that pointer value live
outside the subprogram.  Note that Ada tasks can keep running long after
the main subprogram is done.

>I get that message from GNAT 3.04 for DOS.  I also note the same problem
>prevents compilation of the PMV16 OS/2 bindings, and is gotten around
>in the new OS/2 bindings with "this_is_how'unrestricted_access", which
>I don't see in the LRM.  The message indicates an understandable
>problem, but what's the workaround to allow my package utilities to
>offer a do_stuff procedure.

The Unrestricted_Access attribute is indeed not part of the Ada
language.  It is a GNAT-specific extension.  I've used it some in my own
code, I must admit.  It's dangerous, in the sense that if you leave the
scope containing This_Is_How, and then call through the pointer, you
will get nonsense.

During the design of Ada 9X, we proposed a SAFE way of taking 'Access of
more-deeply-nesting subprograms.  To this day, I remain astonished and
sad that this particular feature didn't make it into Ada 95.  After
all, even Pascal has that feature!  And GNU C, which allows nested
functions (unlike standard C) allows this feature.

The work-around is to use generics.  Pass in This_Is_How as an actual to
a generic formal procedure.  This is verbose, and doesn't allow
recursion.  Alternatively, bully your favorite Ada compiler vendor to
support 'Unrestricted_Access.  This is sad, since 'Unrestricted_Access
is inherently unsafe, whereas we know how to provide the same
functionality safely.  Sigh.

Note also that 'Unrestricted_Access on objects is even less safe -- it
can produce a totally meaningless pointer from the start.  I would much
prefer if GNAT had separated these two things into two separate
features.

- Bob

Re: Q: access to subprogram

[Robert Dewar]

"Note also that 'Unrestricted_Access on objects is even less safe -- it
can produce a totally meaningless pointer from the start.  I would much
prefer if GNAT had separated these two things into two separate
features."

Now Bob, let's not get *too* carried away with worrying about the safety
of this feature! 'Unrestricted_Access on an object is *exactly* equivalent
to taking the 'Address of something and then unchecked_converting it to
a pointer, something that was often done in Ada 83 days, but clearly
Unrestricted_Access is preferable since at least it is typed.

As to making two separate features, hmmmm ... after all 'Access itself
in Ada really is used for two totally difference purposes, so the use
of Unrestricted_Access for two similarly different purposes seemed
quite consistent to me :-)

Q: access to subprogram

[tmoran]

Could someone please explain
  "subprogram must not be deeper than access type".

I want package utilities to offer
  type p is access procedure(x:in integer);
and
  procedure do_stuff(how : in p);

But if my main program 'with utilities' and
  procedure this_is_how(x:in integer);
..
  utilities.do_stuff(this_is_how'access);

I get that message from GNAT 3.04 for DOS.  I also note the same problem
prevents compilation of the PMV16 OS/2 bindings, and is gotten around
in the new OS/2 bindings with "this_is_how'unrestricted_access", which
I don't see in the LRM.  The message indicates an understandable
problem, but what's the workaround to allow my package utilities to
offer a do_stuff procedure.

Re: Q: access to subprogram

[Robert A Duff]

In article <4re2ng$t7u@wdl1.wdl.loral.com>,
Mark A Biggar <mab@dst17.wdl.loral.com> wrote:
>If I remember right, it was felt that implementing "closures" (which is the
>solution to this problem) placed an unacceptable distributed overhead
>on programs that didn't use the feature.  Also I think that half the then
>current Ada implementations were using "static links" and the other half
>were using "displays" and implementing "clousers" would have been real
>difficult for one of those groups (the "display" bunch I think).

We're only talking about "downward closures", which means you can pass a
subprogram (or a pointer to it, which amounts to the same thing) to a
subprogram.  Nobody ever seriously proposed that Ada should support full
closures (as in Lisp), where you can *return* a subprogram from a
function.  Full closures means you really have to store "stack frames"
in the heap, in general, rather than on the stack, and garbage collect
them.

The part about static links vs. displays is correct, although I don't
think it was really 50/50.  I think *most* imlementations used static
links.  It is true that downward closures are harder to implement using
displays.  It is certainly possible, however.  I know of a Pascal
compiler that did it.  Downward closures are a standard part of Pascal,
and this particular Pascal compiler used displays.

The issue was not one of distributed overhead, though.  Passing displays
around may be less efficient, but only in the case where the downward
closure feature is actually used.  It would have no effect on the
efficiency of plain vanilla subprogram calls.

The issue was primarily implementation complexity (for those
implementations that use displays).  The inefficiency issue was raised
also (why add a feature if it's going to be so inefficient that noone
can use it?).  The latter argument always seemed bogus to me.  There was
never a distributed overhead argument.

Oh, and of course, there's the "we don't need it" argument.  Passing a
subprogram as a generic formal parameter does almost the same thing,
though more verbosely, and with a lot of space-inefficiency (unless your
implementation knows how to share generics).  Generics can't be
recursive, though.  I remember exactly one instance in my career where I
used recursive downward closures (in Pascal).

- Bob

Re: Q: access to subprogram

[Robert Dewar]

Bob Duff said

"Now, GNAT has gone and provided the same capability, using an
implementation-defined attribute (Unrestricted_Access), but
unfortunately, this attribute allows dangling pointers to subprograms,
unlike either of the above options."

But unfortunately, virtually all the useful uses of Unrestricted_Access,
at least in my experience are cases where your limited mechanisms would
have been insufficient, since we definitely need to be able to assign
these values.

So we would probably have put the attribute in even if the language had
the safe cases. Note that the two safe cases that Bob mentions are in fact
cases where the work arounds required in the current language are pretty
straightforward, so the limited form of the feature proposed in Bob's
note is not very convincing since it provides rather limited capabilities
and no significant increase in expressive power.

Re: Q: access to subprogram

[Robert A Duff]

In article <4re8bj$qfk@krusty.irvine.com>,
Adam Beneschan <adam@irvine.com> wrote:
>It should be noted that the new object-oriented features of Ada 95
>should make subprogram accesses less necessary than before.  Abstract
>types inherently possess subprogram pointers, so it should be possible
>to take advantage of this feature as an alternative to explicit
>subprogram accesses.

Quite right.  The only problem is that it's a bit verbose.

>    procedure P1 is
>        
>        type My_Error_Handler is new Error_Handler with record
>            Error_File : Text_IO.File_Type;
>        end record;

You need to put:

        procedure Handle_Error (Handler : in My_Error_Handler;
                                Message : in string);

here, to avoid freezing rules rearing their ugly head.

>        EH : My_Error_Handler;
>                -- variable name chosen to avoid being fired  :)
>        
>        procedure Handle_Error (Handler : in My_Error_Handler;
>                                Message : in string) is 
>        begin
>            Text_IO.Put_Line (Handler.Error_File, Message);
>        end Handle_Error;
>
>    begin
>        Text_IO.Create (EH.Error_File, ...
>        ...
>        Pack1.Do_Some_Big_Procedure_That_Can_Report_Errors (EH);
>
>This mechanism doesn't let you *directly* store an access to a
>subprogram in a global variable, the way subprogram accesses do; but
>using accesses to Error_Handler objects should let you accomplish the
>same thing.

Right.  Quite often, if you think you want a pointer to a procedure, a
class-wide object is better.

>Once again, my apologies if my Ada 95 syntax is incorrect.  I haven't
>yet learned all the nuances of Ada 95 programming.  Mainly, I wanted
>to discuss the concepts involved; someone else may need to fill in the
>programming details.

You've got the concepts quite right.  No need to apologize for violating
a freezing rule.  ;-)

My only objection to this technique is that it's a lot of verbiage for a
pretty trivial thing.

- Bob

Re: Q: access to subprogram

[Robert Dewar]

OOps, Bob Duff and I are using downward/upward exactly opposite in our
posts on closures, I think Bob is right, and I was wrong. Downward is
the easy one, Upward is the hard one (which has to save parameter
instances).

Re: Q: access to subprogram

[Robert Dewar]

Jon asks:

"Is there an "elevator version" of why people didn't want this in?  Tucker,
if you are reading this, what swayed you to not let this in????  It's
not one of those things that bothers me all that much (well, it hasn't)
but it is indeed curious..."

The history is as follows.

Ada 83 is carefully designed so that a display model can be efficienctly
used for uplevel references (I am talking about a single global display,
or more accurately one display per task).

The above is fact, and is not open to question or opinion :-)

Many people, me included, feel that the display model is more efficient,
especially for Ada programs which are often deeply nested and often
contain up level references. That however is open to argument (although
I think the case for displays is pretty solid). Anyway the correctness
of this argument is not relevant to the point at hand.

Several implementations (notably Alsys and RR), accepting this argument,
use displays for up level references.

Once you introduce unrestricted access to procedures, displays are a bit
of a menace, and probably this tips the scales in favor of static links
(if you believe like me that displays are more efficient, this can also
be read as meaning that the introduction of unrestricted access to procedures
would introduce distributed inefficiency -- but that still is NOT the reason
this feature was excluded).

However, there was a real concern that existing implementations not be too
badly discombobulated by Ada 95, *especially* in the code generatoin
department (remember that a typical vendor like Alsys has one front end
and dozens of backends -- not all compilers are like this, GCC has only
one back end, but many compilers do have myultiple backends).

The discussion centered around this implementation compatibility issue,
with several people (me included) arguing that it would be a serious
barrier to Ada 95 if existing display implementations had this obstacle
thrown up. And that argument carried the day, especially considering
that reasonable work arounds could be found in almost all cases of
proposed use.

Note that this compatibility issue is not just theoretical. The about to be
released version of Ada 95 for NT/Win95 from Tompson (using the Intermetrics
front end), uses displays for uplevel addressing (a consequence is that it
would NOT be easy in this compiler to implement the Unrestricted_Access
attribute).

Re: Q: access to subprogram

[Robert Dewar]

Mark said

"If I remember right, it was felt that implementing "closures" (which is the
solution to this problem) placed an unacceptable distributed overhead
on programs that didn't use the feature.  Also I think that half the then
current Ada implementations were using "static links" and the other half
were using "displays" and implementing "clousers" would have been real
difficult for one of those groups (the "display" bunch I think)."

The displays issue was the real reason. Closures is a difficult term because
it means two totally different things, sometimes distinguished as upwards
closures (easy to do), and downwards closures (more complex, typically
requiring implicit heap allocation).

No one seriously suggested adding downward closures to Ada 95 (although
there is at least one person who loudly proclaims that this was a fatal
mistake and that Ada 95 is useless as a result -- of course you can
find such a person for almost any feature missing from the language :-)

During discussion of the subprogram pointer issue, the term closure was
often used, but in the more restricted ("upwards") sense, but this may
have caused some residual confusion.

(and just in case I give the wrong impression, I fully understand that
full closures, preferably in conjunction with partial parametrization of
higher order functions, lend tremendous expressive power -- for example
Ackerman's function can be written using primitive recursion if you have
these notions around), but I think the capability goes beyond the
appropriate semantic level for Ada -- no doubt that statement should 
set of a mini-thread :-)

Re: Q: access to subprogram

[Robert Dewar]

Adam said

"It should be noted that the new object-oriented features of Ada 95
should make subprogram accesses less necessary than before.  Abstract
types inherently possess subprogram pointers, so it should be possible
to take advantage of this feature as an alternative to explicit
subprogram accesses."

One nice demonstration of this is to look at the approach taken by 
Intermetrics in their Ada 95 compiler that generates JBC. Java does
not have subprogram pointers, but their Ada 95 compiler can exactly
model Ada 95 subprogram pointers by making them correspond to a class
with a method that calls through the "pointer".

Re: Q: access to subprogram

[Jon S Anthony]

In article <Dtxu2p.97F@world.std.com> bobduff@world.std.com (Robert A Duff) writes:

> During the design of Ada 9X, we proposed a SAFE way of taking 'Access of
> more-deeply-nesting subprograms.  To this day, I remain astonished and
> sad that this particular feature didn't make it into Ada 95.  After
> all, even Pascal has that feature!  And GNU C, which allows nested
> functions (unlike standard C) allows this feature.

Bob,

Is there an "elevator version" of why people didn't want this in?  Tucker,
if you are reading this, what swayed you to not let this in????  It's
not one of those things that bothers me all that much (well, it hasn't)
but it is indeed curious...

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[Fergus Henderson]

bobduff@world.std.com (Robert A Duff) writes:

>During the design of Ada 9X, we proposed a SAFE way of taking 'Access of
>more-deeply-nesting subprograms.  To this day, I remain astonished and
>sad that this particular feature didn't make it into Ada 95.

What was the safe way that you proposed?

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Q: access to subprogram

[Robert A Duff]

In article <JSA.96Jul2221357@organon.com>,
Jon S Anthony <jsa@organon.com> wrote:
>Is there an "elevator version" of why people didn't want this in?  Tucker,
>if you are reading this, what swayed you to not let this in????  It's
>not one of those things that bothers me all that much (well, it hasn't)
>but it is indeed curious...

There are two major ways of implementing up-level variable references in
a language with nested procedures: Static links, and displays.  With
displays, it is somewhat difficult to implement passing nested
procedures as parameters, because you have to pass the display, which is
not of compile-time-known size.  Passing a static link is easy -- it's
just a single address.  Some implementations of Ada 83 used displays.
The primary reason for not putting the feature in was to ease the pain
for such implementations.  This was done at a time when the general
feeling was that Ada 9X had more than enough new features, and we
shouldn't be adding things, but removing them.

- Bob

Re: Q: access to subprogram

[Robert A Duff]

In article <4rd5lu$q4@mulga.cs.mu.OZ.AU>,
Fergus Henderson <fjh@mundook.cs.mu.OZ.AU> wrote:
>What was the safe way that you proposed?

There were two variations, actually.

1. Limited access types.  You would say:

    type T is limited access procedure(...);

T would be limited, meaning no assignment.  Without assignment, you
can't create dangling pointers to procedures.  You could pass values of
type T into subprograms, but all the subprogram could do is call through
that value, or pass it on -- not copy it into a global variable.

2. Access-to-subprogram parameters.  You would say:

    procedure Foo(X: Integer; Y: access procedure(B: Boolean));

This syntax is reminiscent of Pascal's.  There would be a run-time
accessibility check on various operations on Y, just like the access
parameters that DO exist in the language (e.g. "Y: access Integer").
This would allow you to pass procedures around, and call them, as in
option (1).  You could also copy them to *local* variables (that is,
inside Foo, you could say "Local := Local_Access_Type(Y)), but any
attempt to copy to a global variable would require some sort of
type_conversion or whatever that would fail the run-time check.

I preferred option (1) at the time.

Now, GNAT has gone and provided the same capability, using an
implementation-defined attribute (Unrestricted_Access), but
unfortunately, this attribute allows dangling pointers to subprograms,
unlike either of the above options.

- Bob

Re: Q: access to subprogram

[Mark A Biggar]

In article <JSA.96Jul2221357@organon.com> jsa@organon.com (Jon S Anthony) writes:
>In article <Dtxu2p.97F@world.std.com> bobduff@world.std.com (Robert A Duff) writes:
>> During the design of Ada 9X, we proposed a SAFE way of taking 'Access of
>> more-deeply-nesting subprograms.  To this day, I remain astonished and
>> sad that this particular feature didn't make it into Ada 95.  After
>> all, even Pascal has that feature!  And GNU C, which allows nested
>> functions (unlike standard C) allows this feature.
>Is there an "elevator version" of why people didn't want this in?  Tucker,
>if you are reading this, what swayed you to not let this in????  It's
>not one of those things that bothers me all that much (well, it hasn't)
>but it is indeed curious...

If I remember right, it was felt that implementing "closures" (which is the
solution to this problem) placed an unacceptable distributed overhead
on programs that didn't use the feature.  Also I think that half the then
current Ada implementations were using "static links" and the other half
were using "displays" and implementing "clousers" would have been real
difficult for one of those groups (the "display" bunch I think).

--
Mark Biggar
mab@wdl.lmco.com

Re: Q: access to subprogram

[Adam Beneschan]

It should be noted that the new object-oriented features of Ada 95
should make subprogram accesses less necessary than before.  Abstract
types inherently possess subprogram pointers, so it should be possible
to take advantage of this feature as an alternative to explicit
subprogram accesses.

In Ada 83, I missed being able to do things like this:

    with Pack1;
    procedure P1 is
        Error_File : Text_IO.File_Type;

        procedure Report_Error (Message : string) is
        begin
            Text_IO.Put_Line (Error_File, Message);
        end Report_Error;

    begin
        Text_IO.Create (Error_File, ...
        ...
        Pack1.Do_Some_Big_Procedure_That_Can_Report_Errors (Report_Error);
            -- some people would fire me for using a name like this  :)
        ...
    end P1;

The purpose is to call a procedure that can generate error messages,
and to tell it what I want done with those error messages.  Things
can't be done this way in Ada 83.  The problem can be solved using
generics in Ada 83, but I've always thought of this as a strange
reason for using generics, and it can get hairy (suppose, for example,
that the big procedure calls another procedure that also reports
errors; now that procedure has to be turned into a generic also, and
so on).

In Ada 95, you can accomplish this with a subprogram access, but you
have to make Report_Error global, and therefore Error_File has to be
made global also.  So doing things this way forces you to give up some
of the design advantages of using local variables.  (It isn't too big
a problem in the above example, but in more complicated situations,
making things global can be a real pain.)  This is also one of the
things I missed when I was programming in C, since C doesn't have
nested procedures.

Another way to do this is with an abstract type.  (PLEASE NOTE: I
don't guarantee that my Ada 95 syntax is correct!)  You can declare an
"error handler" in some global package like this:

    type Error_Handler is abstract tagged null record;
    procedure Handle_Error (Handler : in Error_Handler;
                            Message : in string) is abstract;

The Do_Some_Big_Procedure_That_Can_Report_Errors can then take an
Error_Handler (or Error_Handler'Class?) as a parameter.  It calls the
Handle_Error routine when it wants to generate an error message.  It
can pass the Error_Handler object around to other procedures that also
report errors.  P1 sets things up to use its own error reporting
routine as the error handler:

    procedure P1 is
        
        type My_Error_Handler is new Error_Handler with record
            Error_File : Text_IO.File_Type;
        end record;
        
        EH : My_Error_Handler;
                -- variable name chosen to avoid being fired  :)
        
        procedure Handle_Error (Handler : in My_Error_Handler;
                                Message : in string) is 
        begin
            Text_IO.Put_Line (Handler.Error_File, Message);
        end Handle_Error;

    begin
        Text_IO.Create (EH.Error_File, ...
        ...
        Pack1.Do_Some_Big_Procedure_That_Can_Report_Errors (EH);

This mechanism doesn't let you *directly* store an access to a
subprogram in a global variable, the way subprogram accesses do; but
using accesses to Error_Handler objects should let you accomplish the
same thing.

Once again, my apologies if my Ada 95 syntax is incorrect.  I haven't
yet learned all the nuances of Ada 95 programming.  Mainly, I wanted
to discuss the concepts involved; someone else may need to fill in the
programming details.

                                -- Adam

            

Re: Q: access to subprogram

[Jon S Anthony]

In article <4re2ng$t7u@wdl1.wdl.loral.com> mab@dst17.wdl.loral.com (Mark A Biggar) writes:

> If I remember right, it was felt that implementing "closures" (which is the
> solution to this problem) placed an unacceptable distributed overhead
> on programs that didn't use the feature.  Also I think that half the then
> current Ada implementations were using "static links" and the other half
> were using "displays" and implementing "clousers" would have been real
> difficult for one of those groups (the "display" bunch I think).

I can maybe buy the second bit (about difficulty for display based
impls) but the first makes no sense.  You wouldn't have to pass
displays or whatever in those cases where the feature wasn't being
used.  Which means that there is _no_ distributed overhead for the
99+% of regular ol' subprogram calls.

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[tmoran]

So if one is interfacing with a system that uses call-backs, any target
of a call-back can only appear in the main procedure if the relevant
'type xxx is access procedure yyy' also appears in the main procedure?

So even with a wonderful set of bindings done as library routines to
handle all the details, the minimum Windows program requires the user
to write a main procedure (which may be trivial) and a separate package
that does the work.

Re: Q: access to subprogram

[Robert A Duff]

In article <JSA.96Jul5141249@organon.com>,
Jon S Anthony <jsa@organon.com> wrote:
>I can maybe buy the second bit (about difficulty for display based
>impls) but the first makes no sense.  You wouldn't have to pass
>displays or whatever in those cases where the feature wasn't being
>used.  Which means that there is _no_ distributed overhead for the
>99+% of regular ol' subprogram calls.

I posted a note in this thread saying the same thing.

But, having read Robert Dewar's posts, I have to admit that the
"distributed overhead" argument is not totally off the wall.  The
argument is:

1. Displays are too much trouble, in the presence of downward closures.
(Or, are they upward closures?  You know what I mean -- passing
procedures as parameters.)

2. Therefore, if we have that feature, compiler writers are forced to
use static links (or are at least sorely tempted to use static links --
it makes things simpler, and as Robert pointed out, the
simplicity-vs-complexity we're talking about is towards the back end of
the compiler, which is the hardest part to debug, and may be duplicated
for numerous kinds of hardware).

3. Displays are clearly faster than static links, for normal direct calls.

4. Therefore, we've got a distributed overhead; QED.

This argument makes *some* sense, but I dispute point 3.  I'm not really
sure, but I think that perhaps static links are faster.  I'm quite
*sure* of two things: it doesn't make much difference, since most code
isn't very deeply nested anyway, and if there *is* a difference, it's
not a big difference.

Of course, one might wish for some scientific experiment that could tell
us once and for all which is better.  Unfortunately, I don't think it's
that easy.  For one thing, you have to write the same compiler both
ways, which is expensive.  For another, the issue is affected by other
optimizations -- for example, a static link implementation will be much
better if the compiler is smart enough to do CSE elimination on loads of
the static link, or chains therefrom.  But a display implementation
won't care so much about that particular optimization.  For another
thing, it depends on the sort of programs you write.  Most Ada code I've
seen has very few procedures-within-procedures, which is where the
difference counts.  And five-level nested procedures are very uncommon,
I suspect.  But some people like to nest more than others.  ;-)

- Bob

Re: Q: access to subprogram

[Robert Dewar]

Bob Duff said

"sure, but I think that perhaps static links are faster.  I'm quite
*sure* of two things: it doesn't make much difference, since most code
isn't very deeply nested anyway, and if there *is* a difference, it's
not a big difference."

If there is no nesting, then neither static links nor displays have
any overhead at all.

If there is nesting, then static links pay a price for calling any routine
other than an outer level library routine.

If there is nesting, then displays pay a price for calling any routine
that contains a nested routine, but there is no price for calling any
routine (at library level or nested) if it contains no nested routines.

It seems to be evident that the great majority of calls are to routines
that do NOT contain  nested routines. Consider in particular the case
of a big procedure q that contains many tested procedures q1 .. q100.

Now for static links, calls to any of q1 .. q100 incur an overhead, but
the call to q does not (assuming q is global level).

For displays, calls to any of q1 .. q100 (assuming there is no further
level of nesting) incur no overhead, only the call to q incurs an overhead.

It seems clear to me from these considerations that displays will be
faster than static links for most typical programs.

Re: Q: access to subprogram

[Robert Dewar]

Jon said

"I can maybe buy the second bit (about difficulty for display based
impls) but the first makes no sense.  You wouldn't have to pass
displays or whatever in those cases where the feature wasn't being
used.  Which means that there is _no_ distributed overhead for the
99+% of regular ol' subprogram calls."

If you buy the second bit, and if you agree that displays are more
efficient than static links for Ada programs (which is not gospel,
it requires discussion and examination -- I certainly think it is
the case), then the first bit is a consequence, since the provision
of closures would push you away from using displays, and hence 
introduce distributed overhead -- that was what was being talked about.

Re: Q: access to subprogram

[Robert A Duff]

In article <dewar.836413642@schonberg>, Robert Dewar <dewar@cs.nyu.edu> wrote:
>(and just in case I give the wrong impression, I fully understand that
>full closures, preferably in conjunction with partial parametrization of
>higher order functions, lend tremendous expressive power -- for example
>Ackerman's function can be written using primitive recursion if you have
>these notions around), but I think the capability goes beyond the
>appropriate semantic level for Ada -- no doubt that statement should 
>set of a mini-thread :-)

OK, sounds like an interesting mini-thread to me.  :-)

Ignore efficiency and implementation difficulty, for the moment.  Show
me an example or two illustrating the tremendous expressive power, using
some imagined syntax for expressing full closures.  (I know there's some
expressive power there, but it's not clear to me how tremendous it is.
I'm wondering if I've just not had enough experience in Lisp, etc.  I've
done some Lisp programming, and used closures, but don't miss them *all*
that much in Ada-like languages.)

- Bob

Re: Q: access to subprogram

[Robert A Duff]

In article <4rjvo0$7gg@news1.delphi.com>,  <tmoran@bix.com> wrote:
>So if one is interfacing with a system that uses call-backs, any target
>of a call-back can only appear in the main procedure if the relevant
>'type xxx is access procedure yyy' also appears in the main procedure?

Clearly, a call-back function has to live "forever" -- you're handing
its address off to, say, some windowing system that will call it
whenever the mouse is clicked.  Therefore, the callback function
typically has to live as long as the whole program.

Unfortunately, the main subprogram does not last as long as the whole
program.  Lots of package elaboration can happen before the main
subprogram starts, and tasks can keep running for a long time after the
main subprogram ends.  Given this model, which has existed since Ada 83,
it makes no sense to have callbacks nested with the main subprogram (or
any other subprogram).  You can of course complain that this is the
wrong model, or you can complain, yeah but I don't need no stinkin'
tasks, so why do I have to be bothered with all this extra complexity.

Note also that the main subprogram can be recursive and reentrant.  For
example, suppose a library package creates a task that calls the main
subprogram (in parallel with the "normal" call to the main subprogram,
from the environment task).  Clearly, there had better not be any
callback functions in there.

>So even with a wonderful set of bindings done as library routines to
>handle all the details, the minimum Windows program requires the user
>to write a main procedure (which may be trivial) and a separate package
>that does the work.

There is no requirement to even have a main procedure at all (in Ada
95).  Alternatively, even if there *is* a main subprogram, you should be
able to write it in C, if you like.

One final point: It's hard for me to get too excited about not being
able to put callback functions inside the main subprogram, because lots
of people have done lots of callback stuff in C, and you can't put a
callback function inside the main function in C, either (you can't nest
functions AT ALL in C).

- Bob

Re: Q: access to subprogram

[Ronald Cole]

dewar@cs.nyu.edu (Robert Dewar) writes:
> not all compilers are like this, GCC has only one back end, but many
> compilers do have myultiple backends).

Not true.  A single instance of GCC doesn't support multiple machine
targets (other than the -m options for some processor families).  GCC
has to be recompiled to support different machine descriptions (that's
what the -b and -V options of gcc are for).  I consider this as having
multiple backends.  Many years ago, when asked about why he didn't
make GCC read loadable md files, Stallman answered that it would hurt
performance (both for the compiler and for the generated code) (there
were probably a few other reasons, but it was too long ago for me to
remember them all.  that was around the time when Stallman said that
writing what we now know as the bfd libraries would be "hard").

-- 
Ronald Cole                                     E-mail: ronald@ridgecrest.ca.us
President, CEO                                          zippy@ecst.csuchico.edu
Forte International                                Fax: (619) 384-2346
     My PGP fingerprint: E9 A8 E3 68 61 88 EF 43  56 2B CE 3E E9 8F 3F 2B

Re: Q: access to subprogram

[Mark Eichin]

> remember them all.  that was around the time when Stallman said that
> writing what we now know as the bfd libraries would be "hard").

Thus giving it the name :-)

If I remember correctly, the other big reason is that reading
externally generated rtl or tree structures would make non-Free
frontends possible, and that would be a Bad Thing. This way anything
that takes advantage of the backend needs to also be Free.
					_Mark_ <eichin@cygnus.com>
					Cygnus Support, Eastern USA

Re: Q: access to subprogram

[Robert Dewar]

Richard Kenner said

"But adding new requirements on the config files is something we try to
avoid, though the work on folding a "zero-cost" exception handling
into GCC is going to require at least some additional work in
each config file."

Sure, but I don't think any of the Ada 95 changes are at the level
that would require config file changes. Yes some config file changes
may be needed for Ada (overflow checking, exception handling ...) but
these are things that are in Ada 83 anyway.

Re: Q: access to subprogram

[Robert Dewar]

Ronald Cole said (commenting on my claim that GCC did not have multiple
backends)

Not true.  A single instance of GCC doesn't support multiple machine
targets (other than the -m options for some processor families).  GCC
has to be recompiled to support different machine descriptions (that's
what the -b and -V options of gcc are for).  I consider this as having
multiple backends.

That's not what I meant, yes, of course there are multiple backends at
the object level, but not at the source level. If you look back in this
thread, you will see that this is the critical issue. If you have a
technology where each backend is a completely different source program,
separately written (such technoologies are pretty common, most Ada 83
compiler technologies were like this), then the point is that the impact
of anything that affects the backend is greatly multiplied, and that is
why during the design, we were very cautious about changes that affect
the backend.

Most Ada technologies have a single front end for all targets (though
Ronald Cole would presumably call these multiple front ends too, because
there are certanly separate object versions), but again the important
thing is that there is only one source program. Thus changes to the front
end are potentially less troublesome, since the change only has to be made
once.

But for technologies like GCC, where there is only one source program for
both front end and backend (though in both cases multiple executables),
this distinction is not significant.

Re: Q: access to subprogram

[Richard Kenner]

In article <m291cv99nr.fsf@devo.ridgecrest.ca.us> Ronald Cole <ronald@ridgecrest.ca.us> writes:
>Not true.  A single instance of GCC doesn't support multiple machine
>targets (other than the -m options for some processor families).  GCC
>has to be recompiled to support different machine descriptions (that's
>what the -b and -V options of gcc are for).  I consider this as having
>multiple backends. 

I don't think that's what Robert meant.  The distinction he was
trying to make is that GCC has only one piece that actually generates
code (what is normally called the "back end") and that the config files
modify what it does.  In most compiler technologies, the config files
say how to generate code, while in GCC (with some small number of
exceptions) they describe the machine.

>Many years ago, when asked about why he didn't
>make GCC read loadable md files, Stallman answered that it would hurt
>performance (both for the compiler and for the generated code)

Yes, having loadable MD files would seriously hurt compiler
performance, but is at least something that could be contemplated.  By
contrast, trying to load the tm.h file at runtime seems hopeless.

>that was around the time when Stallman said that
>writing what we now know as the bfd libraries would be "hard").

Yes, that's the original of the unoffical acronym of "BDF".  However,
note that this library is indeed far from trivial.

Re: Q: access to subprogram

[Richard Kenner]

In article <dewar.836776773@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:
>If you have a technology where each backend is a completely different source
>program, separately written (such technoologies are pretty common, most Ada 83
>compiler technologies were like this), then the point is that the impact
>of anything that affects the backend is greatly multiplied, and that is
>why during the design, we were very cautious about changes that affect
>the backend.
>
>But for technologies like GCC, where there is only one source program for
>both front end and backend (though in both cases multiple executables),
>this distinction is not significant.

I'd say it's not *as* significant.  However, in GCC we are concerned
about things that affect the config files.  We try to avoid making
changes that affect existing config files if at all possible and then
we much prefer changes (such as adding a new parameter to a macro)
that can be made "mechanically" to all the config files.

But adding new requirements on the config files is something we try to
avoid, though the work on folding a "zero-cost" exception handling
into GCC is going to require at least some additional work in
each config file.

Re: Q: access to subprogram

[Norman H. Cohen]

In article <Dtyt4K.Jvx@world.std.com>, bobduff@world.std.com (Robert A Duff)
writes: 

|>                                                                 With
|> displays, it is somewhat difficult to implement passing nested
|> procedures as parameters, because you have to pass the display, which is
|> not of compile-time-known size.

The size of a display for a given procedure IS known at compile time.
It is equal to the number of procedures that lexically surround that
procedure (give or take one, depending on the details of a given
implementation).

In essence, a display is an array of pointers to the stack frames for the
current activations of each subprogram surrounding the current
subprogram.  The array is typically small, fast access to the values of
the array elements is crucial for efficient access to nonlocal variables,
and the array indices needed for addressing nonlocal variables are always
known at compile time, so the elements of this array are typically stored
in registers.

(By the way, I share Bob Duff's amazement at the noninclusion of downward
closures--we called them downward at the time--in Ada 95, and I say this
as one of those Bob described as urging the removal rather than the
addition of proposed Ada-95 features.  I viewed the inclusion of downward
closures as the REMOVAL of an arbitrary restriction.  The decision was
not made in ignorance.  Bill Taylor had made what I considered an
irrefutable case for downward closures, showing how much easier it would
be to write iterators if downward closures were allowed.  It came down to
a conflict between the interests of Ada programmers and the interests of
a minority of Ada implementors, and in this case the interests of the few
implementors using displays prevailed.)

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Q: access to subprogram

[Robert A Duff]

In article <4rqbo9$b02@goanna.cs.rmit.edu.au>,
Richard A. O'Keefe <ok@goanna.cs.rmit.edu.au> wrote:
>bobduff@world.std.com (Robert A Duff) writes:
>
>>1. Displays are too much trouble, in the presence of downward closures.
>>(Or, are they upward closures?  You know what I mean -- passing
>>procedures as 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.

I didn't mean it's impossible.  I just meant that if I were implementing
a compiler for a language with downward closures on a typical modern
machine, I would choose static links, in part because it seems simpler.
On the other hand, I know of compilers that have implemented Pascal
using displays.

Remember that the discussion during the design of Ada 9X was NOT about
"we don't know how to implement this in theory" -- it was more like,
"we've got a multi-target back end (back ends), and we don't want to
mess with it (them)".  Also note that I argued strongly IN FAVOR of
downward closures, and lost the argument.

>Displays are a win if you can afford to dedicate some global registers to
>them.  This was beaten to death by the late 70's surely?

Sure, but inconclusively.  Just like LR vs. LL parsing has been beaten
to death -- it doesn't mean that everybody agrees which one is the right
one to use in all situations.

As for displays being a big win, suppose I can afford to dedicate those
registers on one of my targets, but not on the other?  Do I write a back
end (or pair of back ends) that can do it both ways?  It's an economic
decision, at least in part.  Suppose I have a very rich customer who
desperately needs efficient code, and loves to write 7-level-deep nested
procedures.  That might make a difference, no?

Also, note that it depends on the language.  In my experience, Ada
programs are less deeply nested than Pascal programs.  If you don't use
much nesting, then it's clearly not a "big win" either way.

- Bob

Re: Q: access to subprogram

[Norman H. Cohen]

In article <Du4tvx.13s@world.std.com>, bobduff@world.std.com (Robert A Duff)
writes: 

|> Ignore efficiency and implementation difficulty, for the moment.  Show
|> me an example or two illustrating the tremendous expressive power, using
|> some imagined syntax for expressing full closures.  (I know there's some
|> expressive power there, but it's not clear to me how tremendous it is.
|> I'm wondering if I've just not had enough experience in Lisp, etc.  I've
|> done some Lisp programming, and used closures, but don't miss them *all*
|> that much in Ada-like languages.)

Full closures are what LISP programmers call FUNARGs.

First, a simple example: 

   type Integer_Map_Type is access function (N: Integer) return Integer;

   function Add_M_To (M: Integer) return Integer_Map_Type is
      -- A function that returns M more than its formal parameter: 
      function Result_Function (N: Integer) return Integer is
      begin
         return N + M;
      end Result_Function;
   begin
      return Result_Function'Access;  -- illegal in Ada 95
   end Add_M_To;

   Add_1_To : Integer_Map_Type := Add_M_To(M => 1);
   Add_5_To : Integer_Map_Type := Add_M_To(M => 5);
   X        : Integer := Add_1_To(10); -- returns 11
   Y        : Integer := Add_5_To(10); -- returns 15

Add_M_To returns a pointer to a function more deeply nested than the
access type Integer_Map_Type, in violation of Ada-95 rules.  Note that
the function pointed to, Result_Function, refers to M, which is a formal
parameter of Add_M_To and thus, in Ada 95, goes out of existence when
Add_M_To returns.  In a language supporting full closures, the value of M
is not obliterated when Add_M_To returns.  What Add_M_To returns is a
value designating not only the function Result_Function, but also the
environment in which that function is to be executed, in this case an
environment in which M is bound to 1 or to 5.  The state of the
environment during the call on Add_M_To is retained as part of this
result value even after Add_M_To returns.

Now for a more intricate example.  Robert Dewar mentioned that
Ackermann's function can be programmed out of straightforward loops if
full closures are supported.  The classic definition of Ackermann's
function is: 

   A(0,n) = n+1
   A(m,0) = A(m-1,1)        for m>0
   A(m,n) = A(m-1,A(m,n-1)) for m>0, n>0

If we view A as an unbounded array and let R[m] be the function
corresponding to the m\th "row" of this array, so that A(m,n) = R[m](n),
these equations become: 

   R[0](n) = n+1
   R[m](0) = R[m-1](1)          for m>0
   R[m](n) = R[m-1] o R[m](n-1) for m>0, n>0
      (where o represents functional composition)

By repeatedly replacing R[m](...) in the third equation by the definition
for R[m] given in the third equation, we get, for m>0: 

   R[m](n) = R[m-1] o R[m](n-1)
           = R[m-1] o R[m-1] o R[m](n-2)
           = R[m-1] o R[m-1] o R[m-1] o R[m](n-3)
              ...
           = R[m-1] o ... o R[m-1] o R[m](0)
             \                   /
              \-----------------/
                    n times

Then, by replacing R[m](0) according to the second equation, we get

   R[m](n) = R[m-1] o ... o R[m-1] (1)
             \                   /
              \-----------------/
                   n+1 times

In other words,

   R[0] = the successor function (from the first equation)
   For m>0, the function R[m] is derived from the function R[m-1] as follows: 
      Given an argument n, R[m] returns the result of starting with 1 and
      applying R[m-1] repeatedly, n+1 times.

Here's a formulation using Ada plus full closures: 


package Unbounded_Naturals is
   type Unbounded_Natural is private;
      -- a type representing arbitrarily large nonnegative integers
   ...
   function "+"
      (Left: Unbounded_Natural; Right: Natural) return Unbounded_Natural;
   function "-"
      (Left: Unbounded_Natural; Right: Natural) return Unbounded_Natural;
   function "="
      (Left: Unbounded_Natural; Right: Natural) return Boolean;
   function To_Unbounded_Natural (N: Natural) return Unbounded_Natural;
   ...
private
   ...
end Unbounded_Naturals;


with Unbounded_Naturals; use Unbounded_Naturals;
package Ackermann_Computation is
   function Ackermann (M, N: Integer) return Unbounded_Natural;
end Ackermann_Computation;


package body Ackermann_Computation is

   type Ackermann_Row_Type is
      access function (N: Unbounded_Natural) return Unbounded_Natural;

   function Row_Zero (N: Unbounded_Natural) return Unbounded_Natural is
   begin
      return N + 1;
   end Row_Zero;

   function Successor_Row
      (F: Ackermann_Row_Type) return Ackermann_Row_Type is

      function Next_Row (N: Unbounded_Natural) return Unbounded_Natural is
         Counter : Unbounded_Natural := N + 1;
         Result  : Unbounded_Natural := 1;
      begin
         while Counter /= 0 loop
            Result := F(Result);
               -- F is the parameter of the surrounding function
            Counter := Counter - 1;
         end loop;
         return Result;
      end Result;

   begin

      return Next_Row'Access;  -- Illegal in Ada 95

   end Successor_Row;

   function Ackermann (M, N: Integer) return Unbounded_Natural is
      Row: Ackermann_Row_Type := Row_Zero'Access;  -- R[0]
   begin
      for I in 1 .. M loop
         Row := Successor_Row(Row);
            -- Compute R[1] from R[0], R[2] from R[1], ...
      end loop;
      return Row ( To_Unbounded_Natural(N) );  -- i.e., R[m](n)
   end Ackermann;

end Ackermann_Computation;


The magic is inside Successor_Row, which returns a pointer to a function
more deeply nested than the access type Ackermann_Row_Type, in violation
of Ada-95 rules.  The function pointed to, Next_Row, refers to F, which
is a formal parameter of Successor_Row.  Successor_Row returns a value
designating both the function Next_Row and the environment in which that
function is to be executed, in which F is bound to a particular
Ackermann_Row_Type value.  (After each iteration of the for-loop, Row
designates the function Next_Row and an environment in which F is bound
to whatever the value of Row was at the BEGINNING of that iteration.)

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Q: access to subprogram

[Robert A Duff]

In article <dewar.836709438@schonberg>, Robert Dewar <dewar@cs.nyu.edu> wrote:
>If there is no nesting, then neither static links nor displays have
>any overhead at all.
>
>If there is nesting,...
[lots of good stuff]
>It seems clear to me from these considerations that displays will be
>faster than static links for most typical programs.

But, IMHO, there usually is no nesting.  Therefore, the same facts lead
me to think, "If there's a difference, it's negligible."  Therefore,
compilers ought to do what's simplest (IMHO, static links are simpler to
implement).

Also, you analyzed calls, but you didn't analyze the speed of up-level
references.  For a display, it's some-offset added to some-display-
pointer.  For static links, it's some-offset added to
chaining-up-the-links.  Sure sounds like displays are better.
Especially if the display is in registers.  But it depends a lot on what
optimizations are done.  E.g., can the compiler recognize cases where
the nested procedure does no up-level refs?  Can the compiler recognize
cases where the outer procedure's stack frame can be merged with the
environment task's stack frame (i.e. static allocation)?  Can the
compiler notice multiple loads of the same up-level reference?  Can the
display in fact be stored entirely in registers?  These all make a
difference, but IMHO they are second-order effects, given that most code
isn't nested at all.

I haven't seen any studies showing code is not nested.  It's just my
limited experience.  Why would that be?  I don't think nesting is
necessarily evil.  But, in Ada, you need to be at library level to do
true separate compilation, so there's a strong incentive to avoid
nesting.  Subunits allow separate compilation of bodies (in some
compilers), but to get separate compilation of specs, you have to use
library units.

- Bob

Re: Q: access to subprogram

[Brian Rogoff]

ncohen@watson.ibm.com (Norman H. Cohen) writes:

   (By the way, I share Bob Duff's amazement at the noninclusion of downward
   closures--we called them downward at the time--in Ada 95, and I say this
   as one of those Bob described as urging the removal rather than the
   addition of proposed Ada-95 features.  I viewed the inclusion of downward
   closures as the REMOVAL of an arbitrary restriction.  The decision was
   not made in ignorance.  Bill Taylor had made what I considered an
   irrefutable case for downward closures, showing how much easier it would
   be to write iterators if downward closures were allowed.  It came down to
   a conflict between the interests of Ada programmers and the interests of
   a minority of Ada implementors, and in this case the interests of the few
   implementors using displays prevailed.)

Could you summarize or provide a reference to Bill Taylor's work? Does it 
answer the objection that downward closures impose an inefficiency on programs 
that don't use them?

I like closures myself, but I am thinking of the full (upward I guess you'd 
call them) closures of Lisp, which require garbage collection. Perhaps a 
"syntactically upwards compatible" Ada dialect supporting closures should be 
considered, especially since the Java virtual machine already imposes GC on 
any language that runs on it, and it will be a popular target.

-- Brian

Re: Q: access to subprogram

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

Re: Q: access to subprogram

[Robert Dewar]

Bob said

"Also, note that it depends on the language.  In my experience, Ada
programs are less deeply nested than Pascal programs.  If you don't use
much nesting, then it's clearly not a "big win" either way."

I disagree, the presence of subunits makes it practical to nest very
deeply (the nesting would have to be lexically explicit in Pascal),
and it is common practice to nest deeply this way (common does not
mean everyone or even a majority does it, just that there are quite
a few programs around written that way).

Of course an interesting point is that the difference is more extreme
for light nesting.

Suppose your organization has a main program with lots of procedures
nested inside, but no further nesting. The overhead for displays is
zero in such a program, but static links would be used all the time.

Getting an example the other way round (one that favors static links)
is difficult indeed.

Re: Q: access to subprogram

[Robert Dewar]

Thankyou Norman for that nicely worked out example of Ackerman, now what
do you say Bob? (Bob asked for a demo of the power of closures) :-) :-)

Re: Q: access to subprogram

[Richard Kenner]

In article <xe1enmnmvjn.fsf@maneki-neko.cygnus.com> Mark Eichin <eichin@cygnus.com> writes:
>If I remember correctly, the other big reason is that reading
>externally generated rtl or tree structures would make non-Free
>frontends possible, and that would be a Bad Thing. This way anything
>that takes advantage of the backend needs to also be Free.

The other big reason for what?

What you state is true, but I don't see it having any relevance.

The RTL generated is always customized for a machine, so writing RTL
would not allow one to split off a backend into a separate program.
Tree structures are mostly machine-independent (but not fully, since
size information is encoded into them), but GCC does not operate by
forming a tree for a function and then compiling it (the interface
from the front end to the rest of the compiler is more procedural), so
"writing the tree" out is not meaningful since it never exists.

Some front-ends to GCC (most notably those for Fortran and Ada)
operate by generating a separate tree structure (usually in a
different format) for a function or file and then walking that tree by
making calls to GCC.  In such a case it indeed is somewhat possible to
write out such a tree and separate the front end from GCC.  I can't
speak for Fortran, but can say this is now impractical for Ada.  As
part of the bootstrap process, this used to be done, but there are now
numerous calls from the tree walk routines back into the Ada front
end.  Also, the tree is not machine-independent because sizes of
predefined types are machine-specific.  (Aside from the reason given
by Mark, it would also be inefficient to do this split due to the
amount of I/O required, so this is not only not easy but undesirable.)

Re: Q: access to subprogram

[Richard A. O'Keefe]

bobduff@world.std.com (Robert A Duff) writes:

>1. Displays are too much trouble, in the presence of downward closures.
>(Or, are they upward closures?  You know what I mean -- passing
>procedures as 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.

The B6700 hardware took care of this.

Techniques for marrying procedure parameters and displays were readily
available in the compiler construction literature by the late '70s.
A compiler construction class I was a student in explained how to do
it (and we had to; we were writing a Pascal->Algol compiler which used
a display).

What happened?  When did everyone forget?

Yes, there is overhead:  but the overhead of rewinding the display
is incurred only on entry to / exit from a formal procedure; there
need be *NO* extra overhead for calling visible procedures.

>3. Displays are clearly faster than static links, for normal direct calls.

>This argument makes *some* sense, but I dispute point 3.  I'm not really
>sure, but I think that perhaps static links are faster.

Displays are a win if you can afford to dedicate some global registers to
them.  This was beaten to death by the late 70's surely?

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

Re: Q: access to subprogram

[Robert A Duff]

In article <4rr5tu$sap@watnews1.watson.ibm.com>,
Norman H. Cohen <ncohen@watson.ibm.com> wrote:
>The size of a display for a given procedure IS known at compile time.

True (assuming you don't "really" support separate compilation of
subunits).

But the size of "THE display" is the max of all those.  This is not
known at compile time, but at link time.  To package up a display along
with the corresponding procedure (when 'Access is done), you have to
either know that max size, and copy that much into a compiler-generated
variable, or else you have to manage varying-size displays (and copy
THAT much) -- note that the caller who does P.all(...) doesn't know
where P came from, and so either has to be TOLD the size of P's display,
or always use the max.

Or, I suppose you could simply say that the max is 10, and forbid
nesting more than 10 levels deep.  Perhaps a reasonable restriction, but
I hate having arbitrary restrictions like that, if it's feasible to
avoid.

Any of the above are quite implementable, but I think that static links
are clearly simpler for the implementation.

>...  I viewed the inclusion of downward
>closures as the REMOVAL of an arbitrary restriction.

Me, too.  This is an illustration of Robert's point about simplicity.
We were all shouting for more simplicity, but everybody had their own
idea of simplicity (simple to describe in the RM vs. simple to implement
vs. simple to learn for a beginner vs. simple to use for an experienced
programmer vs. etc etc etc).

>...  The decision was
>not made in ignorance.  Bill Taylor had made what I considered an
>irrefutable case for downward closures, showing how much easier it would
>be to write iterators if downward closures were allowed.  It came down to
>a conflict between the interests of Ada programmers and the interests of
>a minority of Ada implementors, and in this case the interests of the few
>implementors using displays prevailed.)

Well, to be fair, if the implementers can't implement, the users are
kind of stuck.  Probably not true in this particular case, but in the
general case, you don't want to just add every feature anybody wants.
If the compiler gets too big, it gets too buggy -- no matter how much
money you spend on it, apparently.

- Bob

Re: Q: access to subprogram

[Thomas Wolff]

Adam Beneschan: >>>Q: access to subprogram
 : It should be noted that the new object-oriented features of Ada 95
 : should make subprogram accesses less necessary than before.  Abstract
I don't agree with this view, see below.

 : types inherently possess subprogram pointers, so it should be possible
 : to take advantage of this feature as an alternative to explicit
 : subprogram accesses.
 : 
 : In Ada 83, I missed being able to do things like this:
 : 
 :     with Pack1;
 :     procedure P1 is
 :         Error_File : Text_IO.File_Type;
 : 
 :         procedure Report_Error (Message : string) is
 :         begin
 :             Text_IO.Put_Line (Error_File, Message);
 :         end Report_Error;
 : 
 :     begin
 :         Text_IO.Create (Error_File, ...
 :         ...
 :         Pack1.Do_Some_Big_Procedure_That_Can_Report_Errors (Report_Error);
 :             -- some people would fire me for using a name like this  :)
 :         ...
 :     end P1;
 : 
 : The purpose is to call a procedure that can generate error messages,
 : and to tell it what I want done with those error messages.  Things
 : can't be done this way in Ada 83.  The problem can be solved using
 : generics in Ada 83, but I've always thought of this as a strange
 : reason for using generics, and it can get hairy (suppose, for example,
 : that the big procedure calls another procedure that also reports
 : errors; now that procedure has to be turned into a generic also, and
 : so on).
Yes, and the same way you think it's a strange way of employing generics, 
I'd also say it's a strange thing to employ objects (of abstract types) 
for this simple (!) purpose alone as you propose below.

 : In Ada 95, you can accomplish this with a subprogram access, but you
 : have to make Report_Error global, and therefore Error_File has to be
 : made global also.  So doing things this way forces you to give up some
 : of the design advantages of using local variables.  (It isn't too big
 : a problem in the above example, but in more complicated situations,
 : making things global can be a real pain.)  This is also one of the
 : things I missed when I was programming in C, since C doesn't have
 : nested procedures.
 : 
 : Another way to do this is with an abstract type.  (PLEASE NOTE: I
 : don't guarantee that my Ada 95 syntax is correct!)  You can declare an
 : "error handler" in some global package like this:

Compare my other response in this thread for remarks about the 
implementation of the discussed language feature.

Thomas Wolff

Re: Q: access to subprogram

[Thomas Wolff]

Robert Dewar: >>>Q: access to subprogram
 : Once you introduce unrestricted access to procedures, displays are a bit
 : of a menace, and probably this tips the scales in favor of static links
 : (if you believe like me that displays are more efficient, this can also
 : be read as meaning that the introduction of unrestricted access to procedures
 : would introduce distributed inefficiency -- but that still is NOT the reason
 : this feature was excluded).
Why should displays be a menace where static links are not? Who would 
actually prefer to really follow static links at all, effectively almost 
*searching* for variables at run-time? Until now I thought this would 
only be a theoretical concept and perhaps one of very early compilers.


Robert A Duff: >>>Q: access to subprogram
 : There are two major ways of implementing up-level variable references in
 : a language with nested procedures: Static links, and displays.  With
 : displays, it is somewhat difficult to implement passing nested
 : procedures as parameters, because you have to pass the display, which is
This is not true, see below.
 : not of compile-time-known size.  Passing a static link is easy -- it's
 : just a single address.  Some implementations of Ada 83 used displays.
Why not just push the display on the stack and pass its address??
(If you really wanted to pass the display itself for some reason, you 
could still use the program's maximal display size, wasting a few 
bytes in these occasional cases.)

 : The primary reason for not putting the feature in was to ease the pain
 : for such implementations.  This was done at a time when the general
 : feeling was that Ada 9X had more than enough new features, and we
 : shouldn't be adding things, but removing them.
It is a very unfortunate decision to leave out a nice feature of 
systematic program construction just for leaving out features.


Mark A Biggar: >>>Q: access to subprogram
 : In article <JSA.96Jul2221357@organon.com> jsa@organon.com (Jon S Anthony) wri
tes
 : :
 : >In article <Dtxu2p.97F@world.std.com> bobduff@world.std.com (Robert A Duff) 
wri
 : tes:
 : >> During the design of Ada 9X, we proposed a SAFE way of taking 'Access of
 : >> more-deeply-nesting subprograms.  To this day, I remain astonished and
 : >> sad that this particular feature didn't make it into Ada 95.  After
 : >> all, even Pascal has that feature!  And GNU C, which allows nested
 : >> functions (unlike standard C) allows this feature.
I am sad about this, too. I have also always deplored that this 
feature was removed during Wirth's transition from Pascal to Modula, 
presumably for the same unconvincing reasons as used in this 
discussion.

 : If I remember right, it was felt that implementing "closures" (which is the
 : solution to this problem) placed an unacceptable distributed overhead
 : on programs that didn't use the feature.  Also I think that half the then
 : current Ada implementations were using "static links" and the other half
 : were using "displays" and implementing "clousers" would have been real
 : difficult for one of those groups (the "display" bunch I think).
No, with the solution indicated above there is no overhead (i. e. for 
programs that don't use the feature) and no big inefficiency for programs 
that do use the feature and no difficulty either apart from having to 
understand what should happen in the implementation. When I recently 
gave a talk on a topic related to this, some members of the audience 
also seemed to recall they had the impression this was difficult or 
inefficient... I wonder how this rumor evolved.

Compare my other response in this thread for remarks about the 
desirability of the discussed language feature.

Thomas Wolff

Re: Q: access to subprogram

[Jon S Anthony]

In article <dewar.836627383@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:

> Jon said
> 
> "I can maybe buy the second bit (about difficulty for display based
> impls) but the first makes no sense.  You wouldn't have to pass
> displays or whatever in those cases where the feature wasn't being
> used.  Which means that there is _no_ distributed overhead for the
> 99+% of regular ol' subprogram calls."
> 
> If you buy the second bit, and if you agree that displays are more
> efficient than static links for Ada programs (which is not gospel,
> it requires discussion and examination -- I certainly think it is
> the case), then the first bit is a consequence, since the provision
> of closures would push you away from using displays, and hence 
> introduce distributed overhead -- that was what was being talked about.

I don't see how, as most programs will not have _any_ nesting.
Period.  So displays or static links are irrelevant for nearly all
cases.  So, the issue is irrelevant to [probably not even hyperbole
here] 99+% of subprogram calls.  Which means that there really is no
distributed overhead (at least not as I understand the term).

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[Jon S Anthony]

In article <4rr5tu$sap@watnews1.watson.ibm.com> ncohen@watson.ibm.com (Norman H. Cohen) writes:

> (By the way, I share Bob Duff's amazement at the noninclusion of downward
> closures--we called them downward at the time--in Ada 95, and I say this
> as one of those Bob described as urging the removal rather than the
> addition of proposed Ada-95 features.  I viewed the inclusion of downward
> closures as the REMOVAL of an arbitrary restriction.  The decision was
> not made in ignorance.  Bill Taylor had made what I considered an
> irrefutable case for downward closures, showing how much easier it would
> be to write iterators if downward closures were allowed.  It came down to
> a conflict between the interests of Ada programmers and the interests of
> a minority of Ada implementors, and in this case the interests of the few
> implementors using displays prevailed.)

While the lack of direct support for recursive types across package
boundaries and lack of assertions are more important (IMO) goofs, and
while the evinced reasons for the latter one are mind numbingly
incomprehensible, this latest example would appear to take the crown
for the most stupefying goof.  Just amazing...

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[Robert Dewar]

Thomas Wolff said

Why should displays be a menace where static links are not? Who would
actually prefer to really follow static links at all, effectively almost
*searching* for variables at run-time? Until now I thought this would
only be a theoretical concept and perhaps one of very early compilers.

  Static links are by far the more common way of hanling uplevel
  references, and are far from being "only a theoretical concept".
  Most modern compilers use static links. There is no searching
  involved, just loading the entries that are needed, and if they
  are used frequently, they will stay in registers anyway.

  In fact the idea of static links came a little later on, the early
  Algol-60 compilers used displays.

Why not just push the display on the stack and pass its address??
(If you really wanted to pass the display itself for some reason, you
could still use the program's maximal display size, wasting a few
bytes in these occasional cases.)

  That's the original Algol-60 approach but it is never used these
  days that I know of, since it is in practice definitely inferior
  to both static links and the use of global displays. It introduces
  unconditionally a large overhead of copying the display at every
  call whether or not it is useful to do so.

  (Yes, I know the Intel x86 hardware uses that approach. I use this
   as one of the examples of very bad CISC design, not only is an
   over-complex instruction built-in, but it is a bad algorithm
   that is built-in!)

Re: Q: access to subprogram

[Robert Dewar]

Jon Anthony says

"I don't see how, as most programs will not have _any_ nesting.
Period.  So displays or static links are irrelevant for nearly all
cases.  So, the issue is irrelevant to [probably not even hyperbole
here] 99+% of subprogram calls.  Which means that there really is no
distributed overhead (at least not as I understand the term)."

This is wildly overstated. I would say that any large program that has
no nested procedures at all is poorly written, and I have seen very
few large program (actually none in Ada) that had no nesting at all.

On the other hand, I have *quite* often seen programs using nesting
*very* extensively, where the program was divided into large procedures,
containing many nested procedures, where the majority of calls are to
procedures contained within other procedures.

I don't believe Jon's figure of 99+% of subprogram calls being to library
level subprograms is anywhere near right, and I would guess it is just
a rhetorical guess rather than any kind of measurement. Across an
admitedly small sample of large programs that I was involved in measuring,
we saw over 80% of the calls being to procedures that were nested inside
other procedures.

Probably the big picture is that some programs use very little nesting,
and therefore are insensitive to the display mechanism, and other programs
nest heavily, and are potentially sensitive to the mechanism.

I will get some statistics on our Ada 95 database when I have chance to
find out what we see there.

For GNAT itself, there are sections in both styles. For a style where
calls to nested procedures are heavy in frequency, see sem_prag.adb
for example.

Remember that nesting of procedures becomes much more critical in
tasking programs, because it is the cheap way of making task local
data. One of the problems in making C library routines threadsafe
is that they tend to use global variables heavily, which in 
corresponding Ada programs would typically be local uplevel references.

For example, printf is presumably a big nest of functions, and it would
not be surprising if there are some global variables around that make
it thread unsafe. In Ada, one would nest these subsidiary functions inside
the equivalent of printf, and the global variables would become local
variables of printf itself, and therefore task specific.

In any case, I agree it is probably not a critical point. gcc uses static
links for all implementations (and a good thing too, because it is what
made pointers to inner procedures possible, something we depend on quite
a bit). Most of the Alsys implementations used displays, and to our
satisfaction (our = Alsys, I used to work for them :-) our measurements
showed that this was clearly more efficient, but in the big picture
of things, I doubt the difference was very significant.

Re: Q: access to subprogram

[Robert Dewar]

Jon says

"While the lack of direct support for recursive types across package
boundaries and lack of assertions are more important (IMO) goofs, and
while the evinced reasons for the latter one are mind numbingly
incomprehensible, this latest example would appear to take the crown
for the most stupefying goof."

Well it is always easy for users to decide that they want everything
and don't want to worry about the required resources, but a language
design can't be quite that cavalier in balancing requirements.

The fact of the matter is that providing for displays to work reasonably
easy *has* had value in getting at least some Ada 95 compilers to market
more easily than might have otherwise been the case.

I think everyone agrees that it is valuable to have several compilers
competing, and the balance in features vs implementability was always
a tricky one. Note that we did lose one compiler (the DEC Ada compiler),
and a large part of the reason for DEC's decision to get out of the
Ada compiler business was that they estimated it was too expensive
to modify their technology for Ada 95.

We have also lost at least one front end (the old Alsys technology, and
before that the Systeam technology), and more may dissappear before we
are through. At least the Alsys code generators proved largely adaptable
to Ada 95. Of course we have gained at least two new front ends (GNAT and
Intermetrics, so the front end situation looks healthy, although it is
interesting that both of these front ends were "from scratch".

One of the key requirements in the design was that Ada 95 not be such
a big change that it would be impractical to adapt existing Ada 83
front ends. At some points in the design, some people expressed the
opinion that this was impractical, and that we should assume that
"from scratch" development was the only practical path, but WG9
insisted on a  viewpoint that we should not restrict things in this
way. It appears that we at least partially succeeded, since at least
two Ada 95 front ends *are* adaptations of Ada 83 frontends.

There is certainly no doubt that Ada 95 is close to the limits of
acceptable front end complexity. Of course when you look at individual
features, it is hard to label any one feature as a back-breaking straw,
but that's what that little fable is all about after all :-)

Re: Q: access to subprogram

[Robert Dewar]

"While the lack of direct support for recursive types across package
boundaries and lack of assertions are more important (IMO) goofs, and
while the evinced reasons for the latter one are mind numbingly
incomprehensible, this latest example would appear to take the crown
for the most stupefying goof."

One interesting question to ask is how people are using Unrestricted_Access
in GNAT. During the discussion of this issue in WG9, we did have some
examples that purported to show the importance of this issue (I am
including Bill Taylor's discussion of iterators), but they were 
unconvincing, since there seemed to be alternative expressions that
were quite acceptable (the final vote on this issue was unanimous
by delegations as I remember, which means there was no strong advocate
for keeping the feature -- there certainly were some energetic arguments
over an extended period of time -- but by the end, everyone was convinced.

Now the difficulty with arguing by example is that of course you don't know
if you have found the critical examples or not. Note that the entertaining
thing about Jon labeling this as a stupefuing goof is that in the message
*just* before this one, he declared that real programs have no nesting
anyway, and of course all this business about closures is irrelevant
nonsense in programs that don't have any nesting!

So, the intersting question is: are there examples that people are
running into, involving nesting of course, since otherwise the issue
does not arise, where the use of Unrestricted_Access in GNAT seems
really critical. I must say I implemented this attribute because it
fell out literally free to do so (the real thing I needed was an access
attribute that did not require aliased, but the procedure case just
fell out), not because I had a critical use in mind, but I certainly
have found some uses for it, none that I would label as critical.

But if someone can present some really nice example where the use of
Unrestricted_Access is critical, that would be interesting.

Re: Q: access to subprogram

[Robert Dewar]

Richard said

"Ah, but
    - if a procedure at lexical level N
    - directly encloses a procedure at lexical level N+1
    - which is passed as a parameter
all that has to be copied into the parent's activation record is
        D[1:N]
whose size is known at compile time.  The child (or the child's wrapper)
needs to allocate space to hold the old values of D[1:N] when it is
entered."

Sure, this is the well known scheme that was used in the original Algol-60
compiler, and was used frequenly early on, and is almost never used now
(although as I mentioned in an earlier note, it is what Intel implements
in their hardware - the ENTER instruction).

The reason that this loses to static links is that unconditionally you
end up copying the display whether you need it or not. In the case of
static links, you only climb the chain (once per procedure if a reasonable
optimizer is in use) if it is needed. With the scheme above, you have a huge
chain of procedures that never do any up level references copying around
large displays if the nesting depth is deep, just so that someone in the
future might be able to reference one element of this display.

I wonder who designed this feature at Intel? Someone who knew a bit, but
not really enough, about how to deal with up level displays. The ENTER
instruction is an instruction that should never ever be used on any of
the Intel x86 arcitectures. Even the version with a zero count is highly
dubious if you look at the timings. A perfect example of silly CISC design.

Re: Q: access to subprogram

[Robert A Duff]

In article <4rud55$5b0@fu-berlin.de>,
Thomas Wolff <wolff@inf.fu-berlin.de> wrote:
>Robert Dewar: >>>Q: access to subprogram
> : Once you introduce unrestricted access to procedures, displays are a bit
> : of a menace, and probably this tips the scales in favor of static links
> : (if you believe like me that displays are more efficient, this can also
> : be read as meaning that the introduction of unrestricted access to procedures
> : would introduce distributed inefficiency -- but that still is NOT the reason
> : this feature was excluded).
>Why should displays be a menace where static links are not? Who would 
>actually prefer to really follow static links at all, effectively almost 
>*searching* for variables at run-time? Until now I thought this would 
>only be a theoretical concept and perhaps one of very early compilers.

Are you saying that static links are some sort of theoretical concept
from days-gone-by, and nowadays all smart compiler-writers use
displays?  Certainly not true.  I think *most* compiler-writers use
static links, just because it makes things simpler.  The horrible
"searching" you imagine is ameliorated by simple CSE elimination.  And
it's never terrible, since average nesting is approximately 0.01 levels
deep.

>Robert A Duff: >>>Q: access to subprogram
> : There are two major ways of implementing up-level variable references in
> : a language with nested procedures: Static links, and displays.  With
> : displays, it is somewhat difficult to implement passing nested
> : procedures as parameters, because you have to pass the display, which is
>This is not true, see below.
> : not of compile-time-known size.  Passing a static link is easy -- it's
> : just a single address.  Some implementations of Ada 83 used displays.
>Why not just push the display on the stack and pass its address??
>(If you really wanted to pass the display itself for some reason, you 
>could still use the program's maximal display size, wasting a few 
>bytes in these occasional cases.)

I agree -- it's not *that* big of a deal.  But "just push the display on
the stack" is an operation that involves compile-time-unknown-sized
stuff, which is where the complexity comes from.  And "use the max"
involves link-time knowledge, and most compilers (while very smart at
compile time) are very stupid at link time, and changing that fact
involves a lot of work.

> : The primary reason for not putting the feature in was to ease the pain
> : for such implementations.  This was done at a time when the general
> : feeling was that Ada 9X had more than enough new features, and we
> : shouldn't be adding things, but removing them.
>It is a very unfortunate decision to leave out a nice feature of 
>systematic program construction just for leaving out features.

Agreed.  But what's done is done.  (Until Ada 0X, or until you prefer
some other language.  ;-))

>Mark A Biggar: >>>Q: access to subprogram
> : In article <JSA.96Jul2221357@organon.com> jsa@organon.com (Jon S Anthony) wri
>tes
> : :
> : >In article <Dtxu2p.97F@world.std.com> bobduff@world.std.com (Robert A Duff) 
>wri
> : tes:
> : >> During the design of Ada 9X, we proposed a SAFE way of taking 'Access of
> : >> more-deeply-nesting subprograms.  To this day, I remain astonished and
> : >> sad that this particular feature didn't make it into Ada 95.  After
> : >> all, even Pascal has that feature!  And GNU C, which allows nested
> : >> functions (unlike standard C) allows this feature.
>I am sad about this, too. I have also always deplored that this 
>feature was removed during Wirth's transition from Pascal to Modula, 
>presumably for the same unconvincing reasons as used in this 
>discussion.

I was annoyed at that (about Modula-2) long before I joined the Ada 9X
project.  I think the real story is that there are two totally different
features, and both are desirable:

    1. You can pass procedures around, and copy them willy-nilly, and
       save them in global variables.  This is "call backs".  Pascal
       does not have this feature.  Modula-2 does, and Ada 95 does.

    2. You can pass procedures IN, and call them, but must never save
       them in global variables.  Pascal has this feature.  Modula-2
       does not.  Ada 95 does not, unless you count generic formal
       subprograms, which support MOST of this, but not quite all,
       and are overly verbose (IMHO).

Both of the above are desirable, but not at the same time.

Of course, the Smalltalk solution makes even Pascal's equivalent look
verbose.  And of course, I'm assuming in all of the above that "full
closures" are not supported (since they subsume all of the above, and
more, but require a totally different run-time model).

> : If I remember right, it was felt that implementing "closures" (which is the
> : solution to this problem) placed an unacceptable distributed overhead
> : on programs that didn't use the feature.  Also I think that half the then
> : current Ada implementations were using "static links" and the other half
> : were using "displays" and implementing "clousers" would have been real
> : difficult for one of those groups (the "display" bunch I think).
>No, with the solution indicated above there is no overhead (i. e. for 
>programs that don't use the feature) and no big inefficiency for programs 
>that do use the feature and no difficulty either apart from having to 
>understand what should happen in the implementation. When I recently 
>gave a talk on a topic related to this, some members of the audience 
>also seemed to recall they had the impression this was difficult or 
>inefficient... I wonder how this rumor evolved.

The "solution above" is viable, but is not the simplest solution.  The
simplest solution is to use static links.  (And that solution has the
desirably property that calling via an access-to-procedure will not
involve inordinate overhead.)

>Compare my other response in this thread for remarks about the 
>desirability of the discussed language feature.

Please understand that I'm arguing from two opposing points of view
here.  (1) I really think downward closures should have been included
in Ada 95, and (2) I'm trying to explain the arguments about why they
were not (which I disagree with, but are nonetheless rational
arguments).

- Bob

Re: Q: access to subprogram

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

Re: Q: access to subprogram

[Richard A. O'Keefe]

bobduff@world.std.com (Robert A Duff) writes:
>I agree -- it's not *that* big of a deal.  But "just push the display on
>the stack" is an operation that involves compile-time-unknown-sized
>stuff, which is where the complexity comes from.

Ah, but 
    - if a procedure at lexical level N
    - directly encloses a procedure at lexical level N+1
    - which is passed as a parameter
all that has to be copied into the parent's activation record is
	D[1:N]
whose size is known at compile time.  The child (or the child's wrapper)
needs to allocate space to hold the old values of D[1:N] when it is
entered.

>I was annoyed at that (about Modula-2) long before I joined the Ada 9X
>project.  I think the real story is that there are two totally different
>features, and both are desirable:

>    1. You can pass procedures around, and copy them willy-nilly, and
>       save them in global variables.  This is "call backs".  Pascal
>       does not have this feature.  Modula-2 does, and Ada 95 does.

Lisp, Scheme, ML, ... have this.

>    2. You can pass procedures IN, and call them, but must never save
>       them in global variables.  Pascal has this feature.  Modula-2
>       does not.  Ada 95 does not, unless you count generic formal
>       subprograms, which support MOST of this, but not quite all,
>       and are overly verbose (IMHO).

>Both of the above are desirable, but not at the same time.

I'm not quite sure what "not at the same time means".  If it means
"not in the same language", I'd disagree.  If it means "not in the
same program", I wouldn't agree either.

There's someone here doing a Masters thesis on adding support to Ada for
a particular design pattern.  I don't want to say too much, because he's
just beginning implementation studies (what a wonderful thing GNAT is),
but basically, callbacks are needed to do it right, and Ada's rules are
a major headache.  But the very programs that will benefit from this
facility are also likely to abstract iteration as well, thus needing
1 and 2 in the same program.  In Lisp, there would be no point in his
thesis as the whole thing is not only utterly trivial, it is a well
understood and long used technique.

My PL/I is rather rusty, but I know rav reads c.l.a.
Doesn't PL/I have procedure variables as well as procedure parameters?

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

Re: Q: access to subprogram

[Robert A Duff]

In article <4rvo07$bbl@goanna.cs.rmit.edu.au>,
Richard A. O'Keefe <ok@goanna.cs.rmit.edu.au> wrote:
>>    1. You can pass procedures around, and copy them willy-nilly, and
>>       save them in global variables.  This is "call backs".  Pascal
>>       does not have this feature.  Modula-2 does, and Ada 95 does.
>
>Lisp, Scheme, ML, ... have this.
>
>>    2. You can pass procedures IN, and call them, but must never save
>>       them in global variables.  Pascal has this feature.  Modula-2
>>       does not.  Ada 95 does not, unless you count generic formal
>>       subprograms, which support MOST of this, but not quite all,
>>       and are overly verbose (IMHO).

I didn't really describe what I meant very well.  In (1), I meant that
you can assign them into global variables, but you're not allowed to
pass nested ones.  In (2), I meant that you get nesting, but not the
assignment.

Lisp has full closures, which subsumes both (1) and (2), and also
achieves some things that neither (1) and (2) can do.

>>Both of the above are desirable, but not at the same time.
>
>I'm not quite sure what "not at the same time means".  If it means
>"not in the same language", I'd disagree.  If it means "not in the
>same program", I wouldn't agree either.

I didn't mean either of those two.  I agree that a language should have
both 1 and 2, and you should be allowed to use them in the same program.
I just meant that the purposes are different, and you can view them as
two separate features.  You use (1), for example, when you want to hand
a procedure to the windowing system, saying please call it when the
mouse is clicked.  You use (2), for example, in iterators -- please
crawl around this data structure, and call so-and-so procedure for each
component.

This is all assuming that you don't want to pay for full closures.  (As
I said, full closures subsume both of the above features.)  My point is
that you can retain the stack-based run-time model of Ada, and retain
safety against dangling pointers, and still support both (1) and (2) in
the language.  And the safety doesn't need to involve expensive run-time
checks.

- Bob

Re: Q: access to subprogram

[Thomas Wolff]

A few more responses and remarks about implementation and design issues 
of procedure parameters (please excuse if some of them are redundant 
due to other's remarks), consisting of five sections:
1. about the design decision
2. about the implementation and its assumed overhead
3. about incorrect implementations
4. about static chains
5. about future design issues

-----------------------------------------------------------------------------
1. about the design decision

Robert A Duff:
 : Remember that the discussion during the design of Ada 9X was NOT about
 : "we don't know how to implement this in theory" -- it was more like,
 : "we've got a multi-target back end (back ends), and we don't want to
 : mess with it (them)".  Also note that I argued strongly IN FAVOR of
 : downward closures, and lost the argument.
To base design decisions for a language supposed to be an important one 
on compiler considerations is a very bad idea, I think! A shame that you 
lost that argument...;

And Norman H. Cohen:
 : (By the way, I share Bob Duff's amazement at the noninclusion of downward
 : closures--we called them downward at the time--in Ada 95, and I say this
 : as one of those Bob described as urging the removal rather than the
 : addition of proposed Ada-95 features.  I viewed the inclusion of downward
 : closures as the REMOVAL of an arbitrary restriction.  The decision was
 : not made in ignorance.  Bill Taylor had made what I considered an
 : irrefutable case for downward closures, showing how much easier it would
 : be to write iterators if downward closures were allowed.  It came down to
 : a conflict between the interests of Ada programmers and the interests of
 : a minority of Ada implementors, and in this case the interests of the few
 : implementors using displays prevailed.)
So the shame goes on this minority of Ada implementors who were so lame 
not to recognize how an efficient implementation with displays can be done.

-----------------------------------------------------------------------------
2. about the implementation and its assumed overhead

Robert A Duff:

 : 1. Displays are too much trouble, in the presence of downward closures.
No, you only need to find the right trick once. (How much trouble is 
"too much" anyway?)

 : 2. Therefore, if we have that feature, compiler writers are forced to
 : use static links (...)
 : 
 : 3. Displays are clearly faster than static links, for normal direct calls.
 : 
 : 4. Therefore, we've got a distributed overhead; QED.
Due to the invalid first assumption, this pseudo-proof is bogus.


Richard A. O'Keefe:
 : What happened?  When did everyone forget?
Indeed.
 : Yes, there is overhead:  but the overhead of rewinding the display
 : is incurred only on entry to / exit from a formal procedure; there
 : need be *NO* extra overhead for calling visible procedures.

Robert Dewar:
 : > ... the provision
 : > of closures would push you away from using displays, and hence 
No, ...

Robert Dewar:
 : parameters in Pascal or Algol, if done right, clearly violates this, and
 : requires entire sections of displays to be saved and restored.
But only for calls of formal procedures.

 : 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
I do not quite understand your argument about who followed which design 
choice as I thought according to this discussion both Adas cannot pass 
procedure parameters.
However, contradicting the feature with display implementation is not 
an inevitable consequence as has meanwhile been shown in this thread.


I said:
 : Why not just push the display on the stack and pass its address??
 : (If you really wanted to pass the display itself for some reason, you
 : could still use the program's maximal display size, wasting a few
 : bytes in these occasional cases.)

Robert Dewar:
 :   That's the original Algol-60 approach but it is never used these
 :   days that I know of, since it is in practice definitely inferior
 :   to both static links and the use of global displays. It introduces
 :   unconditionally a large overhead of copying the display at every
 :   call whether or not it is useful to do so.
This overhead would not have to be taken on every call as you say 
but only on calls of formal procedures. Don't you think this is acceptable?

Robert A Duff:
 : I agree -- it's not *that* big of a deal.  But "just push the display on
 : the stack" is an operation that involves compile-time-unknown-sized
 : stuff, which is where the complexity comes from.  And "use the max"
 : involves link-time knowledge, and most compilers (while very smart at
 : compile time) are very stupid at link time, and changing that fact
 : involves a lot of work.
Norman H. Cohen:
 : The size of a display for a given procedure IS known at compile time.
 : It is equal to the number of procedures that lexically surround that
 : procedure (give or take one, depending on the details of a given
 : implementation).


Robert A Duff about my idea of implementing it:
 : The "solution above" is viable, but is not the simplest solution.  The
It is probably the simplest solution that uses displays.
 : simplest solution is to use static links.  (And that solution has the
 : desirable property that calling via an access-to-procedure will not
 : involve inordinate overhead.)
Even in the display solutions that do have overhead I would not call 
it "inordinate" - anyway, as Richard A. O'Keefe also describes, there 
need be no overhead at all.
But I don't understand why you think a "simple" solution (which is 
disputable) is the best solution for such a basic thing. As I said 
before, I don't see how static chains can show an advantage without 
relying heavily on optimization.

-----------------------------------------------------------------------------
3. about incorrect implementations

Robert Dewar:
 : By the way, over the years, many Pascal and Algol compilers have cheated.
This is also known as the "most-recent" error.
 : 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.
The test program fits on a cake.
- But then, how should I interpret your words:
 : 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.
This is just the way compilers have cheated, i. e. no correct implementation 
of the Algol semantics, said "most-recent" error.

-----------------------------------------------------------------------------
4. about static chains

I said:
 : Why should displays be a menace where static links are not? Who would
 : actually prefer to really follow static links at all, effectively almost
 : *searching* for variables at run-time? Until now I thought this would
 : only be a theoretical concept and perhaps one of very early compilers.
Robert A Duff:
 : Are you saying that static links are some sort of theoretical concept
 : from days-gone-by, and nowadays all smart compiler-writers use
 : displays?  Certainly not true.  I think *most* compiler-writers use
 : static links, just because it makes things simpler.  The horrible
 : "searching" you imagine is ameliorated by simple CSE elimination.  And
 : it's never terrible, since average nesting is approximately 0.01 levels
 : deep.
Robert Dewar:
 :   Static links are by far the more common way of handling uplevel
 :   references, and are far from being "only a theoretical concept".
 :   Most modern compilers use static links. There is no searching
 :   involved, just loading the entries that are needed, and if they
 :   are used frequently, they will stay in registers anyway.
By "almost *searching*" I meant that the chain has to be followed until 
the desired level is reached, thus having a few indirections per access.
I would, however, not like the idea that a compiler's efficiency in 
a basic design question depends on optimization.
 :   In fact the idea of static links came a little later on, the early
 :   Algol-60 compilers used displays.
Thanks to you two to point out that static chains are really used today.
(I still wonder why.)

-----------------------------------------------------------------------------
5. about future design issues

I:
 : >I am sad about this, too. I have also always deplored that this 
 : >feature was removed during Wirth's transition from Pascal to Modula, 
 : >presumably for the same unconvincing reasons as used in this 
 : >discussion.
 : 
Robert A Duff:
 : I was annoyed at that (about Modula-2) long before I joined the Ada 9X
 : project.  I think the real story is that there are two totally different
 : features, and both are desirable:
 : 
 :     1. You can pass procedures around, and copy them willy-nilly, and
 :        save them in global variables.  This is "call backs".  Pascal
 :        does not have this feature.  Modula-2 does, and Ada 95 does.
 : 
 :     2. You can pass procedures IN, and call them, but must never save
 :        them in global variables.  Pascal has this feature.  Modula-2
 :        does not.  Ada 95 does not, unless you count generic formal
 :        subprograms, which support MOST of this, but not quite all,
 :        and are overly verbose (IMHO).
 : 
 : Both of the above are desirable, but not at the same time.
Is there any research in the literature about making these two more 
compatible in terms of safety and efficiency?

Robert A Duff:
 : >Compare my other response in this thread for remarks about the 
 : >desirability of the discussed language feature.
 : 
 : Please understand that I'm arguing from two opposing points of view
 : here.  (1) I really think downward closures should have been included
 : in Ada 95, and (2) I'm trying to explain the arguments about why they
 : were not (which I disagree with, but are nonetheless rational
 : arguments).
I understand this and have already quoted your previous remark
 : Also note that I argued strongly IN FAVOR of
 : downward closures, and lost the argument.
Maybe your position was not strong enough because you thought yourself 
the feature would require overhead?
Can we hope you'll take up the argument when it comes to Ada 99?

-----------------------------------------------------------------------------
Thomas Wolff

Re: Q: access to subprogram

[Robert A Duff]

In article <4s0qm7$htm@fu-berlin.de>,
Thomas Wolff <wolff@inf.fu-berlin.de> wrote:
>I do not quite understand your argument about who followed which design 
>choice as I thought according to this discussion both Adas cannot pass 
>procedure parameters.

Ada 83 does not.  Ada 95 does, so long as the actual procedure is not
too nested.  It's the more-nested case that we're all chatting about.

And of course Ada 83 and Ada 95 both allow passing procedures to
generics (even the nested case).  This was part of the argument -- who
needs downward closures when we have generics.  (The generic solution is
horribly verbose, in my opinion, but it does work in most cases.)

>Maybe your position was not strong enough because you thought yourself 
>the feature would require overhead?
>Can we hope you'll take up the argument when it comes to Ada 99?

Ada 99?  Maybe Ada 07 or so...  I'll be too old by then.  ;-)

- Bob

Re: Q: access to subprogram

[Ronald Cole]

dewar@cs.nyu.edu (Robert Dewar) writes:
> Ronald Cole said (commenting on my claim that GCC did not have multiple
> backends)
> 
> Not true.  A single instance of GCC doesn't support multiple machine
> targets (other than the -m options for some processor families).  GCC
> has to be recompiled to support different machine descriptions (that's
> what the -b and -V options of gcc are for).  I consider this as having
> multiple backends.
> 
> That's not what I meant, yes, of course there are multiple backends at
> the object level, but not at the source level.

Again not true.  Yes, the source contains all the parts for each
backend, but all the parts are not used to build the backend.
Configure() will determine the correct source files and create links
to properly build one target backend.  The multiple backends at the
source level are kept under the config subdirectory and grouped by
architecture.  I count thirty distinct backends:

1750a/1750a.md      fx80/fx80.md        m88k/m88k.md        sh/sh.md
a29k/a29k.md        gmicro/gmicro.md    mips/mips.md        sparc/sparc.md
alpha/alpha.md      h8300/h8300.md      ns32k/ns32k.md      spur/spur.md
arm/arm.md          i370/i370.md        pa/pa.md            tahoe/tahoe.md
clipper/clipper.md  i386/i386.md        pdp11/pdp11.md      vax/vax.md
convex/convex.md    i860/i860.md        pyr/pyr.md          we32k/we32k.md
dsp16xx/dsp16xx.md  i960/i960.md        romp/romp.md
elxsi/elxsi.md      m68k/m68k.md        rs6000/rs6000.md

> Most Ada technologies have a single front end for all targets (though
> Ronald Cole would presumably call these multiple front ends too, because
> there are certanly separate object versions),

You presume incorrectly.  I consider the frontend to be defined by the
language it accepts, not by the host architecture or the number of
object files in an implementation.  Likewise, I consider the backend
to be defined by the object code it produces.

> But for technologies like GCC, where there is only one source program for
> both front end and backend (though in both cases multiple executables),
> this distinction is not significant.

But it is.  While the union of the sources for each target
architecture is the GCC source tree, the difference of the sources for
each target architecture is not the null set.  

-- 
Ronald Cole                                     E-mail: ronald@ridgecrest.ca.us
President, CEO                                          zippy@ecst.csuchico.edu
Forte International                                Fax: (619) 384-2346
     My PGP fingerprint: E9 A8 E3 68 61 88 EF 43  56 2B CE 3E E9 8F 3F 2B

Re: Q: access to subprogram

[Robert Dewar]

Thomas Wolff said

  "To base design decisions for a language supposed to be an important one
   on compiler considerations is a very bad idea, I think! A shame that you
   lost that argument..."

You cannot really mean this as an absolute principle. All languages are
designed with some concern for implementability. A wonderful Ada 95 which
no one implemented would not be much use to anyone. Sure it is true that
any single feature will not make the difference (but that's what camels
and straws are all about).

You can argue that the decision was made wrong in this particular case,
but to say that as a general principle it is wrong to consider implementation
issues seems quite off base.

 : 1. Displays are too much trouble, in the presence of downward closures.
   No, you only need to find the right trick once. (How much trouble is
   "too much" anyway?)

It is not just that they are too much trouble, but that they are inefficient
for the purpose at hand (when procedure pointers are around). As to only
needing to find the right trick once, that's wrong. Complete solutions need
linker involvement, and that tends to mean finding the solution more than
once and fighting various linker capabilities. As to how much trouble is
"too much" that of course is central to the judgment of the trade off.

  Robert Dewar:
 : parameters in Pascal or Algol, if done right, clearly violates this, and
 : requires entire sections of displays to be saved and restored.
  But only for calls of formal procedures.

Yes, and calls of formal procedures are what we are talking about here!

  I do not quite understand your argument about who followed which design
  choice as I thought according to this discussion both Adas cannot pass
  procedure parameters.
  However, contradicting the feature with display implementation is not
  an inevitable consequence as has meanwhile been shown in this thread.

No, of course you can pass procedure parameters in Ada 95. You really
ought to look at the language feature here to see how the accessibility
restrictions work. You can have procedure pointers and procedures as
parameters in Ada 95, it is just that there are some limitations.
Obviously a careful understanding of the limitations is important in
judging how much functionality has been given up for implementation
concerns.

If you are assuming that Ada 95 completely eliminated procedure parameters,
then your understanding of this thread is a bit distorted, since that would
clearly have been totally unacceptable to everyone.

  This overhead would not have to be taken on every call as you say
  but only on calls of formal procedures. Don't you think this is acceptable?

I don't like the overhead, but could live with it. But in any case
that has nothing at all to do with the decision to exclude the
fully general solution, although it is true that calling a formal procedure
in Ada 95 does NOT require this overhead, even if you are using displays.
The issue was the difficulty of implementation, not the overhead. We
discussed this difficulty in considerable detail (with the implementors
involved), so we certainly had the information to understand what these
difficulties were.

  : 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.
  This is just the way compilers have cheated, i. e. no correct implementation
  of the Algol semantics, said "most-recent" error.

Here I lose you technically. The invariant I give is EXACTLY the correct
one for Algol-60 semantics, and for Ada 83 and Ada 95 semantics. As I
noted it can be modified to make it more efficient by considering only
procedures which contain other procedures, but you seem to contest the
invariant I state above, and that I don't understand.

  By "almost *searching*" I meant that the chain has to be followed until
  the desired level is reached, thus having a few indirections per access.
  I would, however, not like the idea that a compiler's efficiency in
  a basic design question depends on optimization.

The idea of a compiler's efficiency depending on optimization does not
seem odd at all to me. Certainly your puzzlement that static chains
are widely used is perhaps explained by this difference. The fundamental
assumption that is made in choosing static links is the assumption that
compilers will successfully eliminate wasteful duplicate following
of the chain.


Ah, looking back, I think I see why you did not like my invariant, you
are assuming it is applied to a single global display, and that of course
is not possible with generalized procedure parameters, although it is
possible with the procedure parameters of Ada 95. OK, exactly so! You
need multiple displays if you have procedure parameters, and that is
the source of the unpleasant overhead.

Re: Q: access to subprogram

[Robert Dewar]

"I am getting tired of insults"

Sorry, did not mean to insult you, but you seemed not to understand what
was being said, and now I understand why from your article.

The concern about distributed overhead is not that the new feature
per se generates distributed overhead. Yes of course it is trivially
true that if you are using displays, you only pay the penalty when
you actually use procedure pointers and procedure arguments. As you
point out, many real compilers have been written this way.

But then, rather than distributed overhead, if you take the approach of
using displays, you have two problems

  - you have greatly increased overhead when the feature is used. Enough
    increased overhead that almost certainly the proper design approach
    is to use static links instead.

  - if you use displays anyway, then the implementation is greatly 
  - complicated. The maximum depth of the display is not known till
  - link time, so either you take a huge hit in efficiency by using
    some absurd maximum value (I have seen nesting depths well over
    ten coming from the use of subunits), or you have to mess at
    the linker level to determine the maximum, and then all data
    structures that depend on this maximum become dynamcically sized
    objects which must be dynamically allocated.

It is this second concern about implementation difficulty that lead
to the WG9 decision to restrict the feature so that such dynamic
concerns would not be necessary, and also to ensure that the display
model could be used without introducing undue overhead mentioned as
the first concern above.

The distributed overhead argument did *not* enter into the discussion.
The distributed overhead concern (as expressed in Steelman) comes from
a concern that in general static links are less efficient than displays.
So if the language is designed so that static links are the right choice,
then you have a distributed overhead. Of course this is an arguable
point, as you can see from the discussoin, not everyone accepts that
static links are less efficient than displays.

But anyway, your "mighty puzzlement" arises from a confusion on your part
as to the argument that was being made. No one at any point claimed that
implementing procedure pointers in the context of a display implementation
causes distributed overhead. As you point out, it does not, and everyone
agrees with this, and no one has claimed anything to the contrary, and as
I point out above, the distributed overhead argument did not enter into
the WG9 discussions substantially, except in the following sense. There
were people who said things like "well displays are a silly thing to use
in any case, so why on earth are we worrying about compilers that make
such a silly choice." And the discussion of the viabiliyt of displays
in general did come up in that context.

Basically the issue boiled down quite simply to a pragmatic issue. If
the procedure pointers were made general, would this be too much of
an implementation burden for existing implementations usinvg displays?
And how does this balance against the increased utility?

Answering such questions is always difficult because it fundamentally
involves comparing apples and oranges. There is no doubt that it would
have resulted in a substantial implementation burden, and here is no
doubt that it would have been a useful feature. WG9 decided the former
had precedence. Who knows, Richard, maybe you would have agreed to if
you had listened to the detalied arguments (this was very extenisvely
discussed) -- there were people there who felt as you do now when
we started the discussion, but changed their minds.

As to whether the decision is right in retrospect? hard to say. So far
I have not seen any really convincing examples. Perhaps some will appear.
Bob, it would be nice to post the original "safe" design here. Who knows
perhaps one day some extensions might be made to GNAT (certainly we are
seriously considering, and discussing with Tuck, implementing some variant
of his "with type" proposal to deal with the recursive type situation).
Note that any such extensions would of course be under a switch to
keep them under control :-)

Re: Q: access to subprogram

[Robert Dewar]

Jon said

"The reasons for leaving out recursive types across packages definitely
make sense, but are just not convincing (pretty much everyone agrees
now on this).  The ones for leaving out assertions that I've seen here
(certain people getting wigged out over possible optimization effects)
basically make no sense."

OK, so you know from that thread the three separate and quite distinct
possible semantics for an assert pragma. Which of these three is
"obviously what is wanted" according to you? :-)

Just for interest, what areas of the language would you have left out
(to leave room for your favorite features!) ?

Re: Q: access to subprogram

[Richard Kenner]

In article <m2u3vfem42.fsf@devo.ridgecrest.ca.us> Ronald Cole <ronald@ridgecrest.ca.us> writes:
>Again not true.  Yes, the source contains all the parts for each
>backend, but all the parts are not used to build the backend.
>Configure() will determine the correct source files and create links
>to properly build one target backend.  The multiple backends at the
>source level are kept under the config subdirectory and grouped by
>architecture.  I count thirty distinct backends:

What you are actually counting are thirty distinct configuration files
used to tailor the single backend to a particular target machine.

>You presume incorrectly.  I consider the frontend to be defined by the
>language it accepts, not by the host architecture or the number of
>object files in an implementation.  Likewise, I consider the backend
>to be defined by the object code it produces.

So long as you state the definitions you are using, you are free to
use any you want.  But whatever words you use, there is a major
distinction between the GCC approach and that used by other
multi-target systems.

Re: Q: access to subprogram

[Robert Dewar]

Ronald Cole said

"Again not true.  Yes, the source contains all the parts for each
backend, but all the parts are not used to build the backend.
Configure() will determine the correct source files and create links
to properly build one target backend.  The multiple backends at the
source level are kept under the config subdirectory and grouped by
architecture.  I count thirty distinct backends:"

Ronald is still missing the point that started this thread. 

There are two kinds of technologies. In one, the code generators for
different target architectures are completely separate programs that
may not even have the same overall design, let alone the same souce
code. This approach is typical of a number of Ada 83 compiler technologies.

The other kind of technology uses a single common source base for all
backends. GCC is in this category. Yes, the configuration files differ,
but the great majority of the code is common. This is a critical feature
of GCC, and is what allows easy porting of the technology. To port to
a new architecture, a new configuration file needs to be written, but
not a new code generator.

In the context of the original point in this thread, the critical thing is
that if you have a change to the language which affects the backend, rather
than just the front end, then the two technology approaches will be in a very
different situation. In one case, you have to change multiple separate
programs, in the other, unless the change affects configuration files, you
only have to change one program. 

So far the Ada 95 changes have required zero changes to the configuration
files, although eventually we anticipate some minor changes being 
required (and of course no change to configuration files is really minor,
precisely because it has to be done in multiple cases).

Ronald's technical comments on the GCC structure, while quite correct (after
all I know this technology perfectly well, so we do not disagree on what
is there) obscure the central point. There is a BIG difference between
single-common-source-code-generator technologies and multiple-code-generator
technologies when it comes to language changes that affect the back end.

One of the design points in Ada 95 was to minimize changes that would impact
backends, precisely because some Ada technologies (those using multiple
separate front ends) could have been severely affected by such changes.
On the other hand, if you use the GCC approach, the disctinction is not
so important, and had we known that *all* Ada technologies used a single
common source approach we might have made some design decisions differently,
but in fact we knew this definitely was NOT the case.

Re: Q: access to subprogram

[Robert Dewar]

Jon said

"irrelevant nonsense (that would just be plain stupid), I said that
most programs don't have much nesting and that without nesting no cost
is incurred and therefore any argument about distributed cost in the
user model as a reason for not having them was nonsense.  And that is
still just plain true."

Just to be absolutely clear on this, since it seems to have caused a lot
of confusion :-)

The Steelman (and hence Ada 83) reasoning for not allowing procedure
parameters was indeed influenced by concerns about distributed cost
of uplevel reference mechanisms (if you read Steelman, you will see that
concern expressed in black-and-white).

Whether this concern is legitimate or not probably can't be settled without
some hard data on existing Ada programs (what you need is dynamic traces
that show how many calls are to outer level procedures, and how many
calls are to procedures that contain no nested procedures). At least that
will allow you to track the cost of display/static-chain handling. If you
think uplevel references themselves are a significant factor, as some do
in this thread, then you also need dynamic data on the number of such
references and how deep they go (by procedure invocation, so that you
can factor out optimization effects). As is clear from the thread, Jon
and I simply disagree on the bottom line here, but I don't think any
more arguments without data can illuminate this discussion further (it
is by the way a *very* old discussion).

The Ada 95 reasoning for not allowing completely general procedure
parameters (that would handle the case where nested procedures are
involved in all cases), has NOTHING to do with distributed cost. It
had solely to do with concerns about the cost of implementation, and
if you want to track Norman's very nice precis of the written discussion
on this issue, you will see how the back-and-forth went on this issue.

Again, the question of whether the trade-off was made correctly can
be discussed. That's more of a subjective issue, but it would be
influenced in retrospect by nice examples of things you can't do but
would be nice to be able to do, but you can't do in any other convenient
way, and one would think that if there are such, some of them might have
surfaced by now.

Re: Q: access to subprogram

[Robert Dewar]

"As Norm mentioned, most of these issues are documented in the "mrtcomments"
available online.  I hope the designers of Ada 0Y (oh-why) will read these
discussions carefully for the next revision--if there is one--so that they
can make a list of the fallacious arguments that will no doubt pop up again."

fallacious arguments on either side :-)

the same argument of implementability vs functionality will of course arise
if the language is revisited, and the view in either case may have changed.

On the one hand, implementors may come and say "well in retrospect that is
not such a big deal", or "Gosh, this was even more critical than we though
that this be left out because  xxx", and of course a different cast of
implementors and technologies will be around.

On the other hand, programmers may come and say "turns out that was not a 
critical feature after all, so it did not matter that we did not put it in",
or they may say "drat! I *really* find the lack of this feature a pain, and
it should be fixed now, here are some examples: xxx"

Different people will feel different ways (for example I find the lack of
in out and out parameters for functions a real pain, and suspect I will
continue to do so in the future, and that wasn't even left out befcause
of implementation concerns, but rather purity concerns).

One thing to notice is that once a feature is put *in*, then it never comes
out again, even if programmers arrive ten years from now and say "hmm,
we have found that feature useless, it can be removed". I find the
obsolescent features Annex in the Ada 95 a useless fantasy, when we
revise the language, we will still end up levaing these features in
because of compatibility concerns (remember what happened with COBOL 8X
and the attempt to remove ALTER).

Given that ratchet effect, one prefers to leave features out if you are
not absolutely sure they belong in!

Re: Q: access to subprogram

[Norman H. Cohen]

In article <ROGOFF.96Jul8155205@sccm.Stanford.EDU>, rogoff@sccm.Stanford.EDU
(Brian Rogoff) writes: 

|> ncohen@watson.ibm.com (Norman H. Cohen) writes: 
...
|>                            Bill Taylor had made what I considered an
|>    irrefutable case for downward closures, showing how much easier it would
|>    be to write iterators if downward closures were allowed.  It came down to
|>    a conflict between the interests of Ada programmers and the interests of
|>    a minority of Ada implementors, and in this case the interests of the few
|>    implementors using displays prevailed.)
|>
|> Could you summarize or provide a reference to Bill Taylor's work? Does it
|> answer the objection that downward closures impose an inefficiency on programs
|> that don't use them?

Bill Taylor's contribution was part of an ongoing discussion in the form
of comments sent to the Mapping/Revision Team during the design of Ada 9X.
All of these comments from June 1992 on are publicly available in the
following directory: 

ftp://sw-eng.falls-church.va.us/public/AdaIC/standards/95com/mrtcomments/

All the comments through April 1994 are in files with names of the form
YYMMmrt.zip, where YY and MM are the year and month the comment was
received.  (Thus all comments from May 1993 are in 9305mrt.zip.) Starting
with May 1994, there are individual daily files, such as 94.0501 for all
comments received on May 1, 1994.

The discussion on downward closures and their impact on display
implementations included the following comments: 

Date              Comment ID  Author          My summary

April 29, 1993    93.2622.b   Bill Taylor     The initial message about
                                              iterators mentioned above.

May 1, 1993       93-2628.b   Robert Duff     Says he likes the feature,
                                              but Robert Dewar has
                                              frightened WG9 members
                                              about the cost, and the MRT
                                              won't add downward closures
                                              until someone convinces WG9
                                              otherwise.  Claims the size
                                              of a display is not known
                                              at compile time.

May 3, 1993       93-2634.a   Norman Cohen    Reply to Duff, asserting
                                              that the size of a display
                                              IS known at compile time.
                                              Foreshadows an identical
                                              exchange that will take
                                              place on comp.lang.ada in
                                              July 1996.  :-)

May 3, 1993       93-2635.a   Robert Duff     Reply to Cohen.  Size of a
                                              display is not known at the
                                              site of a call through a
                                              pointer.  Says he hates
                                              arguing against a feature
                                              he likes.

May 3, 1993       93-2637.a   Randy Brukardt  Reports that Janus/Ada uses
                              (RR Software)   displays.  Proposes a
                                              workaround involving
                                              unchecked conversion.

May 3, 1993       93-2638.a   Robert Duff     Reply to Brukardt, asking
                                              him to explain workaround.

May 4, 1993       93-2644.a   Antoine Bertier Reports that Alsys uses
                              (Alsys)         displays for most of its
                                              compilers.

May 4, 1993       93-2645.a   Ted Baker       Calls displays an
                                              "anachronism", except on
                                              register-poor machines.

May 4, 1993       93-2646.a   Randy Brukardt  Reply to Duff, explaining
                                              his workaround and
                                              conceding that it is not
                                              portable to compilers that
                                              do NOT use displays.

May 5, 1993       93-2647.a   Brian Dobbing   Also reports that Alsys
                              (Alsys)         uses displays, states that
                                              Alsys cannot afford any
                                              more language changes with
                                              such great impact on their
                                              compilers, and states that
                                              neither the display
                                              approach nor the static
                                              link approach is always
                                              the right choice.

May 5, 1993       93-2651.a   Bill Taylor     Points out that Brukhardt's
                                              proposed workaround does
                                              not work when the pointed-
                                              to procedures reference
                                              data in surrounding scopes,
                                              as they do in his iterators
                                              example.

May 5, 1993       93-2655.a   Robert Dewar    Reply to Baker, defending
                                              displays and asserting
                                              that they can be quite
                                              efficient.

May 5, 1993       93-2656.a   Robert Eachus   Experiments (with a
                                              compiler that was altered
                                              to send Eachus e-mail every
                                              time code was generated for
                                              a call on a nested
                                              subprogram!) show that
                                              calls on nested procedure
                                              are rare, so the expense of
                                              supporting this feature is
                                              not justified.

May 6, 1993       93-2661.a   Ted Baker       Reply to Dewar, claiming
                                              that downward closures were
                                              important for the kind of
                                              applications that justified
                                              ANY inclusion of 'Access
                                              for nested subprograms in
                                              Ada 9X, and worth the cost;
                                              but admitting that Brian
                                              Dobbing's economic argument
                                              might be the deciding
                                              consideration.

May 11, 1993      93-2676.a   Randy Brukardt  Reply to Baker.

May 11, 1993      93-2676.b   Randy Brukardt  States that downward
                                              closures impose a
                                              distributed overhead on all
                                              uses of generics when
                                              generics are implemented by
                                              shared code for all
                                              instances, as in Janus/Ada.

January 14, 1994  94-3669.a   Bjorn Kallberg  An eloquent case for the
                                              importance of downward
                                              closures, pointing out that
                                              their omission would create
                                              the only case in which Ada
                                              is not a functional
                                              superset of Pascal.

February 15, 1994 LSN 1083    Robert Duff     A dispassionate analysis
                                              of all sides of the issue,
                                              explaining why the MRT
                                              decided not to include
                                              downward closures in Ada 9X.

March 4, 1994     94-3985.a   David Tombs     An empassioned plea to
                                              reconsider this decision.

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Q: access to subprogram

[Jon S Anthony]

In article <dewar.836963120@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:

> Jon says
> 
> "While the lack of direct support for recursive types across package
> boundaries and lack of assertions are more important (IMO) goofs, and
> while the evinced reasons for the latter one are mind numbingly
> incomprehensible, this latest example would appear to take the crown
> for the most stupefying goof."
> 
> Well it is always easy for users to decide that they want everything
> and don't want to worry about the required resources, but a language
> design can't be quite that cavalier in balancing requirements.

We had a couple private exchanges on this point.  But just to be
clear: I did not mean that I thought the leaving of "partial closures"
out _itself_ was "stupefying", rather the purported _reasons_ for
doing so are.

The reasons for leaving out recursive types across packages definitely
make sense, but are just not convincing (pretty much everyone agrees
now on this).  The ones for leaving out assertions that I've seen here
(certain people getting wigged out over possible optimization effects)
basically make no sense.

Also, I am far from the camp that wants everything.  Personally I'd
flush various chunks of what eventually got accepted because they fuzz
up the focus of the language and require a fair amount of resources to
get right.  A lot of effort spent on stuff that is on the fringes of
where the language will be applied (and thus not see much actual use).
The saving grace is that the user's model of Ada is orthogonal enough
that they can pretty much be completely ignored.

And at the end of the day, it's still, without doubt, the best of the
viable options.


/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[Jon S Anthony]

In article <dewar.836962533@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:

> Jon Anthony says
> 
> "I don't see how, as most programs will not have _any_ nesting.
> Period.  So displays or static links are irrelevant for nearly all
> cases.  So, the issue is irrelevant to [probably not even hyperbole
> here] 99+% of subprogram calls.  Which means that there really is no
> distributed overhead (at least not as I understand the term)."
> 
> This is wildly overstated. I would say that any large program that has
> no nested procedures at all is poorly written, and I have seen very
> few large program (actually none in Ada) that had no nesting at all.

I can agree with this (even the "wildly" bit :-))

> On the other hand, I have *quite* often seen programs using nesting
> *very* extensively, where the program was divided into large procedures,
> containing many nested procedures, where the majority of calls are to
> procedures contained within other procedures.

And I would say that these are examples where "poorly written" would
equally apply.


> I don't believe Jon's figure of 99+% of subprogram calls being to library
> level subprograms is anywhere near right, and I would guess it is just
> a rhetorical guess rather than any kind of measurement. Across an

Yes, no real data - only anecdotal evidence. Hence the "hyperbole
caveat".

> admitedly small sample of large programs that I was involved in measuring,
> we saw over 80% of the calls being to procedures that were nested inside
> other procedures.

I find that a little surprising, but facts is facts.  I would also say
that this is very likely an indication that something has gone wrong.
Not in the measurement, but in the programs.


> In any case, I agree it is probably not a critical point. gcc uses static

Check!


/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[Jon S Anthony]

In article <dewar.836964092@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:

> if you have found the critical examples or not. Note that the entertaining
> thing about Jon labeling this as a stupefuing goof is that in the message
> *just* before this one, he declared that real programs have no nesting
> anyway, and of course all this business about closures is irrelevant
> nonsense in programs that don't have any nesting!

Nah, that's not what's entertaining.  What's entertaining is that I
failed to make clear that it wasn't the actual leaving out of the
proposal that was "stupefying" but rather the purported reasons for
doing so.  Actually this isn't entertaining either - more like a goof
than anything else!  Oh, and I did _NOT_ say that closures are
irrelevant nonsense (that would just be plain stupid), I said that
most programs don't have much nesting and that without nesting no cost
is incurred and therefore any argument about distributed cost in the
user model as a reason for not having them was nonsense.  And that is
still just plain true.


/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[Magnus Kempe]

ncohen@watson.ibm.com (Norman H. Cohen) writes:
: 
: Bill Taylor's contribution was part of an ongoing discussion in the form
: of comments sent to the Mapping/Revision Team during the design of Ada 9X.

If I remember correctly, the final decision was based on arguments about
displays (Dewar arguing against a more generalized 'Access), alternatives
using generics and abstract types (Barnes arguing de facto against a more
generalized 'Access), and the bad mistake made in Ada 83 (the lack
of access to subprograms, as compared to C, Pascal, etc.).

This is not the only decision that was made on the basis of some implementors'
fears rather than for the sake of Ada users.  For instance, at some point
in the revision process child units of generics were rejected; the "solution"
was a compromise so that some implementors would not need to make any changes
in their linking steps when updating their compiler from Ada 83 to Ada 95.
The consequence is that not all non-generic hierarchies of packages can be
turned into generic hierarchies (just adding "generic" doesn't work, e.g.
if some child unit needs to "with" another child unit in the same hierarchy).

As Norm mentioned, most of these issues are documented in the "mrtcomments"
available online.  I hope the designers of Ada 0Y (oh-why) will read these
discussions carefully for the next revision--if there is one--so that they
can make a list of the fallacious arguments that will no doubt pop up again.

In the meantime, I think it is a very bad idea to try to "fix" such
mistakes by the introduction of an ever-increasing number of "hacking"
attributes.  For one thing, this tends to make Ada programs less portable
(from one compiler to another).

-- 
Magnus Kempe                  "I know not what course others may take, but as
Magnus.Kempe@di.epfl.ch        for me, Give me Liberty... or give me Death!"
http://lglwww.epfl.ch/Team/MK/                               -- Patrick Henry

Re: Q: access to subprogram

[Tucker Taft]

Jon S Anthony (jsa@organon.com) wrote:

: ... What's entertaining is that I
: failed to make clear that it wasn't the actual leaving out of the
: proposal that was "stupefying" but rather the purported reasons for
: doing so.  

It is generally impossible to fully reconstruct the process by which
decisions like this are made.

But I will give it a try...

We originally proposed a version of access-to-subprograms that would
allow for downward closures.  These were called "limited access types"
because allowing assignment for these types would definitely create
the possibility for dangling references.  So these kinds of access
types would need to disallow assignment, and hence be "limited."

At the time of this original proposal (in 1990, I believe), the
9X reviewers were overwhelmed by the number of changes proposed for
Ada 9X, and this just seemed like added complexity for less than
comensurate gain.  This was always the hard question: does the added 
functionality make up for the added complexity, and is the Ada 9X 
"complexity" boat reaching the point of sinking completely?

We had to make a lot of hard decisions.  If you look only at the
"margin", taking one decision at a time, you can very frequently
convince yourself that just this one more feature would have been
a good idea.  However, we were defintely struggling with the 
"overloaded boat" problem.

It is also easy to say that you shouldn't worry about compiler implementation,
but in fact, many of the problems of Ada 83 (and perhaps Algol 68,
and other well-designed languages) were due to the pragmatic realities of
getting a sufficient number of high-quality, fully-compliant compilers out 
the door in a reasonable time-frame.

One of our goals was to minimize changes that required modifications
to compiler back ends.  We achieved this goal to a remarkable extent,
in my view.  Another sub-goal was to allow existing "C" compiler backends 
to be used with Ada 95 front ends, without major changes to the backend.
Support for downward closures clearly began to run afoul of this goal.

Finally, there was already very flexible support for downward closures
in the form of generic formal subprograms.  Admittedly, generics are
more verbose.  However, they don't have any of the limitations that
would likely be associated with an access-to-subprogram approach.  You
can pass a predefined operator, an attribute, even an enumeration literal
as a subprogram parameter to a generic.

Hence, we now have a suggested feature that:

   1) Adds semantic complexity (by requiring two kinds of 
      access-to-subprogram types, limited and non-limited);
   2) Is largely functionally redundant with an existing feature;
   3) May require changes to many backends.

Our main "competitors" in the language wars, C, C++, and now Java,
have no support for this feature.  

Is this the feature we should spend our valuable Ada 9X "chips" on?

I hope you will at least agree that the answer is not a trivially
obvious "yes"...

: Jon Anthony
: Organon Motives, Inc.
: 1 Williston Road, Suite 4
: Belmont, MA 02178

: 617.484.3383
: jsa@organon.com

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Cambridge, MA  USA

Re: Q: access to subprogram

[Robert A Duff]

In article <4rre7j$pv7@watnews1.watson.ibm.com>,
Norman H. Cohen <ncohen@watson.ibm.com> wrote:
[... stuff about closures]

Norman gave a couple of nice examples illustrating how closures work
Thank you.  But I was hoping for something more about what makes
closures so great (as opposed to how they work).  I'm still unsure why
closures are such a wonderful thing.  Some comments:

Ackermann's function isn't something I want to calculate very often.
Is there a more "practical" example?

One can represent closures explicitly using heap-allocated tagged
objects.  A closure in a language that supports full closures is
represented by the address of the function, plus some representation of
the environment in which that function is called.  And this stuff has to
be allocated in the heap, since it can live essentially forever.  One
can do the same thing *explicitly* in Ada, by putting the "environment"
stuff into an object, and allocating it on the heap.  I show a different
version of package body Ackermann_Computation below, that works this
way.

Doing this requires the data that's in the closure to be explicitly
marked as such (by being components of the tagged type(s)).  In Norm's
"true closures" solution, it's implicit -- that is, whatever Norm's
Next_Row function happens to reference is what needs to be packaged up
in the closure.  Is there some advantage to that implicitness?  Does it
make things more substantially more convenient in some way that I don't
understand?  It seems to me that it's an *advantage* to make things
explicit -- it seems nice that a local variable (or parameter) in Ada
doesn't live longer than the containing scope -- it makes it easier to
understand what the purpose of that local is.  And if you want it to
live longer, you *explicitly* put it in the heap.

The solution below explicitly creates heap objects representing
closures, whereas Norman's solution implicitly allocates some stack
frames in the heap.

The "closures by hand" solution is approximately the same size as (a
little bigger than) Norm's solution.

Norman's solution is perhaps more elegant.  But it doesn't seem that
full closures make the grass greener and the sky bluer and the birds
sing more sweetly and all the other wonderfulness that some people seem
to like so much.  And of course there's a cost -- stack frames would
have to be heap-allocated in general, and a good compiler would want to
do all kinds of fancy analysis to avoid that when possible.

So, I guess my question is, "Yeah, it's nice, but what's the big deal?"

(By the way, surely the *simplest* solution is just a direct translation
from the definition:

   function Ackermann (M, N: Unbounded_Natural) return Unbounded_Natural is
   begin
      if M = 0 then
         return N+1;
      elsif N = 0 then
         return Ackermann(M-1, 1);
      else
         return Ackermann(M-1, Ackermann(M, N-1));
      end if;
   end Ackermann;

)

What's the most *efficient* method for calculating Ackermann's?

OK, here's my "closures-by-hand" solution:

package body Ackermann_Computation is

   package Container is
      -- We need to put Ackermann_Row_Type in a package, so
      -- Invoke will be primitive.

      type Ackermann_Row_Type is abstract tagged limited null record;
      -- Six reserved words in a row!

      function Invoke(R: Ackermann_Row_Type; N: Unbounded_Natural) return Unbounded_Natural is abstract;
      -- Invokes the closure represented by R, with parameter N.

      type Ackermann_Row_Ptr is access Ackermann_Row_Type'Class;
   end Container;
   use Container;

   type Row_Zero_Type is new Ackermann_Row_Type with null record;
   function Invoke(R: Row_Zero_Type; N: Unbounded_Natural) return Unbounded_Natural;

   function Invoke(R: Row_Zero_Type; N: Unbounded_Natural) return Unbounded_Natural is
   begin
      return N + 1;
   end Invoke;

   type Successor_Row_Type(Pred: access Ackermann_Row_Type'Class;
                           Row_Num: Natural) is new Ackermann_Row_Type with null record;
   -- Pred points to the predecessor row of this row.  This is analogous
   -- to the parameter F in Norman's Successor_Row function.

   function Invoke(R: Successor_Row_Type; N: Unbounded_Natural) return Unbounded_Natural;

   function Invoke(R: Successor_Row_Type; N: Unbounded_Natural) return Unbounded_Natural is
      Counter : Unbounded_Natural := N + 1;
      Result  : Unbounded_Natural := 1;
   begin
      while Counter /= 0 loop
         Result := Invoke(R.Pred.all, Result);
         Counter := Counter - 1;
      end loop;
      return Result;
   end Invoke;

   function Ackermann (M, N: Natural) return Unbounded_Natural is
      Row: Ackermann_Row_Ptr := new Row_Zero_Type;  -- R[0]
   begin
      for I in 1 .. M loop
         Row := new Successor_Row_Type(Pred => Row, Row_Num => I);
            -- Compute R[1] from R[0], R[2] from R[1], ...
      end loop;
      return Invoke(Row.all, To_Unbounded_Natural(N));  -- i.e., R[m](n)
   end Ackermann;

end Ackermann_Computation;

And here's Norm's solution using closures, for comparison:

package body Ackermann_Computation is

   type Ackermann_Row_Type is
      access function (N: Unbounded_Natural) return Unbounded_Natural;

   function Row_Zero (N: Unbounded_Natural) return Unbounded_Natural is
   begin
      return N + 1;
   end Row_Zero;

   function Successor_Row
      (F: Ackermann_Row_Type) return Ackermann_Row_Type is

      function Next_Row (N: Unbounded_Natural) return Unbounded_Natural is
         Counter : Unbounded_Natural := N + 1;
         Result  : Unbounded_Natural := 1;
      begin
         while Counter /= 0 loop
            Result := F(Result);
               -- F is the parameter of the surrounding function
            Counter := Counter - 1;
         end loop;
         return Result;
      end Result;

   begin

      return Next_Row'Access;  -- Illegal in Ada 95

   end Successor_Row;

   function Ackermann (M, N: Integer) return Unbounded_Natural is
      Row: Ackermann_Row_Type := Row_Zero'Access;  -- R[0]
   begin
      for I in 1 .. M loop
         Row := Successor_Row(Row);
            -- Compute R[1] from R[0], R[2] from R[1], ...
      end loop;
      return Row ( To_Unbounded_Natural(N) );  -- i.e., R[m](n)
   end Ackermann;

end Ackermann_Computation;

- Bob

Re: Q: access to subprogram

[Jon S Anthony]

In article <DuDyus.I8I.0.-s@inmet.camb.inmet.com> stt@henning.camb.inmet.com (Tucker Taft) writes:

> Jon S Anthony (jsa@organon.com) wrote:
> 
> : ... What's entertaining is that I
> : failed to make clear that it wasn't the actual leaving out of the
> : proposal that was "stupefying" but rather the purported reasons for
> : doing so.  
> 
>...[interesting stuff snipped]
>
> At the time of this original proposal (in 1990, I believe), the
> 9X reviewers were overwhelmed by the number of changes proposed for
> Ada 9X, and this just seemed like added complexity for less than
> comensurate gain.  This was always the hard question: does the added 
> functionality make up for the added complexity, and is the Ada 9X 
> "complexity" boat reaching the point of sinking completely?

Now, we are on to something.  This is the sort of analysis I was
hoping was lurking behind the decision, not this emphasis on all the
rubbish about static links vs. displays.


> We had to make a lot of hard decisions.  If you look only at the
> "margin", taking one decision at a time, you can very frequently
> convince yourself that just this one more feature would have been
> a good idea.  However, we were defintely struggling with the 
> "overloaded boat" problem.

Makes _perfect_ sense and is completely reasonable.


> It is also easy to say that you shouldn't worry about compiler
> implementation, but in fact, many of the problems of Ada 83 (and
> perhaps Algol 68, and other well-designed languages) were due to the
> pragmatic realities of getting a sufficient number of high-quality,
> fully-compliant compilers out the door in a reasonable time-frame.

This also definitely makes sense - again in the overall picture!
Sure, in an individual case you don't want to introduce some
wild-6-sigmas-out construct that noone has any experience with in
implementing.  But other than that, the overall goal (best overall
design which can actually be produced) should be primary.


> One of our goals was to minimize changes that required modifications
> to compiler back ends.  We achieved this goal to a remarkable extent,
> in my view.  Another sub-goal was to allow existing "C" compiler backends 
> to be used with Ada 95 front ends, without major changes to the backend.
> Support for downward closures clearly began to run afoul of this goal.

As several have pointed out, this is not particularly convincing.  The
best evidence indicates that this was a red-herring in this instance.


> Hence, we now have a suggested feature that:
> 
>    1) Adds semantic complexity (by requiring two kinds of 
>       access-to-subprogram types, limited and non-limited);
>    2) Is largely functionally redundant with an existing feature;
>    3) May require changes to many backends.

Wow!  Here's an analysis that really makes sense - especially in the
ranking (hopefully this was not accidental!)  Stir in the bits about
balancing the "total reasonable amount of things that can go in" and
weighing it against something else which is much more important and
would have to go if this one got in and _voila_, a perfectly
reasonable and probably even correct decision.


> Our main "competitors" in the language wars, C, C++, and now Java,
> have no support for this feature.  

Well, now we are back to irrelevant...


> I hope you will at least agree that the answer is not a trivially
> obvious "yes"...

Correct.  Thanks, Tucker, for explaining this and showing that the
thinking that I was hoping was lurking behind the decision was.


/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[Robert Dewar]

iJon said

"As several have pointed out, this is not particularly convincing.  The
best evidence indicates that this was a red-herring in this instance."

Nope, this was not a red herring, it (the concern about backend 
reimplementation) was the major focus of the argument. Remember that
this feature was being discussed very late on. Jon, did you read
all the references that Norman pointed to, they will give you a
clear picture of the discussion on this issue.

The reason it was discussed late on was Bill Taylor's late plea to
reexamine this issue in light of the iterator issue (well worth
reading, it is the first of Norman's references). This got a lot
of people interested again, and in the absence of implementatoin
concerns, it is clear that the design would have been revisited.

This late discussion was entirely focused on the issue of

  importance of this functionality

      vs

  impact on existing backends

Note that, as I have tried to emphasize before, static links vs displays
was an irrelevant issue then and now. I suppose someone could ake
the position of the original Steelman and worry about the impact on
implementations at a conceptual level, but in fact NO ONE took this
position that I can remember. The issue was very much focused on the
fact that at least two existing Ada technologies depended on displays
(you should also carefully look at Randy's concerns about shared
generics -- as always Randy was the one defending the shared generic
approach, and there are some interesting concerns here).

Tuck is certainly right that the reason that this originally disappeared
was in the general mood of simplification, although some would feel that
the restriction here is not a simplification but rather an instance of
introducing arbitrary restrictions that make things more complex.

But the failure of Bill Taylor's arguments with repsect to iterators
to succeed in getting the feature in was definitely the above consideration,
and as I say, you should read all the articles -- of course the articles
only capture a part of the argument -- you should also read Jim's
excellent minutes of the Villar's meeting where this issue was discussed
and finally decided on.

Re: Q: access to subprogram

[Robert A Duff]

In article <DuDwA9.99F@world.std.com>,
Robert A Duff <bobduff@world.std.com> wrote:
>OK, here's my "closures-by-hand" solution:
>...

After a couple of hours of CPU time, I see that A(4,1) = 65533.
Many hours later, it's still working on A(4,2).

:-)

- Bob

Re: Q: access to subprogram

[Brian Rogoff]

Magnus.Kempe@di.epfl.ch (Magnus Kempe) writes:
   ncohen@watson.ibm.com (Norman H. Cohen) writes:
   : 
   : Bill Taylor's contribution was part of an ongoing discussion in the form
   : of comments sent to the Mapping/Revision Team during the design of Ada 9X.

First of all, thanks Norman for that clear summary and the pointers. Is there 
a way I could have found out the location of these messages without asking you 
or reading all of the MRTcomments? It would be great if all of these 
arguments were webified and cross referenced so I could look up "closure" or 
something like it and find out the reasoning that went into the design of the 
feature.

On the down side, I have a bit more sympathy for the "contra-downward-closure" 
position than I did before :-). I still don't have a good sense of how much 
faster a display based implementation might be, if at all, and I doubt that 
anyone will be convinced without experiments.

   If I remember correctly, the final decision was based on arguments about
   displays (Dewar arguing against a more generalized 'Access), alternatives
   using generics and abstract types (Barnes arguing de facto against a more
   generalized 'Access), and the bad mistake made in Ada 83 (the lack
   of access to subprograms, as compared to C, Pascal, etc.).

I think that the efficiency argument, if correct, is a valid argument not to 
include the feature given the goals of Ada. The argument about alternatives is 
rather weak, since the alternatives are so clumsy. A similar discussion has 
been going on in the Java community, where it appears that full (upward) 
closures may be added in the near future. Of course you can simulate them 
with objects and interfaces, but that is a rather heavyweight mechanism.

   This is not the only decision that was made on the basis of some 
   implementors' fears rather than for the sake of Ada users.  For instance, 
   at some point in the revision process child units of generics were 
   rejected; the "solution" was a compromise so that some implementors would 
   not need to make any changes
   in their linking steps when updating their compiler from Ada 83 to Ada 95.
   The consequence is that not all non-generic hierarchies of packages can be
   turned into generic hierarchies (just adding "generic" doesn't work, e.g.
   if some child unit needs to "with" another child unit in the same 
   hierarchy).

Magnus, do you have a list of issues such as this one in which you feel that 
orthogonality and usability were traded for the comfort of a few implementors? 
I'd like to hear their arguments too of course.

   As Norm mentioned, most of these issues are documented in the "mrtcomments"
   available online.  I hope the designers of Ada 0Y (oh-why) will read these
   discussions carefully for the next revision--if there is one--so that they
   can make a list of the fallacious arguments that will no doubt pop up again.

Indeed. Also, I think Ada 0X is the way I'd refer to it, although I like your 
humorous jab :-)

I also don't like knocking Ada so much, since every ignoramus with a computer 
seems to think that Ada is awful. Paraphrasing Stroustrup, I think Ada 95 is 
the best C++ there is!

-- Brian

Re: Q: access to subprogram

[Norman H. Cohen]

In article <DuDwA9.99F@world.std.com>, bobduff@world.std.com
(Robert A Duff) writes: 

|> One can represent closures explicitly using heap-allocated tagged
|> objects.  A closure in a language that supports full closures is
|> represented by the address of the function, plus some representation of
|> the environment in which that function is called.  And this stuff has to
|> be allocated in the heap, since it can live essentially forever.

Correct.  The usual implementation of the stack in a "retention-strategy"
language (so called because the environment of a call may be retained
even after that call returns) is as a linked list of heap-allocated
activation records.  Pushing a record onto the stack consists of setting
its link field to point to the old top record and setting the top pointer
to point to the new record; popping the stack consists of setting the top
pointer to point to what is currently pointed to by the link field of the
top record.  If the environment pointed to by the top record did not
become part of any closure, this causes the record to become
inaccessible, and eventually it gets garbage-collected.  Otherwise, since
some live object is still pointing to the old top record, it remains in
existence.  (Association lists work this way in LISP, and full closures
are constructed by calling FUNCTION, which returns a list consisting of
the special atom FUNARG, the A-list for the environment in which FUNCTION
was evaluated, and the S-expression that was passed to FUNCTION.)

|>                                                                   One
|> can do the same thing *explicitly* in Ada, by putting the "environment"
|> stuff into an object, and allocating it on the heap.  I show a different
|> version of package body Ackermann_Computation below, that works this
|> way.
|>
|> Doing this requires the data that's in the closure to be explicitly
|> marked as such (by being components of the tagged type(s)).  In Norm's
|> "true closures" solution, it's implicit -- that is, whatever Norm's
|> Next_Row function happens to reference is what needs to be packaged up
|> in the closure.  Is there some advantage to that implicitness?  Does it
|> make things more substantially more convenient in some way that I don't
|> understand?  It seems to me that it's an *advantage* to make things
|> explicit -- it seems nice that a local variable (or parameter) in Ada
|> doesn't live longer than the containing scope -- it makes it easier to
|> understand what the purpose of that local is.  And if you want it to
|> live longer, you *explicitly* put it in the heap.

Whether the explicitness is a blessing or a curse depends on the level of
abstraction you are used to.  I presume that in typical circumstances you
find the implicit manipulation of registers in

   A := B + C;

preferable to the explicit manipulation of registers in

   LOAD  R1, B
   LOAD  R2, C
   ADD   R3,R1,R2
   STORE R3,A

Similarly, for a programmer in a functional language such as ML, closures
and higher-order functions are the usual language of discourse, the
lowest level of abstraction.  An ML programmer does not want to be
bothered with the low-level details of implementing closures.

The purpose of adding full closures to Ada would be to allow programming
at that same very high level of abstraction.  (This was not, of course,
part of either the Ada-83 or Ada-95 requirements.)

|> The solution below explicitly creates heap objects representing
|> closures, whereas Norman's solution implicitly allocates some stack
|> frames in the heap.

Bob's solution is similar to one I created several years ago when
experimenting with the use of Ada-83 tasks to represent function
manipulable as first class objects.  The task type had an Apply entry
with an in parameter giving the function argument and an out parameter
giving the function result.  There were other entries to "construct" such
a function.  That is, calling the entry would place the task in a state
where future calls on the Apply entry would cause it to behave like one
function or another.  One of the entries caused the task to move into a
loop where Apply acted like the R[0] function, setting its out parameter
to one more than the value of its in parameter. Another entry, with
a pointer to a task object of the same type, presumably representing some
Ackermann "row" R[i], would cause the task to move into a loop where
Apply acted like the R[i+1] function, using its in parameter to control
how many times the R[i] function would be applied to 1, and setting the
out parameter to the result.  (It would have been nice to have task types
where different task objects had different task bodies implementing the
same interface, but that's another discussion for another day.)

|> What's the most *efficient* method for calculating Ackermann's?

No doubt to special-case the lower rows: 

   function Ackermann (M, N: Unbounded_Natural) return Unbounded_Natural is
      Counter : Unbounded_Natural;
      Result  : Unbounded_Natural;
   begin
      if M = 0 then
         return N+1;
      elsif M = 1 then
         return 2*N+3;
      elsif M = 2 then
         return 2**(N+2) - 3;
      else
         Counter := N + 1;
         Result := 1;
         while Counter /= 0 loop
            Result := Ackermann(M-1, Result);
            Counter := Counter - 1;
         end loop;
      endif;
   end Ackermann;

Note that Ackermann(3,n) is (if I didn't make a clerical error)
       3
      2  - 1
     .
    .
   .
  2           - 1
 2                - 1
2                     - 3

where the number of 2s is n.  Thus even using some special representation
for unbounded integers, we quickly exhaust all the storage in the address
space to represent the result.  Thus we need not worry about efficiency
past this point; the computation is intractable.

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Q: access to subprogram

[Ronald Cole]

dewar@cs.nyu.edu (Robert Dewar) writes:
> Ronald is still missing the point that started this thread. 

You are missing the point that I am solely taking exception to your
categorizing gcc as a "single backend" compiler and not the point that
started this thread.  At a meta level, gcc may look like one; but
under close scrutiny, it clearly isn't.

> The other kind of technology uses a single common source base for all
> backends. GCC is in this category. Yes, the configuration files differ,
> but the great majority of the code is common. This is a critical feature
> of GCC, and is what allows easy porting of the technology. To port to
> a new architecture, a new configuration file needs to be written, but
> not a new code generator.

If this were true, then gcc could be made to read the md files
directly.  But since it can't due to some of the code generation
shenanigans that go on in an md file; well, I'll let you figure it
out...

-- 
Ronald Cole                                     E-mail: ronald@ridgecrest.ca.us
President, CEO                                          zippy@ecst.csuchico.edu
Forte International                                Fax: (619) 384-2346
     My PGP fingerprint: E9 A8 E3 68 61 88 EF 43  56 2B CE 3E E9 8F 3F 2B

Re: Q: access to subprogram

[Richard Kenner]

In article <m2g26ufuq2.fsf@devo.ridgecrest.ca.us> Ronald Cole <ronald@ridgecrest.ca.us> writes:
>You probably remember well the wailing and gnashing of teeth
>from the CISC-owners when gcc went from version 1 (handled CISC
>well/RISC not-so-well) to version 2 (handles RISC much better/CISC
>not-as-well-as-version-1/holds "inbetween architectures" like the
>Pentium in contempt).

I remember no such thing since it never happened!  GCC version 2 added
new mechanisms to support RISC processors but had *absolutely no
effect whatsoever* on CISC processors.  None of the config files for
CISC processors had to be changed, nor was there any change in the
generated code for these machines.

As to the Pentium issue, this is more complex and there were two
factors.  First, some of the optimizations required for the
best-quality code on that CPU are both very unique to it and are very
large pieces of code to add to the compiler.  Secondly, the group that
did add these, and other, Pentium-specific optimizations to GCC did
such a bad job that it was not possible to fix their code without
rewriting it and nobody wanted to do that without knowing which of the
optimizations were the most important (otherwise, you'd risk spending
a lot of work on complex optimizations that had a small effect).  By
the time this was done, the P6 became available.  It does not benefit
from most of the Pentium-specific optimizations (which I knew a while
before it came out), so the issue rapidly became moot.

Re: Q: access to subprogram

[Robert Dewar]

"If this were true, then gcc could be made to read the md files
directly.  But since it can't due to some of the code generation
shenanigans that go on in an md file; well, I'll let you figure it
out..."

Again, you miss the point (you seem pretty determined to do so). The point
is that there is a very important qualitative difference, in terms of the
impact of language changes on the backend, between the effect on a technology
like GCC, and a technology where the code generators are substantial
separate programs for each back end. Since I know you know the GCC technology
it is hard for me to believe that you disagree with this!

That is the one and only important point that is relevant to the start
of this thread (which was talking about the effect of definitions of
access-to-subporgram semantics on backend technologies).

Re: Q: access to subprogram

[Ronald Cole]

kenner@lab.ultra.nyu.edu (Richard Kenner) writes:
> What you are actually counting are thirty distinct configuration files
> used to tailor the single backend to a particular target machine.

"Tailor"!  Yes, my point exactly.  The day gcc can read md files
directly is the day I agree that it is a single backend.  Gcc is
really multiple backend with a meta-layer that gives the appearance of
a single backend.

> So long as you state the definitions you are using, you are free to
> use any you want.  But whatever words you use, there is a major
> distinction between the GCC approach and that used by other
> multi-target systems.

IMO, the gcc approach lives somewhere between single and multiple
backend.  You probably remember well the wailing and gnashing of teeth
from the CISC-owners when gcc went from version 1 (handled CISC
well/RISC not-so-well) to version 2 (handles RISC much better/CISC
not-as-well-as-version-1/holds "inbetween architectures" like the
Pentium in contempt).

But this thread has travelled well off topic for this group and this
is my last post on the subject.

-- 
Ronald Cole                                     E-mail: ronald@ridgecrest.ca.us
President, CEO                                          zippy@ecst.csuchico.edu
Forte International                                Fax: (619) 384-2346
     My PGP fingerprint: E9 A8 E3 68 61 88 EF 43  56 2B CE 3E E9 8F 3F 2B

Re: Q: access to subprogram

[Mark A Biggar]

Does tasking mess the static link vs display trade off in any way.  I.E.
a procedure nested in a task nested in a procedure and you want to pass
the inner most procedure as a parameter.

--
Mark Biggar
mab@wdl.lmco.com

Re: Q: access to subprogram

[Robert Dewar]

Mark says

"Does tasking mess the static link vs display trade off in any way.  I.E.
a procedure nested in a task nested in a procedure and you want to pass
the inner most procedure as a parameter."

The only effect is that if you are using a single global display, you need
to switch displays when you switch tasks, which means that the display
has to be per-task data. A common implementation approach is to put the
display in the TCB, and then have a register pointing to the TCB.

Re: Q: access to subprogram

[Robert Dewar]

Fergus wrote

"Well, there's still going to be a lot of Pentiums out there for quite
some time -- I wouldn't call the issue entirely moot yet."

moot means arguable and not yet decided -- I would say that's EXACTLY
the right description here.

Richard was saying that at this stage, the issue will probably stay
arguable and undecided, which seems a reasonable assessment.

(I suspect you meant MOOT as in "doesn't matter any more", but that is not
what the word means in traditional usage, although I agree this US usage
is (unfortunately) getting very common)

Re: Q: access to subprogram

[Robert Dewar]

Jon said

   > Nope, this was not a red herring, it (the concern about backend
   reimplementation) was the major focus of the argument.

  "I agree that this was the major focus of the argument.  My claim is
   that IMO this was an irrelevant distraction and thus a red herring."

OK, that makes very clear Jon's disagreement. If you take the position
that concerns about backend reimplementation were irrelevant, then
of course you will disagree with the conclusion. For a contrary view,
note that Bevin has several times publically stated that the impact of
Ada 95 on the backend was a major factor in DEC's decision to abandon
their Ada product and not attempt to move it to Ada 95.

Re: Q: access to subprogram

[Jon S Anthony]

In article <dewar.837226494@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:

> iJon said
> 
> "As several have pointed out, this is not particularly convincing.  The
> best evidence indicates that this was a red-herring in this instance."
> 
> Nope, this was not a red herring, it (the concern about backend 
> reimplementation) was the major focus of the argument. Remember that

I agree that this was the major focus of the argument.  My claim is
that IMO this was an irrelevant distraction and thus a red herring.


/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[Jon S Anthony]

In article <dewar.837095740@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:

> Whether this concern is legitimate or not probably can't be settled without
> some hard data on existing Ada programs (what you need is dynamic traces
> that show how many calls are to outer level procedures, and how many
>...[sort of data needed]
> can factor out optimization effects). As is clear from the thread, Jon
> and I simply disagree on the bottom line here, but I don't think any
> more arguments without data can illuminate this discussion further (it
> is by the way a *very* old discussion).

At the risk of starting another branch in this goofy thread, you are
quite correct here in that to some extent this aspect of the
discussion has been a case of "arguing in a vacuum.  I suppose at this
point Jay Martin would start blow torching academics for this, but it
is curious that this sort of thing is not given much attention despite
the fact that it does have real world impact and would appear to be
very important.

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[Robert Dewar]

Jon said

"At the risk of starting another branch in this goofy thread, you are
quite correct here in that to some extent this aspect of the
discussion has been a case of "arguing in a vacuum.  I suppose at this
point Jay Martin would start blow torching academics for this, but it
is curious that this sort of thing is not given much attention despite
the fact that it does have real world impact and would appear to be
very important."

Actually this data DOES exist, but it tends to be proprietary. For example,
IBM has *extensive* PL/1 execution traces that would certainly yield this
information for a large set of existing PL/1 applications. Similarly you
will find that Ada companies have this kind of informatoin available, but
do not necessarily share it.

I would not blow torch academics here. The trouble is that to get this
information, you need widespread acccess to large real-world applications.
Such access is usually only available to large companies, and not to
universities, and measuremens on small non-typical programs may be
worse than useless.

Re: Q: access to subprogram

[Fergus Henderson]

kenner@lab.ultra.nyu.edu (Richard Kenner) writes:

>As to the Pentium issue, this is more complex and there were two
>factors.  First, some of the optimizations required for the
>best-quality code on that CPU are both very unique to it and are very
>large pieces of code to add to the compiler.  Secondly, the group that
>did add these, and other, Pentium-specific optimizations to GCC did
>such a bad job that it was not possible to fix their code without
>rewriting it and nobody wanted to do that without knowing which of the
>optimizations were the most important (otherwise, you'd risk spending
>a lot of work on complex optimizations that had a small effect).  By
>the time this was done, the P6 became available.  It does not benefit
>from most of the Pentium-specific optimizations (which I knew a while
>before it came out), so the issue rapidly became moot.

Well, there's still going to be a lot of Pentiums out there for quite
some time -- I wouldn't call the issue entirely moot yet.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Q: access to subprogram

[tmoran]

In <dewar.837008174@schonberg> Robert Dewar said:
>(although as I mentioned in an earlier note, it is what Intel implements
>in their hardware - the ENTER instruction).
>...
>I wonder who designed this feature at Intel? Someone who knew a bit, but
>not really enough, about how to deal with up level displays. The ENTER
  Has anyone ever published a genealogy of CPU architectures?  My
impression has always been that the Intel, or West Coast, architecture
derived from HP which derived from Burroughs.  The 'display' would seem
to follow that.  (As opposed to the Dec/C/East Coast architecture ;)

Re: Q: access to subprogram

[Robert Dewar]

tmoran asks

"  Has anyone ever published a genealogy of CPU architectures?  My
impression has always been that the Intel, or West Coast, architecture
derived from HP which derived from Burroughs.  The 'display' would seem
to follow that.  (As opposed to the Dec/C/East Coast architecture ;)"

There is a fairly complete history of the designb of Intel architectures
in my book on microprocessors (McGraw Hill 1990). There is no HP or
Burroughs influence to speak of in these designs (at least not up 
through the 8086, it is certainly possible that someone familiar with
HP or Burroughs machines was involved later on).

Re: Q: access to subprogram

[Richard Kenner]

In article <4sdt1i$nqa@mulga.cs.mu.OZ.AU> fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) writes:
>Well, there's still going to be a lot of Pentiums out there for quite
>some time -- I wouldn't call the issue entirely moot yet.

I would because the issue is optimization, not functionality.  The people
who want every last cycle of performance are now going to be the ones
who use a P6, not a Pentium.

Re: Q: access to subprogram

[Magnus Kempe]

rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:
: Magnus, do you have a list of issues such as this one in which you
: feel that orthogonality and usability were traded for the comfort of a
: few implementors?

A list?  No.  For the most part, Ada 95 is great.  I'll submit comments
when it is time for Ada 0Y (and/or I'll experiment with the source code
of GNAT :-).

An interesting research project for academic people would be to add
downward closure to GNAT and measure the impact on the compiler and
generated code; then do the same on another compiler to compare static
vs display effects.  Brian, maybe you know someone who would do that? :-)
Now that the source code of an Ada compiler is available, where are
the academic experiments?

I think some improvements that were seen as too expensive or risky this
time around would have brought Ada closer to the power of functional
languages.  In a few years the OO movement will be followed by another
one, and it will be interesting to see if Ada can gracefully adapt a
second time.

In the meantime, our best path is to learn how to use the full power of
the language--in order to create many usable, reliable, maintainable,
and profitable applications.

-- 
Magnus Kempe                  "I know not what course others may take, but as
Magnus.Kempe@di.epfl.ch        for me, Give me Liberty... or give me Death!"
http://lglwww.epfl.ch/Team/MK/                               -- Patrick Henry

The Ada Home is at http://lglwww.epfl.ch/Ada/

Re: Q: access to subprogram

[Brian Rogoff]

Magnus.Kempe@di.epfl.ch (Magnus Kempe) writes:
   rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:
   : Magnus, do you have a list of issues such as this one in which you
   : feel that orthogonality and usability were traded for the comfort of a
   : few implementors?

   A list?  No.  For the most part, Ada 95 is great.  I'll submit comments
   when it is time for Ada 0Y (and/or I'll experiment with the source code
   of GNAT :-).

I agree that Ada 95 is great for the most part, which is why I read this 
newsgroup. However, it is not as good as it could be, for a number of 
important reasons, some of which are more "economic" than technical, like
backwards compatibility. Now, backwards compatibility is very important, 
so I wouldn't suggest just starting from scratch. However, at some point 
in Ada's evolution there will have to be an incompatible shift, as that 
"ratchet effect" that Robert Dewar mentioned will just keep making the 
language larger.

   An interesting research project for academic people would be to add
   downward closure to GNAT and measure the impact on the compiler and
   generated code; then do the same on another compiler to compare static
   vs display effects.  Brian, maybe you know someone who would do that? :-)
   Now that the source code of an Ada compiler is available, where are
   the academic experiments?

I'm temporarily out of academia, though I use the account :-). But your 
question gets to the heart of one part of the discussion. Are displays 
faster? If so, by how much? On what types of programs? On the other hand, 
if there were a compiler which supported downward closures, how much would 
they be used? How often are they used in languages that support them, like 
Pascal? Lots of questions like this have to be considered, and I don't envy 
the designers! I went from being a strong supporter of downward closures to 
being not so sure after I followed Norman's paper trail. The arguments about 
complicating a shared implementation for generics worried me, though I haven't 
thought through it carefully enough (I am not a compiler writer) I do 
appreciate arguments about implementability. 

From where I was sitting, Stanford, Ada has a long way to go. The languages 
used in the CS curricula are for the most part

(1) C and C++ (by far the most popular)
(2) ML among the theoretical CS types
(3) Fortran and MATLAB among numerical analysts unlike me and engineers

and now Java seems to be gaining popularity. GNAT is nowhere to be seen. 
How are things in Lausanne? Much better I take it :-).

However, this is not a reason for despair. The academic research will come 
when the language is more widely accepted in industry. Just look at all 
of the academic work on C++, and now Java. I think it is good that Windows 
is slowly becoming the primary GNAT environment, as this will hasten that 
acceptance.

   I think some improvements that were seen as too expensive or risky this
   time around would have brought Ada closer to the power of functional
   languages.  In a few years the OO movement will be followed by another
   one, and it will be interesting to see if Ada can gracefully adapt a
   second time.

It also remains to be seen whether the problems solved by the powerful 
features are that important. In his excellent paper "Hints for Computer 
System Design", Butler Lampson says a lot about this, and recommends 
simple, fast operations are usually "the right thing". 

So what do you think will follow OO? Functional Constraint Logic 
Programming? :-) 

   In the meantime, our best path is to learn how to use the full power of
   the language--in order to create many usable, reliable, maintainable,
   and profitable applications.

Yes!

-- Brian

Re: Q: access to subprogram

[Adam Beneschan]

In article <dewar.837456126@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:
 >Fergus wrote
 >
 >"Well, there's still going to be a lot of Pentiums out there for quite
 >some time -- I wouldn't call the issue entirely moot yet."
 >
 >moot means arguable and not yet decided -- I would say that's EXACTLY
 >the right description here.
 >
 >Richard was saying that at this stage, the issue will probably stay
 >arguable and undecided, which seems a reasonable assessment.
 >
 >(I suspect you meant MOOT as in "doesn't matter any more", but that is not
 >what the word means in traditional usage, although I agree this US usage
 >is (unfortunately) getting very common)

_Webster's Ninth New Collegiate_ (Merriam-Webster, 1984):

[3]moot adj.  1 a: open to question: DEBATABLE b: subjected to
discussion: DISPUTED  2: deprived of practical significance: made
abstract or purely academic

So the "doesn't matter any more" meaning is a legitimate meaning.

_Dictionary or Problem Words and Expressions_, by Harry Shaw
(McGraw-Hill, 1975):

    This word when used as an adjective means (1) subject to debate,
    arguable, unresolved; and (2) of only slight importance or
    significance: "This is a _moot_ question."  "Whether the player
    is black or white is a _moot_ consideration."  That is, a
    "_moot_ question" is debatable; "a _moot_ point" is of no
    importance. . . .

So according to this, both meanings of "moot" are correct, and which
meaning is the correct one depends on what it applies to---i.e.
whether it's a Question or a Point you're saying is moot.  Whether
an Issue is more like a Question or a Point is---well, a moot issue.
(Heh heh heh.)

                                -- Adam

Re: Q: access to subprogram

[Richard Kenner]

In article <4sjbjc$pae@mulga.cs.mu.OZ.AU> fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) writes:
>Yes, that's what I meant, moot as in "no longer important in practice,
>relevant only for hypothetical debate (e.g. at a moot [in law,
>students' discussion of hypothetical case for practice] ;-)",
>not moot as in "debatable".

>I suspect that when Richard Kenner introduced the word in the article
>to which I was replying, he meant it in the same "doesn't matter any
>more" sense, rather than in the "debatable" sense that you think he
>meant.  Perhaps Richard could enlighten us? ;-)

Yes, that's correct.

Re: Q: access to subprogram

[Brian Rogoff]

dewar@cs.nyu.edu (Robert Dewar) writes:
   <talking about downward closures>

   Tuck is certainly right that the reason that this originally disappeared
   was in the general mood of simplification, although some would feel that
   the restriction here is not a simplification but rather an instance of
   introducing arbitrary restrictions that make things more complex.

I am surprised that anyone would feel that it is not a restriction that makes 
things more complex for the user. It's not arbitrary, in that there are 
several implementation oriented arguments favoring the restriction. I can 
accept the decision as reasonable given the circumstances, and lack of 
compelling data refuting the implementation arguments or less compelling data 
about the utility of the feature in similar languages.

   But the failure of Bill Taylor's arguments with repsect to iterators
   to succeed in getting the feature in was definitely the above consideration,
   and as I say, you should read all the articles -- of course the articles
   only capture a part of the argument -- you should also read Jim's
   excellent minutes of the Villar's meeting where this issue was discussed
   and finally decided on.

Is this online somewhere? 

-- Brian

Re: Q: access to subprogram

[Fergus Henderson]

[Warning: this thread no longer has much relevance to Ada.
Apologies in advance.]

dewar@cs.nyu.edu (Robert Dewar) writes:

>(I suspect you meant MOOT as in "doesn't matter any more",

Yes, that's what I meant, moot as in "no longer important in practice,
relevant only for hypothetical debate (e.g. at a moot [in law,
students' discussion of hypothetical case for practice] ;-)",
not moot as in "debatable".

I suspect that when Richard Kenner introduced the word in the article
to which I was replying, he meant it in the same "doesn't matter any
more" sense, rather than in the "debatable" sense that you think he
meant.  Perhaps Richard could enlighten us? ;-)

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Q: access to subprogram

[Brian Rogoff]

ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
   dewar@cs.nyu.edu (Robert Dewar) writes:
   <... about the decision to omit "downward closures"...>

   >As to whether the decision is right in retrospect? hard to say. So far
   >I have not seen any really convincing examples.

   Self-fulfilling prophecy.  It's a better use of my time to figure out
   how I _can_ accomplish something in Ada 95 (my favourite imperative
   language) than to construct examples showing what I'd like to do and can't.
   If I _were_ going to spend time on that, I'd explain why I would like to
   be able to pass a generic procedure as a generic parameter (not an
   *instance* of a generic procedure, the generic itself).

I guess I would ask Pascal programmers how useful they found this, and whether 
any interesting idioms emerged which used this feature. The same for similar 
languages (does Borland's Delphi have Pascal-like downward closures?). The 
iterator example is a good one I think, but apparently not good enough. 
Maybe a few more useful examples, and a consensus on the implementation 
issues would enable this issue to be reopened in the future.

While I (as a user) think that downward closures and some other language 
tidying would have been good, the ability to write OCXes easily in GNAT 
would be far more useful :-). 

-- Brian

Re: Q: access to subprogram

[Richard A. O'Keefe]

dewar@cs.nyu.edu (Robert Dewar) writes:

>  - if you use displays anyway, then the implementation is greatly 
>  - complicated. The maximum depth of the display is not known till
>  - link time, so either you take a huge hit in efficiency by using
>    some absurd maximum value (I have seen nesting depths well over
>    ten coming from the use of subunits), or you have to mess at
>    the linker level to determine the maximum, and then all data
>    structures that depend on this maximum become dynamcically sized
>    objects which must be dynamically allocated.

>It is this second concern about implementation difficulty that lead
>to the WG9 decision to restrict the feature so that such dynamic
>concerns would not be necessary, and also to ensure that the display
>model could be used without introducing undue overhead mentioned as
>the first concern above.

But (a) the maximum depth of the display is not *relevant* to the code
        generated for any procedure, with or without procedure parameters.
	The only depth that is relevant to any one procedure is the depth
	of that procedure itself
and (b) you don't know the maximum depth of the display until link time
        *anyway*.
So I still don't see what the problem is.  As for 10, that seems small to
me.  (The B6700 had 32 display registers, and there were actually Burroughs
customers who were rather upset when later models cut that back to 16.)
In any reasonable implementation of procedure parameters based on displays
(such as is necessary for Algol 60, Pascal, and PL/I) there is NO data
structure that cares the slightest tiniest little bit what the maximum
display size is, with the unique exception of the display itself.

>The distributed overhead argument did *not* enter into the discussion.

It did enter into _this_ discussion (thread).

>Basically the issue boiled down quite simply to a pragmatic issue. If
>the procedure pointers were made general, would this be too much of
>an implementation burden for existing implementations usinvg displays?
>And how does this balance against the increased utility?

We are agreed that there _is_ a burden, but we seem to disagree quite
a bit about what exactly that burden is.  Space-wise, it can be
	- N links in the parent of a passed-procedure
	- N links in the passed-procedure itself
	- 3N link assignments in a call
This is to provide the same level of support for procedure parameters
as Pascal; *not* the more general Algol 68 model which I have not been
talking about.

>Who knows, Richard, maybe you would have agreed to if
>you had listened to the detalied arguments (this was very extenisvely
>discussed) -- there were people there who felt as you do now when
>we started the discussion, but changed their minds.

I have found the Ada 9x design documents that I _have_ read (which comes
to a stack about 4 feet high) to be *extremely* interesting and valuable
for the field of language design.  If these detailed arguments have been
written up, I would be most interested to read them.

Basically, what I've read _here_ boils down to "People who designed Ada
implementations on the assumption that procedure calls are not
exceptionally important feared that providing a Pascal-like
procedure-related feature would be too expensive.", and it seems as if
either a much richer feature than I wanted (procedure _pointers_; I just
wanted procedure _parameters_) or a much dumber implementation than I
have in mind was envisaged.

>As to whether the decision is right in retrospect? hard to say. So far
>I have not seen any really convincing examples.

Self-fulfilling prophecy.  It's a better use of my time to figure out
how I _can_ accomplish something in Ada 95 (my favourite imperative
language) than to construct examples showing what I'd like to do and can't.
If I _were_ going to spend time on that, I'd explain why I would like to
be able to pass a generic procedure as a generic parameter (not an
*instance* of a generic procedure, the generic itself).

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

Re: Q: access to subprogram

[Robert Dewar]

Micheal said

"Actually, the "unfortunate" US usage of "moot" is quite normal in
legal circles, and has been for a long time. Courts will use the term
to mean a legal issue they don't have to worry about deciding, because
the conditions in the suit were overtaken by events, or some other
such cause."

That's confused -- look up moot in any legal dictionary, and you will
find the first definition only -- that is the legal definition. A moot
issue is one that is undecided, and hence arguable. When a judge declares
an issue moot, he is declaring that the court will not decide the issue.
The reasons for this may be many, and sometimes an observer thinking in
terms of the second definition will find it consistent, but it is always
the first meaning that is operable -- the court will leave the decision
undecided!

A moot court is one that considers an undecided arguable issue, again, only
the first definition applies.

Re: Q: access to subprogram

[Michael Feldman]

In article <dewar.837456126@schonberg>, Robert Dewar <dewar@cs.nyu.edu> wrote:

>(I suspect you meant MOOT as in "doesn't matter any more", but that is not
>what the word means in traditional usage, although I agree this US usage
>is (unfortunately) getting very common)

The English and the Americans are two people separated by a common
language. (Shaw?)

Actually, the "unfortunate" US usage of "moot" is quite normal in
legal circles, and has been for a long time. Courts will use the term
to mean a legal issue they don't have to worry about deciding, because
the conditions in the suit were overtaken by events, or some other
such cause.

Law schools have a ritual they call "moot court", which is essentially
a simulated courtroom drama, where students debate each other to get
practice for doing so in real courtrooms. I think both senses of "moot"
apply here - it is a court where things are debated, but it doesn't
matter what the outcome is (well, except maybe for a student's grade.:-))

Your 1-man crusade to hold back the tide is (in both senses) moot.:-)

Mike Feldman

Re: Q: access to subprogram

[Brian Rogoff]

ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
   rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:
   [about nested procedures as parameters of other procedures]

   >I guess I would ask Pascal programmers how useful they found this, and whether 
   >any interesting idioms emerged which used this feature.

   As an old Algol/Pascal programmer, I would answer "very useful".
   I don't quite grasp the intent of the "any useful idioms" question.

Idiom in the sense of "pattern",  an interesting interaction with other 
features of the language they appear in. In Ada, for example, the idiom 
to simulate mixin inheritance involves parametrizing a mixin type with 
its enclosing type through access discriminants. Other languages might have 
other features to do the same thing.

   Procedures as parameters are an abstraction mechanism.
   Hen's teeth, even Fortran has them.  Why?
   So you can build abstractions like "integrate over an interval";
   "Monte-Carlo integration in N-dimensional space";
   "find the minimum of a function over an interval";
   "find the mimimum of a function in N-space" (Nelder-Mead, for example);
   "solve ODE"; ...

Scheme was my first language. I like it, and I understand the benefits of 
closures and lazy evaluation and such. But Ada is designed to have a fairly 
intuitive performance model for most operations, unlike Scheme.

Also, as I am sure you know, Ada 95 has access to subprogram, which can be 
used to implement the numerical routines you describe, albeit not as cleanly 
as you do. By "procedure parameters", I take it that you mean the general case 
of Pascalish nested procedures, but not Scheme or ML closures, which require 
more sophisticated (usually garbage collected) runtimes. 

   <... excellent example of how composition of functions leads to concise 
        multidimensional integrator from single dimensional version
        sadly deleted >

Yes, the version with generics isn't as pretty as the version with downward 
closures in Pascal, even without your extension. I could code the same thing 
with other Ada 95 features, but I agree that for some things this functional 
style is very appropriate.

   Most of all, consider the effect on program style and clarity.
   Many people, of whom I am one, consider passing procedures as parameters
   a *fundamental* control structure (really fundamental; people in this
   camp like to use it as a primitive to explain IF), and while it is
   possible to program without it, so would it be possible to program in
   a language with no FOR statements or where no expression was allowed
   to have more than one operator or where there was no automatic storage
   allocation.  All of these are *possible*, but why make programming any
   harder than it has to be?

I am not the right person to argue against this, since I think it should have 
been part of the language, but there are arguments about the effect of this 
feature on implementations using shared generics, and about the impact on 
existing implementations. At least one company dropped its Ada efforts, 
ostensibly for the reason of added implementation burden. I think all issues 
of the interaction of the implementation of downward closures with other 
parts of the language would have to have been closed for this argument to have 
been won. 

As I said above though, I agree that this approach is also easier to 
understand (more readable!) than the generic approach. In fact it is hard 
to imagine a more understandable approach...

   >Maybe a few more useful examples, and a consensus on the implementation 
   >issues would enable this issue to be reopened in the future.

   Procedures as parameters have been around since the late 1950s.  There
   are many thousands of commercially important Fortran programs and
   libraries using them.  There are libraries full of books about the
   functional programming paradigm and the importance of procedures as a
   (not "the", "a") tool of abstraction.

Almost all of the books on functional programming use full "upward" closures, 
which are not quite what Ada would get if these get added to GNAT say. There 
are also books around on simulating the features of functional languages 
with "functor" objects. I find these idioms a little clumsy, but I think that 
I'll wait a while to pronounce judgement. It may be that as I get more used to 
Ada I'll find those and other methods more palatable...

Or maybe they'll all look like Rube Goldberg devices and I'll keep wishing 
it were different. But for me the choice is not between Ada 95 and Clean or 
ML, but Ada 95 and C++. Ada 95 still looks very good ;-).

-- Brian

Re: Q: access to subprogram

[Richard A. O'Keefe]

rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:
[about nested procedures as parameters of other procedures]

>I guess I would ask Pascal programmers how useful they found this, and whether 
>any interesting idioms emerged which used this feature.

As an old Algol/Pascal programmer, I would answer "very useful".
I don't quite grasp the intent of the "any useful idioms" question.

Procedures as parameters are an abstraction mechanism.
Hen's teeth, even Fortran has them.  Why?
So you can build abstractions like "integrate over an interval";
"Monte-Carlo integration in N-dimensional space";
"find the minimum of a function over an interval";
"find the mimimum of a function in N-space" (Nelder-Mead, for example);
"solve ODE"; ...

Now it _is_ possible to do a lot of this using Ada generics.

Let's consider one special case, and I'll use Scheme syntax.

	(define (integrate-1D L1 U1 F)
	    ; compute and return
	    ; integral F(x) dx for x in [L1,U1]
	    <<some expression>>
	    )

	(define (integrate-2D L1 U1 L2 U2 F)
	    ; compute and return
	    ; integral F(x,y) dx dy for x in [L1,U1] y in [L2,U2]
	    (integrate-1D L2 U2 (lambda (y)
		(integrate-1D L1 U1 (lambda (x)
		    (F x y)) )) ))

The Pascal (ISO 10206) equivalent would be

	function Integrate_1D(L1, U1: Real;
			      function F(x: Real): Real): Real;
	    (* some locals *)
	begin
	    (* some body *)
	end;

	function Integrate_2D(L1, U1, L2, U2: Real;
			      function F(x, y: Real): Real): Real;
	    function Inner(y: Real): Real;
		function Curried_F(x: Real): Real;
		begin Curried_F := F(x, y) end;
	    begin Inner := Integrate_1D(L1, U1, Curried_F) end;
	begin Integrate_2D := Integrate_1D(L2, U2, Inner) end;

The Ada equivalent of this would be


    generic
        with function F(x: Float) return Float;
    function Integrate_1D(L1, U1: Float) return Float;

    function Integrate_1D(L1, U1: Float) return Float is
	-- some locals
    begin
	-- some body
    end;

    generic
	with function F(x, y: Float) return Float;
    function Integrate_2D(L1, U1, L2, U2: Float) return Float;

    function Integrate_2D(L1, U1, L2, U2: Float) return Float is
	function Outer_Integrand(y: Float) return Float is
	    function Inner_Integrand(x: Float) return Float is
	    begin return F(x, y); end Inner_Integrand;
	    function Inner_Integrator is new Integrate_1D(F => Inner_Integrand);
	begin return Inner_Integrator(L1, U1); end Outer_Integrand;
	function Outer_Integrator is new Integrate_1D(F => Outer_Integrand);
    begin return Outer_Integrator(L2, U2); end Integrate_2D;

[Layout chosen to give Scheme no unfair advantage with respect to number
of lines needed.  I would normally lay the Ada version out exactly the
way that AQAS guidelines recommend.]

In the Scheme version, only the top-level procedures need names.
In the Pascal version, the lambda-expressions have to be given names;
there is nothing in the Pascal model which actually *requires* this;
Pascal *could* be extended with context-sensitive lambda-expressions
so as to allow

	function Integrate_2D(L1, U1, L2, U2: Real;
			      function F(x, y: Real): Real): Real;
	begin
	    Integrate_2D :=
		Integrate_1D(L2, U2, lambda (y)
		    Integrate_1D(L1, U1, lambda (x)
			F(x, y)));
	end;

without requiring any backend changes.

In the Ada version, not only do the *arguments* of Integrate_1D need
names, so also do the *calls*.

In the Scheme and Pascal versions, there is one copy of Integrate_1D
which is called twice.  In the Ada version, at least as compiled by
"gcc -S -O" (gcc 2.7.2, gnat 3.04, SPARC Solaris 2.5), there are two
copies of Integrate_1D.  The optimised SPARCompiler Pascal code for a
program using this is in fact about half the size of optimised GNAT Ada
code.

For this example, it doesn't seem so important, but consider larger examples,
and consider caching effects.

Most of all, consider the effect on program style and clarity.
Many people, of whom I am one, consider passing procedures as parameters
a *fundamental* control structure (really fundamental; people in this
camp like to use it as a primitive to explain IF), and while it is
possible to program without it, so would it be possible to program in
a language with no FOR statements or where no expression was allowed
to have more than one operator or where there was no automatic storage
allocation.  All of these are *possible*, but why make programming any
harder than it has to be?

>Maybe a few more useful examples, and a consensus on the implementation 
>issues would enable this issue to be reopened in the future.

Procedures as parameters have been around since the late 1950s.  There
are many thousands of commercially important Fortran programs and
libraries using them.  There are libraries full of books about the
functional programming paradigm and the importance of procedures as a
(not "the", "a") tool of abstraction.

>While I (as a user) think that downward closures and some other language 
>tidying would have been good, the ability to write OCXes easily in GNAT 
>would be far more useful :-). 

One must be practical.  I would far rather have Ada 95 *now* the way it
is than the way it might have been "some time next year".  Any time I want
a language with less compromise, I can turn to Clean.

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

Re: Q: access to subprogram

[Robert A Duff]

In article <ROGOFF.96Jul22154757@sccm.Stanford.EDU>,
Brian Rogoff <rogoff@sccm.stanford.edu> wrote:
>ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
>   rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:
>   [about nested procedures as parameters of other procedures]
>
>   >I guess I would ask Pascal programmers how useful they found this, and whether 
>   >any interesting idioms emerged which used this feature.

Iterators.

- Bob (ex-Pascal-programmer)

Re: Q: access to subprogram

[Brian Rogoff]

bobduff@world.std.com (Robert A Duff) writes:
   In article <ROGOFF.96Jul22154757@sccm.Stanford.EDU>,
   Brian Rogoff <rogoff@sccm.stanford.edu> wrote:
   >ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
   >   rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:
   >   [about nested procedures as parameters of other procedures]
   >
   >   >I guess I would ask Pascal programmers how useful they found this, and whether 
   >   >any interesting idioms emerged which used this feature.

   Iterators.

Hi Bob,
	While this is now straying a bit from Ada 95, I'm curious as to 
whether you find Pascal style iterators using downward funargs (there, I'm 
using Lisp terminology) superior to CLU/Sather-1.0 style iterators. And 
how do the Ada 95 alternatives stack up? Also, were these downward funargs 
widely used, or was there a small set of problems in which they were the ideal
vehicle of expression, like the multidimensioal integration example? I realize 
in Scheme that functions are used for everything, so I am interested more in 
the answer for Pascal and other Ada-like languages.

	This is a really fascinating question in language design. I'd like 
find some examples like the ones Richard O'Keefe posted, and see what the 
best Ada 95 alternatives are. That way I can get a better sense as to how much 
we are really missing.

   - Bob (ex-Pascal-programmer)

-- Brian (hopefully ex-C-programmer ;-)

Re: Q: access to subprogram

[Robert A Duff]

In article <ROGOFF.96Jul23093858@sccm.Stanford.EDU>,
Brian Rogoff <rogoff@sccm.stanford.edu> wrote:
>Hi Bob,

Hi Brian,

>	While this is now straying a bit from Ada 95,

Indeed.  I hope people don't get too annoyed at us for discussing
general language design stuff.

>.. I'm curious as to 
>whether you find Pascal style iterators using downward funargs (there, I'm 
>using Lisp terminology) superior to CLU/Sather-1.0 style iterators. 

No.  When I was a Pascal programmer many years ago, I used
procedures-as-params a lot for iterators.  But CLU iterators are clearly
superior.  I don't know Sather, but from what I've read, they seem even
more superior.

>...And 
>how do the Ada 95 alternatives stack up?

Not very well, I'm afraid.  You can use generics, but you end up with a
lot of verbose junk for some simple things.  Sigh.

>... Also, were these downward funargs 
>widely used, or was there a small set of problems in which they were the ideal
>vehicle of expression, like the multidimensioal integration example? 

I'd say Pascal's downward "funargs" were widely used for iterators.  At
least in the code I saw, and the code I wrote.

>...I realize 
>in Scheme that functions are used for everything, so I am interested more in 
>the answer for Pascal and other Ada-like languages.
>
>	This is a really fascinating question in language design. 

Indeed.

>...I'd like 
>find some examples like the ones Richard O'Keefe posted, and see what the 
>best Ada 95 alternatives are. That way I can get a better sense as to how much 
>we are really missing.

Ada's generics can do *almost* everything that Pascal can do.  They
can't recurse, in Ada, like they can in Pascal.  (I needed that once.)
And they're verbose, as I said.

Smalltalk's version is pretty nice, by the way.  You don't pass
procedures -- you pass blocks.  And that avoids the annoyance of having
to name something that doesn't need or deserve a name -- it's just the
Body_Of_The_Loop, or whatever.

- Bob

P.S. I was away for more than a week, so I may have missed some answers
to my question about full closures.  Did anybody answer that?

Re: Q: access to subprogram

[Brian Rogoff]

bobduff@world.std.com (Robert A Duff) writes:
   Brian Rogoff <rogoff@sccm.stanford.edu> wrote:
   >.. I'm curious as to 
   >whether you find Pascal style iterators using downward funargs (there, I'm 
   >using Lisp terminology) superior to CLU/Sather-1.0 style iterators. 

   No.  When I was a Pascal programmer many years ago, I used
   procedures-as-params a lot for iterators.  But CLU iterators are clearly
   superior.  I don't know Sather, but from what I've read, they seem even
   more superior.

Yes, Sather iterators are a pleasure to use. There is a paper on the web page 
about their design, and I imagine it has been published by now. On the other 
hand, their integration into Ada would have been rather major, whereas the 
Pascal approach would probably have been easier.

   >...And 
   >how do the Ada 95 alternatives stack up?

   Not very well, I'm afraid.  You can use generics, but you end up with a
   lot of verbose junk for some simple things.  Sigh.

Ada generics are great, but it seems that they are (over)used to hide certain 
ugly little corners of the language (like jgv's mutually recursive types 
fix). I don't like using them for this. 

   >... Also, were these downward funargs 
   >widely used, or was there a small set of problems in which they were the ideal
   >vehicle of expression, like the multidimensioal integration example? 

   I'd say Pascal's downward "funargs" were widely used for iterators.  At
   least in the code I saw, and the code I wrote.

Anecdotal evidence, but useful. So when the feature was there, people used it 
a lot.

   Ada's generics can do *almost* everything that Pascal can do.  They
   can't recurse, in Ada, like they can in Pascal.  (I needed that once.)
   And they're verbose, as I said.

Do you feel that they are the right solution though? The generic approach to 
function composition looked ugly to me, whereas the direct approach looks 
beautiful. That may be subjective, but I don't think so. I bet even most of 
the people who argued against this feature in Ada would admit that for this 
problem, generics are kind of ugly.

   Smalltalk's version is pretty nice, by the way.  You don't pass
   procedures -- you pass blocks.  And that avoids the annoyance of having
   to name something that doesn't need or deserve a name -- it's just the
   Body_Of_The_Loop, or whatever.

Just like Scheme, which had anonymous and named lambda expressions. I suppose 
that in a future Ada, called Ada 0X rather than the plaintive sounding Ada 0Y, 
we could have anonymous downward funargs, as Richard O'Keefe suggested for 
Pascal.

   - Bob

   P.S. I was away for more than a week, so I may have missed some answers
   to my question about full closures.  Did anybody answer that?

Was this the "why are they any better than wrapping up the environment and 
func in a tagged type" question?

-- Brian

Re: Q: access to subprogram

[Richard A. O'Keefe]

rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:
>Idiom in the sense of "pattern",  an interesting interaction with other 
>features of the language they appear in.

I didn't say that I didn't grasp the *meaning* of the word "idiom" in
this context, only that I didn't grasp the *intent* of the question.

The point is that this is such a basic and quirk-free building block
that you don't think in terms of "idioms" for it any more than you
think in terms of there being special idioms for assignment statements
or while loops.

>Scheme was my first language. I like it, and I understand the benefits of 
>closures and lazy evaluation and such. But Ada is designed to have a fairly 
>intuitive performance model for most operations, unlike Scheme.

Concerning performance models:
    I spent this afternoon (when not talking to students) taking the
    integration example and beefing it up to the point where it would
    plausibly take a reasonable amount of time.  I produced three
    versions:

	Ada (using generic instantiation)
		compiled with gnatmake -gnatp -cargs -O4
		Size: 94 lines.

	Pascal (using nested procedures passed as parameters)
		compiled with SPARCompiler 4.0 pc -s -native -O4
		Size: 57 lines.

	Scheme
		compiled with stalin -copt "-O4" -d -On -dc
		(this compiles Scheme to C, then uses gcc as a back end)
		Size: 40 lines.

    Guess what:  the Pascal and Ada versions both took 18 seconds on
    a "sunu4, Ultra-Enterprise", whatever that is, while the Scheme
    version took 6 seconds.
I guess Scheme running 3 times faster than Ada or Pascal is not "intuitive"
for many programmers.

To be really honest, I *thought* I knew what the cost model for generics
was, but have heard repeatedly in this newsgroup that I shouldn't think
of generic instantiation as macro instantiation.

>Also, as I am sure you know, Ada 95 has access to subprogram, which can be 
>used to implement the numerical routines you describe, albeit not as cleanly 
>as you do.

Yes, I do know.  The point I am defending, which has been made before by
others, is that "access to procedure" is one thing, and "procedure as
parameter" is another, and that you don't *need* to allow access to
procedure in order to either implement or use procedure as parameter,
and you particularly don't need to allow restrictions related to the
former to limit the use of the latter.

>By "procedure parameters", I take it that you mean the general case 
>of Pascalish nested procedures, but not Scheme or ML closures, which require 
>more sophisticated (usually garbage collected) runtimes. 

Exactly so.  Although the code generated for the Scheme version of this
program uses stack allocation and does (and _can_ do) no garbage collection.

>   <... excellent example of how composition of functions leads to concise 
>        multidimensional integrator from single dimensional version
>        sadly deleted >

>>  Most of all, consider the effect on program style and clarity.

In this particular case (big is bad).
	Scheme : Pascal	: Ada
Size	4      : 6      : 9
Time	1      : 3      : 3

DO NOT EXTRAPOLATE THE SIZE OR TIME NUMBERS TO OTHER KINDS OF PROBLEMS.

>I am not the right person to argue against this, since I think it should have 
>been part of the language, but there are arguments about the effect of this 
>feature on implementations using shared generics, and about the impact on 
>existing implementations.

I must have missed the discussion of how this would affect shared generics.
I am all in favour of shared generics, but surely generics cannot _always_
be shared, so there's always a fallback strategy, or have I misunderstood?

>Almost all of the books on functional programming use full "upward" closures, 
>which are not quite what Ada would get if these get added to GNAT say.

This is misleading.  They use *languages* in which there are few or no
restrictions on closures.  This does not mean that every *program* using
closures in these books or in day-to-day functional programming uses
upward closures all over the place.

>Or maybe they'll all look like Rube Goldberg devices and I'll keep wishing 
>it were different. But for me the choice is not between Ada 95 and Clean or 
>ML, but Ada 95 and C++. Ada 95 still looks very good ;-).

Well, if you want object orientation, there's O'Caml, which is supposed to
be pretty good.  
-- 
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.

Re: Q: access to subprogram

[Brian Rogoff]

ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
   Concerning performance models:
       I spent this afternoon (when not talking to students) taking the
       integration example and beefing it up to the point where it would
       plausibly take a reasonable amount of time.  I produced three
       versions:

	   Ada (using generic instantiation)
		   compiled with gnatmake -gnatp -cargs -O4
		   Size: 94 lines.

	   Pascal (using nested procedures passed as parameters)
		   compiled with SPARCompiler 4.0 pc -s -native -O4
		   Size: 57 lines.

	   Scheme
		   compiled with stalin -copt "-O4" -d -On -dc
		   (this compiles Scheme to C, then uses gcc as a back end)
		   Size: 40 lines.

       Guess what:  the Pascal and Ada versions both took 18 seconds on
       a "sunu4, Ultra-Enterprise", whatever that is, while the Scheme
       version took 6 seconds.

   I guess Scheme running 3 times faster than Ada or Pascal is not "intuitive"
   for many programmers.

Note that the Pascal compiler was not any better than GNAT on this. The data 
does suggest that the nested procedure approach may have performance 
advantages in addition to its general advantages as a simple programming 
construct. What is stalin doing? Is it dependent on any simplifying 
assumptions about the code?

   To be really honest, I *thought* I knew what the cost model for generics
   was, but have heard repeatedly in this newsgroup that I shouldn't think
   of generic instantiation as macro instantiation.

I like Ada generics, but this is one of those cases where using generics as 
a workaround seems ugly to me, so I'd write integrators differently. I agree 
with your point that generics are one of the parts of the language model where 
the performance model is less clear.

   >>  Most of all, consider the effect on program style and clarity.

   In this particular case (big is bad).
	   Scheme : Pascal	: Ada
   Size	4      : 6      : 9
   Time	1      : 3      : 3

   DO NOT EXTRAPOLATE THE SIZE OR TIME NUMBERS TO OTHER KINDS OF PROBLEMS.

This is a nice little example of the conciseness of this style, and I think 
anyone would be hard pressed to say that the Ada version would be more 
readable.

   >I am not the right person to argue against this, since I think it should have 
   >been part of the language, but there are arguments about the effect of this 
   >feature on implementations using shared generics, and about the impact on 
   >existing implementations.

   I must have missed the discussion of how this would affect shared generics.
   I am all in favour of shared generics, but surely generics cannot _always_
   be shared, so there's always a fallback strategy, or have I misunderstood?

It was one of the refs in Norman Cohen's precis of the discussion, from 
Randy Brukardt at RR Software. Here is the relevant excerpt:

--------------------------------------------------------------------------- 
To put the problem in a nutshell:
 
If 'Access is allowed in generic bodies, generic code sharing requires
distributed overhead.  (Or compilers have to do body analysis of generics
in order to prevent sharing on them).
 
To explain this in detail, I'd have to give a crash course on the construction
of shared generics.  However, here is a simplified version of the problem:
A shared generic passes in some way a pointer to a data area identifying the
generic, and containing its local objects.  [Note that this exists in any but
the most simplified versions of sharing - any sharing algorithm which allows
data in the generic specification or body would have the problem].
However, an access-to-subprogram does not know that the routine comes from
a generic, or even which generic.  The solution to this problem in the
specification is to construct a 'wrapper' routine at instantiation time,
which knows about the appropriate generic instantiation.
 
However, a wrapper cannot be built for 'Accesses in the generic body
inside the generic body.  To do so at instantiation time requires that the
body be compiled before the instantiation, something that has generally been
considered bad in Ada 83.  Doing so eliminates virtually all of the advantages
of sharing.  The main alternative would be to carry and add generic data to
every use of a access to subprogram object - a significant distributed
overhead.
 
(Note that GNU's solution of generating the wrapper at runtime will not work
on some operating systems, because these systems prohibit self-modifying code
for security reasons.  We have even had problems doing this on some UNIX
systems, for this reason.  Therefore, it is not a generally applicable
solution).
 
The result that that eliminating the restrictions on 'Access would make some
code easy to write, but would force the junking of existing code sharing
algorithms, or make the cost of access-to-subprogram substantially higher than
in competing languages.  Those both are very bad ideas.
 
 
                                Randy.
--------------------------------------------------------------------------- 
 

   >Almost all of the books on functional programming use full "upward" closures, 
   >which are not quite what Ada would get if these get added to GNAT say.

   This is misleading.  They use *languages* in which there are few or no
   restrictions on closures.  This does not mean that every *program* using
   closures in these books or in day-to-day functional programming uses
   upward closures all over the place.

How much are upward funargs used in day to day functional programming? I 
think Bob Duff is still looking for a compelling example of why they are 
so much better than the explicitly simulated closure via an instance of a 
tagged type.

   >Or maybe they'll all look like Rube Goldberg devices and I'll keep wishing 
   >it were different. But for me the choice is not between Ada 95 and Clean or 
   >ML, but Ada 95 and C++. Ada 95 still looks very good ;-).

   Well, if you want object orientation, there's O'Caml, which is supposed to
   be pretty good.  

I've played with it. The Win NT versions' GUI doesn't work. The language is 
nice, but I often do work where I can't tolerate boxing of certain types, 
like numerical or pixel types in arrays, and CAML is a bit weak here. 
Ada bindings to the Win 32 API also help. 

-- Brian

Re: Q: access to subprogram

[Jon S Anthony]

In article <Dv0LHw.Jq6@world.std.com> bobduff@world.std.com (Robert A Duff) writes:

> In article <ROGOFF.96Jul23093858@sccm.Stanford.EDU>,
> Brian Rogoff <rogoff@sccm.stanford.edu> wrote:
> >Hi Bob,
> 
> Hi Brian,
> 
> >	While this is now straying a bit from Ada 95,
> 
> Indeed.  I hope people don't get too annoyed at us for discussing
> general language design stuff.

I hope not.  This is good stuff.  There aren't many places on the net
where you can find this sort of discussion.


> >.. I'm curious as to 
> >whether you find Pascal style iterators using downward funargs (there, I'm 
> >using Lisp terminology) superior to CLU/Sather-1.0 style iterators. 
> 
> No.  When I was a Pascal programmer many years ago, I used
> procedures-as-params a lot for iterators.  But CLU iterators are clearly
> superior.  I don't know Sather, but from what I've read, they seem even
> more superior.

Sather iterators (IMO) are pretty clearly about as kewl as iterators
get.  They are _extremely_ flexible and can be combined in arbitrary ways
(basically allowing you to "snap together" new iterators from the ones
you have in your bag - the ones provided in the class definitions).  I'd
also recommend the Sather Iterator Technical Report paper on the Sather
home page:

http://http.icsi.berkeley.edu/Sather/


> >how do the Ada 95 alternatives stack up?
> 
> Not very well, I'm afraid.  You can use generics, but you end up with a
> lot of verbose junk for some simple things.  Sigh.

Agreed.  They are more or less "good enough"...


> P.S. I was away for more than a week, so I may have missed some answers
> to my question about full closures.  Did anybody answer that?

I don't recall even seeing it.  I've been noticing lately that several
posts from various people (including myself) have not "got out"...

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[Jon S Anthony]

In article <Dv0LHw.Jq6@world.std.com> bobduff@world.std.com (Robert A Duff) writes:

> In article <ROGOFF.96Jul23093858@sccm.Stanford.EDU>,
> Brian Rogoff <rogoff@sccm.stanford.edu> wrote:
> >Hi Bob,
> 
> Hi Brian,
> 
> >	While this is now straying a bit from Ada 95,
> 
> Indeed.  I hope people don't get too annoyed at us for discussing
> general language design stuff.

I hope not.  This is good stuff.  There aren't many places on the net
where you can find this sort of discussion.


> >.. I'm curious as to 
> >whether you find Pascal style iterators using downward funargs (there, I'm 
> >using Lisp terminology) superior to CLU/Sather-1.0 style iterators. 
> 
> No.  When I was a Pascal programmer many years ago, I used
> procedures-as-params a lot for iterators.  But CLU iterators are clearly
> superior.  I don't know Sather, but from what I've read, they seem even
> more superior.

Sather iterators (IMO) are pretty clearly about as kewl as iterators
get.  They are _extremely_ flexible and can be combined in arbitrary ways
(basically allowing you to "snap together" new iterators from the ones
you have in your bag - the ones provided in the class definitions).  I'd
also recommend the Sather Iterator Technical Report paper on the Sather
home page:

http://http.icsi.berkeley.edu/Sather/


> >how do the Ada 95 alternatives stack up?
> 
> Not very well, I'm afraid.  You can use generics, but you end up with a
> lot of verbose junk for some simple things.  Sigh.

Agreed.  They are more or less "good enough"...


> P.S. I was away for more than a week, so I may have missed some answers
> to my question about full closures.  Did anybody answer that?

I don't recall even seeing it.  I've been noticing lately that several
posts from various people (including myself) have not "got out"...

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: access to subprogram

[David Kristola]

In article cbo@mulga.cs.mu.OZ.AU, fjh@mundook.cs.mu.OZ.AU (Fergus Henderson) writes:
>rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:

[snip] (I apologize if i am attributing these words to the wrong person, i was
not able to locate the original post).

>>If 'Access is allowed in generic bodies, generic code sharing requires
>>distributed overhead.  (Or compilers have to do body analysis of generics
>>in order to prevent sharing on them).

Maybe i am misunderstanding the meaning of "distributed overhead", but don't
all shared generics have some?  But anyway...

[snip]

>>To explain this in detail, I'd have to give a crash course on the construction
>>of shared generics.  However, here is a simplified version of the problem:
>>A shared generic passes in some way a pointer to a data area identifying the
>>generic, and containing its local objects.  [Note that this exists in any but
>>the most simplified versions of sharing - any sharing algorithm which allows
>>data in the generic specification or body would have the problem].
>>However, an access-to-subprogram does not know that the routine comes from
>>a generic, or even which generic.  The solution to this problem in the
>>specification is to construct a 'wrapper' routine at instantiation time,
>>which knows about the appropriate generic instantiation.
>
>I think I follow you so far...

This is how i understand generics with shared code to work.

>>However, a wrapper cannot be built for 'Accesses in the generic body
>>inside the generic body. 
>
>Can you explain in a bit more detail when this would be necessary,
>and why it is not possible?

Maybe a code example here would help (let me know if i have missed the mark):

generic
   ...
package Pkg is
   procedure P;
end Pkg;

with ...
package body Pkg is
   function F(...) return ... is
      ...
   begin
      ...
   end F;

   procedure P is
      ...
   begin
      ...
      Call_Something(F'Access);
      ...
   end P;
end Pkg;

Since F might depend on the generic parameters to Pkg, F'Access would need to
point to a wrapper for F, which is not known inside Pkg at compile time (there
may be no instantiations, and therefore no wrappers created).  I do not know if
F would have it's own wrapper anyway, because it is not visible in the spec of
Pkg, and therefore not externally callable.

BUT, why not have a wrapper for F, and, include in the instantiation data, the
addresses of the wrapper routines (F in this case), so that P could reference the
instantiated data passed to it to get the address to resolve F'Access?  There is
a bit of indirection here, but then that is an everyday part of shared generics.

I hope my mostly Ada 83 view of the world has not blinded me to something in Ada
that makes this approach fail (or some general blindness to a common feature
that i have overlooked).  And before i start a flame war, this is just a comment
on how such a thing could be done, please do not point out the RM sections that
forbid it (that is not the point).

>--
>Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
>WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
>PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

david kristola
"maybe i would not see the solution so clearly if i could see all of the problem"
Work: davidk@os1.ese.lmsc.lockheed.com
Play: DJKristola@aol.com

My suggestion for Lockheed Martin's next slogan:
"Lockheed Martin, we make things that go BOOM!"

Re: Q: access to subprogram

[Fergus Henderson]

rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:

>It was one of the refs in Norman Cohen's precis of the discussion, from 
>Randy Brukardt at RR Software. Here is the relevant excerpt:
>
>--------------------------------------------------------------------------- 
>To put the problem in a nutshell:
> 
>If 'Access is allowed in generic bodies, generic code sharing requires
>distributed overhead.  (Or compilers have to do body analysis of generics
>in order to prevent sharing on them).

Having implemented shared generic handling for Mercury, without any
distributed overhead as far as I am aware, I'm keen to understand in
detail how this problem arises in Ada.  

>To explain this in detail, I'd have to give a crash course on the construction
>of shared generics.  However, here is a simplified version of the problem:
>A shared generic passes in some way a pointer to a data area identifying the
>generic, and containing its local objects.  [Note that this exists in any but
>the most simplified versions of sharing - any sharing algorithm which allows
>data in the generic specification or body would have the problem].
>However, an access-to-subprogram does not know that the routine comes from
>a generic, or even which generic.  The solution to this problem in the
>specification is to construct a 'wrapper' routine at instantiation time,
>which knows about the appropriate generic instantiation.

I think I follow you so far...

>However, a wrapper cannot be built for 'Accesses in the generic body
>inside the generic body. 

Can you explain in a bit more detail when this would be necessary,
and why it is not possible?

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Q: access to subprogram

[Robert A Duff]

In article <4t8rfo$g71@butch.lmsc.lockheed.com>,
David Kristola <davidk@OS2.ifs> wrote:
>Maybe i am misunderstanding the meaning of "distributed overhead", but don't
>all shared generics have some?  But anyway...

I think you're misunderstanding "distrib overhead".  "Feature X causes
distributed overhead" means that your program will have some overhead,
caused by the mere existence of feature X in the language, even if you
don't use feature X.  If feature X is slow, that's just plain old
overhead, not "distributed overhead".

An example from another thread: tasking causes distributed overhead,
because when generating code for a subprogram containing a
package-body-subunit, you have to *assume* that the package body will
contain a task, and generate some extra task-waiting code in the
subunit.  So the poor programmer who wants to use subunits, but never
used a task in his life is paying some cost for the mere existence of
tasking.  This is distributed overhead.  Of course, this assumes a
certain implementation model -- namely that code is generated for the
parent subprogram at compile time, when the subunits might not exist
yet.  It also assumes the user doesn't have a feature saying "I promise
not to use tasking."

Another example: Text_IO keeps track of line and column numbers, which
is an overhead you pay even if you are just sending characters to
stdout, and don't care about line and column numbers.  (Assuming a
straightforward implementation of Text_IO.)

Arguments about distributed overhead generally need to have some
implementation model in mind (which usually assumes, for example, that
fancy optimizations are not done at link time).

The case in *this* thread assumes an always-shared generic
implementation.  Always sharing generics has a *lot* of overhead, but I
don't think it has much *distributed* overhead.  We're also assuming
that you're not allowed to generate code at run time.

Distributed overhead is evil.  Overhead is not evil, necessarily,
because the programmer can choose whether to use the feature (and incur
the overhead).  Almost any feature causes *some* distributed overhead.
The goal is to make it close enough to zero that nobody cares.

>generic
>   ...
>package Pkg is
>   procedure P;
>end Pkg;
>
>with ...
>package body Pkg is
>   function F(...) return ... is
>      ...
>   begin
>      ...
>   end F;
>
>   procedure P is
>      ...
>   begin
>      ...
>      Call_Something(F'Access);
>      ...
>   end P;
>end Pkg;
>
>Since F might depend on the generic parameters to Pkg,

Yes, or perhaps a variable declared in the package body.

>... F'Access would need to
>point to a wrapper for F, which is not known inside Pkg at compile time (there
>may be no instantiations, and therefore no wrappers created).  I do not know if
>F would have it's own wrapper anyway, because it is not visible in the spec of
>Pkg, and therefore not externally callable.

Suppose Call_Something were *outside* the generic, and saved F'Access in
a global variable.  This is illegal, but we're arging about "what if
this were legal?"

>BUT, why not have a wrapper for F, and, include in the instantiation data, the
>addresses of the wrapper routines (F in this case), so that P could reference the
>instantiated data passed to it to get the address to resolve F'Access?  There is
>a bit of indirection here, but then that is an everyday part of shared generics.

Because when you compile F, you don't know about the instantiations.
And when you compile the instantiations, you don't know about F, because
F is declared in the generic *body*.  Sure, you could have the compiler
take a peek at the generic body, but as Randy pointed out, that defeats
the purpose of the always-share model (i.e. to be able to generate code
without seeing the body).

So this doesn't work.  Therefore you have to *always* have this extra
generic related info, even if you're not using generics.  Hence,
distributed overhead.  Hence, Ada 9X outlawed the feature.

Note that the workaround isn't so bad: declare F in the private part,
and then it's legal (and then the compiler knows about it at
instantiation time, and can generate the wrapper at that time).

- Bob

Re: Q: access to subprogram

[Ken Garlington]

Richard A. O'Keefe wrote:
> 
>         Ada (using generic instantiation)
>                 compiled with gnatmake -gnatp -cargs -O4
>                 Size: 94 lines.

I don't know how to read the gnat command lines, so could some one tell me
if this means all exceptions are suppressed?

Also, is source line size being given here as a measure of efficiency? What
were the other measures compared to the alternatives (readability, reusability,
etc.)?

> I guess Scheme running 3 times faster than Ada or Pascal is not "intuitive"
> for many programmers.

It's certainly not intuitive to _me_. However, I would certainly have no problem 
with a statement that a particular Scheme toolset might generate code that is 
three times more efficient than an Ada _toolset_, for a given host/target 
platform. (Do we really believe GNAT is the most efficient Ada compiler available, 
for example? I keep reading that not all optimizations have been implemented in 
GNAT yet...)


-- 
LMTAS - "Our Brand Means Quality"

Re: Q: access to subprogram

[Robert A Duff]

In article <4t7dvt$cbo@mulga.cs.mu.OZ.AU>,
Fergus Henderson <fjh@mundook.cs.mu.OZ.AU> wrote:
>>However, a wrapper cannot be built for 'Accesses in the generic body
>>inside the generic body. 
>
>Can you explain in a bit more detail when this would be necessary,
>and why it is not possible?

It would be necessary when you say P'Access inside a generic body, and P
is in that body (and not declared in the spec), and you then let the
pointer escape outside the generic.  This is illegal in Ada 95.

I believe we're talking about full generic sharing here.  Most
implemtnations of sharing share *sometimes* and not other times,
depending on what sort of generic it is, and what the formals are.  But
here, we *always* share.  Well, when you call through the pointer, the
called subprogram needs a pointer to the generic data -- an area of
memory where variables declared in the generic package body live.
There's one such are per instance.  But since you have only one copy of
the generic code, that code doesn't know which instance is the current
one.

You could generate code to do this at run time, as gcc does, but Randy
said that doesn't work on some OS's.  Generating code to do it at
compile time is impossible, since there's only one piece of code, but
many instances.

If you *always* represent access-to-subprogram values with extra data
telling where the generic instance data is, then it can work, but that's
distributed overhead for the case where you didn't use generics.

Make sense?

I know nothing of Mercury, in particular how its version of generics
relates to Ada's.  Could you outline how you did it, and why you say it
has no distributed overhead?

- Bob

Re: Q: access to subprogram

[Fergus Henderson]

bobduff@world.std.com (Robert A Duff) writes:

>If you *always* represent access-to-subprogram values with extra data
>telling where the generic instance data is, then it can work, but that's
>distributed overhead for the case where you didn't use generics.
>
>Make sense?

After much thought -- nope, I'm still confused ;-)

Mercury's shared-generics implementation doesn't have any distributed
overhead when compared to "Mercury minus generics".  I don't think it
has any distributed overhead when compared to Pascal either (i.e.
I think Pascal could be extended with Mercury-style generics without
imposing any distributed overhead.)  But there is distributed overhead
compared to C, if you're not willing to adopt the GNU C trampoline
approach or something along those lines.

I'm still confused about whether there is distributed overhead compared
to Ada.

You can't represent higher-order types (Mercury's equivalent to
access-to-subprogram types) using a single code address, you
need a data address as well -- presuming you don't use trampolines.
But I thought Ada already imposed that requirement, since you can
take the address of nested procedures in Ada? (can't you?)

The way the Mercury implementation handles taking the address of a
generic instance in a shared generic is to package up the generic
instance data in basically the same way that the stack frame data in an
enclosing procedure is packed up when you take the address of a nested
procedure.  So as long as you are already committed to being able to
take the address of nested procedures, there is no distributed
overhead -- I think.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Q: access to subprogram

[Robert A Duff]

In article <ROGOFF.96Jul24163007@sccm.Stanford.EDU>,
Brian Rogoff <rogoff@sccm.stanford.edu> wrote:
>Anecdotal evidence, but useful.

Anecdotal is all you ever get in this business.  ;-)

>   Ada's generics can do *almost* everything that Pascal can do.  They
>   can't recurse, in Ada, like they can in Pascal.  (I needed that once.)
>   And they're verbose, as I said.
>
>Do you feel that they are the right solution though?

No.  They work in many cases, but they're not the best solution.

>   P.S. I was away for more than a week, so I may have missed some answers
>   to my question about full closures.  Did anybody answer that?
>
>Was this the "why are they any better than wrapping up the environment and 
>func in a tagged type" question?

Yes.  Not just "why are they better", but "why are the a LOT better"
(which is the claim I often hear).

- Bob

Re: Q: access to subprogram

[Richard A. O'Keefe]

ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
>       I spent this afternoon (when not talking to students) taking the
>       integration example and beefing it up to the point where it would
>       plausibly take a reasonable amount of time.  I produced three
>       versions:  [now four, using two C compilers]

Lang	Time	Size	How compiled
Ada	18	94	3.04 gnatmake -gnatp -cargs -O4
Pascal	18	57	SPARCompiler 4.0 pc -s -native -O4
C	20	92	2.7.2 gcc -O4
C	13	92	SPARCompiler 4.0 cc -fsimple -native -fast -xO4
Scheme	 6	40	stalin -copt "-O4" -d -On -dc
Scheme	 5	40	stalin -cc cc -copt "-native -xO4" -d -On
	Seconds	Lines

rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:

>Note that the Pascal compiler was not any better than GNAT on this.

The C code simulates a model where top level procedures do not have
a static link, but nested procedures do (a realistic implementation
model).  The C times bracket the Ada/Pascal times.  The really 
interesting thing was that the Ada, Pascal, and Scheme versions worked
the first time they got through the compiler, while the C version
crashed.  (lclint pointed me to an uninitialised variable...)

>The data 
>does suggest that the nested procedure approach may have performance 
>advantages in addition to its general advantages as a simple programming 
>construct. What is stalin doing? Is it dependent on any simplifying 
>assumptions about the code?

The -d option says "inexact numbers are C doubles".
The -On option says "do not check for exact integer overflow",
    which I put in to make the comparison fair.
The -dc option says "yes you can use alloca"; as you see from the
    last line, leaving it out didn't make much difference.

Does Stalin make any simplifying assumptions about the code?
Well, it doesn't support bignums or rationals (neither do Ada, Pascal,
or C).  It doesn't support complex arithmetic (neither does C, and
neither does SPARCompiler Pascal, even though it's in the current standard.)
It doesn't support DELAY/FORCE (nor do Ada, Pascal, or C).
It doesn't support LOAD (adding new code at run time, or replacing existing
code).  Neither do Ada, Pascal, or C.

Stalin makes *no* other assumptions about the program.  Even CAR and CDR
receive no special magic treatment.  It just does a really thorough job
of static analysis and optimisation.  Jeff Siskind has put a *lot* of
work into the algorithms in this compiler.  It's a one-man show; he is
the only one working on it, and his latest grant proposal to do more
work on it was turned down, so it is also by a rather large margin the
slowest of the compilers tested.  This is a pity, because while a lot of
the methods in Stalin are related to dynamically typed languages,
"Stalin also does global static life-time analysis for all allocated
data.  This allows much temporary allocated storage to be reclaimed
without garbage collection.  Finally, Stalin has very efficient
strategies for compiling closures."  Of course, when you introduce OOP,
dynamic typing joins the party, so it's not that clear that Stalin has
nothing to contribute to the art of Ada compilation.

>A shared generic passes in some way a pointer to a data area identifying the
>generic, and containing its local objects.

I see.  This is like "type classes" as found in Mercury and Haskell.
I note that Haskell manages to combine this with unrestricted closures;
I don't know how the Glasgow Haskell Compiler handles it, but I don't
_think_ it involves run-time code generation.

>The result that that eliminating the restrictions on 'Access would make some
>code easy to write, but would force the junking of existing code sharing
>algorithms, or make the cost of access-to-subprogram substantially higher than
>in competing languages.  Those both are very bad ideas.

Ah *hah*.  This is *not* an argument against procedure parameters,
it is an argument against identifying them with procedure *pointers*.
The force of the integration example is that even though current Ada
"has" procedure parameters they can't be *used* for the things that
people have historically wanted to use them for,  Now I understand why
it was thought that the maximum size of the display mattered:  people
wanted to know how much stuff to put in a procedure pointer, and a
procedure pointer of a type declared at lexlevel N needs N+c pointers,
and a pointer declared who-knows-where needs who-knows-how-many pointers.
Fine, but NONE of this is a problem with procedure parameters, only
with bodging them up Borland-style as procedure pointers.

>How much are upward funargs used in day to day functional programming? I 
>think Bob Duff is still looking for a compelling example of why they are 
>so much better than the explicitly simulated closure via an instance of a 
>tagged type.

Whenever you simulate any mechanism,

 - you lose clarity
	This is demonstrated by the line numbers.

 - you introduce the risk of error
	The Scheme and Pascal versions didn't have to "simulate" anything.
	They worked, as soon as the compiler was happy with them.
	The C version crashed, precisely *because* having to simulate the
	feature added complexity, and I slipped, even though I was	
	transcribing code, not rewriting from scratch.  All I had to worry
	about was how to simulate the feature, in < 100 lines of code, and
	I got it wrong.

 - you lose efficiency.
	The compiler doesn't understand the feature.  It compiles your
	simulation using general methods.  In this example, even when I
	told the SPARCompiler C compiler (there is no redundancy there;
	that's it's name) to in-line some crucial functions, it didn't
	improve the speed.  The fact that Stalin really thoroughly
	understands procedures does pay off in this small example where
	procedure calling is a major cost factor.

One might as well say, "why have direct language support for OOP?  You
can always simulate it!"  And in fact Scheme programmers have often said
this, because a language that takes procedures really seriously makes it
dead simple to simulate OOP with procedures.



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

Re: Q: access to subprogram

[Brian Rogoff]

bobduff@world.std.com (Robert A Duff) writes:
   Brian Rogoff <rogoff@sccm.stanford.edu> wrote:
   >Anecdotal evidence, but useful.

   Anecdotal is all you ever get in this business.  ;-)

Correct. But by collecting this anecdotal evidence and analyzing it we 
can hopefully get some idea of what we're doing :-).

   >   Ada's generics can do *almost* everything that Pascal can do.  They
   >   can't recurse, in Ada, like they can in Pascal.  (I needed that once.)
   >   And they're verbose, as I said.
   >
   >Do you feel that they are the right solution though?

   No.  They work in many cases, but they're not the best solution.

That's my feeling too, although when I thought about it more I couldn't 
really rationalize why I disliked generics so much for this problem and 
yet like the use of null bodied generic formal package parameters for 
signatures. Maybe in a few days the generic approach won't seem so bad.

   >Was this the "why are they any better than wrapping up the environment and 
   >func in a tagged type" question?

   Yes.  Not just "why are they better", but "why are the a LOT better"
   (which is the claim I often hear).

I think that you posted that you like Smalltalk blocks a lot, which are 
essentially just anonymous closures, right? I think the beauty of this 
construct is that you can implement lots of features cleanly in terms of 
it, like control structures. Also the implementation of closures on objects 
seems heavy/verbose to me. I think in a language like Smalltalk, which 
already has GC, that upward funargs and objects are (a LOT) better than 
objects alone. On the other hand, if you are asking if they are so much 
better than explicitly managing the heap that Ada should adopt GC :-), I'd 
say no.

-- Brian

Re: Q: access to subprogram

[Robert A Duff]

In article <4tb4ii$5fc@mulga.cs.mu.OZ.AU>,
Fergus Henderson <fjh@mundook.cs.mu.OZ.AU> wrote:
>You can't represent higher-order types (Mercury's equivalent to
>access-to-subprogram types) using a single code address, you
>need a data address as well -- presuming you don't use trampolines.
>But I thought Ada already imposed that requirement, since you can
>take the address of nested procedures in Ada? (can't you?)

Ada's access-to-subprogram types are rather severely restricted.  Yes,
you can make a pointer-to-nested-proc, but that pointer can't survive
longer than the immediately enclosing procedure.

Define "level of X" to mean "the number of procedures statically
enclosing X", so a procedure in a library package is "level 0", a
procedure in that is "level 1", and so on.  You also need to count block
statements and tasks as levels, but not packages.

Now, an access type at level N can have values pointing at procedures of
levels less than or equal to N, but not greater.

In particular, a level-0 access type can only be used to point to
level-0 procedures.

Various rules ensure the above property.  The special rule for generics
ensures that the above property holds without requiring the compiler to
see the generic body when compiling an instantiation.

For a static-link implementation, a level-0 access-to-proc type can be
implemented as a single address (of the procedure's code).  This is
important, for interfacing to C.  (E.g. passing call-back procedures to
X windows.)  A level-1 access-to-proc can also be implemented as a
single address, since there is only one possibility for the static link,
assuming the run-time model allows level-0 procedures to sometimes get a
static link which they then ignore.  Level-2 and deeper access types
need the pair of pointers you talked about.

A display implementation can always implement access-to-subp as a single
address, at all levels.

Does this help?

>The way the Mercury implementation handles taking the address of a
>generic instance in a shared generic is to package up the generic
>instance data in basically the same way that the stack frame data in an
>enclosing procedure is packed up when you take the address of a nested
>procedure.  So as long as you are already committed to being able to
>take the address of nested procedures, there is no distributed
>overhead -- I think.

Yes, this makes sense, I think, but doesn't it imply that level-0
access-to-proc types have a static link attached?  That would constitute
a distributed overhead, would it not, given the stuff I said above?  And
make the interface to C more painful?

- Bob

Re: Q: access to subprogram

[Robert A Duff]

In article <ROGOFF.96Jul26095803@sccm.Stanford.EDU>,
Brian Rogoff <rogoff@sccm.stanford.edu> wrote:
>I think that you posted that you like Smalltalk blocks a lot, which are 
>essentially just anonymous closures, right? 

Yes, I did post that.  But it's not because they are full closures --
almost all of the uses in my code, and almost all of the uses I've seen,
are the downward kind.  The reason I like them is that you can do things
like iterators without a lot of fuss.  In Pascal, using the
procedures-as-parameters method, you have to write a procedure for the
body of the loop, and you have to give it a name.  In Ada, using the
generics method, you have to do that, and you also have to write a
generic instantiation, and give *that* a name.  You end up cluttering
the program with useless names for things that should really be
anonymous (The_Loop_Body, or Do_One_Item, or whatever).  So, I like
Smalltalks blocks because they are anonymous.

I also like them because they are written in line.  When I write a loop,
I want to write the iteration stuff controlling the loop, and then I
want the repeated statements to be inside the loop.  The
procedures-as-params solution forces a weird ordering in the code.

>....I think the beauty of this 
>construct is that you can implement lots of features cleanly in terms of 
>it, like control structures. 

No, that merely requires downward closures.  I'm still looking for an
example that really makes the upward direction look wonderfully
powerful.

>...Also the implementation of closures on objects 
>seems heavy/verbose to me.

True.  But that's OK, unless full closures are really as powerful and
commonly needed as I've heard.  Also, the heavy/verbose way of doing it
has an advantage -- it makes quite clear which data is going to survive
the return of this procedure (by being attached to a closure), as
opposed to purely "local" data.

- Bob

Re: Q: access to subprogram

[Fergus Henderson]

ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:

>This is like "type classes" as found in Mercury and Haskell.

Mercury doesn't have type classes, I'm afraid, only
pure parametric polymorphism.  Maybe in some later version...
(You can do the same sort of things using parametric polymorphism
by explicitly passing the necessary operations as higher-order
predicates or functions, but it's a bit more cumbersome than
Haskell's type classes.)

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Q: access to subprogram

[Robert A Duff]

In article <4t9un9$imn@goanna.cs.rmit.edu.au>,
Richard A. O'Keefe <ok@goanna.cs.rmit.edu.au> wrote:
>>How much are upward funargs used in day to day functional programming? I 
>>think Bob Duff is still looking for a compelling example of why they are 
>>so much better than the explicitly simulated closure via an instance of a 
>>tagged type.
>
>Whenever you simulate any mechanism,
>...[all manner of evil happens]

True, but the logical conclusion is that all useful mechanisms that
anybody has ever thought of should be included in the language.  One has
to make a trade-off between a useful gizmo and language complexity
(etc).

Anyway, I think this argument is getting confused between "downward
closures" and "full closures".  If I understand your example correctly,
it needs downward closures, but not full closures.  True?  I have argued
in favor of downward closures (because in my experience they have been
very useful, and they are very cheap to implement).  But I remain
unconvinced about full closures (because they seem less commonly needed,
and they are substantially more expensive to implement -- although your
benchmark shows that in at least one case, the run-time cost is a myth).
And the only serious example anybody posted was Ackermann's function,
which is useful in explaining how full closures work, but doesn't
exactly make me want to use them every day.  I have never in my entire
career needed to compute Ackermann's function, as far as I can recall.
;-)

- Bob

Re: Q: access to subprogram

[Fergus Henderson]

bobduff@world.std.com (Robert A Duff) writes:

>Ada's access-to-subprogram types are rather severely restricted.  Yes,
>you can make a pointer-to-nested-proc, but that pointer can't survive
>longer than the immediately enclosing procedure.  [...]
>For a static-link implementation, a level-0 access-to-proc type can be
>implemented as a single address (of the procedure's code).   [...]
>A display implementation can always implement access-to-subp as a single
>address, at all levels.
>
>Does this help?

Yes, thanks.  I think I understand things now.

>Fergus Henderson <fjh@mundook.cs.mu.OZ.AU> wrote:
>>The way the Mercury implementation handles taking the address of a
>>generic instance in a shared generic is to package up the generic
>>instance data in basically the same way that the stack frame data in an
>>enclosing procedure is packed up when you take the address of a nested
>>procedure.  So as long as you are already committed to being able to
>>take the address of nested procedures, there is no distributed
>>overhead -- I think.
>
>Yes, this makes sense, I think, but doesn't it imply that level-0
>access-to-proc types have a static link attached?  That would constitute
>a distributed overhead, would it not, given the stuff I said above?  And
>make the interface to C more painful?

Yes, you're correct in all of the above.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Q: access to subprogram

[Richard A. O'Keefe]

bobduff@world.std.com (Robert A Duff) writes:
>>Whenever you simulate any mechanism,
>>...[all manner of evil happens]

>True, but the logical conclusion is that all useful mechanisms that
>anybody has ever thought of should be included in the language.  One has
>to make a trade-off between a useful gizmo and language complexity
>(etc).

I do not call that a logical conclusion.
"All useful mechanisms which have ever been *commonly used* should be
included" comes closer to being a reasonable generalisation of what I
wrote.

>Anyway, I think this argument is getting confused between "downward
>closures" and "full closures".  If I understand your example correctly,
>it needs downward closures, but not full closures.

Right.  And that is all _I_ have ever been talking about in this thread.
As it happens, I like full closures, principally because they fit very
well with a "building blocks" approach to reuse, and because it greatly
simplifies things like graphic programming in Clean:  it's the *compiler's*
job to worry about which things need to survive for a callback, not mine.
But I am not advocating full closures (or continuations, or first class
environments, or anything sexy) for Ada.  All I am saying is that one
specific feature -- downward funargs -- has proven its usefulness over
many years in a lot of other languages, is demonstrably clumsy to
simulate in Ada 83, can demonstrably be implemented efficiently by a
compiler (5 seconds for the program in Scheme compiled by Stalin into C
then into SPARC code by SPARCompiler C SC4.0, compared with 18 seconds for
the program in Ada compiled by GNAT 3.04 GCC 2.7.2), was expected for
Ada 95, but arrived in an unusable fashion because that feature was
confounded with another feature, namely access-to-procedure.

You can have nested procedures as parameters without procedure pointers
(Pascal, Fortran, Algol 60).
You have have procedure pointers without nested procedures as parameters
(C).
You can have both without restriction (Lisp, Scheme, ML, Smalltalk).

The point is, you don't *have* to tangle them up, and the restrictions
that are necessary for the one (procedure pointers) if you don't want
to support full closures are NOT necessary for the other (procedures
as parameters).

Not only that, you *can* tangle them up in a different way from the Ada 95
way:  you say that the lexical level of a procedure parameter is the lexical
level of the procedure in whose header it appears, and forbid (copies) of
that parameter outliving the callee.

So it would have been possible to have both procedure pointers with a
lexical level restriction (thus permitting an implementation in which
library level pointers are fully compatible with C) *and* unrestricted
passing of nested procedures as parameters.

>I have argued
>in favor of downward closures (because in my experience they have been
>very useful, and they are very cheap to implement).  But I remain
>unconvinced about full closures (because they seem less commonly needed,
>and they are substantially more expensive to implement -- although your
>benchmark shows that in at least one case, the run-time cost is a myth).

Ahem.  My benchmark is solely concerned with DOWNward closures, not full
closures.  Just because I ran the benchmark in a language which supports
full closures doesn't mean that the benchmark itself used that power.

>And the only serious example anybody posted was Ackermann's function,
>which is useful in explaining how full closures work, but doesn't
>exactly make me want to use them every day.

Well, the classic application of full closures in Scheme is OOP.
Scheme has far too many OOP dialects, because it is extremely easy for
everyone to implement their own OOP system using closures.
The classic *idiom* using closures is simulating modules:

	(define export1)		; top level placeholder declarations
	(define export2)

	(let (  <<local declarations >> )
	    (set! export1 (lambda <<args>> <<body>>))
	    (set! export2 (lambda <<args>> <<body>>)))
	    
The exported functions have access to the local declarations.

My argument about simulation extends to this as well:  it is better to have
a module construct so that the compiler knows what you are up to and can
check that you got it right.


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

Re: Q: access to subprogram

[Robert A Duff]

In article <4tha38$1p@goanna.cs.rmit.edu.au>,
Richard A. O'Keefe <ok@goanna.cs.rmit.edu.au> wrote:
>I do not call that a logical conclusion.
>"All useful mechanisms which have ever been *commonly used* should be
>included" comes closer to being a reasonable generalisation of what I
>wrote.

Fair enough.

>Ada 95, but arrived in an unusable fashion because that feature was
>confounded with another feature, namely access-to-procedure.

I don't understand why you say that.  It's not historically accurate.

The MRT was well aware of the two different features, and proposed two
different features, with different sets of rules.  The "passing nested
procedures as params" features was not included in the final design.
You can complain about that fact (and I will agree), but you shouldn't
complain that the language designers "confounded" the two features --
they didn't.

>Ahem.  My benchmark is solely concerned with DOWNward closures, not full
>closures.  Just because I ran the benchmark in a language which supports
>full closures doesn't mean that the benchmark itself used that power.

Right.  I just meant that your benchmark shows that it's possible for
downward closures to be efficient even in a language that has full
closures (a distributed overhead issue).  We already knew that, of
course -- there are compilers for many languages that require
heap-allocated stack frames in general, but are capable of avoiding that
it many cases.  And anyway, your benchmark is just one example, and thus
not very convincing on this point.

>Well, the classic application of full closures in Scheme is OOP.

Which of course doesn't convince *me* that full closures are a Very Good
Thing, since I'm happy to have the OOP features built in, and do the
"similating" in the other direction.

>My argument about simulation extends to this as well:  it is better to have
>a module construct so that the compiler knows what you are up to and can
>check that you got it right.

... And apparently you agree.  Either one can be used to "simulate" the
other.  So, is there any reason to have both?

- Bob

Re: Q: access to subprogram

[Richard A. O'Keefe]

ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
>       I spent this afternoon (when not talking to students) taking the
>       integration example and beefing it up to the point where it would
>       plausibly take a reasonable amount of time.  I produced three
>       versions:  [now four, using two C compilers]

Lang	Time	Size	How compiled
Ada	18	94	3.04 gnatmake -gnatp -cargs -O4
Pascal	18	57	SPARCompiler 4.0 pc -s -native -O4
C	20	92	2.7.2 gcc -O4
C	13	92	SPARCompiler 4.0 cc -fsimple -native -fast -xO4
Scheme	 6	40	stalin -copt "-O4" -d -On -dc
Scheme	 5	40	stalin -cc cc -copt "-native -xO4" -d -On
	Seconds	Lines

[All of these were double precision; single precision trimmed 1 second off
the time for C and Pascal, made no apparent change for Ada, and had yet to
be tried at the time of reposting for Scheme.]

rogoff@sccm.Stanford.EDU (Brian Rogoff) writes:

>Note that the Pascal compiler was not any better than GNAT on this.

The C code simulates a model where top level procedures do not have
a static link, but nested procedures do (a realistic implementation
model).  The C times bracket the Ada/Pascal times.  The really 
interesting thing was that the Ada, Pascal, and Scheme versions worked
the first time they got through the compiler, while the C version
crashed.  (lclint pointed me to an uninitialised variable...)

>The data 
>does suggest that the nested procedure approach may have performance 
>advantages in addition to its general advantages as a simple programming 
>construct. What is stalin doing? Is it dependent on any simplifying 
>assumptions about the code?

The -d option says "inexact numbers are C doubles".
The -On option says "do not check for exact integer overflow",
    which I put in to make the comparison fair.
The -dc option says "yes you can use alloca"; as you see from the
    last line, leaving it out didn't make much difference.

Does Stalin make any simplifying assumptions about the code?
Well, it doesn't support bignums or rationals (neither do Ada, Pascal,
or C).  It doesn't support complex arithmetic (neither does C, and
neither does SPARCompiler Pascal, even though it's in the current standard.)
It doesn't support DELAY/FORCE (nor do Ada, Pascal, or C).
It doesn't support LOAD (adding new code at run time, or replacing existing
code).  Neither do Ada, Pascal, or C.

Stalin makes *no* other assumptions about the program.  Even CAR and CDR
receive no special magic treatment.  It just does a really thorough job
of static analysis and optimisation.  Jeff Siskind has put a *lot* of
work into the algorithms in this compiler.  It's a one-man show; he is
the only one working on it, and his latest grant proposal to do more
work on it was turned down, so it is also by a rather large margin the
slowest of the compilers tested.  This is a pity, because while a lot of
the methods in Stalin are related to dynamically typed languages,
"Stalin also does global static life-time analysis for all allocated
data.  This allows much temporary allocated storage to be reclaimed
without garbage collection.  Finally, Stalin has very efficient
strategies for compiling closures."  Of course, when you introduce OOP,
dynamic typing joins the party, so it's not that clear that Stalin has
nothing to contribute to the art of Ada compilation.

>A shared generic passes in some way a pointer to a data area identifying the
>generic, and containing its local objects.

I see.  This is like "type classes" as found in Mercury and Haskell.
I note that Haskell manages to combine this with unrestricted closures;
I don't know how the Glasgow Haskell Compiler handles it, but I don't
_think_ it involves run-time code generation.

>The result that that eliminating the restrictions on 'Access would make some
>code easy to write, but would force the junking of existing code sharing
>algorithms, or make the cost of access-to-subprogram substantially higher than
>in competing languages.  Those both are very bad ideas.

Ah *hah*.  This is *not* an argument against procedure parameters,
it is an argument against identifying them with procedure *pointers*.
The force of the integration example is that even though current Ada
"has" procedure parameters they can't be *used* for the things that
people have historically wanted to use them for,  Now I understand why
it was thought that the maximum size of the display mattered:  people
wanted to know how much stuff to put in a procedure pointer, and a
procedure pointer of a type declared at lexlevel N needs N+c pointers,
and a pointer declared who-knows-where needs who-knows-how-many pointers.
Fine, but NONE of this is a problem with procedure parameters, only
with bodging them up Borland-style as procedure pointers.

>How much are upward funargs used in day to day functional programming? I 
>think Bob Duff is still looking for a compelling example of why they are 
>so much better than the explicitly simulated closure via an instance of a 
>tagged type.

Whenever you simulate any mechanism,

 - you lose clarity
	This is demonstrated by the line numbers.

 - you introduce the risk of error
	The Scheme and Pascal versions didn't have to "simulate" anything.
	They worked, as soon as the compiler was happy with them.
	The C version crashed, precisely *because* having to simulate the
	feature added complexity, and I slipped, even though I was	
	transcribing code, not rewriting from scratch.  All I had to worry
	about was how to simulate the feature, in < 100 lines of code, and
	I got it wrong.

 - you lose efficiency.
	The compiler doesn't understand the feature.  It compiles your
	simulation using general methods.  In this example, even when I
	told the SPARCompiler C compiler (there is no redundancy there;
	that's it's name) to in-line some crucial functions, it didn't
	improve the speed.  The fact that Stalin really thoroughly
	understands procedures does pay off in this small example where
	procedure calling is a major cost factor.

One might as well say, "why have direct language support for OOP?  You
can always simulate it!"  And in fact Scheme programmers have often said
this, because a language that takes procedures really seriously makes it
dead simple to simulate OOP with procedures.




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

Re: Q: access to subprogram

[Brian Rogoff]

bobduff@world.std.com (Robert A Duff) writes:
   In article <ROGOFF.96Jul26095803@sccm.Stanford.EDU>,
   Brian Rogoff <rogoff@sccm.stanford.edu> wrote:
   >I think that you posted that you like Smalltalk blocks a lot, which are 
   >essentially just anonymous closures, right? 

   Yes, I did post that.  But it's not because they are full closures --
   almost all of the uses in my code, and almost all of the uses I've seen,
   are the downward kind.  

On reflection, this makes a lot of sense, because a lot of the uses I saw 
of full closures in Scheme (in the SICP book) would use Smalltalk objects.
So in a language with both objects and closures, full closures might seem 
redundant. 

If your experience can be generalized, it seems like some kind of (potentially 
anonymous) downward closure construct would fit in well with the Ada ideal 
of "high abstraction if it can be easily implemented efficiently". I guess 
that this is one of the constructs Magnus Kempe had in mind when he mentioned 
that he thought Ada could have headed further in the direction of functional 
programming. 

   <... other reasons for liking anonymous blocks deleted ...>

   >....I think the beauty of this 
   >construct is that you can implement lots of features cleanly in terms of 
   >it, like control structures. 

   No, that merely requires downward closures.  I'm still looking for an
   example that really makes the upward direction look wonderfully
   powerful.

I'm still thinking :-). I don't know if you'll find a "killer example", just 
a wide range of examples that can be solved using closures. 

   >...Also the implementation of closures on objects 
   >seems heavy/verbose to me.

   True.  But that's OK, unless full closures are really as powerful and
   commonly needed as I've heard.  

Powerful, yes. If you have objects, downward closures, packages and generics, 
they might be a bit redundant.

-- Brian

Re: Q: access to subprogram

[Robert A Duff]

In article <4tldre$lco@fu-berlin.de>,
Thomas Wolff <wolff@inf.fu-berlin.de> wrote:
>Regarding the popularity of distributed systems, the terminology is 
>confusing. Was it invented in this thread or is it common elsewhere? 

I don't know where the term comes from, but it certainly existed before
this thread.  It was commonly used, for example, during the Ada 9X
design.  An accusation of "proposed feature X has distributed overhead"
happened many times, and was taken quite seriously.  I suspect the term
is much older than that.

>Perhaps something like "propagated overhead" should rather be used.

Shrug.  It seems to me that one should be able to tell from context
whether you're talking about "distributed overhead" (i.e. overhead
distributed across unused features of the language) or "distributed
systems" (i.e. programs consisting of partitions distributed across a
network of computers).

- Bob

Re: Q: access to subprogram

[David Kristola]

In article B9F@world.std.com, bobduff@world.std.com (Robert A Duff) writes:
>In article <4t8rfo$g71@butch.lmsc.lockheed.com>,
>David Kristola <davidk@OS2.ifs> wrote:
>>Maybe i am misunderstanding the meaning of "distributed overhead", but don't
>>all shared generics have some?  But anyway...
>
>I think you're misunderstanding "distrib overhead".  "Feature X causes
>distributed overhead" means that your program will have some overhead,
>caused by the mere existence of feature X in the language, even if you
>don't use feature X.  If feature X is slow, that's just plain old
>overhead, not "distributed overhead".

Yes, i was confused.  Thank you.


[snip]

>Distributed overhead is evil.

[snip]

>Suppose Call_Something were *outside* the generic, and saved F'Access in
>a global variable.  This is illegal, but we're arging about "what if
>this were legal?"

I should have used dot notation to indicate that Call_Something was outside
the generic.  I also should have used an access-to-subprogram type.  I suppose
there are still problems, considering that the generic instance could be
temporary.

Maybe by placing a pointer in the generic data block (actually, in every
generic data block) and allocating (on the heap) generic body specific data
during elaboration of the generic instance body (but deallocating is now a
problem), and filling in the pointer to point to the additional information
during the instance body elaboration....

I guess this is all a moot point (i hope i am using "moot" correctly, i
skipped the big discussion on that topic :-).

[snip]

>Note that the workaround isn't so bad: declare F in the private part,
>and then it's legal (and then the compiler knows about it at
>instantiation time, and can generate the wrapper at that time).

Now if i only had a job where i could use Ada95, i could use this ;).

>- Bob

david kristola
Work: davidk@os1.ese.lmsc.lockheed.com
Play: DJKristola@aol.com

My suggestion for Lockheed Martin's next slogan:
"Lockheed Martin, we make things that go BOOM!"

Re: Q: access to subprogram

[Thomas Wolff]

bobduff@world.std.com (Robert A Duff) writes:

: In article <4t8rfo$g71@butch.lmsc.lockheed.com>,
: David Kristola <davidk@OS2.ifs> wrote:
: >Maybe i am misunderstanding the meaning of "distributed overhead", but don't
: >all shared generics have some?  But anyway...

: I think you're misunderstanding "distrib overhead".  "Feature X causes
: distributed overhead" means that your program will have some overhead,
: caused by the mere existence of feature X in the language, even if you
: don't use feature X.  If feature X is slow, that's just plain old
: overhead, not "distributed overhead".

Regarding the popularity of distributed systems, the terminology is 
confusing. Was it invented in this thread or is it common elsewhere? 
Perhaps something like "propagated overhead" should rather be used.

Re: Q: access to subprogram

[Richard A. O'Keefe]

Ken Garlington <garlingtonke@lmtas.lmco.com> writes:

>Richard A. O'Keefe wrote:
>> 
>>         Ada (using generic instantiation)
>>                 compiled with gnatmake -gnatp -cargs -O4
>>                 Size: 94 lines.

>I don't know how to read the gnat command lines, so could some one tell me
>if this means all exceptions are suppressed?

If I may quote from "gnatinfo.txt"
    To disable constraint checks, compile the program with th
    "-gnatp" option.  This is equivalent to having Pragma suppress
    applied to everything.

So yes, it does suppress everything.  -O4 is high optimisation level.

>Also, is source line size being given here as a measure of efficiency?

Don't be ridiculous, of *course* not.
The number of source lines required to express the same algorithm
naturally is an inverse measure of EXPRESSIVENESS, and has no
intrinsic connexion whatsoever with efficiency.  Why would you imagine
otherwise?  The sole measure of efficiency I proposed is TIME.

>What were the other measures compared to the alternatives
>(readability, reusability, etc.)?

Obviously, if it takes you more lines, it's likely to be harder to read.
I have no objective measurements of readability.  I believe that I am
equally familiar with all four languages (I have, and have studied hard,
the standards for all of them, and have written a fair amount of code in
all four).  In this case:

	Scheme is the most readable.
	Pascal comes close; no warping to fit the language.

	The C code is shorter, but it has some nasty internal coupling,
	so I rank the Ada code (all connections explicit) as more
	readable (though longer) than the C.

As for re-use, where I can be objective:

	Scheme is by far the most reusable, having no constraints
	on reuse at all.

	The Pascal code is cut-and-paste reusable; in Turbo Pascal or
	Think Pascal or ISO Pascal Extended the integration code could
	be in a unit/module.

	The Ada code is as reusable as the Pascal code, in the sense of
	requiring no modifications for reuse, but has higher reuse costs.
	(It takes more source code to effect reuse, and generates more
	object code).

	The C code was not written for re-use.  The need to explicitly
	simulate funargs by passing environment pointers pushes up reuse
	cost; unlike the Scheme and Pascal code you cannot combine the
	integration functions with *existing* real-valued functions but
	must write glue code.


>> I guess Scheme running 3 times faster than Ada or Pascal is not "intuitive"
>> for many programmers.

>It's certainly not intuitive to _me_. However, I would certainly have no problem 
>with a statement that a particular Scheme toolset might generate code that is 
>three times more efficient than an Ada _toolset_, for a given host/target 
>platform. (Do we really believe GNAT is the most efficient Ada compiler available, 
>for example? I keep reading that not all optimizations have been implemented in 
>GNAT yet...)

For sure.  Stalin has a fair bit in common, I think, with VORTEX, with
the Self compiler, and with Stanford's FUSE.  The common factor here is
tools that start with very high level languages and optimise the heck out
of them; there are analyses and transformations that they perform which I
expect Gnat will _never_ perform.  Partly this is because they deal with
simpler languages.  For Ada, I think it is more important to get tasking
absolutely right than to perform aggressive optimisations.

Note also that in a previous thread in this group I was pleased to report
that GNAT's time for a certain numerical program was close to the time
from SPARCompiler Fortran 77.  Whether or not GNAT is the best, it is
pretty darned good.

But please, don't attack a proposition your interlocutor never defended.
Gnat is the best Ada compiler *I've* got, that's all.  So far I have tried
this example in
	Clean 1.0		-- not the latest version
	Gambit 2.2.2		-- pretty recent, but maybe not the latest
	Think C 5.0		-- far from the latest version
on the Mac
	Gnat 3.04		-- not the latest version
	SPARCompiler C 4.0	-- is the latest version
	SPARCompiler Pascal 4.0	-- is the latest version
	Gcc 2.7.2		-- probably not the latest any more
	Stalin 0.6		-- latest generally available
on an UltraSparc.  Why these versions?  Because that's what I've got.
That's all.

Remember:  I am not interested in establishing which _language_ is the
best.  My sole concern was to provide an example showing that the
restrictions on procedure parameters which make my example *impossible*
to write directly in Ada 95 are not *necesary* for efficiency.  This
does not, unfortunately, prove that it would be easy for _any_ Ada
vendor to support Algol-style funargs, still less that it would have
been affordable for _every_ Ada vendor to do so.  ALL my example can
accomplish, and I believe it does accomplish this, is to show that
Algol/Pascal-style funargs are fully consistent with more efficiency
than I can currently get from a good Ada compiler.
-- 
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.

Re: Q: access to subprogram

[Jon S Anthony]

In article <4tha38$1p@goanna.cs.rmit.edu.au> ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:

[...]
> simulate in Ada 83, can demonstrably be implemented efficiently by a
> compiler (5 seconds for the program in Scheme compiled by Stalin into C
> then into SPARC code by SPARCompiler C SC4.0, compared with 18 seconds for
> the program in Ada compiled by GNAT 3.04 GCC 2.7.2), was expected for
> Ada 95, but arrived in an unusable fashion because that feature was
> confounded with another feature, namely access-to-procedure.
[...] 
> 
> The point is, you don't *have* to tangle them up, and the restrictions
> that are necessary for the one (procedure pointers) if you don't want
> to support full closures are NOT necessary for the other (procedures
> as parameters).

Exactly so.  What is more, this particular scheme was in fact
considered: access to procedure parameters.  It would have fit fairly
well with the language (maybe even rather well) in this area.  But it
seems that certain of those involved becamed "obsessed" with the view
that the only way to achieve the effect was with some sort of
access-to-procedure _type_ (the so called limited access type in
particular).

> Not only that, you *can* tangle them up in a different way from the
> Ada 95 way: you say that the lexical level of a procedure parameter
> is the lexical level of the procedure in whose header it appears,
> and forbid (copies) of that parameter outliving the callee.

Meaning simply that only procedures at or below the lex level of the
procedure P with the parameter could be legally supplied in a call of
P.  I suppose in this context (still involving an access type) the
access to subprogram type to which the procedure access would belong
would also have to be at or below P (which would effectively cover
the stuff in the first sentence...)

> So it would have been possible to have both procedure pointers with a
> lexical level restriction (thus permitting an implementation in which
> library level pointers are fully compatible with C) *and* unrestricted
> passing of nested procedures as parameters.

Certainly sounds right.  So, what are the gotchas?...

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com