Version 1.3 of ais/ai-10359.txt

Unformatted version of ais/ai-10359.txt version 1.3
Other versions for file ais/ai-10359.txt

!standard 12.03 (12)          04-07-02 AI95-00359-02/02
!standard 12.03 (20)
!standard 13.14 (05)
!class amendment 04-04-02
!status work item 04-06-24
!status ARG Approved 6-1-4 04-06-17
!status work item 04-04-02
!status received 04-04-02
!priority Low
!difficulty Medium
!subject Deferring Freezing of a Generic Instantiation
!summary
To better support generic signature packages, and mutually dependent types that involve generic instantiations, it is proposed that a generic instantiation not cause freezing immediately if the generic is preelaborated.
For such an instantiation, no special freezing happens at the point of the instantiation, other than the freezing that is due to the elaboration of the declarations within the specification of the instantiation. Elaboration of the body of the instantiation is deferred until the first use of a two-part entity exported by the generic, or until a "general" freezing point, whichever occurs first.
An instantiation is illegal if its body would need to be elaborated at a place where the actual parameters are not all completely defined.
NOTE: This proposal is guaranteed to be upward compatible: the place where the body of an instance gets elaborated may change, but the elaboration of a preelaborated unit has no observable effect, so that's not a problem. All existing instantiations are legal, because they freeze their actual parameters, so surely these parameters are completely defined.
!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
(See summary.)
!wording
Change paragraph 12.3(12) as follows:
A generic_instantiation declares an instance; it is equivalent to the instance declaration (a package_declaration or subprogram_declaration) followed [immediately] by the instance body[, both at the place of the instantiation]. {The instance declaration is located at the place of the instantiation. The instance body is located immediately following the instance declaration if the generic is not preelaborated. If the generic is preelaborated, the instance body is located immediately prior the first of:
o the next reference to a subprogram, protected subprogram, or generic unit
declared within the instantiation;
o creation of an object of a type that does not have preelaboratable
initialization;
o the next non-instance body;
o the end of the nearest enclosing declarative_part or library_item.}
Change paragraph 12.3(20) as follows:
... Finally, the instance declaration [and body are] {is} elaborated. {The instance body is elaborated later, at the place where it (implicitly) occurs.}
Change paragraph 13.14(5) as follows:
o The occurrence of a generic_instantation causes freezing {except when the
generic is preelaborated}; also, if a parameter of [the] {an} instantiation {that causes freezing} is defaulted, the default_expression or default_name for that parameter causes freezing. {for an instantiation that does not cause freezing, the constructs of the instance declaration cause freezing according to the rules of this clause; at the place where the instance body (implicitly) occurs, it freezes the parameters of the instantiation, and the default_expressions or default_names for all defaulted parameter cause freezing.}
!example
(See problem.)
!discussion
Signature packages can be a very useful feature, but if they can't be instantiated in the generic that defines the abstraction, they become of much less use.
Generics in general can be very useful, but the freezing rules mean that they are not as powerful as cut-and-paste, since they can't be applied to private types before the private type is completely defined.
This proposal makes it possible for a generic instantiation to be used in more places than before, since it can be used with a private type before the type is completely defined, provided that the generic is preelaborated. As things stand now, it is often necessary to completely restructure things to be able to use a generic container as part of defining a private type.
This proposal is based on preelaborability, because the elaboration of a preelaborated unit has no visible effect, other than establishing that the entities it declares can be used (called, instantiated, activated). Therefore, moving the place where elaboration occurs has no effect, provided that it doesn't cause access-before-elaboration problems. To avoid such problems, the location of the instance body is guaranteed to always occur before any construct that could fail an Elaboration_Check. This has the nice property of maintaining the invariant that there is never any Elaboration_Check for entities exported by an instance.
Note that the rule about private types is necessary to prevent a privacy violation: a private type exported by an instance might contain tasks, in which case freezing that private type might activate tasks, and this activation might fail an Elaboration_Check.
Of course, it is possible for the instance body to be (implicitly) located at a place where some of the actual types are not completely defined, and that's problematic. We solve this by changing the freezing rules so that the instance body freezes the actual parameters. This may lead to compile-time errors with rather mysterious error messages, but hopefully these errors will be infrequent.
It's interesting to point out that, when the source code is modified, the location of the instance body is likely to move around, but this is not observable (except that it may cause compile-time errors in rare cases).
With this proposal, the following example extracted from the email discussion works as expected:
generic type Elem is private; with function Code (I : Elem) return Natural; type Elem_Array is array (Positive range <>) of Elem; package Array_Hashing is function Hash (Arr : Elem_Array) return Natural; end Array_Hashing;
package body Array_Hashing is type Nat_Mod is mod Natural'Last; function Hash (Arr : Elem_Array) return Natural is Res : Nat_Mod := 1; begin for I in Arr'range loop Res := Res*3 + Nat_Mod(Code(Arr(I))); end loop; return Natural(Res); end Hash; end Array_Hashing;
package User is type Something is private; function Count (A : Something) return Natural; type Array_of_Something is array (Positive range <>) of Something; package My_Hash is new Array_Hashing (Something, Count, Array_of_Something); NULL_HASH : constant Natural; private type Something is range 0 .. 200; NULL_HASH : constant Natural := My_Hash.Hash ((1..0 => 0)); end User;
The instance body for My_Hash is located immediately before the call to My_Hash.Hash, so this call doesn't raise Program_Error. The instance body freezes Something, but this type is already completely defined so there is no illegality.
--!corrigendum 13.14(05)
!ACATS test
An ACATS test should be created for this feature.
!summary
!appendix

From: Tucker Taft
Sent: Saturday, June 19, 2004  7:45 AM

I thought some more about the impact of "piecemeal"
freezing of generic instances in the face of shared
generics.  I became convinced that there is a simpler
solution which avoids the implementation earthquake
that Randy predicted.

The simpler solution would be:

    1) Leave the semantic rules of 12.3 untouched, since
       if something is preelaborable, then exactly "when" it is
       actually elaborated is supposed to be invisible semantically.

    2) Don't just require the generic to be preelaborated, instead
       require the generic_instantiation to be preelaborable.
       This might not be any different, but it seems safer.
       NOTE: I am wondering whether AI-161 on
        "preelaborable_initialization" might need some explicit
        words in 12.5.1 saying that if a formal type has
        preelaborable initialization, then so must the actual.

    3) Change the freezing rules for generic instances so that
       a preelaborable generic instance is not frozen until
       some name refers to an entity declared inside the instance
       is frozen.

    Hence, we would eliminate the changes to 12.3,
    and change 13.14 as follows:

    Replace 13.14(5) with:
        * The occurrence of a generic_instantiation causes
          freezing, unless it is preelaborable (see 10.2.1).

    Add after 13.14(15):
        * At the place where an entity is frozen, if the entity
          is declared inside a generic instance, then the corresponding
          generic_instantiation causes freezing.

        * At the place where a generic_instantiation causes freezing,
          if a parameter of the instantation is defaulted, the
          default_expression or default_name for that parameter
          causes freezing.

I don't believe this is any harder to implement for non-shared
generics (it might be significantly simpler), and I believe for
shared generics, it could make a huge difference in implementability.

Essentially, we just ignore a preelaborable generic instantiation
as far as freezing goes, and freeze it when there is a reference
to an entity declared inside the instance.  We don't need to look
"inside" the generic at the point of instantiation, we can still
treat it pretty much like a black box.

On a somewhat related topic, Pascal mentioned that the RM2000 rule
"An implicit call freezes the same entities that would be frozen
by an explicit call" is a pain for them.  This seems to be the
only rule that relates to dynamic semantics.  This also seems to
violate the "black box" view I just mentioned above.  I am wondering
whether we can replace this new rule by something that relates
more to the "surface" features of the construct involved.  I presume
the problem is that we are trying to get Initialize, Adjust,
and Finalize frozen (are there any others?).  Alternatively,
perhaps this is all unnecessary now, if we say that *all* the
primitive operations of a tagged type are frozen when the tagged
type is frozen.

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

From: Pascal Leroy
Sent: Sunday, June 20, 2004  5:45 AM

>         * At the place where an entity is frozen, if the entity
>           is declared inside a generic instance, then the corresponding
>           generic_instantiation causes freezing.

This rule is one of the key differences between alternatives 1 and 2 of
the AI, and it is unacceptable to me.

Each time we freeze an entity, it means that we need to look if that
entity happens to live in an instance and if so freeze the instance.  This
hairs up the freezing code considerably, and more importantly all this
business of searching for an instance is going to be extremely expensive
in terms of compilation time.

It seems to me that Ed had similar concerns, although I won't try to put
words in his mouth.

One of the key properties of alternative 2 is that, once you have
macro-expanded the generic spec (sorry, Randy) you can just fallback on
the normal freezing code.  If this invariant cannot be maintained, I am
not interested in solving the problem in the first place.

I am open to the notion of re-discussing the two alternatives of this AI
at the next meeting, but I won't let you change alternative 2 until it
looks like the twin of alternative 1.

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

From: Robert Dewar
Sent: Sunday, June 20, 2004  6:43 AM

I strongly agree with Pascal on this point.

Note also that if implementors are not interested in solutions that are
proposed, 'then they won't get implemented, regardless of what the standard
says.

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

From: Tucker Taft
Sent: Sunday, June 20, 2004  8:01 AM

> Each time we freeze an entity, it means that we need to look if that
> entity happens to live in an instance and if so freeze the instance. ...

I don't think this new alternative is as different from yours as it
sounds.  My goal was to try to make it as similar as possible.
Although this alternative is phrased in terms of freezing, yours
required that every call and every creation of an object of
a non-preelaborable type be checked to see whether the entity
is from an instance whose freezing/elaboration was postponed.
Calls and object creations are both freezing occurrences.

I also admit that I am quite disappointed that you and Robert
saw this as some kind of attempt to screw the implementors, or
turn your proposal back into my earlier suggestion.  I have
absolutely no ulterior motive here.  I am only trying to give the
shared generics folks (RR Software and Irvine) some consideration.

My sense was that if you look at the actual work involved, the
shift I am proposing is modest, and might actually be
a simplification.  For example, it is not uncommon for entities
to have some kind of indication of their source position.  In
our compiler, objects from instances need a somewhat special
source position, since we want to be able to report their original
location within the generic, as well as the location of the
instance(s) that brought them into being.  If you are doing
macro expansion, then it might be easy to somehow mark entities
as being the result of a generic instance.  If this is so, then
there would be little extra overhead in noticing a freezing reference
to an unfrozen entity from an instance, and only then taking the
time to identify the instance(s) involved.  As one possibility,
the flag that indicates whether or not an entity is frozen could
be a three-state flag, unfrozen, unfrozen from an instance, and
frozen.

 > ... I am open to the notion of re-discussing the two alternatives of this AI
> at the next meeting, but I won't let you change alternative 2 until it
> looks like the twin of alternative 1.

I am not trying to do anything of the sort.  I very much like your
approach of using preelaboration as the trigger, and not
"hairing" up the user's model.  I think there is no need in
any case to talk about postponing the elaboration of the
instance body, since there is no visible semantic effect
associated with it, presuming the instance is preelaborable.
What remains is then deciding which events cause the (rest of
the) instance to be frozen.  In your proposal, it was events that might
result in an access before elaboration.  The first such event would
result in the entire instance being frozen and the body being
elaborated.  In this slight shift, it is any freezing reference that
triggers the freezing of the entire instance, and might be a
convenient place to actually do instance body elaboration, though
it doesn't really matter, since the elab is invisible.

My instinct is that the work involved in noticing these "triggering"
events is similar, and if anything, freezing is a little easier,
since it is already something associated with static semantics
and legality rules.  Access before elaboration relates more to
dynamic semantics, and that makes it sound more like the annoying
"implicit call" freezing rule you were bemoaning during the meeting.

Trying to do freezing piecemeal seems like a real burden to
shared-generics implementations, because their whole approach
seems based on building an instance descriptor, and until that
is done, they really can't say much about the entities inside
the instance.  Building an instance descriptor almost certainly
requires freezing all the actuals, which is the one thing we
don't want to do until necessary.  So piecemeal freezing really
puts the shared-generic implementor into a nearly impossible
situation.

Both your proposal and this one do eventually
freeze everything in the instance that is as yet unfrozen, so
the ability to do that will exist.  The difference is whether
freezing occurrences prior to that are permitted, and exactly
what events trigger the whole-instance freezing.  My sense is
that the events are very similar, and allowing a few freezing
occurrences but not all to occur piecemeal adds huge burden
to the shared-generic implementor, with little benefit to
either the user or to the macro-expansion implementor.

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

From: Robert A. Duff
Sent: Sunday, June 20, 2004  1:40 PM

I think it is a mistake to base the solution to this problem on pragma
Preelaborate, as proposed by alternative AI-359-02.

The restrictions on preelaborability are really quite severe, and are
also rather arbitrary.  For example, you can't use the single most
important abstraction tool invented in the entire history of programming
-- namely, the subroutine call.

One case where I would very badly like to solve this problem in my own
code involves a generic Sequences package (something like the new
proposed Vectors thing).  There are a huge number of places in my code
where there's a Thing which is defined recursively to contain sequences
of Things.  I want to say:

    type Thing is private;
    package Thing_Sequences is new Sequences(Thing); -- illegal!
    type Thing_Sequence is new Thing_Sequences.Sequence;
    ... -- some exported operations refer to type Thing_Sequence.
private
    type Thing is
        record
            Sub_Things: Thing_Sequence;
            ...
        end record;

Unfortunately, generic package Sequences is not preelaborable, and could
not be made preelaborable without damaging the structure of the program,
or reducing its functionality.

Each instance of Sequences "registers" itself in another data structure,
for the purpose of later printing out statistics about memory usage and
the like.  It does this by declaring an object of a controlled type in
the package body.  That's not preelaborable.

I certainly do not care precisely when the body of instance
Thing_Sequences is elaborated.  I do not want to abide by a whole bunch
of onerous restrictions, just to ensure that such elaboration is
invisible -- it's *not* invisible, but I still don't care when it
happens.

----------------

The library-level elaboration rules were badly broken in Ada 83.
We tried to fix them in Ada 95 by adding pragmas Elaborate_All,
Elaborate_Body, Preelaborate, and Pure.  But we didn't fix the
underlying problems, and the rules for these pragmas are a mess.
GNAT has a better solution, although still not perfect, and of course
not standard.  I think a perfect solution is in fact impossible without
major incompatible changes to the language.

Let's not exacerbate the problems by basing AI-359 on this mess.

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

From: Pascal Leroy
Sent: Monday, June 21, 2004  5:02 AM

Bob groaned:

> Each instance of Sequences "registers" itself in another data
> structure, for the purpose of later printing out statistics
> about memory usage and the like.  It does this by declaring
> an object of a controlled type in the package body.  That's
> not preelaborable.

That's preelaborable unless the controlled type has a user-defined
Initialize routine.  See AI 161.

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

From: Robert A. Duff
Sent: Monday, June 21, 2004  7:34 AM

It does.  That's how it "registers" itself.  That is, Initialize puts it
onto a doubly-linked list in some other package.

The other thing I should point out is that preelaborability is
transitive -- one little thing poisons all the clients.  In the case of
my Sequences package, it depends on some storage management stuff
(based on System.Storage_Pools) and that stuff has all kinds of
non-preelaborable code.

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

From: Pascal Leroy
Sent: Monday, June 21, 2004  10:18 AM

Tuck wrote:

> Both your proposal and this one do eventually
> freeze everything in the instance that is as yet unfrozen, so
> the ability to do that will exist.

Agreed, and I don't like that too much in either case.

> What remains is then deciding which events cause the (rest of
> the) instance to be frozen.  In your proposal, it was events
> that might result in an access before elaboration.  The first
> such event would result in the entire instance being frozen
> and the body being elaborated.  In this slight shift, it is
> any freezing reference that triggers the freezing of the
> entire instance, and might be a convenient place to actually
> do instance body elaboration, though it doesn't really
> matter, since the elab is invisible.

My proposal was actually trying to help the shared generics folks, the
assumption being that it is the events that are executing code or
referencing declarations in the body that are really obnoxious to them.
Maybe that was misguided, since Randy thought the problem was
intractable.

Ignoring the shared generic business for a moment, what I would really
like to say is this:

1 - The generic specification freezes piecemeal, as if it was
macro-expanded by hand.

2 - The body elaboration takes place at the next general freezing point
(i.e., body or end of declarative part).  Note that even though body
elaboration is largely immaterial for a preelaborable unit, it still has
the effect of setting the elaboration bits, so we must specify when it
happens.  If there are several instances, their bodies are elaborated in
the same order as their specs.

3 - Any subprogram call/generic instantiation/task activation taking
place between the instantiation and the point where the body gets
elaborated results in a Program_Error.

I believe that item #1 is only problematic for implementations that do
not expand the spec, i.e. that share both the spec and the body.  I
don't know if any such implementation exists: we used to do just that,
but it became completely impractical in Ada 95 where you have to recheck
all sorts of rules on the instance.

Item #3 is certainly problematic for shared generics, because if you
don't even have an instance descriptor it's hard to make a call into the
instance; chances are that you would dump a core before raising P_E.
One option might be to make *illegal* all the constructs that could
result in an access-before-elaboration check between the spec and the
body of the instance.  This might actually be the best approach, as it
doesn't mess with freezing.

It would be good to hear what Randy thinks, assuming that he managed to
fly back home without getting stranded again.

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

From: Randy Brukardt
Sent: Wednesday, June 23, 2004  10:55 PM

Pascal wrote:

...
> I believe that item #1 is only problematic for implementations that do
> not expand the spec, i.e. that share both the spec and the body.  I
> don't know if any such implementation exists: we used to do just that,
> but it became completely impractical in Ada 95 where you have to recheck
> all sorts of rules on the instance.

Janus/Ada still shares the spec as well as the body. The "recheck in the
instance" rules are of course done outside of the spec; anything dynamic
about those rules (such as the tag of a type extension) is included in the
generic descriptor. (One way to think of such things is that they become
additional generic formal parameters; for instance, a tagged type extension
in a generic spec. becomes a generic formal tagged private or derived type
[same as the formal it comes from] with the actual type declared at the
point of the instance.

> Item #3 is certainly problematic for shared generics, because if you
> don't even have an instance descriptor it's hard to make a call into the
> instance; chances are that you would dump a core before raising P_E.
> One option might be to make *illegal* all the constructs that could
> result in an access-before-elaboration check between the spec and the
> body of the instance.  This might actually be the best approach, as it
> doesn't mess with freezing.

That might be the seeds of an appropriate idea.

> It would be good to hear what Randy thinks, assuming that he managed to
> fly back home without getting stranded again.

Well, I did manage to miss the plane in Frankfurt (by 3 minutes!) thanks to
too many planes landing at once. But I was able to get a flight from
Amsterdam to Minneapolis to Madison -- the only problem being that I had to
go on standby for the flight from Frankfurt to Amsterdam. After 20
hair-raising minutes of waiting, all three standby passengers were boarded,
and I ended up getting home only about an hour late. And my suitcase even
managed to make the trip with me. A lot better than the outbound trip.

----

Anyway, back to the problem. I still think that the appropriate solution is
to be found in the "forward" instance declaration that I proposed in the
past. The major problem with Tucker's pragma solution is that there is no
indication of the "forward" nature of the instance; I think a bit of syntax
would be the better solution there.

After all, the primary problem to be solved is making an instance visible
that 'naturally' has to go in the private part. (Quiet Bob, I'll get to
recursive data structures later...)

That is, we want the clients of a package to be able to use an instance
whose actuals can't be frozen in the visible part. That looks something
like:

   package Example is
       type Priv is private;
       -- We want the instance to appear here to clients:
       package Inst is new Gen (Priv, ...);
   private
       type Priv is ...;
       -- But the instance has to go here in order that the actuals can be
frozen:
       package Inst is new Gen (Priv, ...);
   end Example;

Pascal's suggestion of a legality rule is essentially what I proposed way
back when.

Let me try to explain a bit what I have in mind.

   package Example is
       type Priv is private;
       package Inst is deferred new Gen (Priv, ...); -- Visible to clients
only.
   private
       type Priv is ...;
       package Inst is new Gen (Priv, ...); -- Real instance goes here.
   end Example;

I think that some syntax is best to express this idea, even if that makes it
seem a bit heavier than it otherwise would.

Now, what can you do with the deferred instance between the client
declaration and the "real" instance? The easiest rule is nothing at all:
referring to the name Inst would be illegal. That would be cheaper to
implement than anything else suggested!

The semantics would be simply that the generic instance would appear for
visibility purposes at the point in the declarative list where the deferred
instantiation is written. OTOH, for freezing and elaboration purposes, it wo
uld appear at the point that it was given again.

Note that the second occurrence could be (probably should be) some
shorthand, or even a pragma, in order to avoid conformance issues.

Now, Bob is going to complain about recursive data structures. I can't get
too excited about those that don't include an explicit access type
somewhere, because such structures are implicitly violating the contract of
the generic unit (by depending on its implementation - that is, the fact
that it has some indirection in its implementation). But it would seem
useful to support explicit access types.

So a slightly more complex alternative would be to support the initial
instance as a limited view (just like limited with) between the deferred
instance and the full instance. That would mean that any types exported from
the instance are treated as incomplete, the package name can be referenced,
and that's it. (No use clauses!) That also would not require any freezing or
elaboration to work.

So an example like (assuming Gen declares List_Type):

   package Example is
       type Priv is private;
       package Inst is deferred new Gen (Priv, ...); -- Visible to clients
only.
   private
       type Priv is record
           List : access Inst.List_Type; -- OK if incomplete.
           ...
       end record;
       Obj : Inst.List_Type; -- Illegal (obviously).
       elaborate package Inst; -- Instance freezes and is elaborated here.
   end Example;

This feature only has to work within a single compilation unit, since it
really is about deferring freezing and elaboration to a later point. Other
units don't care about this units freezing or elaboration order! Therefore,
problems might as well be checked statically; there's no value to raising an
exception.

I think this solves the problem without breaking everything in sight. The
only problem that I see is that adding syntax will annoy some people. But if
we need a first class feature, it ought to *look* like a first class
feature.

(Bob probably will argue that instances should always work this way, and he
would be right if there wasn't any investment in the existing language.
Clearly Duff 2010 should work this way. But silent incompatibilities cannot
be tolerated for a marginal improvement to the language, so Ada 2005 cannot
default to this behavior.)

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

From: Robert A. Duff
Sent: Thursday, June 24, 2004  10:39 AM

Randy said:

> Now, Bob is going to complain about recursive data structures. I can't get
> too excited about those that don't include an explicit access type
> somewhere, because such structures are implicitly violating the contract of
> the generic unit (by depending on its implementation - that is, the fact
> that it has some indirection in its implementation).

This made me think that the rule in 3.2.1(5), which says "A given type
shall not have a subcomponent whose type is the given type itself."
needs to be fixed for AI-359.  In particular, we need to add the usual
"In addition to the places where Legality Rules normally apply (see
12.3), this rule applies also in the private part of an instance of a
generic unit."  I think with the current rules, the freezing rules
prevent a type T declared in a generic package spec from containing a
component of a formal type, while the actual type contains a component
of type T.  But if we relax the rules (in any of the proposed ways), it
seems like that will no longer be true.  Am I right?

If so, will Pascal wave the "breaking private parts" flag?

I tried this example:

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;

It caused both GNAT and AdaMagic to crash.  :-(  GNAT crashed even
without the "X: T1;".  AdaMagic compiled it happily (no errors) without
the "X: T1;".

I'm curious what other compilers do with it.  Is it not illegal by
3.2.1(5), and does this not already break privacy (causing confusion for
at least two compilers)?

This seems like a minor side issue, and should not affect which proposal
we choose for AI-359.

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

From: Randy Brukardt
Sent: Thursday, June 24, 2004   6:55 PM

> It caused both GNAT and AdaMagic to crash.  :-(  GNAT crashed even
> without the "X: T1;".  AdaMagic compiled it happily (no errors) without
> the "X: T1;".
>
> I'm curious what other compilers do with it.  Is it not illegal by
> 3.2.1(5), and does this not already break privacy (causing confusion for
> at least two compilers)?

Janus/Ada went into an infinite loop. :-( I killed it after 45 seconds.

It's probably illegal, but it is extremely hard to check in general (you'd
have to construct a graph of all of the types in your program - certainly
something that we're not going to try to do!). I believe that we put in some
hack in order to pass the ACATS test on this rule, but made no attempt to
check this in general.

This seems like a fine case to consider as a pathology, and not worry about
it. But I could be convinced outwise.

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

From: Pascal Leroy
Sent: Friday, June 25, 2004   4:32 AM

Bob wondered:

> I'm curious what other compilers do with it.  Is it not
> illegal by 3.2.1(5), and does this not already break privacy
> (causing confusion for at least two compilers)?

Here is the output of Apex:

11:18:27 >>> Line 15: X1 : Sub.T2;
11:18:27 *** Sub.T2 contains a circularity [RM_95 3.2.1(5)]
11:18:27 >>> Line 17: X : T1;
11:18:27 *** T1 contains a circularity [RM_95 3.2.1(5)]

So at least one implementer seems to agree that this is illegal by
3.2.1(5).  And yes, it breaks privacy, but that's an absurd program, and
the privacy breaking only occurs in a single unit.  Yawn.

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

From: Robert A. Duff
Sent: Thursday, June 24, 2004  10:56 AM

Randy wrote:

> Anyway, back to the problem. I still think that the appropriate solution is
> to be found in the "forward" instance declaration that I proposed in the
> past. The major problem with Tucker's pragma solution is that there is no
> indication of the "forward" nature of the instance; I think a bit of syntax
> would be the better solution there.

Randy's idea of marking the "first" instantiation as having a deferred
body seems perfectly acceptable.  I think a good way to look at it is
that there are two "instantiations" -- the spec and the body.  The spec
instantiation can be made public, and the body instantiation does the
actual freezing and body elaboration.

However, I don't like some of the restrictions proposed.
For example:

>    package Example is
>        type Priv is private;
>        package Inst is deferred new Gen (Priv, ...); -- Visible to clients
> only.
>    private
>        type Priv is ...;
>        package Inst is new Gen (Priv, ...); -- Real instance goes here.
>    end Example;
>
> I think that some syntax is best to express this idea, even if that makes it
> seem a bit heavier than it otherwise would.
>
> Now, what can you do with the deferred instance between the client
> declaration and the "real" instance? The easiest rule is nothing at all:
> referring to the name Inst would be illegal. That would be cheaper to
> implement than anything else suggested!

Not as cheap as leaving the language broken!

I think that restriction is onerous.  Even if you don't have mutually
recursive data types, you might want to export a procedure that has a
parameter of type Priv and another parameter of type
Inst.Data_Structure.

> Note that the second occurrence could be (probably should be) some
> shorthand, or even a pragma, in order to avoid conformance issues.

It seems to me that the "shorthand" could be nothing at all.
That is, if you mark the spec instantiation as "deferred",
then the second occurrence (what I like to think of as the
"body instantiation") occurs implicitly at the next relevant
freezing point.

> Now, Bob is going to complain about recursive data structures. I can't get
> too excited about those that don't include an explicit access type
> somewhere, because such structures are implicitly violating the contract of
> the generic unit (by depending on its implementation - that is, the fact
> that it has some indirection in its implementation). But it would seem
> useful to support explicit access types.

Well, certainly Ada requires mutually recursive data types to have an
access type somewhere in the cycle, and I'm not proposing to change
that.  The kinds of examples we're talking about have a type T,
which contains a component of type Instance.Data_Structure,
which contains components of the formal type, and the corresponding
actual is T.  There are a number of places where the programmer can
insert the extra access type:

    - You can pass access-to-T instead of T as the formal.
    - You can use access-to-Data_Structure, declared in the generic.
    - You can declare access-to-Instance.Data_Structure
      in the package where T is declared.  Either visible or private.

Whatever the rules are, they should allow the programmer complete
freedom to choose any of these.  There are various reasons, involving
storage management, and other annoying restrictions of Ada, to choose
one over the other.  (Example of annoying restriction: I've got some
code that (evilly) exports an access type that ought to be private,
just so clients can have discriminants of that type.)

> So a slightly more complex alternative would be to support the initial
> instance as a limited view (just like limited with) between the deferred
> instance and the full instance. That would mean that any types exported from
> the instance are treated as incomplete, the package name can be referenced,
> and that's it. (No use clauses!) That also would not require any freezing or
> elaboration to work.

Still too restrictive, I think.  It disallows exporting a procedure that
has a parameter of the type in the instance.

> So an example like (assuming Gen declares List_Type):
>
>    package Example is
>        type Priv is private;
>        package Inst is deferred new Gen (Priv, ...); -- Visible to clients
> only.
>    private
>        type Priv is record
>            List : access Inst.List_Type; -- OK if incomplete.
>            ...
>        end record;
>        Obj : Inst.List_Type; -- Illegal (obviously).
>        elaborate package Inst; -- Instance freezes and is elaborated here.
>    end Example;

If you let the "second" (body) instance be implicit, then user's won't
have to worry about that.  It will just happen at the "right" place.

> This feature only has to work within a single compilation unit, since it
> really is about deferring freezing and elaboration to a later point. Other
> units don't care about this units freezing or elaboration order! Therefore,
> problems might as well be checked statically; there's no value to raising an
> exception.

OK.

> I think this solves the problem without breaking everything in sight. The
> only problem that I see is that adding syntax will annoy some people. But if
> we need a first class feature, it ought to *look* like a first class
> feature.
>
> (Bob probably will argue that instances should always work this way, and he
> would be right if there wasn't any investment in the existing language.
> Clearly Duff 2010 should work this way. But silent incompatibilities cannot
> be tolerated for a marginal improvement to the language, so Ada 2005 cannot
> default to this behavior.)

I don't think it's a "marginal improvement", since I have a lot of ugly
code working around this problem.  But I'm willing to give in on the
compatibility issue, if folks thinks it's too incompatible.  It just
means that everybody should adopt a coding style in new code: "Always
use the 'deferred' keyword in generic instantiations."

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

From: Robert I. Eachus
Sent: Thursday, June 24, 2004  10:39 AM

Randy Brukardt wrote:

>Let me try to explain a bit what I have in mind.
>
>   package Example is
>       type Priv is private;
>       package Inst is deferred new Gen (Priv, ...); -- Visible to clients
>only.
>   private
>       type Priv is ...;
>       package Inst is new Gen (Priv, ...); -- Real instance goes here.
>   end Example;
>
>I think that some syntax is best to express this idea, even if that makes it
>seem a bit heavier than it otherwise would.
>
>Now, what can you do with the deferred instance between the client
>declaration and the "real" instance? The easiest rule is nothing at all:
>referring to the name Inst would be illegal. That would be cheaper to
>implement than anything else suggested!

I like this idea very much.  I would even be willing to say that any
reference to Inst between the public declaration and the private
instantiation would result in ABE (Program_Error).  That probably means
less (no) work on things like overloading rules.  I did a little Norm
Cohen like thinking about which existing reserved words could be used.
The best I could come up with was:

   package Example is
       type Priv is private;
       declare package Inst is new Gen (Priv, ...);
   private
       type Priv is ...;
       package body Inst is new Gen (Priv, ...);
   end Example;

I like the idea of adding deferred as a reserved word instead.  But the word
body to indicate that the instance is a completion has promise.

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

From: Randy Brukardt
Sent: Thursday, June 24, 2004   7:50 PM

Bob Duff wrote:

> Randy's idea of marking the "first" instantiation as having a deferred
> body seems perfectly acceptable.  I think a good way to look at it is
> that there are two "instantiations" -- the spec and the body.  The spec
> instantiation can be made public, and the body instantiation does the
> actual freezing and body elaboration.

That isn't quite the right model. *All* of the freezing and elaboration
occurs at the second point (including elaboration of the specification). The
whole idea is to be able to use the existing rules and implementations for
the freezing and elaboration.

> However, I don't like some of the restrictions proposed.

Fair enough. The first one was a straw man anyway. Let's just look at the
limited view idea....

...
> > Note that the second occurrence could be (probably should be) some
> > shorthand, or even a pragma, in order to avoid conformance issues.
>
> It seems to me that the "shorthand" could be nothing at all.
> That is, if you mark the spec instantiation as "deferred",
> then the second occurrence (what I like to think of as the
> "body instantiation") occurs implicitly at the next relevant
> freezing point.

That doesn't really work. Readers of the program will need an explicit
indication of the point where the restrictions (whatever they are) are
lifted. And they'll want them lifted before the end of the scope in at least
some cases.

Moreover, we don't want ordinary users to have to understand freezing in
order to understand the dynamic semantics of their program. After all, we in
the ARG hardly understand freezing!

...
> > So a slightly more complex alternative would be to support the initial
> > instance as a limited view (just like limited with) between the deferred
> > instance and the full instance. That would mean that any types exported
from
> > the instance are treated as incomplete, the package name can be
referenced,
> > and that's it. (No use clauses!) That also would not require any
freezing or
> > elaboration to work.
>
> Still too restrictive, I think.  It disallows exporting a procedure that
> has a parameter of the type in the instance.

That not really true. A limited view exports tagged incomplete types where
appropriate, and those can be used as parameters. And you can always use
access parameters. You couldn't use a parameter of an untagged type in this
case, but that's one of the problematic cases (for macro-expanded
implementations) that we're trying to avoid. The standard containers are now
tagged (and other large abstractions should be, as well), so I don't think
that the limitation would be too serious in practice.

Using yet another syntax suggestion:

   package Example is
       type Priv is private;
       limited package Inst is new Gen (Priv, ...); -- Visible to clients
only.
       procedure Check_and_Insert (Item : in Priv; List : Inst.List_Type);
           -- OK if List_Type is tagged.
   private
       type Priv is record
           List : access Inst.List_Type; -- OK if incomplete.
           ...
       end record;
       Obj : Inst.List_Type; -- Illegal (obviously).
       not limited package Inst; -- Instance freezes and is elaborated here.
   end Example;

> If you let the "second" (body) instance be implicit, then user's won't
> have to worry about that.  It will just happen at the "right" place.

As mentioned before, that really doesn't work. We don't want significant
code to change behavior just because someone added a declaration somewhere.

Moreover, the whole reason this AI is still open is because implementers
have major problems with changing the freezing rules for generic units.
Every proposal has required a "touch something and freeze the whole
instance" sort of rule, and Pascal and Ed indicated serious heartburn with
that idea. Similarly, the "freeze as if macro expanded" rules give *me*
heartburn, because it means separating "solidification" (as Tucker called
it) from freezing - that is, we determine the representations of things when
the generic unit's declarations are frozen. While that's not strictly
correct, you cannot tell the difference in Ada 95 -- and that is wholly
intentional. (I screamed to patch any holes where you could tell the
difference.)

Anyway, the whole idea of providing an explicit location for the real
instance and for using a limited view of the initial instance is to
eliminate freezing from the discussion (since no agreement can be reached
there) -- rather, those rules are unchanged. And elaboration is also
unchanged.

...
> I don't think it's a "marginal improvement", since I have a lot of ugly
> code working around this problem.  But I'm willing to give in on the
> compatibility issue, if folks thinks it's too incompatible.  It just
> means that everybody should adopt a coding style in new code: "Always
> use the 'deferred' keyword in generic instantiations."

That would only make sense in package specifications (it should be illegal
in library-level instantiations, 'cause where would it be deferred to?).

One additional point on compatibility that I forgot last night: someone
indicated that they had seen code which used generic instantiation to get a
body to execute in a declarative part. (Precisely why that was necessary
wasn't explained.) An instantiation is the only way to do that -- which is
why we can't change the location of elaboration of that body!

---

The biggest advantage of using "limited view" for the restrictions is that
we can piggyback on the support for that in the compiler (I'm presuming that
support for "limited with" will be a priority for everyone). In one model,
at least, that would just be an indication on the instantiation name - there
wouldn't need to be any other special code.

The 'limited' instantiation would be expanded in the symboltable in the
normal manner; the only difference is that the 'limited view' indicator
would be set on the instantiation unit name.

When the full instantiation is encountered, the 'limited view' indicator
would turned off, freezing would be done, and the code for the instance
would be generated.

---

The only problem I see with this so far is the terminology for the two parts
of the instantiation. Let's try some ideas:

   limited package Inst is new Gen (Priv, ...); -- Limited instance.
   not limited package Inst; -- Non-limited completing instance.

   limited package Inst is new Gen (Priv, ...); -- Limited instance.
   full package Inst; -- Full (completing) instance.

Since the 'initial' part of the instance is normal outside of the package
itself, it's a bit weird to call it 'limited' (as above) or 'partial'.

Robert Eachus suggested:

   package Inst is deferred new Gen (Priv, ...); -- Deferred instance.
   package body Inst; -- Instance body (but not really)

which seems ambiguous (we don't want to repeat the parameters!) and
misleading (because both the spec and the body are elaborated at this
point).

   package Inst is deferred new Gen (Priv, ...); -- Deferred instance.
   elaborate package Inst; -- Instance elaboration point.

or, using a pragma:

   package Inst is deferred new Gen (Priv, ...); -- Deferred instance.
   pragma Elaborate (Inst); -- Instance elaboration point (but reuses a
pragma name)

(In the pragma case, omitting it would mean that it happened at
end-of-scope, which would get some of Bob's semantics back.)

If you don't like 'deferred':

   package Inst is new Gen (Priv, ...) with out elaboration; -- Deferred
instance.
   elaboration of package Inst; -- Instance elaboration point.

<Grin>

Another idea would be to call the initial instantiation a "generic
interface":

   package Inst is new interface of Gen (Priv, ...); -- Generic interface
   pragma Complete(Inst);

or
   package Inst is new interface of Gen (Priv, ...); -- Generic interface
   complete package Inst;

Nothing looks wonderful here. Sigh.

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


Questions? Ask the ACAA Technical Agent