Version 1.3 of ai05s/ai05-0074-3.txt

Unformatted version of ai05s/ai05-0074-3.txt version 1.3
Other versions for file ai05s/ai05-0074-3.txt

!standard 12.5(3)          08-10-24 AI05-0074-3/00
!class Amendment 08-10-24
!status No Action (9-0-0) 10-02-27
!status work item 08-10-24
!status received 08-10-21
!priority Medium
!difficulty Hard
!subject Deferred instance freezing
!summary
!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.
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
The general idea is that for a package instance with an actual type that is not yet completely defined:
1) Fine-grained freezing is performed for the
expanded spec of the instance, as if the spec had been expanded by hand.
2) The elaboration of the instance body is deferred until
some point after the actual types are completely defined. Statically, the general freezing associated with the instance body is also deferred until this point.
3) The runtime check that the generic
body has been elaborated is performed when the instance body is elaborated, not when the instance spec is elaborated.
It seems to me that the generic ought to have some indication that the formal type is intended to be used in this way. Otherwise, a change such as, for example, adding
Null_Vector : constant Formal_Type_Array (1 .. 0 => <>);
to the private part of the generic could cause a previously-legal instance to be rejected. If it is intended that a formal type should be usable in this way, then that ought to be included as part of the contract and violations should be detected when compiling the generic, not the instance.
So today's approach is to define a pragma, May_Be_Partial, which applies to a formal private type (or to a formal derived type with a private extension) of a generic package. (Is there any justification for messing around at all with the rules for generic subprograms? I don't know of any.) Obviously the name of the pragma is subject to change but "May_Be_Partial" seems better than "Has_Polka_Dots" for today's discussion.
The only effect this pragma has when compiling a generic is to disallow uses of the type in the generic spec (including the private part) which would freeze the formal type or otherwise require that the formal type be completely defined.
This example would be illegal because of the pragma:
generic type T is private; pragma May_Be_Partial (T); package G is X : T; end G;
When compiling an instance, the pragma allows the corresponding actual type to be a type which is not yet completely defined (but not an incomplete type).
The (static) freezing and (dynamic) elaboration associated with the instance body occurs at the earliest point after the freezing/elaboration of the instance spec where all of the actual types of the instance are completely defined. This coincides with the existing static and dynamic semantics in all cases which are legal according to the existing rules (strictly speaking, in order to get this equivalence it would also be necessary to add an implementation permission to the effect that if an instance body is elaborated immediately after its spec, then it is ok to move the elaboration check ahead of the elaboration of the instance spec; this would only make a difference in the case where the check fails and no one cares about this case).
!wording
!discussion
Ada 2005 WORKAROUNDS
Here are some examples of how the problem could be addressed using existing Ada 2005 capabilities.
For the first example, making the instantiation a child unit solves the problem. However, this is annoying, because accessing the instance requires an extra with and instantiation (since children of generics must be generic):
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; ... private type Set is record ... end record; end Hashed_Sets;
generic package.Hashed_Sets.Signature is package The_Signature is new Set_Signature(Elem, Set); end Hashed_Sets.Signature;
A user of Hashed_Sets must with and instantiate Hashed_Sets.Signature in order to access the instance.
The second problem can also be solved with child units, using the limited with:
limited with Expressions.Sequences; package Expressions is type Expr_Ref is private;
type Seq_Of_Expr is access Expressions.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;
package Expressions.Sequences is package Expr_Sequences is new Sequences(Expr_Ref); type Sequences is new Expr_Sequences.Sequence; end Expressions.Sequences;
Here, besides the extra with clause, we need to declare an extra type simply so that the type is visible to the limited with clause (which operates purely syntactally). This means that extra type conversions are necessary.
Here is the generic signature example, using "end private;":
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; ...
private type Set is record ... end record; end private;
package Signature is new Set_Signature(Elem, Set);
end Hashed_Sets;
Here is an example where we want to instantiation a container:
package Expressions is type Expr_Ref is private;
type Expr_Seq; -- incomplete type type Seq_Of_Expr is access Expr_Seq;
function Operands(Expr : Expr_Ref) return Seq_Of_Expr;
...
private type Expression; -- completion deferred to body type Expr_Ref is access Expression; end private;
package Expr_Sequences is new Sequences(Expr_Ref); type Expr_Seq is new Expr_Sequences.Sequence; -- completion of incomplete type
end Expressions;
Here is the nested generic with a private extension:
package Constructs is type Root_Construct_Handle is abstract tagged private;
...
private type Root_Construct_Record; -- completed in pkg body type Root_Construct_Access is access all Root_Construct_Record;
type Root_Construct_Handle is abstract tagged record Construct : Root_Construct_Access; ... end record; end private;
generic type Data_Part is private; package Handles is type Construct_Handle is new Root_Construct_Handle with private; type RO_Access is access constant Data_Part; type RW_Access is access all Data_Part; function Get_RO_Access(Handle : Construct_Handle) return RO_Access; function Get_RW_Access(Handle : Construct_Handle) return RW_Access; private type Construct_Handle is new Root_Construct_Handle with ... -- ERROR: Parent type of record extension -- must be completely defined. end Handles;
end Constructs;
!ACATS test
ACATS B and C-Test(s) are necessary.
!appendix

[Editor's note: For earlier ideas on this topic, see AI95-359-1, AI95-359-2,
AI95-359-3, AI95-359-4, and AC-123, as well as the other alternatives.]

From: Steve Baird
Date: Tuesday, October 21, 2008  5:58 PM

At the risk of incurring Randy's wrath for bringing up old proposals that have
already been discarded, I want to revive the discussion of allowing

    type T is private;
    package I is new G (T);
  private
    type T is ... ;

in some cases. This is intended as an alternative to the post-private visible
part (aka "end private") proposal, which I believe is a far bigger change than
is warranted for the problem it is intended to solve.

Several variations on this approach have been explored in the various versions
of AI95-359 and in alternative #1 of AI05-74. See any of these AIs for s
description of the problem that both this proposal and the post-private visible
part proposal are intended to solve.

The general idea is that for a package instance with an actual type that is not
yet completely defined:

  1) Fine-grained freezing is performed for the
     expanded spec of the instance, as if the
     spec had been expanded by hand.

  2) The elaboration of the instance body is deferred until
     some point after the actual types are completely defined.
     Statically, the general freezing associated with the
     instance body is also deferred until this point.

  3) The runtime check that the generic
     body has been elaborated is performed when the
     instance body is elaborated, not when the instance
     spec is elaborated.

It seems to me that the generic ought to have some indication that the formal
type is intended to be used in this way. Otherwise, a change such as, for
example, adding
   Null_Vector : constant Formal_Type_Array (1 .. 0 => <>);
to the private part of the generic could cause a previously-legal instance to be
rejected. If it is intended that a formal type should be usable in this way,
then that ought to be included as part of the contract and violations should be
detected when compiling the generic, not the instance.

So today's approach is to define a pragma, May_Be_Partial, which applies to a
formal private type (or to a formal derived type with a private extension) of a
generic package. (Is there any justification for messing around at all with the
rules for generic subprograms? I don't know of any.) Obviously the name of the
pragma is subject to change but "May_Be_Partial" seems better than
"Has_Polka_Dots" for today's discussion.

The only effect this pragma has when compiling a generic is to disallow uses of
the type in the generic spec (including the private part) which would freeze the
formal type or otherwise require that the formal type be completely defined.

This example would be illegal because of the pragma:

   generic
     type T is private;
     pragma May_Be_Partial (T);
   package G is
     X : T;
   end G;

When compiling an instance, the pragma allows the corresponding actual type to
be a type which is not yet completely defined (but not an incomplete type).

The (static) freezing and (dynamic) elaboration associated with the instance
body occurs at the earliest point after the freezing/elaboration of the instance
spec where all of the actual types of the instance are completely defined. This
coincides with the existing static and dynamic semantics in all cases which are
legal according to the existing rules (strictly speaking, in order to get this
equivalence it would also be necessary to add an implementation permission to
the effect that if an instance body is elaborated immediately after its spec,
then it is ok to move the elaboration check ahead of the elaboration of the
instance spec; this would only make a difference in the case where the check
fails and no one cares about this case).

It can be viewed as either good or bad that this approach does not allow the
case where there is no pragma but there is also nothing in the generic package
spec that would preclude the pragma. This is good because, as mentioned above,
we don't want seemingly innocuous changes to, say, the private part of a generic
to cause an instance to become illegal. It is bad because it means that if the
generic package spec lacks the pragma for some type (e.g. consider the current
versions of the various container generics), then the instantiator is out of
luck.

This proposal therefore includes adding the pragma to the container generics
where possible and probably to other language-defined generic packages.

If it eased some implementation problems, a rule could certainly be added that
the point of the deferred freezing/elaboration must still occur within the same
immediately enclosing scope as the instance. This would disallow the following
example

   with G;
   pragma Elaborate_All (G);
   package Pkg is
     type T is private;

     package Nested is
        package I is new G (Formal_Type_With_The_New_Pragma => T);
     end Nested;
   private
     type T is ... ;
   end Pkg;

Alternatively, one could hair things up even further and defer instance body
elaboration into the body of the enclosing package in this case. It's not clear
whether this would be worth the added complexity.

One could certainly argue that there is little in this proposal that is new.
Associating the pragma with the formal type, not the instance, and thereby
strengthening the contract model is about the only idea here that has not been
proposed before.

Given that this general approach was explored some time ago and not adopted, why
is it worthy of discussion now? I think there was an assumption that "surely we
can come up with something better than this". Time has passed and, in my
opinion, we haven't. Instead, discussion seems to have focused on the
post-private visible part approach. I believe that this pragma is a better
solution to the problems that both proposals are trying to address.

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

From: Randy Brukardt
Date: Tuesday, October 21, 2008  6:18 PM

I object to discussing this now, because we have to finish ASIS first, and I
have too much ASIS work to do before the meeting to properly vet this proposal.
It might work, and it might not, and I don't want to be tossing FUD around about
whether or not it is implementable. (My initial reaction is that it would be
impossible to implement in Janus/Ada, but I have no facts to back that up.) And
this topic is very important to me, both from a usability and an
implementability perspective.

In any case, I will not be filing any of the mail on this topic before the
meeting (unless some major miracle in terms of time occurs), so it will not be
available at the meeting.

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

From: Ed Schonberg
Date: Tuesday, October 21, 2008  8:26 PM

> in some cases. This is intended as an alternative to the post-private
> visible part (aka "end private") proposal, which I believe is a far
> bigger change than is warranted for the problem it is intended to
> solve.

I will incur the same ire and say that at first reading I like this proposal and
would like to discuss it soon. However, we'll defer to Randy's overloaded
agenda, and assume that we won't have a chance to examine this in Portland.  In
any case this is worth reopening. When we last discussed this, Pascal and I were
adamant that changing freezing rules was an earthquake. I've changed my mind on
this, and will try to implement some version of deferred freezing to gauge the
impact on the compiler.

At first reading, my impression is that we want the restricted version: the
instance must appear in the same scope as that of the type, not in a nested
context.

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

From: Robert Dewar
Date: Tuesday, October 21, 2008  9:31 PM

> I will incur the same ire and say that at first reading I like this
> proposal

I agree that this proposal is attractive (and in my mind has higher priority
than ASIS work, which I am unconvinced will have any impact)

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

From: Steve Baird
Date: Tuesday, October 21, 2008  10:48 PM

> The (static) freezing and (dynamic) elaboration associated with the
> instance body occurs at the earliest point after the
> freezing/elaboration of the instance spec where all of the actual
> types of the instance are completely defined.

This isn't quite right, but the problem is easily correctable (although finding
the best wording to express it might be more challenging).

As written above, freezing might occur too early.
It might occur before a pending representation item that applies to an actual
type.

     package P is
       type T is private;
       package I is new G (T);
     private
       type T is ... ;

       -- don't want freezing to occur here

       for T'Some_Aspect use ... ;
     end P;

A somewhat stronger condition than "completely defined" is needed. "Freezable"
or "really truly completely defined" or somesuch. A type is freezable if it is
completely defined, all of its component types (if any) are freezable, and all
applicable operational and representation items have been applied.

It might also be possible to formulate a rule for when the instance is
elaborated in terms of the freezing points of the actual parameters, but care
would be needed to avoid circular definition problems.

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

From: Robert I. Eachus
Date: Wednesday, October 22, 2008  10:51 AM

I've been thinking about this proposal, and my inclination is that the freezing
rule needs to be simple.  If this makes some programs illegal where a compiler
could otherwise figure out where to do the freezing so be it.

So far, my best candidate is "if one or more parameters of a generic in a
package specification are of an incomplete or private type declared in the same
package specification, the generic shall be instantiated at the end of the
private part of the package, or at the first use of the name of the generic
instance, if earlier."

This would mean that renaming components of a generic package can become more
complex in some cases, but as far as I can see those cases are all illegal now.
The most painful case is where you want to initialize a variable of a type other
than a private type to a variable visible in the spec of a generic package.
(You need to do the initialization in the body of the package that declares the
private type, which can lead to uninitialized references to the variable during
elaboration.) But I don't see this case as real.  There will be many cases where
you want to shorten the name of a constant in a generic package.but deferred
constants work fine for that case.

The main question though, is does this solve the issue we are really trying to
solve?  As I see it, this works just fine for containers, but I'd rather try it
"for real" with a modified compiler.

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

From: Tucker Taft
Date: Wednesday, October 22, 2008  11:07 AM

I believe it is quite important that the instantiation can be followed
immediately by type derivations making the types defined by the instance visible
in the enclosing package.  Hence:

     package I is new G(T);
     type Coll_Of_T is new I.Coll [with null record];

I am concerned that this will force the freezing to happen right away anyway,
which defeats the purpose.

On other hand, deferring the instantiation to after the private part where T is
completely defined avoids this issue quite cleanly.

Other than philosophical concerns (with which I do sympathize), are there some
substantive *technical* problems that have been found with the post-private-part
visible declarations?  I feel that that proposal is still on the table, and
should be evaluated carefully before we give up and try to reincarnate other
older proposals.

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

From: Steve Baird
Date: Wednesday, October 22, 2008  1:05 PM

> I believe it is quite important that the instantiation can be followed
> immediately by type derivations making the types defined by the
> instance visible in the enclosing package.  Hence:
>
>      package I is new G(T);
>      type Coll_Of_T is new I.Coll [with null record];
>
> I am concerned that this will force the freezing to happen right away
> anyway, which defeats the purpose.
>
> On other hand, deferring the instantiation to after the private part
> where T is completely defined avoids this issue quite cleanly.
>

I agree that that is an advantage of the post-private visible part (ppvp)
solution. The problem goes away if a subtype is used instead of a derived type,
but then you don't get inherited subprograms. If you really want to make the
subprograms look as though they were declared in the scope enclosing the
instance, you would also have to add a bunch of subprogram renames. This
detracts from readability, is a maintenance issue, is cumbersome, etc. On the
other hand, the subtype does have some advantages if other types in the instance
refer to the given type. If, for example, the instance declares a type and then
a second type which includes the first type as a component type, then this
component relationship is not preserved if you declare two derived types. In
this case it may be more useful to declare two subtypes. Subtypes may also more
accurately reflect the intention of the programmer - if the derived type was
being introduced just to avoid requiring users to name the instance as opposed
to because there was really a desire for two distinct types.

> Other than philosophical concerns (with which I do sympathize), are
> there some substantive *technical* problems that have been found with
> the post-private-part visible declarations?

No. My objections to the ppvp proposal are not based on some convoluted scenario
which results in definitional problems (I am not sure that no such scenarios
exist, but that's just FUD).

I think:
  1) This is too big a change for the problem it is addressing,
     particularly given that a much more lightweight solution
     seems to be available.
  2) The solution is inelegant and detracts from readability.
  3) Even if this were a good idea for a language being designed
     from scratch, it's not a good idea to incorporate into Ada.

All of these are matters of opinion and taste on which reasonable people may
(and apparently do) disagree.

> I feel
> that that proposal is still on the table, and should be evaluated
> carefully before we give up and try to reincarnate other older
> proposals.


I completely agree that the post-private visible part solution is still on the
table. I'm proposing ("proposing" sounds so much better than "dredging up") an
alternative which I claim should also be considered.

Incidentally, I thought of a couple more points that need to be addressed in the
pragma-based alternative:

  1) A prefer-the-original-order-of-the-instances tie-breaker
     rule is needed to specify the the order in which the
     two instance bodies are elaborated in a case like

       package P is
         type T is private;
         package I1 is new G1 (T);
         package I2 is new G2 (T);
       private
         type T is ... ;
       end P;

  2) In the case of an instance of a generic which is itself
     exported from another instance, we want to elaborate the
     two instance bodies in the right order. In this example

       package P is
         type T is private;
         package I1 is new G1 (T);
         package I2 is new I1.G2;
       private
         type T is ... ;
       end P;

     we don't want to elaborate the body of I2 until after the
     body of I1 (elaborating I2's body before the elaboration
     of the body of I1.G2 leads to an elaboration check failure).
     Thus, the elaboration of I2's body needs to be deferred even
     though G1.G2 has no formal parameters.

I concede that wrinkles like this do not do anything to improve the
attractiveness of this proposal.

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

From: Ed Schonberg
Date: Wednesday, October 22, 2008  2:12 PM

> I've been thinking about this proposal, and my inclination is that the
> freezing rule needs to be simple.

Commendable goal, but about 10 years too late...  However I think that Steve's
rules can probably reduced to a simple formulation:

      the freezing of an entity declared in an instance freezes the instance.

This takes care of successive instances that depend on each other.   In the
simplest case (pure packages) it means that instance bodies will be elaborated
at the end of the private part, as you suggest.

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

From: Randy Brukardt
Date: Wednesday, October 21, 2008  6:49 PM

> I agree that this proposal is attractive (and in my mind has higher
> priority than ASIS work, which I am unconvinced will have any impact)

You're probably right about the impact, but it is way to late to argue with
priorities set by WG 9 long ago. In any case, we've promised to deliver a
finished ASIS standard by the June WG 9 meeting, and that will have the effect
of freeing up the resources to work on things that are certainly more
interesting. That is, the sooner we get done with ASIS, the sooner we can move
on to other things.

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

From: Dan Eilers
Date: Wednesday, October 22, 2008  8:51 PM

> I believe it is quite important that the instantiation can be followed
> immediately by type derivations making the types defined by the
> instance visible in the enclosing package.  Hence:
>
>      package I is new G(T);
>      type Coll_Of_T is new I.Coll [with null record];
>
> I am concerned that this will force the freezing to happen right away
> anyway, which defeats the purpose.

There is some discussion in AI95-00391 about possibly adding new syntax to
directly support this idiom.  Maybe such new syntax would be helpful with regard
to freezing as well.

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

[Editor's note: Part of the thread starting June 26, 2009 at
8:45 AM in AI-135 discusses this proposal.]

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

Questions? Ask the ACAA Technical Agent