Version 1.1 of ai05s/ai05-0011-1.txt

Unformatted version of ai05s/ai05-0011-1.txt version 1.1
Other versions for file ai05s/ai05-0011-1.txt

!standard 4.1(2)          06-03-27 AI05-0011-1/01
!standard 4.7(0)
!class Amendment 06-03-27
!status work item 06-03-27
!status received 06-03-19
!priority Medium
!difficulty Hard
!subject Recursive types and generic instantiations
!summary
(See proposal.)
!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
!wording
!discussion
Ada 2005 provides solutions to these problems, but they are not ideal.
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 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.
!example
!ACATS test
!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.]

From: Tucker Taft
Date: Sunday, March 19, 2006  6:57 AM

As many of you know, my one main regret about the Ada 2005
process is that we never could figure out a way to allow
instantiations using a private type prior to it being
completely defined.  Making generic "signatures" useful was
one reason, but there are others.  One of Randy's was to
include in a package various instantiations of useful container
generics.  I have been searching for various alternative
ways of accomplishing this.  One I have mentioned before
is the idea of a "not private" or "end private" syntax that
would allow a package to have a visible part that followed
the private part.  Here is yet another alternative.

If one of the goals is to ensure that when one instantiates a generic
library unit one gets visibility on certain nested instantiations
as well, this might be accomplished by a combination of two
features:

   1) allowing children of generics to be instantiations
      rather than generics; the actual parameters of the
      instantiations could be entities declared
      within the formal part or visible part of the parent
      generic G.  Within the scope of a with clause for the
      child of the generic, any instantiation of the generic
      will create a child of the instantiation with the same name.
      E.g.:

      generic
         type Real is digits <>;
      package Generic_Complex_Types is
         type Complex is private;
         ...
      end Generic_Complex_Types;

      with Ada.Containers.Vectors;
      package Generic_Complex_Types.Vectors is
        new Ada.Containers.Vectors(
          Index_Type => Positive; Element_Type => Complex);

      with Generic_Complex_Types.Vectors;
      package My_Complex is new Generic_Complex_Types(My_Float);
         -- Creates a child "My_Complex.Vectors" that is
         -- an instantiation of Ada.Containers.Vectors

   2) allow a library unit to specify particular children as
      being implicitly "with"ed whenever the library unit is
      with'ed.  This would allow implementations to compile
      portions of a standard spec as separate library units
      (something I believe GNAT already does for parts of
      Text_IO), but the client only has to use one "with"
      clause to get them all.  A possible syntax might be:

      package Ada.Text_IO is
         ...
      end Ada.Text_IO and
        with Ada.Text_IO.Float_IO, Ada.Text_IO.Integer_IO;

      That is, "and with <child-unit>" would be an indication
      that certain children of the library unit are
      implicitly "with"ed whenever the library unit is with'ed.
      ("With"ing them explicitly would probably be disallowed.)

The combined effect of the above two capabilities would provide
for "preinstantiations" of generics without running afoul of the
private type freezing rules, while also standardizing a capability
for breaking package specs into separately compilable pieces if
there are advantages to doing so.

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

From: Randy Brukardt
Date: Wednesday, March 22, 2006  8:57 PM

>... One of Randy's was to
> include in a package various instantiations of useful container
> generics.

"visible package specification", to be clear.

>... I have been searching for various alternative
> ways of accomplishing this.  One I have mentioned before
> is the idea of a "not private" or "end private" syntax that
> would allow a package to have a visible part that followed
> the private part.  Here is yet another alternative.
>
> If one of the goals is to ensure that when one instantiates a generic
> library unit one gets visibility on certain nested instantiations
> as well, this might be accomplished by a combination of two
> features:
>
>    1) allowing children of generics to be instantiations
>       rather than generics;

I think for maximum impact, you should have put these in the other order.
The generic case is less interesting, and the mere thought of children of
generics makes me ill. I nearly didn't read the second part...

...
>    2) allow a library unit to specify particular children as
>       being implicitly "with"ed whenever the library unit is
>       with'ed.  This would allow implementations to compile
>       portions of a standard spec as separate library units
>       (something I believe GNAT already does for parts of
>       Text_IO), but the client only has to use one "with"
>       clause to get them all.  A possible syntax might be:

This seems like a useful idea irrespective of the generic instantiation of
a private type problem. Where was it two years ago?? :-)

I'm a bit dubious that there needs to be a separate, different, solution for
generics in this case. It seems at first blush that this idea can be made to
work for all packages. (And that would be preferable so that converting from
a regular package to a generic is as easy as possible...) I suppose it might
be necessary to work with the existing abomination...

I guess I'd like to see a full write-up of this idea, but off-hand I don't
see any gotchas that we don't already have because of normal children.

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

From: Pascal Leroy
Date: Thursday, March 23, 2006  7:47 AM

> If one of the goals is to ensure that when one instantiates a 
> generic library unit one gets visibility on certain nested 
> instantiations as well...

I am not sure that I can get too excited about this goal.  More later.

>    1) allowing children of generics to be instantiations
>       rather than generics;

That sounds like a great idea.  I think it would be generally useful,
regardless of the business of instantiations-with-private-types.  (Unlike
Randy, I don't have any mystic opposition to children of generics.)

>    2) allow a library unit to specify particular children as
>       being implicitly "with"ed whenever the library unit is
>       with'ed.

I really don't like the notion of a library unit having to name its
children in one way or another.  It kills extensibility, and it reminds me
of the awful idea of the  incomplete-type-completed-in-a-child.  On the
other hand, I could see the advantage of a child being able to specify
that it wants to be automatically withed when its parent is withed.  But
there might be implementation trouble there, and possibly language
definition trouble too.

--

The problem *I* was interested in solving is that of a type that wants to
include a pointer to a container based on the type being defined.  Here is
the canonical example:

	package P is
	   type T is private;
	private
	   package T_Vectors is new Vectors (T); -- Oops, freezes T.
	   type T is
	      record
	         V : access T_Vectors.Vector;
	      end record;
	end P;

Now I believe that you can actually do this in Ada 2005, although it is
awkward and requires contortions:

	limited private with P.Vectors;
	package P is
	   type T is private;
	private
	   type T is
	      record
	         V : access P.Vectors.Vector;
	      end record;
	end P;

	private package P.Vectors is
	   package T_Vectors is new Vectors (T);
	   type Vector is new T_Vectors.Vector;
	end P.Vectors;

I remember that when we were working on AI 359, Randy kept telling us that
we should be using limited views somehow.  It seems to me that if we could
find some sort of syntactic sugar to provide essentially the semantics of
the above code fragment without the awkwardness, we would be closer to a
solution.

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

From: Tucker Taft
Date: Thursday, March 23, 2006  9:37 AM

...
> I really don't like the notion of a library unit having to name its
> children in one way or another.  It kills extensibility, ...

It doesn't *have* to name its children.  The point is that these are
defined to be *nested* packages, but we are providing a way to compile
nested package specs separately.  I suppose we could just use the
"is separate" syntax on a package spec.  I was trying to piggy-back
on the idea of child units to define a separately compilable
nested package.  But perhaps it is better to piggy-back on subunits
(though I admit I am more a "fan" of child units than subunits).  Hence:

     package Ada.Text_IO is ...
         generic package Float_IO is separate;
         ...
     end Ada.Text_IO;

     separate(Ada.Text_IO);
     generic
        ...
     package Float_IO is
        ...
     end Float_IO;

Independent of where the package spec stub is, presumably
the spec actually operates more like a child, in that it
conceptually comes after the completion of any private types
of the parent type, so it could contain freezing occurrences.

Whether you would also need a stub for the package body is an
interesting question.  You probably want to have one so
the package body can see the innards of the parent's body.
But perhaps the body stub would be optional?

...
> I remember that when we were working on AI 359, Randy kept telling us that
> we should be using limited views somehow.  It seems to me that if we could
> find some sort of syntactic sugar to provide essentially the semantics of
> the above code fragment without the awkwardness, we would be closer to a
> solution.

I think one issue was that the view was only limited within the
spec itself, but it was a full view outside, so using "limited"
in the visible declaration was misleading, since there was nothing
limited about it from the client's perspective.  Recently I was
thinking about what other reserved word could be used instead
of "limited" and I came up with:

     delay package T_Vectors is new Vectors(T);

This would effectively delay the actual elaboration of the
instantiation to the end of the enclosing package spec,
but make a limited view visible in the interim.
 From the outside a full view of the instantiation is provided.

Of course what Bob and I were hoping for was an ability to
use T_Vectors.Vector directly, without a level of indirection.
But that seemed to break privacy, along with create some
real implementation complexities.

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

From: Robert A. Duff
Date: Thursday, March 23, 2006 11:47 AM

One way to judge potential solutions to this problem is to consider that
Vectors are analogous to arrays.  Whatever you can do with arrays,
you ought to be able to do with Vectors (or other generic data structures).

Imagine this conversation:

    Java (or Lisp or C# or...) zealot: I have this:

        package P is
            type T is private;
            type T_Sequence is array(Positive range <>) of T;
        private
            ...
        end P;

    Ada sucks because it doesn't have unbounded growable arrays.

    Ada zealot: Ada doesn't NEED growable arrays built in, because it's an
    extensible language.  Just write a generic package.  In fact, in Ada 2005
    you will find such a package in the standard library.

    Java zealot: OK, please show me how to make T_Sequence growable.

    Ada zealot: Well, you have to instantiate Vectors, move T_Sequence into a
    child, add a level of indirection (and therefore manage heap data), stand
    on your ear, and spit nickels.  There are good reasons, but only language
    lawyers can understand them.

    Java zealot: You gotstobe kidding!

----

With an array, we can choose to make the array public or private.  If we want
an array of T'Class, we are forced to use an array-of-access-to-T'Class
instead.  We can choose to make that access type public or private.  We can
choose to make the array part of the same abstraction, or make it a separate
abstraction in its own (child?) package.  We can choose to have T recursively
contain an access-to-array-of-T, or an array-of-access-to-T'Class, or an
access-to-array-of-access-to-T'Class (but T cannot contain an array-of-T, nor
an array-of-T'Class).

My point is that if we replace "array" with "Vector", the programmer should
retain all of the same choices.  The choices should be chosen based on the
natural structure of the application, rather than silly language
restrictions.

Ada requires "access" for T'Class.  It also requires "access" for recursive
data structures.  If you have both, you can usually get away with just one
access type, because you have some choice in where to put the indirection.

...
> Now I believe that you can actually do this in Ada 2005, although it is
> awkward and requires contortions:
> 
> 	limited private with P.Vectors;
> 	package P is
> 	   type T is private;
> 	private
> 	   type T is
> 	      record
> 	         V : access P.Vectors.Vector;
> 	      end record;
> 	end P;
> 
> 	private package P.Vectors is
> 	   package T_Vectors is new Vectors (T);
> 	   type Vector is new T_Vectors.Vector;
> 	end P.Vectors;

Cool.  I hadn't realized this would work.  But what if I want a Vector of
T'Class objects?  Equivalently, what if T has a discriminant (no default)?

	limited private with P.Vectors;
	package P is
	   type T is tagged private;
	private
           type T_Ref is access all T'Class;
	   type T is
	      record
	         V : P.Vectors.Vector; -- No "access" here.  Illegal!
	      end record;
	end P;

	private package P.Vectors is
	   package T_Vectors is new Vectors (T_Ref);
	   type Vector is new T_Vectors.Vector;
	end P.Vectors;

Is there a clean way to do that without TWO levels of indirection (one for
T'Class, and one for the incomplete view of the vector type)?
I don't count the level of indirection inside Vectors itself,
because that's invisible (client need not worry about heap
management).

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

From: Randy Brukardt
Date: Thursday, March 23, 2006  1:42 PM

...
> Cool.  I hadn't realized this would work.  But what if I want a Vector of
> T'Class objects?  Equivalently, what if T has a discriminant (no default)?

You don't need a separate indirection for them, just for the vector.
(Because the vector has that built-in.

> 	limited private with P.Vectors;
> 	package P is
> 	   type T is tagged private;
> 	private
>            type T_Ref is access all T'Class;

You usually don't need this; certainly not for the vector. You only need it
for the built-in data structures.

> 	   type T is
> 	      record
> 	         V : P.Vectors.Vector; -- No "access" here.  Illegal!

Right, and this is a good thing. You want the indirection here and here
alone.

> 	      end record;
> 	end P;
>
> 	private package P.Vectors is
> 	   package T_Vectors is new Vectors (T_Ref);

Use Indefinite_Vectors and T'Class directly:

         package T_Vectors is new Indefinite_Vectors (T'Class);

which lets the container manage the indirection.

> 	   type Vector is new T_Vectors.Vector;
> 	end P.Vectors;
>
> Is there a clean way to do that without TWO levels of indirection (one for
> T'Class, and one for the incomplete view of the vector type)?
> I don't count the level of indirection inside Vectors itself,
> because that's invisible (client need not worry about heap
> management).

But you should, because that level of indirection eliminates the need for an
explicit indirection for T'Class. (Yes, there is one inside the
implementation of Indefinite_Vectors, but as you said, I don't count that
because its invisible.)

(Indeed, I think that types like T_Ref usually should be anonymous in Ada
2005, because they're not fundamental to the abstraction; rather they are
implementation artifacts to be hidden as much as possible.)

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

From: Randy Brukardt
Date: Thursday, March 23, 2006  1:54 PM

...
> > I really don't like the notion of a library unit having to name its
> > children in one way or another.  It kills extensibility, ...
>
> It doesn't *have* to name its children.  The point is that these are
> defined to be *nested* packages, but we are providing a way to compile
> nested package specs separately.

Right, and it's piggybacking on the semantics for children (which are
logically present at the end of the specification anyway).

In any case, this is optional, and it surely wouldn't "kill extensibility"
as you'd never be required to use it.

> I suppose we could just use the
> "is separate" syntax on a package spec.  I was trying to piggy-back
> on the idea of child units to define a separately compliable
> nested package.  But perhaps it is better to piggy-back on subunits
> (though I admit I am more a "fan" of child units than subunits).

Me too, and the mapping is much cleaner.

> Hence:
>
>      package Ada.Text_IO is ...
>          generic package Float_IO is separate;
>          ...
>      end Ada.Text_IO;
>
>      separate(Ada.Text_IO);
>      generic
>         ...
>      package Float_IO is
>         ...
>      end Float_IO;
>
> Independent of where the package spec stub is, presumably
> the spec actually operates more like a child, in that it
> conceptually comes after the completion of any private types
> of the parent type, so it could contain freezing occurrences.

That's why this idea is far more complex. You have different visibility
and freezing for this than you do for other subunits.

> Whether you would also need a stub for the package body is an
> interesting question.  You probably want to have one so
> the package body can see the innards of the parent's body.
> But perhaps the body stub would be optional?

Yes, even more complexity and problems. Let's not go there.

...
> I think one issue was that the view was only limited within the
> spec itself, but it was a full view outside, so using "limited"
> in the visible declaration was misleading, since there was nothing
> limited about it from the client's perspective.

Right. We need a reserved word that disappears when you are a client. :-)
Sort of like those variable inks that they use in money these days.

> Recently I was
> thinking about what other reserved word could be used instead
> of "limited" and I came up with:
>
>      delay package T_Vectors is new Vectors(T);
>
> This would effectively delay the actual elaboration of the
> instantiation to the end of the enclosing package spec,
> but make a limited view visible in the interim.

Please, lets not start this baloney about "delaying" elaboration again.
That's *not* a way that this can be modeled. It has to be modeled more like
a "forward" declaration, with an explicit completion somewhere. After all,
the items in a specification are just specs for the most part; the fact that
an instantiation includes a body is what causes the trouble.

>  From the outside a full view of the instantiation is provided.

Right, like any other specification.

What we really want is something like:

     package T_Vectors is new Vectors(T) and will be completed later;

but I can't think of a sequence of reserved words that has the right
meaning. (And I don't want to add these as reserved words!!) By putting the
words after, it doesn't pollute the clients view as much; they're much
easier to ignore. (And harder to parse, I know.)

> Of course what Bob and I were hoping for was an ability to
> use T_Vectors.Vector directly, without a level of indirection.
> But that seemed to break privacy, along with create some
> real implementation complexities.

Right again.

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

From: Pascal Leroy
Date: Friday, March 24, 2006  4:02 AM

> What we really want is something like:
> 
>      package T_Vectors is new Vectors(T) and will be completed later;

At this point I'd say that what we really want is something that has the
same effect as the trick that I showed in my previous message, but with
better integrated syntax and semantics.  Roughly:

1 - Instantiating with an incompletely defined private type (or deferred
constant) is legal, but it only gives you a limited view of the
instantiation.
2 - The instantiation becomes a full view (and is elaborated) at the end
of the enclosing specification.

An alternative to rule (2) would be to elaborate the instantiation when
all of its parameters are frozen, but that would mean that the elaboration
point could float, and this is unpleasant for the user, because she is
unlikely to have a clue about the freezing rules.

Rule (1) would of course be compatible and would not require new syntax.
One could argue that it is a bit misleading for the semantics of the
instantiation to depend on the nature of the actual parameters, but I
don't think it would be a big deal.  There are already numerous
limitations to what you can do with a private type between the two views,
and the compiler is going to give you a slap on the hand anyway if you
have a limited view and use entities that are not part of that view.

This seems much simpler than the alternatives: I have this feeling that in
80% of the cases the user can just write the natural thing and be
blissfully unaware of what is going on behind the scenes.

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

From: Robert A. Duff
Date: Friday, March 23, 2006 12:28 PM

...
> > 	   type T is
> > 	      record
> > 	         V : P.Vectors.Vector; -- No "access" here.  Illegal!
> 
> Right, and this is a good thing. You want the indirection here and here
> alone.

No, I most certainly do NOT want an indirection here.

Vector already encapsulates a level of indirection,
and I presume Indefinite_Vector has two levels.
And these packages do the necessary memory management.
Requiring the above to be "V : access P.Vectors.Vector;"
defeats the purpose -- now I have memory management in the client
of Vector, which should be unnecessary.

IMHO, any solution to this problem that requires extra levels of indirection
is not a complete solution.

> Use Indefinite_Vectors and T'Class directly:
> 
>          package T_Vectors is new Indefinite_Vectors (T'Class);
> 
> which lets the container manage the indirection.

OK, good.  But I don't want another indirection in the client.

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

From: Tucker Taft
Date: Friday, March 24, 2006 12:57 PM

We had this argument in the ARG, and I was
convinced by Pascal and Randy that you are breaking
privacy by presuming that there is a level of
indirection in the implementation of the generic.

I guess you could say "so what" since you wrote
the generic.  But I think there is some legitimacy
to the argument that the Vector type *might*
include the Element type directly within it.  For
example, Vector might be a variant record, with
the elements stored directly in the record
until the length got above some minimum number,
such as 2.  Clearly if that approach were used,
you couldn't then embed a component of type Vector
back into Element itself.

I suppose you could imagine some way of "promising"
that the Vector type didn't use the Element type
directly, but that doesn't seem easy.  Or you could
say this is just another case where there would be
a check in the private part of an instance upon
instantiation.  All such checks effectively break
privacy, so why get so excited about this one.

In any case, with this argument added on to the
other extraordinary difficulty we had coming up
with a mechanism that would work reliably and
provide for the "direct" embedding, I have
become convinced that the best you can do is
the limited view/incomplete type thing.  I just
don't like using the word "limited" directly, since
it is misleading.  I thought "delay" communicated
the relevant semantics.  Pascal seemed to think
it was OK for the "delay" to be implicit in the
fact that one of the type parameters was private,
while Randy didn't like postponing automatically
to the end of the enclosing package spec, and
wanted an explicit "completion" of the instantiation.
In both cases, using a prefix like "delay" seems
helpful, but I'm not sure either Randy or Pascal
liked that particular word.  "Forward" is the
Pascal (language) equivalent.

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

From: Randy Brukardt
Date: Friday, March 24, 2006  1:44 PM

> I suppose you could imagine some way of "promising"
> that the Vector type didn't use the Element type
> directly, but that doesn't seem easy.

It would have to be part of the contract of a private type. Not sure what
that would look like.

> Or you could
> say this is just another case where there would be
> a check in the private part of an instance upon
> instantiation.  All such checks effectively break
> privacy, so why get so excited about this one.

But the problem isn't in the instantiation; it's in the full type (which is
using the type without indirection). Blaming the problem on the generic
complicates things, and makes a nasty problem for implementers.

Imagine an implementer that decides to improve the efficiency of their
vector type by removing the indirection. Now, that would have the potential
of breaking clients because they're depending on a property of the
implementation that isn't even in the contract.

And remember that this isn't just about the predefined containers; it's easy
to imagine a user-defined type that much more easily avoids indirection.

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

From: Randy Brukardt
Date: Friday, March 24, 2006  1:45 PM

...
> No, I most certainly do NOT want an indirection here.
>
> Vector already encapsulates a level of indirection,
> and I presume Indefinite_Vector has two levels.

There is no guarentee of that; it's certainly not part of the contract of
either type. If it was part of the contract you'd have a better argument,
but as long as it is not, it is privacy breaking. Moreover, it means that
Ada compilers would have to make a very expensive check on every type
declaration to ensure that no component was recursive (it would be expensive
because it would be very hard to tell if you have a loop unless you marked
every symbol table node that was reached - meaning a global walk to set the
bits in the first place).

> And these packages do the necessary memory management.
> Requiring the above to be "V : access P.Vectors.Vector;"
> defeats the purpose -- now I have memory management in the client
> of Vector, which should be unnecessary.
>
> IMHO, any solution to this problem that requires extra levels of
> indirection is not a complete solution.

The only way to do this is to get "indirection" into the contract of a
private type.

In any case, it was this "it's not a complete solution" attitude that was a
primary reason that we don't have even a partial solution to this important
problem. We can't even write this *with* a level of indirection today
because of your complaining about "complete solutions".

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

From: Randy Brukardt
Date: Friday, March 24, 2006  1:57 PM

...
> > What we really want is something like:
> >
> >      package T_Vectors is new Vectors(T) and will be completed later;
>
> At this point I'd say that what we really want is something that has the
> same effect as the trick that I showed in my previous message, but with
> better integrated syntax and semantics.

This trick is quite complex to get right; you have to re-export the type to
make it work, which introduces a number of complications (such as mistakely
using the original generic type in code and getting type errors). (I was
thinking that it didn't work, but I had forgotten about the re-export.)

> Roughly:
>
> 1 - Instantiating with an incompletely defined private type (or deferred
> constant) is legal, but it only gives you a limited view of the
> instantiation.

There were a number of us that were uncomfortable with this, because it's
hell for syntax directed compilers. Essentially, we have to figure out
whether the types are frozen before we can generate code. And it confusing
for the user, when they get an error message using something that is
"clearly" declared right in front of them. I think it is better to have a
keyword to get this behavior, since it reduces surprises.

> 2 - The instantiation becomes a full view (and is elaborated) at the end
> of the enclosing specification.

I think this is too limiting. You couldn't use entities declared (other than
types) anywhere in the specification, even though there is no problem with
doing so once the private type is frozen. For instance, you couldn't declare
deferred constants based on the generic.

We agreed that "floating" was uncomfortable, so I still think the only sane
solution is an explicit completion. Incomplete anythings have explicit
completions, so it seems to fit the model.

But I'm pretty much willing to live with your workaround and forget the
whole thing. I've been under the impression that this couldn't be done in
any way; if that's not true, it is much less of a problem. (It also shows
that the limited view solution works...)

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

From: Tucker Taft
Date: Friday, March 24, 2006  1:58 PM

> ...  But I think there is some legitimacy
> to the argument that the Vector type *might*
> include the Element type directly within it.  For
> example, Vector might be a variant record, with
> the elements stored directly in the record
> until the length got above some minimum number,
> such as 2.  Clearly if that approach were used,
> you couldn't then embed a component of type Vector
> back into Element itself...

Actually, it is somewhat worse than that.  You get
into trouble even if you always use a level of
indirection in implementing Vector, if the default
value for a Vector includes some minimal preallocated
length.  Perhaps a stupid choice, but not without
some justification in some cases.  That is, rather
than waiting for the first element to be added to
the vector to do the first allocation, why not
do an allocation right away as part of the
default initialization of the type?  E.g.:

    type Vector is record
       Current_Len : Natural := 0;
       Buffer : access Element_Array := new Element_Array(1..Minimum_Size);
    end record;

This would also create trouble if you embedded
a Vector-of-Elements into type Element, because
the default initialization process would never
stop.  That's probably worse than finding out at
instantiation time.

The advantage of the limited view approach is that
it requires the use of indirection when
embedding Vector into Element.  Hence you have an
automatic default of null, and furthermore, you
can't write an allocator even if you wanted to give
the embedded "access Vector" a default initial value,
since the Vector type is still incomplete at the point
where you give the full type for Element.

Actually, that gives me a thought:

   Perhaps what we really need is a new kind of formal
   generic type, perhaps a "formal limited incomplete type."
   You would be forced to use it only with a level of
   indirection, but you would be allowed to instantiate
   it with an incompletely-defined type.  If we distinguish
   between formal definite vs. formal indefinite limited
   incomplete (which might be interesting for non-formal
   incomplete types), then we might be able to allow you
   to declare arrays of a formal limited incomplete type,
   which would of course also be limited incomplete.
   This would allow the following:

      generic
         type Element is limited;
              -- formal definite limited incomplete type
              -- (not an ideal name/syntax, admittedly)
      package Vectors is
         type Vector is private;
        ...
      private
         type Element_Array is
           array(Positive range <>) of Element;
            -- limited incomplete array type.

         type Vector is record
             Cur_Len : Natural := 0;
             Buffer : access Element_Array;
         end record;
      end Vectors;

   We might require that the actual for a formal limited
   incomplete types be completely defined before the next
   "global" freezing point (end of library unit spec or
   at the point of a body).  That would ensure you could verify
   that it was in fact a "definite" rather than an "indefinite"
   subtype.  Or perhaps only require that it be completely
   defined by then if the formal is "definite," so if the formal
   is indefinite, you could instantiate it with an incomplete
   type taken from the limited view of a package, or with
   one whose completion is deferred to a package body.

Any bites on this idea?  Note that this *would* allow
the embedding of a Vector in the definition of Element.

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

From: Stephen W. Baird
Date: Friday, March 24, 2006  2:19 PM

>    1) allowing children of generics to be instantiations
>       rather than generics;
>    ...
> Within the scope of a with clause for the
> child of the generic, any instantiation of the generic
> will create a child of the instantiation with the same name.

This would introduce an inconsistency in the treatment of
child units of generics which are not withed at the point of
an instantiation of the parent unit.

Consider

    generic
    package G is
    end G;

    with G;
    package I is new G; -- no children withed here

    generic
    package G.Generic_Child is
    end G.Generic_Child;

    package G.Non_Generic_Child is
    end G.Non_Generic_Child.

    with G.Generic_Child;
    with G.Non_Generic_Child;
    with I;
    package Pkg is
       generic package Generic_Child_Rename renames
           I.Generic_Child; -- legal
       package Non_Generic_Child_Rename renames
           I.Non_Generic_Child; -- illegal
    end Pkg;

This isn't a fatal flaw and there are good reasons for it, but it isn't 
pretty.

While I'm on the subject, here are some other details:

  1) Either conservative assumptions could be required for formal instances,
     or else more complicated matching rules for actuals would be needed.
     One way or another, this example would have to be rejected

        with G.Non_Generic_Child;
        generic
          with package Formal_Instance is new G;
        package G2 is
          package Non_Generic_Child_Rename
            renames Formal_Instance.Non_Generic_Child;
        end G2;

        with G2;
        with I;
        package I2 is new G2 (Formal_Instance => I);

     because I.Non_Generic_Child doesn't exist.

  2) The precise point at which these implicitly declared instantiations are
     elaborated would need to be specified. This ought to occur at some point
     where calling operations out of the parent unit will not result in
     elaboration check failures.

  3) There would be little additional implementation burden in allowing
     arbitrary non-generic packages (i.e., not just instances) as
     children of generics. Note that I am not claiming that this is therefore
     a good idea; I'm just mentioning it as an option.

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

From: Randy Brukardt
Date: Friday, March 24, 2006  2:32 PM

...
> Consider
>
>     generic
>     package G is
>     end G;
>
>     with G;
>     package I is new G; -- no children withed here
>
>     generic
>     package G.Generic_Child is
>     end G.Generic_Child;
>
>     package G.Non_Generic_Child is
>     end G.Non_Generic_Child.

Not sure if this matter to your argument, but you can't declare
Non_Generic_Child; as a child of a generic it has to be a generic or (in
Tucker's proposal) an instance.

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

From: Stephen W. Baird
Date: Friday, March 24, 2006  3:01 PM

> Not sure if this matter to your argument, but you can't declare
> Non_Generic_Child; as a child of a generic it has to be a generic or (in
> Tucker's proposal) an instance.

Good point.

It could be declared as something like

    with Some_Generic;
    package G.Non_Generic_Child is new Some_Generic;

Thanks.

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

From: Tucker Taft
Date: Friday, March 24, 2006  2:50 PM

> This would introduce an inconsistency in the treatment of
> child units of generics which are not withed at the point of
> an instantiation of the parent unit.

Yes, I know that, but I felt it needed to work that way
because you don't know when to create the "actual" instantiation
of the child if you don't require the child to be "with"ed
at the point of instantiation of the parent.  Having
the "actual" child instantiation occur as an implicit
side-effect of withing the child of the generic at some
later point just seemed too weird.  Of course in C++
all instantiations are implicit upon reference, so
you could make it work if you had to.

And as you point out later, once you require the "with" at
the point of instantiation of the parent generic, the child
could really be any kind of unit, since it is getting "plugged"
into the generic before it is instantiated.

If we went this route, I would end up explaining it that
for generic children of a generic, you can defer specifying
the child until you instantiate the child, whereas for
non-generic children of a generic, you have to specify the
child when you instantiate the parent generic.  Whether you
could *allow* an "early" with of a generic child to provide
for the generic child to appear "inside" the instantiation
without further "with"ing seems like a possible option.
I'm not sure whether it would be upward compatible, particularly
in the presence of "use" clauses for the instantiation.

...
> This isn't a fatal flaw and there are good reasons for it, but it isn't 
> pretty.

This doesn't seem so bad, and I trust you understand why
it is necessary for the "with" to be provided at the point
of instantiation of the parent generic if the child is
non-generic.

> While I'm on the subject, here are some other details:
...
>      because I.Non_Generic_Child doesn't exist.

Good point.  I suppose we could check in the spec and
assume the worst in the body.  Perhaps better would
be to require that the actual match the formal in
that if the formal instance includes an instantiation
of some child, then so must the actual.

>   2) The precise point at which these implicitly declared instantiations are
>      elaborated would need to be specified. This ought to occur at some point
>      where calling operations out of the parent unit will not result in
>      elaboration check failures.

Normally the body of an instance is elaborated immediately after
the spec of the instance.  So I would presume that the instance
children would be elaborated after the body of the parent instance.

> 
>   3) There would be little additional implementation burden in allowing
>      arbitrary non-generic packages (i.e., not just instances) as
>      children of generics. Note that I am not claiming that this is therefore
>      a good idea; I'm just mentioning it as an option.

Yes, it seems there is no reason to limit it to instantiations.
In fact, it seems a more natural way of extending a generic
than the Ada 95 approach, since you don't need to do an
additional instantiation.  I'm wondering now why we did it
the way we did in Ada 95.  It seems a bit counterintuitive.

I suppose a problem with this new proposal is that we are
effectively making "with" clauses transitive.  Better might
be to require the with clause to be repeated wherever
you want to refer to an "actual" child instance.  Hopefully we
would allow you to refer to either the original child
of the generic or the actual child of some particular instance
of the parent generic, if the instantiation of the parent
generic is itself a library unit.

As usual, you have managed to rapidly find all the crufty
details behind my naive proposal!  ;-)

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

From: Robert A. Duff
Date: Friday, March 24, 2006  3:49 PM

> In any case, it was this "it's not a complete solution" attitude that was a
> primary reason that we don't have even a partial solution to this important
> problem. We can't even write this *with* a level of indirection today
> because of your complaining about "complete solutions".

But Pascal showed the partial solution -- with an extra level of indirection.
I'm pretty-much satisfied with that solution, except for the indirection.
(The child package seems like a minor annoyance.)

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

From: Randy Brukardt
Date: Friday, March 24, 2006  4:17 PM

That suggests that you're now lobbying for no solution. Interesting. :-)

I agree that the child package isn't too bad, but the I think the necessary
re-declaration of the types involved can get very messy. If there's only one
such type, that works OK, but for something like the containers, it gets
messy (especially as operations don't inherit properly from multiple types).

Taking Pascal's example:

	package P.Vectors is
	   package T_Vectors is new Vectors (T);
	   type Vector is new T_Vectors.Vector;
	end P.Vectors;

If a client wanted to do an operation on this vector as using a cursor,
you'd have something like this:

      V : P.Vectors.Vector;
      C : P.Vectors.T_Vectors.Cursor;

      C := P.Vectors.Find (V, E);

The fact that the types are declared in different places is annoying. Also
note that you're using an inherited Find (its not the one declared in
T_Vectors). If you're in the habit of "use"ing everything, this probably
doesn't matter to you, but for those of us that don't use "use" clauses, or
use them sparingly, this will be a mess.

If you try to fix this by re-exporting the cursor type, too, you have a
bigger mess:

	package P.Vectors is
	   package T_Vectors is new Vectors (T);
	   type Vector is new T_Vectors.Vector;
         type Cursor is new T_Vectors.Cursor;
	end P.Vectors;

because there will be two inherited Find's, and neither will take both a
P.Vectors.Vector and a P.Vectors.Cursor.

Manually re-exporting everything will work, but that's insane for an
Ada.Containers.Vector (that's a 200+ line specification).

The other solution is for clients to use the contents of T_Vectors
exclusively; but then type conversions will be needed for the ones declared
in P.

The need for new types for the limited view to work is what makes this fix
unworkable in practice. Otherwise, I would be tempted to declare the problem
solved and find something else to work on.

(One simple fix would be to extend limited views to subtypes:

	package P.Vectors is
	   package T_Vectors is new Vectors (T);
	   subtype Vector is T_Vectors.Vector;
         subtype Cursor is T_Vectors.Cursor;
	end P.Vectors;

These subtypes aren't imported as limited views currently, and that means
separate types have to be used. But I don't know off-hand what horrors that
would introduce -- there probably is some.)

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

From: Robert A. Duff
Date: Friday, March 24, 2006  5:15 PM

> That suggests that you're now lobbying for no solution. Interesting. :-)

I don't know what I'm lobbying for.  ;-)

I guess I'm lobbying for no solution, or a complete solution.
Half-solutions seem less interesting, to me.

> messy (especially as operations don't inherit properly from multiple types).

Right.  But this is a much more general issue.  In many cases, one wants to
create an abstraction in several packages, but let the client view it as a
single thing.  Ada doesn't provide much help here.  The "type Vector is new
T_Vectors.Vector;" thing is a hack -- you inherit the primitive ops, but you
don't inherit the related exceptions and generics and whatnot.
You didn't really want a new type -- just visibility on the old type and
everything that has to do with it.
And, as you pointed out, if there are two types involved, you can't use
inheritance of both to get the "right" operations.

I'd like to see a solution to this problem, but it seems like a separate
issue, not particularly related to generics.

It seems like a simple idea: I want to say, everything visible in package
Mumble should be visible HERE, and (transitively) whereever HERE is visible.
Some sort of bulk renaming might do.

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

From: Tucker Taft
Date: Friday, March 24, 2006  5:40 PM

Unfortunately, unless it is syntactic, the "limited with"
won't be able to see it.  You would at least need to
individually name all the types you want imported into
the scope.  E.g. "with type Mumble.T1, Mumble.T2, ...;"
(imagining that "with type" is the way to import a type into
a new scope, along with its primitives).  You might need a
"with exception" and "with generic" for the others, though
renaming can work for those.  Types are a little special
if you want an imported type to complete a private type
or an incomplete type declaration ("a little special"
might be a bit of an understatement, given our past heated
discussions about type renaming).

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

From: Tucker Taft
Date: Friday, March 24, 2006  4:30 PM

Any comments on my "formal limited incomplete type"
proposal?  I think it provides a solution that
does not require a level of indirection in the
use of Vector, though it requires Vector to be
implemented with a level of indirection internally.

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

From: Randy Brukardt
Date: Sunday, March 26, 2006 12:41 AM

I have some time to kill waiting for files to upload, so let me channel
Steve Baird and post a bunch of random thoughts I have on this idea.

1) The basic idea seems sound to me. I do worry about the details. OTOH, I
can't complain too much, since it seems to require everyone to implement
something similar to our implementation of generic sharing. :-) The basic
idea is not too far from how we implement formal private types anyway.

2) I don't think we want to get too far from the carefully defined
"incomplete view" rules that we already have. That makes the "definite" part
of Tucker's idea very suspicious. I have no idea how arrays (for instance)
could be implemented statically; my guess is that you'd have to resort to an
"implicit" indirection. At the very least, you'd have to require that the
array was then treated as incomplete, which seems like a massive
complication. So I wouldn't try to figure out how to allow anything beyond
what ordinary incomplete types allow (but see below).

3) You might as well have tagged and untagged versions; the tagged version
would allow parameter passing (without "access"), just as for "regular"
tagged incomplete types. OTOH, the untagged version could not: it would be a
nightmare to have frozen subprograms for which the parameter passing mode
isn't known. Similarly, we'd need limited and non-limited versions. The
non-limited tagged version could provide a partial replacement for the
indefinite containers. (The limited untagged version could provide a form of
limited containers, but there would be lifetime issues to deal with, which
would make use user-beware.)

3) The incompleteness of this formal couldn't extend over the entire generic
unit, or you couldn't do much useful with these types. But it does have to
extend over the package level stuff in order to ensure the indirection
that's required. In particular, we need to allow allocators and assignment
in the subprograms (if we want to be able to build containers with them, at
least). This is uncomfortable. Another possibility would be to allow
assignment and allocators *only* in addition to the normal stuff. That
requires extra checking, see below.

4) For this to be useful as intended, the generic will have to export
"normal" stuff; it can't be partially defined (we've already proved that
partially defined stuff is a nightmare, and provides all kinds of stuff that
wasn't previously possible). That's OK, because the incomplete type doesn't
need to be frozen to freeze things depending on it. That also implies that
the generic will have to be elaborated at the point of the instantiation.
(Can't have types that depend on run-time things that are frozen and usable
to declare an object, but aren't elaborated.)

5) But the elaboration cannot depend on the size of formal incomplete type.
But calls to routines in the generic could execute an allocator or
assignment. Ugh. I can think of three ways to deal with this:
   (A) Require that the generic is Preelaborable. This would make such calls
illegal. This however is pretty heavy, as it means the generic cannot with
"normal" units like Text_IO. (Adopting special rules for this generic that
are "almost like Preelaborable" would work, but seems too complex for this
single use.) Note that there are a lot of ways to cause trouble here; it
doesn't need to be a direct call to a local subprogram:
    package Trouble is new Calls_Formal (Local_Proc);
    Call_Me (Local_Proc'Access); -- Call_Me takes an anon
access-to-subprogram
Both of these (if placed at the package level) would make indirect calls to
a local subprogram. You also could cause trouble with Initialize/Finalize.
   (B) Require the implementation to raise Program_Error if an operation not
allowed on an incomplete type is done before the completion of the
corresponding type. (BTW, that completion will have to be local, or there
would be no obvious way to update the generic information block with the
properties of the frozen actual [for our implementation]. And I don't think
that the rest of you want generics whose operation depends on the view... An
alternative would be for a generic whose actual isn't completed by the end
of the scope to stay incomplete forever - but that seems weird.)
    Such a runtime check would seem to be fairly easy to implement in both
generic models, and it would allow the maximum flexibility in allowing
assignments and allocators. As long as you don't execute problematic stuff,
everything is fine. But the dynamic nature of the checking will likely
bother some.
   (C) Enforce "no allocators" and "no assignment" in the package level of
the generic, allow them with a runtime check in the nested subprograms.
(Essentially combining (B) with a static check.)

(6) As I said previously, this seems easy for a code sharing implementation.
(Presuming that there is a well-defined single point where it becomes
complete.) But it seems ugly for a macro-based one. You'd have to generate
code for the generic without knowing anything (much) about the actual. (Or
you'd have to be able to delay the code generation for the *entire* generic
to some later point, even though the instantiation is physically nested.) At
a very least, you'd have to generate everything needed to handle calls,
references to types, constants, exceptions, etc. at the point of the
instance. (Note that the well-defined point where it becomes complete is
needed if you want to delay the code generation, too, unless you're willing
to delay it all the way to link time.)

(7) I think my Steve Baird channeling has fallen short, because I haven't
identified any insurmountable interactions with slices of tasks. :-) Still,
I wonder precisely what operations will be allowed on this formal and how
those will interact with "early" calls to the generic. What will happen if
we had code like:

    package P is
       type Priv is private;
       package Something is new Something_Else (Priv);
       A : access Priv := Something.Default_Creator;
    ...
    end P;

where Default_Creator includes a (default) allocator for type. (Creator's
spec would look like:
    function Default_Creator return access Incomp_Lim;
)

This better raise an exception, or something.

I think this is enough for tonight. Tucker can now run around sticking his
fingers in the holes... ;-)

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

From: Robert A. Duff
Date: Sunday, March 26, 2006  9:46 AM

I have a general comment on this issue:  In previous discussions of AI-359,
we came up with about 5 or 6 viable solutions, any of which would have been
acceptable (to me).  Each was rejected for fairly minor reasons, IMHO:
(1) Aesthetic concerns about the syntax (some people don't like "delay", some
people find "limited" confusing from the client's point of view, some people
don't like pragmas, etc).  (2) Concerns about upward compatibility (if we
change where elaboration happens).  I can't imagine that being a real problem
in practise -- I can't think of a realistic example where it would matter.
(3) Concerns about the place of elaboration moving in subtle ways due to
changing the code in various ways.  Again, I can't think of a realistic
example.

All of these are legitimate concerns, but they're not fatal flaws.
Yet we have allowed them to paralyze us.

Tucker writes:

> We had this argument in the ARG, and I was
> convinced by Pascal and Randy that you are breaking
> privacy by presuming that there is a level of
> indirection in the implementation of the generic.

Yes, it breaks privacy.  But privacy is already broken
without any generics, as I pointed out in an e-mail on
June 24, 2004, which is included in AI95-00359-02/02
(that is, ai-10359.txt):

package Junk is
    type T1 is private;

    package Sub is
        type T2 is private;
    private
        type T2 is
            record
                X2: T1;
            end record;
    end Sub;
private
    type T1 is
        record
            X1: Sub.T2;
        end record;
    X: T1;
end Junk;

Of 4 compilers tested, only one correctly noted that this is illegal
by 3.2.1(5).

No change was made to the RM to fix this problem,
so it's not clear to me that it's worth worrying about.

> I guess you could say "so what" since you wrote
> the generic.  But I think there is some legitimacy
> to the argument that the Vector type *might*
> include the Element type directly within it.  For
> example, Vector might be a variant record, with
> the elements stored directly in the record
> until the length got above some minimum number,
> such as 2.  Clearly if that approach were used,
> you couldn't then embed a component of type Vector
> back into Element itself.

OK.  We would need to specify for each language-defined container whether it
can be used cyclically.  User-defined ones are on their own (though I admit
it's always sad to break privacy).

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

From: Robert A. Duff
Date: Sunday, March 26, 2006 10:02 AM

> Actually, it is somewhat worse than that.

>     type Vector is record
>        Current_Len : Natural := 0;
>        Buffer : access Element_Array := new Element_Array(1..Minimum_Size);
>     end record;

This one doesn't bother me at all.  Privacy-breaking is a compile-time concept
only.  There are thousands of ways to write a private part that will break at
run time.

>    Perhaps what we really need is a new kind of formal
>    generic type, perhaps a "formal limited incomplete type."

With my language-lawyer hat on, this seems like a sensible idea.
Randy pointed out various issues, which are probably solvable,
but I'm not sure.

But with my user hat on, it seems like a lot of added complexity for not so
much gain.

If we do this, I suppose Vectors (and others?) should use it.
(As always, I am in favor of restricting implementations'
freedom to represent container data structures as they
see fit.)

I'm not sure it solves the whole problem.  For example:

    package P is
        type T is private;
        type A is array(...) of T;
    private
        type T is new Integer;
    end P;

No recursive types, here.

Now I want to replace A with some sort of *bounded* container,
which does not want to have a formal limited incomplete type:

    with Bounded_Container;
    package P is
        type T is private;
        package Bounded_Container_Of_T is new Bounded_Container(Element => T);
        subtype A is Bounded_Container_Of_T.Container;
    private
        type T is new Integer;
    end P;

That would still be illegal, right?  I must move Bounded_Container_Of_T into a
child.  I can live with that, but it's the sort of annoyance that frustrates
users, because only language lawyers understand the reasons.

In summary, for "formal limited incomplete types", I come down firmly on the
side of "not sure".  ;-)

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

From: Robert A. Duff
Date: Sunday, March 26, 2006 10:11 AM

> Unfortunately, unless it is syntactic, the "limited with"
> won't be able to see it.  You would at least need to
> individually name all the types you want imported into
> the scope.  E.g. "with type Mumble.T1, Mumble.T2, ...;"
> (imagining that "with type" is the way to import a type into
> a new scope, along with its primitives).  You might need a
> "with exception" and "with generic" for the others, though
> renaming can work for those.  Types are a little special
> if you want an imported type to complete a private type
> or an incomplete type declaration ("a little special"
> might be a bit of an understatement, given our past heated
> discussions about type renaming).

I'm completely confused by the above (sorry).  Starting with "unless it is
syntactic" -- unless what is syntactic, and what do you mean by syntactic?
In "won't be able to see it", what's "it"?

If I have two packages, P and P.C, I can say:

    with P.C;
    package P_View is
        subtype T is P.T;
        procedure Mumble renames P.Mumble;
        X: exception renames P.X;
        ...

        procedure Dumble renames P.C.Dumble;
        ...
    end P_View;

simply listing out all the declarations in the two packages,
and renaming them all.  What I was asking for is a shorthand way to say
"rename everything from P and P.C HERE."  I can't imagine why such a
feature would cause difficulties, since I can already do it by hand.
The only problem with by hand is that it's error prone, unreadable,
and unmaintainable -- so much so that people simply require clients
to know about P and P.C directly.

I don't understand how your above comment addresses this idea.
You talk about importing types and generics and exceptions and
so forth separately -- but that defeats the purpose.
The purpose is to build an abstraction in parts,
and combine them into one view for client's use.

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

From: Bibb Latting
Date: Sunday, March 26, 2006  5:29 PM

> simply listing out all the declarations in the two packages,
> and renaming them all.  What I was asking for is a shorthand way to say
> "rename everything from P and P.C HERE."  I can't imagine why such a

I think I want some way to choose what gets made visible -- although having 
a bulk method is good too.  This way I can try to keep a cleaner abstraction 
when the underlying abstractions are less-than-perfect.

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

From: Tucker Taft
Date: Sunday, March 26, 2006  7:18 PM

> I'm completely confused by the above (sorry).  Starting with "unless it is
> syntactic" -- unless what is syntactic, and what do you mean by syntactic?
> In "won't be able to see it", what's "it"?

Sorry if my response was mysterious.

The underlying model for "limited with P" is that it performs
only syntactic analysis on the package P.  It performs no
name resolution, no instantiation, no renaming, etc.
Hence, a shorthand renaming of everything in an
instantiation wouldn't work to create symbols made
visible by a limited with, since it completely ignores
instantiations, and definitely doesn't know what
symbols are inside an instantiation.

> If I have two packages, P and P.C, I can say:
> 
>     with P.C;
>     package P_View is
>         subtype T is P.T;
>         procedure Mumble renames P.Mumble;
>         X: exception renames P.X;
>         ...
> 
>         procedure Dumble renames P.C.Dumble;
>         ...
>     end P_View;
> 
> simply listing out all the declarations in the two packages,
> and renaming them all.  What I was asking for is a shorthand way to say
> "rename everything from P and P.C HERE."  I can't imagine why such a
> feature would cause difficulties, since I can already do it by hand.

The difficulties are that "limited with" doesn't look
inside of instantiations.

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

From: Robert I. Eachus
Date: Monday, March 27, 2006  1:31 PM

...
>What I was asking for is a shorthand way to say
>"rename everything from P and P.C HERE."  I can't imagine why such a
>feature would cause difficulties, since I can already do it by hand.
>The only problem with by hand is that it's error prone, unreadable,
>and unmaintainable -- so much so that people simply require clients
>to know about P and P.C directly.
 
What is so wrong with: use P; use P.C instead of a separate view 
package? It might be nice to allow:

   *with* P.A; *with* P.B; *with* P.C; *use all* P;

As a shorthand?  It is syntactic sugar, but it might be useful syntactic 
sugar.  Of course the same shortcut should not be used in with clauses, 
even if added to the language.  The use all notation would apply only to 
those decendents of P made visible by the with clauses.

As long as we are on the subject of syntactic sugar, let me suggest 
another piece that would probably resolve most of the issues discussed 
here.  Right from the start, Ada has allowed variant records with 
default discriminants to change in size.  But there has been a problem 
in that the similar feature does not exist for array types.  You can write:

    *type* Int_Array *is array* (Integer) *of* Integer;
    *type* Variable_Sized_Array(Size: Integer := 0) *is record*
      Contents: Int_Array(1..Size);
    *end record*;

But there are several problems with this idiom.  First there is a 'junk' 
type required because you can't declare an array type inside a record 
declaration.  But more important, a lot of uses of the type need to 
reference the junk name of the array compontent.  The final problem is 
that the compiler doesn't really know to treat this differently from 
record variants that are limited in size.  What if we added default 
values for array types to Ada 1Z:

   *type* Vector *is array* (Integer *range* <>) *of* Integer := (1..0 => 0);

Unconstrained objects of such types would have variable bounds, and the 
default value would guarantee that the attributes were always defined. 
Yes, it takes a some stuff we just put in the annexes and obsoletes it, 
but that is a good thing.  It also obsoletes much of the previous 
discussion in this thread, and that is an even better thing.  It is a 
language extension with no distributed cost--dynamic array objects must 
be of a (new) dynamic array type.  It is also cheap for implementors, it 
can be converted into the equivalent mutant records.  The big win is 
that it hugely simplifies some types of code.  Notice that you can have 
constrained and unconstrained objects of such a type, like you can with 
the equivalent record type.  Once the user has decided to 'pay the 
price' (of indirection and finalization) in some objects) all other 
concerns visibility, freezing, etc. issues go away.  Only in some object 
declarations is there any difference from current array types, and using 
the objects is just like using objects of current unconstrained array types.

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

From: Robert A. Duff
Date: Monday, March 27, 2006  4:27 PM

> The underlying model for "limited with P" is that it performs
> only syntactic analysis on the package P.  It performs no
> name resolution, no instantiation, no renaming, etc.
> Hence, a shorthand renaming of everything in an
> instantiation wouldn't work to create symbols made
> visible by a limited with, since it completely ignores
> instantiations, and definitely doesn't know what
> symbols are inside an instantiation.

OK, thanks for explaining.  I think you misunderstood what I was getting at,
so I misunderstood your response.  My point here was a small side issue, not
closely related to the main points of this thread.

The point is: Pascal's partial solution to the main problem requires an
abstraction to be split into two parts (perhaps P and P.C).  At some point,
you suggested a way to alleviate that from the client's point of view (by
having "with P" automatically imply "with P.C" in some cases, or something
like that).  My suggestion here has the same purpose -- to let the client view
an abstraction as one whole, when the abstraction is implemented in multiple
pieces.

> > If I have two packages, P and P.C, I can say:
> >     with P.C;
> >     package P_View is
> >         subtype T is P.T;
> >         procedure Mumble renames P.Mumble;
> >         X: exception renames P.X;
> >         ...
> >         procedure Dumble renames P.C.Dumble;
> >         ...
> >     end P_View;
> > simply listing out all the declarations in the two packages,
> > and renaming them all.  What I was asking for is a shorthand way to say
> > "rename everything from P and P.C HERE."  I can't imagine why such a
> > feature would cause difficulties, since I can already do it by hand.
> 
> The difficulties are that "limited with" doesn't look
> inside of instantiations.

There is no "limited with" in the above example.  Perhaps P says "limited
with P.C", but that's irrelevant.  P_View above has complete views of both P
and P.C, so when compiling P_View, we know the names and types of everything
in P and P.C.

Do you understand what I'm getting at, now?  Care to make another response?

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

From: Robert A. Duff
Date: Monday, March 27, 2006  4:34 PM

> I think I want some way to choose what gets made visible -- although having a
> bulk method is good too.  This way I can try to keep a cleaner abstraction
> when the underlying abstractions are less-than-perfect.

I'm not sure exactly what you mean.  We already have a way to choose what's
visible -- just rename the things you want.  I guess you asking for "rename
everything EXCEPT blah and mumble".  That makes sense, but I suspect it's
substantially more complicated than the simple "rename everything" I
suggested.

One point about the "bulk rename" idea: it will pick up things defined in the
future.

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

From: Robert A. Duff
Date: Monday, March 27, 2006  4:46 PM

> What is so wrong with: use P; use P.C instead of a separate view package?

It's not "so wrong", but it doesn't solve the (admittedly minor) problem I was
trying to solve.  That is, it does not allow clients to view the abstraction
as a single package, when it is implemented as multiple packages.  I might
want to say P_View.Mumble and P_View.Dumble.  Or, I might want to say "use
P_View" and then refer to Mumble and Dumble directly.  With the current
language, all 100 clients of this P_View abstraction have to know about the
individual parts of it (P and P.C in this case).

>... It
> might be nice to allow:
> 
>    *with* P.A; *with* P.B; *with* P.C; *use all* P;
> 
> As a shorthand?  It is syntactic sugar, but it might be useful syntactic
> sugar.  Of course the same shortcut should not be used in with clauses, even
> if added to the language.  The use all notation would apply only to those
> decendents of P made visible by the with clauses.

Such a feature makes sense, but I don't see a big advantage of it.

> As long as we are on the subject of syntactic sugar, let me suggest another
> piece that would probably resolve most of the issues discussed here.

The variable sized array is just one (important!) example.  What's being
discussed here is any container-like generic package.

>...Right
> from the start, Ada has allowed variant records with default discriminants to
> change in size.  But there has been a problem in that the similar feature does
> not exist for array types.  You can write:
> 
>     *type* Int_Array *is array* (Integer) *of* Integer;
                                          ^ range <>
>     *type* Variable_Sized_Array(Size: Integer := 0) *is record*
>       Contents: Int_Array(1..Size);
>     *end record*;
> 
> But there are several problems with this idiom.

Such as, it doesn't work in many compilers (raises Storage_Error)!  ;-)

>...First there is a 'junk' type
> required because you can't declare an array type inside a record declaration.
> But more important, a lot of uses of the type need to reference the junk name
> of the array compontent.  The final problem is that the compiler doesn't
> really know to treat this differently from record variants that are limited in
> size.  What if we added default values for array types to Ada 1Z:
> 
>    *type* Vector *is array* (Integer *range* <>) *of* Integer := (1..0 => 0);

I believe Ada 9X originally proposed to allow:

    type Vector(First: Integer := 1; Last: Integer := 0) is
        array(Integer range First..Last) of Integer;

which would have accomplished the same thing.

> Unconstrained objects of such types would have variable bounds, and the
> default value would guarantee that the attributes were always defined. Yes, it
> takes a some stuff we just put in the annexes and obsoletes it, but that is a
> good thing.  It also obsoletes much of the previous discussion in this thread,
> and that is an even better thing.  It is a language extension with no
> distributed cost--dynamic array objects must be of a (new) dynamic array type.
> It is also cheap for implementors, it can be converted into the equivalent
> mutant records.  The big win is that it hugely simplifies some types of code.
> Notice that you can have constrained and unconstrained objects of such a type,
> like you can with the equivalent record type.  Once the user has decided to
> 'pay the price' (of indirection and finalization) in some objects) all other
> concerns visibility, freezing, etc. issues go away.  Only in some object
> declarations is there any difference from current array types, and using the
> objects is just like using objects of current unconstrained array types.

Good ideas, and they make "growable arrays" less painful.  But I don't think
they solve the general problem.  For example, "array(String range <>) of Boolean"
still requires a hash-table generic, or some such.

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

From: Randy Brukardt
Date: Monday, March 27, 2006  5:16 PM

> There is no "limited with" in the above example.  Perhaps P says "limited
> with P.C", but that's irrelevant.  P_View above has complete
> views of both P
> and P.C, so when compiling P_View, we know the names and types of
> everything
> in P and P.C.
>
> Do you understand what I'm getting at, now?  Care to make another
> response?

I will. That's interesting, but it doesn't provide a solution to the other
major annoyance of this approach, which is the fact that you have to declare
an extra type; one that's incompatible with the one declared by the
instantiation so that the limited with will work. The best solution would
handle both.

Our example looked like:
    package P.C is
        package T_Vector is new Vector (P.T);
        type Vector is new T_Vector.Vector with null record;
    end P.C;

The type declaration of "Vector" is only needed here so the type will be
visible via a limited with. The problem, as previously explained, was that
limited with can't see inside of instantations, so we need some way to pull
the information out.

The easiest solution to this is to invent a hack:
     for limited with use T_Vector.Vector, T_Vector.Cursor;
which has only two semantics: the names given must exist, and must be types
declared in this package specification, and these names are visible to
limited withs.

The better solution would be to come up with a form of type renaming. That
would be more generally useful. I can't think of a great syntax for this,
but I'm sure someone else can:
     type renames T_Vector.Vector, T_Vector.Cursor;
This would work much like Bob's idea:
    * The types would have to be frozen (or this would be freezing). [That's
necessary so that we know the set of primitive operations.]
    * The type(s) would be declared here as subtypes, with the given simple
names.
    * The newly given (subtypes) would be visible to limited withs.
    * The primitive operations of the type(s) would be declared here as
renames of the originals, with the appropriate simple names.

Note that using two separate type renames would not work quite the same as a
single one, as you'd get multiple copies of any routines primitive to both
types. That's either illegal, or any calls would be ambiguous, and neither
is going to work right.

To make a Bob-like pronouncement, I'm not interested in a solution that
doesn't get rid of this extra type. The naming issue is minor; indeed, I've
nearly convinced myself that it's better to have these things as separate
children than for them to be nested. The extra type causes complications all
over, requiring extra type conversions somewhere and/or screwing up the
visibility of things.

Thoughts?

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

From: Randy Brukardt
Date: Monday, March 27, 2006  8:33 PM

...
> All of these are legitimate concerns, but they're not fatal flaws.
> Yet we have allowed them to paralyze us.

There were a number of other reasons that were at least as important, such
as:

(4) Problems with the export of partially defined things from an
unelaborated generic unit;
(5) The inability of some implementations to implement generics where
freezing is piece-meal (certainly code-shared implementations, but others
also indicated problems);
(6) The inability of other implementations to implement the "freeze
everything in the generic if anything is" model;
(7) No sane model for "partially elaborating" a generic unit;
(8) The privacy issues that you discuss below.

The only solution that we looked at that gets close to working is the
limited view one, which you have repeatedly said you won't accept. For that
one *only* do the concerns about syntax come into play; none of the others
get close enough to working to even make that worth worrying about. We
thought for a while that the partial view idea that Tucker was persuing was
going to work, but then Erhard and Steve Baird blew it out of the water with
the staticness and primitive operations and partially defined items
problems.

...
> Yes, it breaks privacy.  But privacy is already broken
> without any generics, as I pointed out in an e-mail on
> June 24, 2004, which is included in AI95-00359-02/02
> (that is, ai-10359.txt):
...
> Of 4 compilers tested, only one correctly noted that this is illegal
> by 3.2.1(5).
>
> No change was made to the RM to fix this problem,
> so it's not clear to me that it's worth worrying about.

Please do not draw conclusions about subjects not discussed by the ARG. This
issue fell through the cracks (as many other issues have), because it was
filed on a mostly unrelated subject. Arguably, it falls under the Duff rule:
"The ARG is not in the business of answering random interesting questions."

Anyway, this is a very big deal to me. The check for 3.2.1(5) is
computationally very expensive. That because child units can be involved, so
you can't stop the checking until you've reached every leaf (or you have to
use a very expensive algorithm to figure out which units cannot be involved
in a loop). So you have to look at every component type, and the component
type of those types, and so on: you either end up doing the same checks many
times, or you have to do a global marking of all types so you can stop on
ones previously reached. *And* you have to do this check on every component
of type declaration, because it's likely to be too late if you don't: once
you're into an infinite loop, it's too late to recover.

I suspect that existing 3.2.1(5) checks don't recurse, and certainly don't
check outside of the current unit. Both of which are obviously wrong, given
this example.

And the privacy breakage is unacceptable. I would expect that you would hear
the same from Mr. Private. So I think a fix is worth having; certainly worth
investigating and discussing.

Moreover, this is fairly unlikely code to write; you have to stand on your
head to write it in a single unit. (It's somewhat more likely with child
units.) You want to make it a lot of prevalent: that will make trouble far
more likely. Two wrongs surely don't make a right!

...
> OK.  We would need to specify for each language-defined container whether it
> can be used cyclically.  User-defined ones are on their own (though I admit
> it's always sad to break privacy).

Then stop advocating breaking privacy, and figure out a good way to get that
information into the contract.

My thinking is that that is a property of the exported private type, so
there should be some indication of that in the private type declaration.
Something like:

    type List is private with indirection;

But I'm not sure what the rules on the full type should be. Perhaps the only
component types allowed would be by-copy types, or other "with indirection"
types.

The problem with this, however, is that it doesn't allow early instantiation
(all of the problems with partially declared, unelaborated entities would
still remain). The only kind of early instantiation that we could make work
was limited views, and that isn't what you want.

Tucker's idea works better that way, but my guess is it isn't going to fly;
both for the usability issues you noted in another message, and for the
definitional reasons I noted in my message.

So I continue to believe that your problem is intractable, given the rules
of Ada as they are or reasonably could be. The Duff language may have
different results (I'm sure it wouldn't need access parameters to fake "in
out" parameters for functions, for instance) - but we're talking about Ada.

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


Questions? Ask the ACAA Technical Agent