Version 1.1 of acs/ac-00003.txt

Unformatted version of acs/ac-00003.txt version 1.1
Other versions for file acs/ac-00003.txt

!standard 12.5.2 (00)          00-10-30 AC95-00003/01
!status received 00-10-30
!subject Generic formal parameter control for generic sharing
!summary
!appendix

From: Dan Eilers
Sent: Thursday, October 19, 2000 11:51 AM

!topic floating-point shared generic bodies with unchecked_conversion
!from Dan Eilers
!discussion

The attached email from Robert Dewar mentions an unresolved issue
with sharing generic bodies when more than one floating-point type
exists.  This hole should be fixed (one way or another), so that
vendors such as ourselves that do such sharing are not perceived
to be "cheating" in any way.

Possible fixes (not mutually exclusive) include:
   1)  noting that unchecked_conversion may not work properly in this case;
   2)  disallowing unchecked_conversion in this case;
   3)  strengthening the contract model by providing a mechanism for the
user to declare in the generic formal part that all instantiations of
the generic will use actual parameters of a particular size, allowing
the compiler to generate shared code based on that assumption and reject
any other instantiations;
   4)  providing a way for the user to declare that the compiler should
create more than one shared executable version of the body, where the
version of the body to be used for a particular instantiation is selected
based on user-specified characteristics of the actual generic parameter(s).
   5)  provide a way for the user to declare more than one source-code
version of a body for a generic unit, with the version of the body to be
used for a particular instantiation is selected based on user-specified
characteristics of the actual generic parameter(s).

Note that DEC has a patent that if presumed to be valid prevents other
compilers from automatically doing #4, but it does not appear to prevent
languages from having mechanisms for user-controlled sharing of generics
based on properties of the actual generic parameters.  The abstract of
the DEC patent is attached below.

        -- Dan Eilers

=======================================================================
To: ARG@acm.org, dan@irvine.com
Subject: Re: Draft Agenda, Laurel ARG mtg.
Message-Id: <20001017000729.46C4E34D82@nile.gnat.com>
Date: Mon, 16 Oct 2000 20:07:29 -0400 (EDT)
From: dewar@gnat.com (Robert Dewar)

By the way, it seems there are many unresolved issues for full
implementation of sharing, especially if you have more than one
floating-point type, because then doing unchecked conversion properly
in the shared object is really quite complex for example. The only
compilers I know of doing generic sharing either had one fpt type (Rational)
or cheated and did UC wrong (RR).

cheated should of course be in quotes there, indeed it is hard to see how
else you could do it except by approximating there.

Indeed at one point there was an attempt to change the RM to allow this
particular problem to be solved.

I suspect there are many other similar problems lurking.

=======================================================================
     _________________________________________________________________

   United States Patent 5,280,617
   Brender ,   et al. January 18, 1994
     _________________________________________________________________

   Automatic program code generation in a compiler system for an
   instantiation of a generic program structure and based on formal
   parameters and characteristics of actual parameters

                                  Abstract

   A compiler maintains a library of sharable program structures
   generated in response to instantiations of a generic program
   structure, along with characteristics of parameters which were used in
   generating the sharable program structure. In response to an
   instantiation of a generic program structure, the compiler generates
   information relating to the characteristics and usage of each
   parameter which are used in connection with the instantiation. The
   compiler then compares that information to the corresponding
   information associated with the sharable program structures in the
   library. If the library contains a sharable program structure whose
   parameter information compares satisfactorily, that sharable program
   structure is used in connection with further operations in connection
   with the instantiation. On the other hand, if the library does not
   contain such a sharable program structure, one is generated and stored
   in the library, along with the characteristics of the parameters used
   in its generation, for use in sharing with later instantiations. In
   addition, the just-generated sharable program structure is used in
   further operations in connection with the instantiation.
     _________________________________________________________________

****************************************************************

From: Tucker Taft
Sent: Thursday, October 19, 2000 2:39 PM

Unfortunately Robert's email does not provide an example
of the problem.  Can you include a detailed explanation of
the problem for those of us that forget it?

For most such sharing problems, I have frequently heard
the solution to be simply adding another "thunk" to the
instantiation descriptor, though I don't know how realistic
that is for unchecked conversion.

> Note that DEC has a patent that if presumed to be valid prevents other
> compilers from automatically doing #4,

This patent is definitely not valid.  Intermetrics engineer
Gary Bray published (in a SIGPlan conference proceedings)
many years before essentially the same algorithm that
DEC patented.  From a pragmatic point of view, DEC
is almost certainly not interested in trying to defend the patent.

> ... but it does not appear to prevent
> languages from having mechanisms for user-controlled sharing of generics
> based on properties of the actual generic parameters.  The abstract of
> the DEC patent is attached below.

In any case, you could certainly provide pragmas that
do (3) .. (5) [(1) and (2) sound like a cure that is worse
than the disease].  It is not clear that it is worth
at this point trying to standardize such pragmas.
There was some thought that pragma Optimize(Space) or
pragma Optimize(Time) might be used to select shared
versus macro-expanded approaches, but I don't know if
any vendor followed up on that idea.

****************************************************************

From: Randy Brukardt
Sent: Thursday, October 19, 2000 3:09 PM

> Unfortunately Robert's email does not provide an example
> of the problem.  Can you include a detailed explanation of
> the problem for those of us that forget it?

For what it's worth, I don't think that there is any such problem, at least
not for generic float types.

The problem with Janus/Ada stems from our (self-imposed) rule that the size
of both operands of the unchecked conversion match. (We have found that this
rule catches a lot of errors, and it also avoids the need to define what
happens if there aren't enough bits, or too many bits). In order to avoid
contract model problems, we check this rule in generic bodies in an
assume-the-worst manner. The result is that most generic formal types can't
be converted (because the size isn't known).

If we didn't care about that, implementing the conversion would be easy (at
least if we don't care about leftover bits). We'd just use the thunk that
already exists to handle accesses through general access types, which has to
be prepared to read/write in the format of the original type. For example,
to go from a GFLT to an Integer, we would just allocate some scratch space
in the largest possible size (which is known, of course), use the thunk to
write the value to it, cast the address as a ptr to Integer, and go on. And
the reverse conversion is about the same.

The issue Robert remembers originally came up with the unchecked conversions
of generic discrete types to packed arrays of Boolean in the ACVC. That is a
somewhat messier case, because both items depend on the generic. In this
case, we rejected the conversion because the array of Boolean (which
depended on 'Size of the generic discrete type) did not have a static
constraint. We've since changed our compiler model which would eliminate
that problem (at least if we ever got bit packed arrays to work...); but we
still have the assume-the-worst check.

I would have been happy if there was a permission for the instantiation (or
call) to raise an exception if the sizes don't match. (Note that I'm
generally talking about the "Object_Size" [in more-or-less the GNAT sense],
not necessarily 'Size.) The Ada 95 RM essentially gives that permission (all
of the discussion I think was in the context of Ada 83 which definitely did
not have such a permission; in any case we've made no real changes in UC in
a long time), so I don't think there is any specific problem that the ARG
need discuss here. In all probability, we would make the conversion work if
the size matched, and raise Program_Error otherwise. No problem.

The more general issue of additional mechanisms to support sharing certainly
would be worth discussing in any case. (But of course that is an amendment
AI.)

****************************************************************

From: Robert Dewar
Sent: Friday, October 20, 2000 11:00 AM

I do not think this is important enough to fix at this stage. Most
certainly the idea of disallowing UC is quite unacceptable, as is
the idea of allowing it not to work. Basically my feeling is that
we should not modify the language in any restrictive way to accomodate
shared generics at this stage. Implementations are free to rig up
pragmas etc to restrict things anyway they like, no language change
is appropriate.

****************************************************************

From: Dan Eilers
Sent: Saturday, October 21, 2000 1:08 PM

Tuck wrote:
> Unfortunately Robert's email does not provide an example
> of the problem.  Can you include a detailed explanation of
> the problem for those of us that forget it?
>
> For most such sharing problems, I have frequently heard
> the solution to be simply adding another "thunk" to the
> instantiation descriptor, though I don't know how realistic
> that is for unchecked conversion.

I think the problem is that such a "thunk" would copy only 32 bits
if the instantiation was for short-float, and that this would not
copy all 64 bits of variables declared within the generic and
implemented as a 64-bit float.  Since the representation of 64-bit
floats is different from 32-bit floats, copying only the first 32-bits
is fatal.

> In any case, you could certainly provide pragmas that
> do (3) .. (5) [(1) and (2) sound like a cure that is worse
> than the disease].

Since facilitating generic code sharing was a formal Ada9x requirement,
relying on implementation-defined pragmas doesn't seem to be the right
solution to problems that aren't implementation specific.

> There was some thought that pragma Optimize(Space) or
> pragma Optimize(Time) might be used to select shared
> versus macro-expanded approaches, but I don't know if
> any vendor followed up on that idea.

We didn't.  These pragmas don't address the problem of "cluster analysis",
identifying groups of instantiations for which the user wants a shared
a generic body.

****************************************************************

From: Robert Dewar
Sent: Saturday, October 21, 2000 7:30 PM

<<Since facilitating generic code sharing was a formal Ada9x requirement,
relying on implementation-defined pragmas doesn't seem to be the right
solution to problems that aren't implementation specific.>>

So what? That's not a justification for upwards incompatible changes
this late in the game. My own opinion is that it is not worth spending
any more time at this stage modifying the language to further ease
generic sharing.

****************************************************************

From: Tucker Taft
Sent: Sunday, October 22, 2000 9:56 PM

Dan Eilers wrote:
> I think the problem is that such a "thunk" would copy only 32 bits
> if the instantiation was for short-float, and that this would not
> copy all 64 bits of variables declared within the generic and
> implemented as a 64-bit float.  Since the representation of 64-bit
> floats is different from 32-bit floats, copying only the first 32-bits
> is fatal.

I presume the thunk would have to do the "right thing" whatever
that might be.  So if the short float values are really being
represented as longer floats, then the thunk would presumably
convert them to the "official" representation expected by
unchecked conversion.  The "usual" unchecked conversion process
could then actually do the conversion/bit copy, and then
conceivably a different thunk might be invoked to convert back
from the "official" representation to the "shared" representation.

> Since facilitating generic code sharing was a formal Ada9x requirement,
> relying on implementation-defined pragmas doesn't seem to be the right
> solution to problems that aren't implementation specific.

What is doable and practical in the way of generic sharing
still seems very much dependent on implementation-specific
details of an implementation, so it does not seem unreasonable
that the pragmas would be implementation-specific.

Certainly if there are a group of vendors with a real interest
in generic sharing, it might be worth their sharing ideas about
generic sharing pragmas.  However, there doesn't seem to be
enough of a groundswell of interest, nor adequate expertise,
probably, in the ARG, to make it seem worthwhile for the ARG
to spend energy on this now.  A well researched proposal, including
information from multiple vendors' implementation approaches,
might be of interest.  But at the moment, this seems relatively
low priority.

> > There was some thought that pragma Optimize(Space) or
> > pragma Optimize(Time) might be used to select shared
> > versus macro-expanded approaches, but I don't know if
> > any vendor followed up on that idea.
>
> We didn't.  These pragmas don't address the problem of "cluster analysis",
> identifying groups of instantiations for which the user wants a shared
> a generic body.

For our implementation, we never considered "universal" generic
sharing, we only considered the cluster analysis, and so for us,
pragma Optimize(Space) would have triggered the cluster analysis.
I can see that if you plan to have 3 approaches (macro, universal,
and cluster), then pragma Optimize wouldn't give enough flexibility.

****************************************************************

From: Robert Dewar
Sent: Sunday, October 22, 2000 11:04 PM

In any case it seems probably more appropriate to introduce a separate
pragma. Note that DEC has already defined pragma Shared_Generic.

****************************************************************

From: Dan Eilers
Sent: Monday, October 23, 2000 3:26 AM

Robert Dewar wrote:
> <<Since facilitating generic code sharing was a formal Ada9x requirement,
> relying on implementation-defined pragmas doesn't seem to be the right
> solution to problems that aren't implementation specific.
> >>
>
> So what? That's not a justification for upwards incompatible changes
> this late in the game. My own opinion is that it is not worth spending
> any more time at this stage modifying the language to further ease
> generic sharing.

What is it in my 5 possible suggested fixes that appears upwards
incompatible to you, other than perhaps #2, disallowing unchecked_conversion
in circumstances where it can't be correctly implemented?
I would recommend one of solutions 3..5, for which I see no upward
incompatibility problems at all.

Paragraph 10 of the Introduction to the RM states:
   "Every construct of the language was examined in the light of
present implementation techniques.  Any proposed construct whose
implementation was unclear or that required excessive machine
resources was rejected."

This statement is not true with respect to generics with floating-point
formal parameters, such as the predefined generic_elementary_functions
package.  There is no clear and efficient way to implement this package,
or similar packages defined by the user.

****************************************************************

From: Robert A Duff
Sent: Monday, October 23, 2000 10:45 AM

> Paragraph 10 of the Introduction to the RM states:
>    "Every construct of the language was examined in the light of
> present implementation techniques.  Any proposed construct whose
> implementation was unclear or that required excessive machine
> resources was rejected."
>
> This statement is not true with respect to ...

I wish this was the *only* case where paragraph 10 turned out not to be
true...

;-)

****************************************************************

From: Robert Dewar
Sent: Wednesday, October 25, 2000 8:11 AM

<<What is it in my 5 possible suggested fixes that appears upwards
incompatible to you, other than perhaps #2, disallowing unchecked_conversion
in circumstances where it can't be correctly implemented?
I would recommend one of solutions 3..5, for which I see no upward
incompatibility problems at all.>>

The "perhaps" is rather amazing in the above sentence!

****************************************************************

From: Dan Eilers
Sent: Monday, October 23, 2000 3:53 AM

Tuck wrote:
> > I think the problem is that such a "thunk" would copy only 32 bits
> > if the instantiation was for short-float, and that this would not
> > copy all 64 bits of variables declared within the generic and
> > implemented as a 64-bit float.  Since the representation of 64-bit
> > floats is different from 32-bit floats, copying only the first 32-bits
> > is fatal.
>
> I presume the thunk would have to do the "right thing" whatever
> that might be.  So if the short float values are really being
> represented as longer floats, then the thunk would presumably
> convert them to the "official" representation expected by
> unchecked conversion.  The "usual" unchecked conversion process
> could then actually do the conversion/bit copy, and then
> conceivably a different thunk might be invoked to convert back
> from the "official" representation to the "shared" representation.

I don't think there is any way the "thunk" could in general know
whether its parameter was a 64-bit object declared within the generic,
or a 32-bit object declared outside the generic.  So it would be
impossible to do the "right thing".

> What is doable and practical in the way of generic sharing
> still seems very much dependent on implementation-specific
> details of an implementation, so it does not seem unreasonable
> that the pragmas would be implementation-specific.

I would think the difficulties of sharing between instantiations
of different object representations would be common to all
implementations, and that providing a mechanism to assure that sizes
(and alignments) would be the same would make such shared generics
relatively straightforward to implement in all implementations.
The issues are very similar if not identical to the criteria for
efficient implementation of view conversions.

****************************************************************

From: Tucker Taft
Sent: Monday, October 23, 2000 10:34 AM

Dan Eilers wrote:
>
> Tuck wrote:
> ...
> > I presume the thunk would have to do the "right thing" whatever
> > that might be.  So if the short float values are really being
> > represented as longer floats, then the thunk would presumably
> > convert them to the "official" representation expected by
> > unchecked conversion.  The "usual" unchecked conversion process
> > could then actually do the conversion/bit copy, and then
> > conceivably a different thunk might be invoked to convert back
> > from the "official" representation to the "shared" representation.
>
> I don't think there is any way the "thunk" could in general know
> whether its parameter was a 64-bit object declared within the generic,
> or a 32-bit object declared outside the generic.  So it would be
> impossible to do the "right thing".

I obviously don't know how your compiler works, but I would
certainly presume that the compiler knows whether it is
dealing with a 32-bit object declared outside the generic,
or a 64-bit object that is inside, and it would only generate
a call on the thunk when it needed an "extra" conversion
to be performed.

> > What is doable and practical in the way of generic sharing
> > still seems very much dependent on implementation-specific
> > details of an implementation, so it does not seem unreasonable
> > that the pragmas would be implementation-specific.
>
> I would think the difficulties of sharing between instantiations
> of different object representations would be common to all
> implementations, and that providing a mechanism to assure that sizes
> (and alignments) would be the same would make such shared generics
> relatively straightforward to implement in all implementations.
> The issues are very similar if not identical to the criteria for
> efficient implementation of view conversions.

I've lost track of where we are going with this discussion.
Feel free to make a formal proposal, but I don't know if
you will find sufficient interest for it to become a high
priority standardization issue.  It may be better to lead
by example in a case like this, that is, implement something
that you think others will want to emulate, and then
suggest it for standardization at some point.  Because
we are just talking about a pragma, which is presumably going
to be of an advisory nature in any case, it can progress
at its own rate as far as standardization, it doesn't need
to ride some kind of Ada 2005 train (though I'm not convinced
there will be any sort of thing).

****************************************************************

From: Robert A Duff
Sent: Monday, October 23, 2000 12:53 PM

> That's far too expensive, you don't want to pass a UC thunk for every
> case where a generic float parameter is involved.

But what else can you do, if you want to always-share, and you want UC
to work?

It seems to me the always-share model involves a LOT of thunk-izing, and
many of those thunks are necessarily very inefficient.  This isn't the
only case.  If you choose this model, you're necessarily making a big
trade-off for compile-time efficiency at the expense of run-time
efficiency.  Remember I'm talking *always* share, here.

By the way, the thunk-izing of float UC is worse than anyone's
mentioned: what about UC of an array of floats, or UC of access to array
of floats?

I do have a great deal of sympathy with the idea that the language ought
to make shared bodies feasible -- as illustrated by some of the
AARM quotes Dan Eilers posted.

****************************************************************

From: Dan Eilers
Sent: Monday, October 23, 2000 2:03 PM

Tuck wrote:
> > I don't think there is any way the "thunk" could in general know
> > whether its parameter was a 64-bit object declared within the generic,
> > or a 32-bit object declared outside the generic.  So it would be
> > impossible to do the "right thing".
>
> I obviously don't know how your compiler works, but I would
> certainly presume that the compiler knows whether it is
> dealing with a 32-bit object declared outside the generic,
> or a 64-bit object that is inside, and it would only generate
> a call on the thunk when it needed an "extra" conversion
> to be performed.

The way our compiler works, and the way I presume every compiler
works, there is never more than one flavor of a subprogram that
the compiler must choose between based on the location of its arguments.
If the unchecked_conversion function were itself passed as an
actual parameter to yet another shared generic, which flavor would
you pass, the one that expects 64-bit parameters or the one that
expects 32-bit parameters?

> I've lost track of where we are going with this discussion.
> Feel free to make a formal proposal, but I don't know if
> you will find sufficient interest for it to become a high
> priority standardization issue.  It may be better to lead
> by example in a case like this, that is, implement something
> that you think others will want to emulate, and then
> suggest it for standardization at some point.  Because
> we are just talking about a pragma, which is presumably going
> to be of an advisory nature in any case, it can progress
> at its own rate as far as standardization, it doesn't need
> to ride some kind of Ada 2005 train (though I'm not convinced
> there will be any sort of thing).

My proposal would probably _not_ be based on a pragma.
Instead, I would probably allow abstract generic units.
Such a unit could not be instantiated until it was made concrete,
and would not necessarily include a body.  It could be made concrete
by "constraining" formal parameters, and/or supplying a body,
where "constraining" includes restricting the allowable parameters
to a single class-wide type.

****************************************************************

From: Randy Brukardt
Sent: Monday, October 30, 2000 8:41 PM

This silliness has gone on long enough.

You cannot implement Ada 95 with that model. Period. I tried for years, but
gave it up some years ago, faced with too many examples that are
unimplementable.

You have to implement (universally) shared generics in Ada 95 with the model
that (almost) all objects are represented in the representation of the
actual type. (You can make an exception for stand-alone non-aliased objects
if you want; Janus/Ada does so only for for loop objects).

If you try the model of using the largest representation in the body of the
generic, you will be finding bugs forever.

If I remember right, the example that caused me to give it up looked
something like:

    generic
        type A_Float is digits <>;
        type An_Array_of_Float is array (Character) of A_Float;
        type A_Ptr_at_Array_of_Float is access all An_Array_of_Float;
    package My_Generic is
        My_Object : aliased An_Array_of_Float;
        type Another_Array_of_Float is array (Character) of A_Float;
        Another_Object : aliased Another_Array_of_Float;
        function Return_Ptr_at_Array return A_Ptr_at_Array_of_Float;
    end My_Generic;

    package body My_Generic is
        function Return_Ptr_at_Array return A_Ptr_at_Array_of_Float is
        begin
		if <Something> then
                return My_Object'Unchecked_Access;
		else
		    return Another_Object'Unchecked_Access;
		end if;
        end Return_Ptr_at_Array;
    end My_Generic;

If A_Float is always represented as a 64-bit float, an instantiation of this
with a 32-bit float type would make the array objects have 64-bit
components. But, outside of the generic, these components would be
referenced as 32-bit objects. Immediate death. You could thunk the generic
formal type somehow, but the local object and type could have been
implemented in the body, so you can't thunk it.

I wasn't able to find anyway around this that was worth bothering with. So I
changed to the model that these sorts of things are *allocated* as 64-bits,
but that the real representation is used. (This does mean that the
'Component_Size of such arrays is not static inside the generic body, but
that is not a major problem - it just means you have to use a multiply
always [no "shift" optimizations are possible]). (Note that this wasn't the
only problem by any means, it just was the last straw problem.)

If you're doing cluster sharing; then the problem doesn't arise: just don't
cluster types with different base type representations.

> > I've lost track of where we are going with this discussion.
> > Feel free to make a formal proposal, but I don't know if
> > you will find sufficient interest for it to become a high
> > priority standardization issue.  It may be better to lead
> > by example in a case like this, that is, implement something
> > that you think others will want to emulate, and then
> > suggest it for standardization at some point.  Because
> > we are just talking about a pragma, which is presumably going
> > to be of an advisory nature in any case, it can progress
> > at its own rate as far as standardization, it doesn't need
> > to ride some kind of Ada 2005 train (though I'm not convinced
> > there will be any sort of thing).
>
> My proposal would probably _not_ be based on a pragma.
> Instead, I would probably allow abstract generic units.
> Such a unit could not be instantiated until it was made concrete,
> and would not necessarily include a body.  It could be made concrete
> by "constraining" formal parameters, and/or supplying a body,
> where "constraining" includes restricting the allowable parameters
> to a single class-wide type.

I agree with Tucker in the sense that I don't see a proposal here, just a
long discussion about an implementation model that doesn't work. (It *did*
work in Ada 83, so some of us used it, and stuck to it long past the point
of sanity...)

Note that the only effect of not being able to use the "use the largest
rep." implementation is simply one of performance; it certainly does not
make it any harder to implement shared generics.

I could see some performance benefit to having pragmas/syntax to restrict
the instantiatably of generic parameters. However, I wonder if any users
would actually use something like:

    generic
        type A_Float is digits <>;
        for A_Float'Size use 32;
        ...

Anyway, as editor, I'm not sure what to do with this discussion. There
doesn't seem to be a question; the original issue is based on a
misconception of how shared generics are implemented. I'd like to save the
discussion, but there doesn't seem to be an AI at this point. It looks like
an amendment proposal would be in order.

****************************************************************

From: Dan Eilers
Sent: Wednesday, November 01, 2000 8:03 PM

Randy wrote:

> You cannot implement Ada 95 with that model. Period. I tried for years, but
> gave it up some years ago, faced with too many examples that are
> unimplementable.
>
> You have to implement (universally) shared generics in Ada 95 with the model
> that (almost) all objects are represented in the representation of the
> actual type. (You can make an exception for stand-alone non-aliased objects
> if you want; Janus/Ada does so only for for loop objects).
>
> If you try the model of using the largest representation in the body of the
> generic, you will be finding bugs forever.

There is of course absolutely no point in sharing a generic body if
the code in the shared body doesn't know what size objects it is
dealing with.  The resulting shared code would be laughable.

> If you're doing cluster sharing; then the problem doesn't arise: just don't
> cluster types with different base type representations.

We are in violent agreement here.  The key to practical shared generics
is that the compiler must not be expected to generate code that works
simultaneously with different sized objects.

I am suggesting that the user should have control in this area, rather
than hoping for the best from the compiler, for much the same reasons
that the user was given control in Ada95 with protected records, rather
than hoping that the compiler could figure out which tasks didn't
really need a thread of control.  The evidence has shown that compilers
can't generally be trusted to do a good job of automatic cluster analysis.

****************************************************************

Questions? Ask the ACAA Technical Agent