Version 1.2 of ais/ai-00359.txt

Unformatted version of ais/ai-00359.txt version 1.2
Other versions for file ais/ai-00359.txt

!standard 12.03 (12)          03-09-29 AI95-00359/02
!standard 12.03 (20)
!standard 13.14 (05)
!class amendment 03-07-22
!status work item 03-09-29
!status received no action 03-07-22
!status received 03-04-14
!priority Low
!difficulty Medium
!subject Deferring Freezing of a Generic Instantiation
!summary
To better support generic signature packages, and mutually dependent types that involve generic instantiations, it is proposed that a generic instantiation not cause freezing immediately if any of its actual parameters are types that have not been completely defined.
For such an instantiation, no special freezing happens at the point of the instantiation, other than the freezing that is due to the elaboration of the declarations within the "spec" of the instantiation. Elaboration of the body of the instantiation is deferred until a "general" freezing point occurs, which occurs at the end of the enclosing library unit or declarative part, upon encountering a "real" body, etc.
NOTE: This more "relaxed" freezing and deferred body elaboration could be used for all generic instantiations, but that could create some incompatibilities, since we would be altering the point when the body of the instantiation was elaborated. This proposal is guaranteed to be upward compatible, since only instantiations that are currently illegal would be using "relaxed" freezing and deferred body elaboration.
!problem
Ada 95 provides formal package parameters. One way of using these parameters is to define a "signature" for a class of abstractions, such as all set abstractions, or all physical unit abstractions, and then build a new generic abstraction on top of the original class of abstractions using this signature as the template for a formal package parameter.
Unfortunately, it is difficult to use signatures because of the fact that an instantiation freezes all of its actual parameters.
For example:
Given the signature for a set abstraction:
generic type Element is private; type Set is private; with function Size(Of_Set : Set) return Natural is <>; with function Union(Left, Right : Set) return Set is <>; with function Intersection(Left, Right : Set) return Set is <>; with function Empty return Set is <>; with function Unit_Set(With_Item : Element) return Set is <>; with function Nth_Element(Of_Set : Set) return Element is <>; package Set_Signature is end;
... we could define a generic that required some set abstraction, but it didn't care which one so long as it implemented the above signature:
generic with package Base_Set is new Set_Signature(<>); package Layered_Abstraction is type Cool_Type(Set : access Base_Set.Set) is limited_private; procedure Massage(CT : in out Cool_Type; New_Set : Base_Set.Set); ...
end Layered_Abstraction;
Now if we want to define a set type and provide the pre-instantiated signature for it, we run into trouble:
generic type Elem is private; with function Hash(El : Elem) return Integer; package Hashed_Sets is type Set is private; function Union(Left, Right : Set) return Set;
...
package Signature is new Set_Signature(Elem, Set); private type Set is record
... end record; end Hashed_Sets;
The problem is that we can't do the instantiation of Set_Signature where we would want to do so, because the instantiation freezes the type "Set" prematurely.
[For an extended example of use of signatures, see the physical units AI (AI-00324).]
A similar problem occurs when a type wants to include a pointer to a container based on the type being defined. For example:
package Expressions is type Expr_Ref is private;
package Expr_Sequences is new Sequences(Expr_Ref); -- Freezing trouble here! type Seq_Of_Expr is access Expr_Sequences.Sequence;
function Operands(Expr : Expr_Ref) return Seq_Of_Expr;
...
private type Expression; -- completion deferred to body type Expr_Ref is access Expression;
end Expressions;
Here we have a case where we want to instantiate a generic using a private type, and use the results of the instantiation as the designated type of an access type, which is in turn used as a parameter or result type of an operation on the private type.
Unfortunately, we can't instantiate the "Sequences" generic with Expr_Ref, since it is private.
!proposal
(See summary.)
!wording
Change paragraph 12.3(12) as follows:
A generic_instantiation declares an instance; it is equivalent to the instance declaration (a package_declaration or subprogram_declaration) followed [immediately] by the instance body[, both at the place of the instantiation]. {The instance declaration is located at the place of the instantiation. The instance body is located immediately following the instance declaration if none of the actual parameters denote types that are not yet completely defined. If one of the actual parameters denotes a type not completely defined, the location of the instance body is immediately prior to the next non-instance body, or the end of the nearest enclosing declarative_part or library_item.}
Change paragraph 12.3(20) as follows:
... Finally, the instance declaration [and body are] {is} elaborated. {The instance body is elaborated either immediately following the instance declaration, or deferred until the next non-instance body or end of the enclosing declarative_part or library_item if there are any actuals that denote types that are not yet completely defined.}
Change paragraph 13.14(5) as follows:
* The occurrence of a generic_instantation causes freezing {except when one of the actual parameters denotes a type that is not yet completely defined}; also, if a parameter of [the] {an} instantiation {that causes freezing} is defaulted, the default_expression or default_name for that parameter causes freezing. {For an instantiation that does not cause freezing, the constructs of the instance declaration cause freezing according to the rules of this clause. The elaboration of the instance body is deferred until the end of an enclosing construct or a non-instance body which would cause freezing of all enclosed or prior declarations.}
!example
(See problem.)
!discussion
Signature packages can be a very useful feature, but if they can't be instantiated in the generic that defines the abstraction, they become of much less use.
Generics in general can be very useful, but the freezing rules mean that they are not as powerful as cut-and-paste, since they can't be applied to private types before the private type is completely defined.
This proposal makes it possible for a generic instantiation to be used in more places than before, since it can be used with a private type before the type is completely defined. As things stand now, it is often necessary to completely restructure things to be able to use a generic container as part of defining a private type.
--!corrigendum 13.14(05)
!ACATS test
An ACATS test should be created for this pragma.
!summary
!appendix

From: Tucker Taft
Sent: Wednesday, February 12, 2003  5:50 PM

I talked about this AI a bit with Pascal in Padua.
Here is a first cut at it.  The basic idea is to
relax the freezing rules associated with generic
instantiations, so signatures can actually be used
in a reasonable way.

---

!standard 13.14     (05)           03-02-12  AI95-<<melting_instantiations>>/01
!class amendment 03-02-12
!status work item 03-02-12
!status received 03-02-12
!priority Medium
!difficulty Medium
!subject Deferring Freezing of a Generic Instantiation

!summary

To better support generic signature packages, and
mutually dependent types that involve generic instantiations,
it is proposed that a generic instantiation not cause
freezing immediately if any of its actual parameters
are types that have not been completely defined.

For such an instantiation, no special freezing happens
at the point of the instantiation, other than the freezing
that is due to the elaboration of the declarations within
the "spec" of the instantiation.   Elaboration of the body
of the instantiation is deferred until a "general" freezing
point occurs, which occurs at the end of the enclosing
library unit or declarative part, upon encountering a "real" body, etc.

NOTE: This more "relaxed" freezing and deferred body elaboration
could be used for all generic instantiations, but that could
create some incompatibilities, since we would be altering
the point when the body of the instantiation was elaborated.
This proposal is guaranteed to be upward compatible, since
only instantiations that are currently illegal would be
using "relaxed" freezing and deferred body elaboration.

!problem

Ada 95 provides formal package parameters.  One way of using
these parameters is to define a "signature" for a class of abstractions,
such as all set abstractions, or all physical unit abstractions, and
then build a new generic abstraction on top of the original
class of abstractions using this signature as the template for
a formal package parameter.

Unfortunately, it is difficult to use signatures because
of the fact that an instantiation freezes all of its
actual parameters.

For example:

  Given the signature for a set abstraction:

    generic
	type Element is private;
	type Set is private;
	with function Size(Of_Set : Set) return Natural is <>;
	with function Union(Left, Right : Set) return Set is <>;
	with function Intersection(Left, Right : Set) return Set is <>;
	with function Empty return Set is <>;
	with function Unit_Set(With_Item : Element) return Set is <>;
	with function Nth_Element(Of_Set : Set) return Element is <>;
    package Set_Signature is end;

  ... we could define a generic that required some set
  abstraction, but it didn't care which one so long
  as it implemented the above signature:

    generic
	with package Base_Set is new Set_Signature(<>);
    package Layered_Abstraction is
	type Cool_Type(Set : access Base_Set.Set) is limited_private;
	procedure Massage(CT : in out Cool_Type; New_Set : Base_Set.Set);
        ...

    end Layered_Abstraction;

  Now if we want to define a set type and provide the pre-instantiated
  signature for it, we run into trouble:

    generic
	type Elem is private;
	with function Hash(El : Elem) return Integer;
    package Hashed_Sets is
	type Set is private;
	function Union(Left, Right : Set) return Set;
	...

	package Signature is new Set_Signature(Elem, Set);
    private
	type Set is record
	   ...
	end record;
    end Hashed_Sets;

The problem is that we can't do the instantiation of Set_Signature
where we would want to do so, because the instantiation freezes
the type "Set" prematurely.

[For an extended example of use of signatures, see the physical
units AI (AI-00324).]

A similar problem occurs when a type wants to include a pointer
to a container based on the type being defined.  For example:

    package Expressions is
	type Expr_Ref is private;

	package Expr_Sequences is new Sequences(Expr_Ref);
	    -- Freezing trouble here!
	type Seq_Of_Expr is access Expr_Sequences.Sequence;

	function Operands(Expr : Expr_Ref) return Seq_Of_Expr;

	...

   private
	type Expression;  -- completion deferred to body
	type Expr_Ref is access Expression;

   end Expressions;

Here we have a case where we want to instantiate a generic
using a private type, and use the results of the instantiation
as the designated type of an access type, which is in turn
used as a parameter or result type of an operation on the
private type.

Unfortunately, we can't instantiate the "Sequences" generic
with Expr_Ref, since it is private.

!proposal

(See summary.)

!wording

(See summary.)

!example

(See problem.)

!discussion

Signature packages can be a very useful feature, but
if they can't be instantiated in the generic that defines
the abstraction, they become of much less use.

Generics in general can be very useful, but the freezing
rules mean that they are not as powerful as cut-and-paste,
since they can't be applied to private types before
the private type is completely defined.

This proposal makes it possible for a generic instantiation
to be used in more places than before, since it can
be used with a private type before the type is completely
defined.  As things stand now, it is often necessary to
completely restructure things to be able to use a generic
container as part of defining a private type.

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

From: Robert A Duff
Sent: Wednesday, February 12, 2003  7:09 PM

As a user of Ada, I would find this relaxation of the freezing rules to
be of *huge* benefit.

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

From: Tucker Taft
Sent: Sunday, September 28, 2003  4:24 PM

Here is an update to an AI that never made
it into the AI database.  (I think the editor might
be doing some editorializing ... ;-).
Basically, I added wording.

Personally, I think this is an important AI,
because it enables an important use of generic
signatures on private types, but also makes
generics more flexible in general.

[Editor's note: This is version /02 of the AI.]

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

From: Pascal Leroy
Sent: Sunday, September 28, 2003  4:24 PM

If you look at the procedures, you'll see that "if the Editor, in
consultation with the Rapporteur, determines that a comment ...  is of
interest to only a tiny minority of users, the commentary is given a
status of Received No Action".  This is what happened to your previous
submission on this topic, and it was filed as AC95-00060/01.  The
procedures specify that, to resurrect this proposal from the dead, it
must have the support from two ARG members.  So you need to find someone
else who is excited about mucking with the freezing rules.

I am not trying to make a nuisance of myself, but as we are nearing the
deadline for adding new stuff to the Amendment, I am going to insist
that we go by the book: there is no point in spending precious ARG time
on proposals that don't have a modicum of support from the group.

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

From: Tucker Taft
Sent: Monday, September 29, 2003  7:16 AM

Well if I remember correctly, Bob Duff
said "attaboy!" when I submitted this proposal.
So I only need one more ;-).

(I promise I didn't intend to violate procedures,
but I was unaware that it had been classified
as "no action."  I thought that was reserved for
proposals that clearly had little merit.  I had the
sense that mine was a bit above that level, but
apparently not...)

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

From: Tucker Taft
Sent: Monday, September 29, 2003  2:39 PM

As I said Bob Duff I believe expressed support for this proposal.
Is that enough, or do you want another?  If so, anyone out there
interested in making generics more useful by relaxing these
freezing rules?  Please speak up now!

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

From: Robert A. Duff
Sent: Monday, September 29, 2003  3:37 PM

> As I said Bob Duff I believe expressed support for this proposal.
> Is that enough, or do you want another?  If so, anyone out there
> interested in making generics more useful by relaxing these
> freezing rules?  Please speak up now!

Yes, I do support this.

Put your user hats on, please, and take off your implementer and
language lawyer hats.  This is one of the most frustrating parts of Ada.

I want to write "package P is new G(T);" in the same package as T.
But that's illegal.  So a huge amount of restructuring is required.

Quite often, "G" is some sort of "growable sequence of T", or whatever,
and T *contains* such a sequence.  So it's no good to put P in a child.
Type T *needs* visibility upon the instance, P.

Note that if "sequence of T" happened to be "array of T", all would be
well.  But surely, replacing "array of T" with "Growable_Seq_Of_T"
should not require such major restructuring of the code.

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

From: Gary Dismukes
Sent: Monday, September 29, 2003  3:44 PM

I'll add my second.  I agree this is worth discussing.

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

From: Randy Brukardt
Sent: Monday, September 29, 2003  5:45 PM

> I want to write "package P is new G(T);" in the same package as T.
> But that's illegal.  So a huge amount of restructuring is required.

Tweet!!! Excessive use of generics! 15 yard penalty from the spot of the
foul!

(Sorry, it's football season. :-)

No, that has never, ever happened to me as an Ada user. OK, I can see how it
could happen with some models. But I think you're overstating the likelihood
of this case in practice. This is just like the 'problem' discussed in AARM
13.14(19.q-s), in which the premise is faulty (it's not important, no one
writes code like that), which of course leads to faulty rules which are
unnecessarily hard to implement.

But, merits of the problem aside, does it bother others (like it does me)
that the proposed 'solution' is to change the freezing and elaboration rules
of the language in order to 'fix' what is essentially a visibility problem?
What Bob needs is a partial view of a generic to go along with partially
viewed type.

This proposal has two serious technical problems:

1) Changing some unrelated type far away from an instantiation silently
changes the semantics of the instantiation. A program can start failing with
Program_Error simply because a type was changed to be a private type.

2) The changes to the elaboration model of instantiations are substantial.
Ada 83 is carefully designed so that once an instantiation is elaborated, no
elaboration checks are needed on the use of anything in that instantiation.
Changing that will have gigantic effects all over compilers - most of the
elaboration assumptions will be invalid. (I wonder what this would do to the
GNAT static elaboration model?)

And then there is freezing and generics. This is a dead body issue for me -
relaxing the freezing rules is simply impossible: we're generating the code
for a generic at the point that it is seen.

So, I'll be bringing an extra shoe along to the meeting (I don't want to
cause anyone to pass out by taking mine off).

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

From: Randy Brukardt
Sent: Monday, September 29, 2003  8:59 PM

Here's part of a note that I sent to Pascal when we were discussing what to do
with this proposal:

----

Anyway, it occurs to me that the main problem could be solved with an
"incomplete" instantiation. To show Tucker's original example:

    generic
        type Elem is private;
        with function Hash(El : Elem) return Integer;
    package Hashed_Sets is
        type Set is private;
        function Union(Left, Right : Set) return Set;
        ...
        incomplete package Signature is new Set_Signature(Elem, Set);
    private
        type Set is record
           ...
        end record;
        package Signature is new Set_Signature(Elem, Set);
    end Hashed_Sets;

(Syntax to be chosen.) This would make the instantiation available anywhere
after it is completed (which would include all external users), but nothing
from it could be used until that point. (We could go further and export
incomplete types or something like that, which would fix Tucker's second
example, but I don't think that complication is really necessary.)

The point is to allow an instantiation that has to be elaborated in the private
part still be to visible; it also makes the deferred elaboration crystal clear.
(Of course, it isn't really deferred.)

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


Questions? Ask the ACAA Technical Agent