!standard 12.5(3) 08-10-24 AI05-0074-3/00 !class Amendment 08-10-24 !status work item 08-10-24 !status received 08-10-21 !priority Medium !difficulty Hard !subject Deferred instance freezing !summary !problem Ada 95 provides formal package parameters. One way of using these parameters is to define a "signature" for a class of abstractions, such as all set abstractions, or all physical unit abstractions, and then build a new generic abstraction on top of the original class of abstractions using this signature as the template for a formal package parameter. Unfortunately, it is difficult to use signatures because of the fact that an instantiation freezes all of its actual parameters. For example: Given the signature for a set abstraction: generic type Element is private; type Set is private; with function Size(Of_Set : Set) return Natural is <>; with function Union(Left, Right : Set) return Set is <>; with function Intersection(Left, Right : Set) return Set is <>; with function Empty return Set is <>; with function Unit_Set(With_Item : Element) return Set is <>; with function Nth_Element(Of_Set : Set) return Element is <>; package Set_Signature is end; ... we could define a generic that required some set abstraction, but it didn't care which one so long as it implemented the above signature: generic with package Base_Set is new Set_Signature(<>); package Layered_Abstraction is type Cool_Type(Set : access Base_Set.Set) is limited_private; procedure Massage(CT : in out Cool_Type; New_Set : Base_Set.Set); ... end Layered_Abstraction; Now if we want to define a set type and provide the pre-instantiated signature for it, we run into trouble: generic type Elem is private; with function Hash(El : Elem) return Integer; package Hashed_Sets is type Set is private; function Union(Left, Right : Set) return Set; ... package Signature is new Set_Signature(Elem, Set); private type Set is record ... end record; end Hashed_Sets; The problem is that we can't do the instantiation of Set_Signature where we would want to do so, because the instantiation freezes the type "Set" prematurely. A similar problem occurs when a type wants to include a pointer to a container based on the type being defined. For example: package Expressions is type Expr_Ref is private; package Expr_Sequences is new Sequences(Expr_Ref); -- Freezing trouble here! type Seq_Of_Expr is access Expr_Sequences.Sequence; function Operands(Expr : Expr_Ref) return Seq_Of_Expr; ... private type Expression; -- completion deferred to body type Expr_Ref is access Expression; end Expressions; Here we have a case where we want to instantiate a generic using a private type, and use the results of the instantiation as the designated type of an access type, which is in turn used as a parameter or result type of an operation on the private type. Unfortunately, we can't instantiate the "Sequences" generic with Expr_Ref, since it is private. !proposal The general idea is that for a package instance with an actual type that is not yet completely defined: 1) Fine-grained freezing is performed for the expanded spec of the instance, as if the spec had been expanded by hand. 2) The elaboration of the instance body is deferred until some point after the actual types are completely defined. Statically, the general freezing associated with the instance body is also deferred until this point. 3) The runtime check that the generic body has been elaborated is performed when the instance body is elaborated, not when the instance spec is elaborated. It seems to me that the generic ought to have some indication that the formal type is intended to be used in this way. Otherwise, a change such as, for example, adding Null_Vector : constant Formal_Type_Array (1 .. 0 => <>); to the private part of the generic could cause a previously-legal instance to be rejected. If it is intended that a formal type should be usable in this way, then that ought to be included as part of the contract and violations should be detected when compiling the generic, not the instance. So today's approach is to define a pragma, May_Be_Partial, which applies to a formal private type (or to a formal derived type with a private extension) of a generic package. (Is there any justification for messing around at all with the rules for generic subprograms? I don't know of any.) Obviously the name of the pragma is subject to change but "May_Be_Partial" seems better than "Has_Polka_Dots" for today's discussion. The only effect this pragma has when compiling a generic is to disallow uses of the type in the generic spec (including the private part) which would freeze the formal type or otherwise require that the formal type be completely defined. This example would be illegal because of the pragma: generic type T is private; pragma May_Be_Partial (T); package G is X : T; end G; When compiling an instance, the pragma allows the corresponding actual type to be a type which is not yet completely defined (but not an incomplete type). The (static) freezing and (dynamic) elaboration associated with the instance body occurs at the earliest point after the freezing/elaboration of the instance spec where all of the actual types of the instance are completely defined. This coincides with the existing static and dynamic semantics in all cases which are legal according to the existing rules (strictly speaking, in order to get this equivalence it would also be necessary to add an implementation permission to the effect that if an instance body is elaborated immediately after its spec, then it is ok to move the elaboration check ahead of the elaboration of the instance spec; this would only make a difference in the case where the check fails and no one cares about this case). !wording !discussion Ada 2005 WORKAROUNDS Here are some examples of how the problem could be addressed using existing Ada 2005 capabilities. For the first example, making the instantiation a child unit solves the problem. However, this is annoying, because accessing the instance requires an extra with and instantiation (since children of generics must be generic): generic type Elem is private; with function Hash(El : Elem) return Integer; package Hashed_Sets is type Set is private; function Union(Left, Right : Set) return Set; ... private type Set is record ... end record; end Hashed_Sets; generic package.Hashed_Sets.Signature is package The_Signature is new Set_Signature(Elem, Set); end Hashed_Sets.Signature; A user of Hashed_Sets must with and instantiate Hashed_Sets.Signature in order to access the instance. The second problem can also be solved with child units, using the limited with: limited with Expressions.Sequences; package Expressions is type Expr_Ref is private; type Seq_Of_Expr is access Expressions.Sequences.Sequence; function Operands(Expr : Expr_Ref) return Seq_Of_Expr; ... private type Expression; -- completion deferred to body type Expr_Ref is access Expression; end Expressions; package Expressions.Sequences is package Expr_Sequences is new Sequences(Expr_Ref); type Sequences is new Expr_Sequences.Sequence; end Expressions.Sequences; Here, besides the extra with clause, we need to declare an extra type simply so that the type is visible to the limited with clause (which operates purely syntactally). This means that extra type conversions are necessary. Here is the generic signature example, using "end private;": generic type Elem is private; with function Hash(El : Elem) return Integer; package Hashed_Sets is type Set is private; function Union(Left, Right : Set) return Set; ... private type Set is record ... end record; end private; package Signature is new Set_Signature(Elem, Set); end Hashed_Sets; Here is an example where we want to instantiation a container: package Expressions is type Expr_Ref is private; type Expr_Seq; -- incomplete type type Seq_Of_Expr is access Expr_Seq; function Operands(Expr : Expr_Ref) return Seq_Of_Expr; ... private type Expression; -- completion deferred to body type Expr_Ref is access Expression; end private; package Expr_Sequences is new Sequences(Expr_Ref); type Expr_Seq is new Expr_Sequences.Sequence; -- completion of incomplete type end Expressions; Here is the nested generic with a private extension: package Constructs is type Root_Construct_Handle is abstract tagged private; ... private type Root_Construct_Record; -- completed in pkg body type Root_Construct_Access is access all Root_Construct_Record; type Root_Construct_Handle is abstract tagged record Construct : Root_Construct_Access; ... end record; end private; generic type Data_Part is private; package Handles is type Construct_Handle is new Root_Construct_Handle with private; type RO_Access is access constant Data_Part; type RW_Access is access all Data_Part; function Get_RO_Access(Handle : Construct_Handle) return RO_Access; function Get_RW_Access(Handle : Construct_Handle) return RW_Access; private type Construct_Handle is new Root_Construct_Handle with ... -- ERROR: Parent type of record extension -- must be completely defined. end Handles; end Constructs; !ACATS test ACATS B and C-Test(s) are necessary. !appendix [Editor's note: For earlier ideas on this topic, see AI95-359-1, AI95-359-2, AI95-359-3, AI95-359-4, and AC-123, as well as the other alternatives.] From: Steve Baird Date: Tuesday, October 21, 2008 5:58 PM At the risk of incurring Randy's wrath for bringing up old proposals that have already been discarded, I want to revive the discussion of allowing type T is private; package I is new G (T); private type T is ... ; in some cases. This is intended as an alternative to the post-private visible part (aka "end private") proposal, which I believe is a far bigger change than is warranted for the problem it is intended to solve. Several variations on this approach have been explored in the various versions of AI95-359 and in alternative #1 of AI05-74. See any of these AIs for s description of the problem that both this proposal and the post-private visible part proposal are intended to solve. The general idea is that for a package instance with an actual type that is not yet completely defined: 1) Fine-grained freezing is performed for the expanded spec of the instance, as if the spec had been expanded by hand. 2) The elaboration of the instance body is deferred until some point after the actual types are completely defined. Statically, the general freezing associated with the instance body is also deferred until this point. 3) The runtime check that the generic body has been elaborated is performed when the instance body is elaborated, not when the instance spec is elaborated. It seems to me that the generic ought to have some indication that the formal type is intended to be used in this way. Otherwise, a change such as, for example, adding Null_Vector : constant Formal_Type_Array (1 .. 0 => <>); to the private part of the generic could cause a previously-legal instance to be rejected. If it is intended that a formal type should be usable in this way, then that ought to be included as part of the contract and violations should be detected when compiling the generic, not the instance. So today's approach is to define a pragma, May_Be_Partial, which applies to a formal private type (or to a formal derived type with a private extension) of a generic package. (Is there any justification for messing around at all with the rules for generic subprograms? I don't know of any.) Obviously the name of the pragma is subject to change but "May_Be_Partial" seems better than "Has_Polka_Dots" for today's discussion. The only effect this pragma has when compiling a generic is to disallow uses of the type in the generic spec (including the private part) which would freeze the formal type or otherwise require that the formal type be completely defined. This example would be illegal because of the pragma: generic type T is private; pragma May_Be_Partial (T); package G is X : T; end G; When compiling an instance, the pragma allows the corresponding actual type to be a type which is not yet completely defined (but not an incomplete type). The (static) freezing and (dynamic) elaboration associated with the instance body occurs at the earliest point after the freezing/elaboration of the instance spec where all of the actual types of the instance are completely defined. This coincides with the existing static and dynamic semantics in all cases which are legal according to the existing rules (strictly speaking, in order to get this equivalence it would also be necessary to add an implementation permission to the effect that if an instance body is elaborated immediately after its spec, then it is ok to move the elaboration check ahead of the elaboration of the instance spec; this would only make a difference in the case where the check fails and no one cares about this case). It can be viewed as either good or bad that this approach does not allow the case where there is no pragma but there is also nothing in the generic package spec that would preclude the pragma. This is good because, as mentioned above, we don't want seemingly innocuous changes to, say, the private part of a generic to cause an instance to become illegal. It is bad because it means that if the generic package spec lacks the pragma for some type (e.g. consider the current versions of the various container generics), then the instantiator is out of luck. This proposal therefore includes adding the pragma to the container generics where possible and probably to other language-defined generic packages. If it eased some implementation problems, a rule could certainly be added that the point of the deferred freezing/elaboration must still occur within the same immediately enclosing scope as the instance. This would disallow the following example with G; pragma Elaborate_All (G); package Pkg is type T is private; package Nested is package I is new G (Formal_Type_With_The_New_Pragma => T); end Nested; private type T is ... ; end Pkg; Alternatively, one could hair things up even further and defer instance body elaboration into the body of the enclosing package in this case. It's not clear whether this would be worth the added complexity. One could certainly argue that there is little in this proposal that is new. Associating the pragma with the formal type, not the instance, and thereby strengthening the contract model is about the only idea here that has not been proposed before. Given that this general approach was explored some time ago and not adopted, why is it worthy of discussion now? I think there was an assumption that "surely we can come up with something better than this". Time has passed and, in my opinion, we haven't. Instead, discussion seems to have focused on the post-private visible part approach. I believe that this pragma is a better solution to the problems that both proposals are trying to address. **************************************************************** From: Randy Brukardt Date: Tuesday, October 21, 2008 6:18 PM I object to discussing this now, because we have to finish ASIS first, and I have too much ASIS work to do before the meeting to properly vet this proposal. It might work, and it might not, and I don't want to be tossing FUD around about whether or not it is implementable. (My initial reaction is that it would be impossible to implement in Janus/Ada, but I have no facts to back that up.) And this topic is very important to me, both from a usability and an implementability perspective. In any case, I will not be filing any of the mail on this topic before the meeting (unless some major miracle in terms of time occurs), so it will not be available at the meeting. **************************************************************** From: Ed Schonberg Date: Tuesday, October 21, 2008 8:26 PM > in some cases. This is intended as an alternative to the post-private > visible part (aka "end private") proposal, which I believe is a far > bigger change than is warranted for the problem it is intended to > solve. I will incur the same ire and say that at first reading I like this proposal and would like to discuss it soon. However, we'll defer to Randy's overloaded agenda, and assume that we won't have a chance to examine this in Portland. In any case this is worth reopening. When we last discussed this, Pascal and I were adamant that changing freezing rules was an earthquake. I've changed my mind on this, and will try to implement some version of deferred freezing to gauge the impact on the compiler. At first reading, my impression is that we want the restricted version: the instance must appear in the same scope as that of the type, not in a nested context. **************************************************************** From: Robert Dewar Date: Tuesday, October 21, 2008 9:31 PM > I will incur the same ire and say that at first reading I like this > proposal I agree that this proposal is attractive (and in my mind has higher priority than ASIS work, which I am unconvinced will have any impact) **************************************************************** From: Steve Baird Date: Tuesday, October 21, 2008 10:48 PM > The (static) freezing and (dynamic) elaboration associated with the > instance body occurs at the earliest point after the > freezing/elaboration of the instance spec where all of the actual > types of the instance are completely defined. This isn't quite right, but the problem is easily correctable (although finding the best wording to express it might be more challenging). As written above, freezing might occur too early. It might occur before a pending representation item that applies to an actual type. package P is type T is private; package I is new G (T); private type T is ... ; -- don't want freezing to occur here for T'Some_Aspect use ... ; end P; A somewhat stronger condition than "completely defined" is needed. "Freezable" or "really truly completely defined" or somesuch. A type is freezable if it is completely defined, all of its component types (if any) are freezable, and all applicable operational and representation items have been applied. It might also be possible to formulate a rule for when the instance is elaborated in terms of the freezing points of the actual parameters, but care would be needed to avoid circular definition problems. **************************************************************** From: Robert I. Eachus Date: Wednesday, October 22, 2008 10:51 AM I've been thinking about this proposal, and my inclination is that the freezing rule needs to be simple. If this makes some programs illegal where a compiler could otherwise figure out where to do the freezing so be it. So far, my best candidate is "if one or more parameters of a generic in a package specification are of an incomplete or private type declared in the same package specification, the generic shall be instantiated at the end of the private part of the package, or at the first use of the name of the generic instance, if earlier." This would mean that renaming components of a generic package can become more complex in some cases, but as far as I can see those cases are all illegal now. The most painful case is where you want to initialize a variable of a type other than a private type to a variable visible in the spec of a generic package. (You need to do the initialization in the body of the package that declares the private type, which can lead to uninitialized references to the variable during elaboration.) But I don't see this case as real. There will be many cases where you want to shorten the name of a constant in a generic package.but deferred constants work fine for that case. The main question though, is does this solve the issue we are really trying to solve? As I see it, this works just fine for containers, but I'd rather try it "for real" with a modified compiler. **************************************************************** From: Tucker Taft Date: Wednesday, October 22, 2008 11:07 AM I believe it is quite important that the instantiation can be followed immediately by type derivations making the types defined by the instance visible in the enclosing package. Hence: package I is new G(T); type Coll_Of_T is new I.Coll [with null record]; I am concerned that this will force the freezing to happen right away anyway, which defeats the purpose. On other hand, deferring the instantiation to after the private part where T is completely defined avoids this issue quite cleanly. Other than philosophical concerns (with which I do sympathize), are there some substantive *technical* problems that have been found with the post-private-part visible declarations? I feel that that proposal is still on the table, and should be evaluated carefully before we give up and try to reincarnate other older proposals. **************************************************************** From: Steve Baird Date: Wednesday, October 22, 2008 1:05 PM > I believe it is quite important that the instantiation can be followed > immediately by type derivations making the types defined by the > instance visible in the enclosing package. Hence: > > package I is new G(T); > type Coll_Of_T is new I.Coll [with null record]; > > I am concerned that this will force the freezing to happen right away > anyway, which defeats the purpose. > > On other hand, deferring the instantiation to after the private part > where T is completely defined avoids this issue quite cleanly. > I agree that that is an advantage of the post-private visible part (ppvp) solution. The problem goes away if a subtype is used instead of a derived type, but then you don't get inherited subprograms. If you really want to make the subprograms look as though they were declared in the scope enclosing the instance, you would also have to add a bunch of subprogram renames. This detracts from readability, is a maintenance issue, is cumbersome, etc. On the other hand, the subtype does have some advantages if other types in the instance refer to the given type. If, for example, the instance declares a type and then a second type which includes the first type as a component type, then this component relationship is not preserved if you declare two derived types. In this case it may be more useful to declare two subtypes. Subtypes may also more accurately reflect the intention of the programmer - if the derived type was being introduced just to avoid requiring users to name the instance as opposed to because there was really a desire for two distinct types. > Other than philosophical concerns (with which I do sympathize), are > there some substantive *technical* problems that have been found with > the post-private-part visible declarations? No. My objections to the ppvp proposal are not based on some convoluted scenario which results in definitional problems (I am not sure that no such scenarios exist, but that's just FUD). I think: 1) This is too big a change for the problem it is addressing, particularly given that a much more lightweight solution seems to be available. 2) The solution is inelegant and detracts from readability. 3) Even if this were a good idea for a language being designed from scratch, it's not a good idea to incorporate into Ada. All of these are matters of opinion and taste on which reasonable people may (and apparently do) disagree. > I feel > that that proposal is still on the table, and should be evaluated > carefully before we give up and try to reincarnate other older > proposals. I completely agree that the post-private visible part solution is still on the table. I'm proposing ("proposing" sounds so much better than "dredging up") an alternative which I claim should also be considered. Incidentally, I thought of a couple more points that need to be addressed in the pragma-based alternative: 1) A prefer-the-original-order-of-the-instances tie-breaker rule is needed to specify the the order in which the two instance bodies are elaborated in a case like package P is type T is private; package I1 is new G1 (T); package I2 is new G2 (T); private type T is ... ; end P; 2) In the case of an instance of a generic which is itself exported from another instance, we want to elaborate the two instance bodies in the right order. In this example package P is type T is private; package I1 is new G1 (T); package I2 is new I1.G2; private type T is ... ; end P; we don't want to elaborate the body of I2 until after the body of I1 (elaborating I2's body before the elaboration of the body of I1.G2 leads to an elaboration check failure). Thus, the elaboration of I2's body needs to be deferred even though G1.G2 has no formal parameters. I concede that wrinkles like this do not do anything to improve the attractiveness of this proposal. **************************************************************** From: Ed Schonberg Date: Wednesday, October 22, 2008 2:12 PM > I've been thinking about this proposal, and my inclination is that the > freezing rule needs to be simple. Commendable goal, but about 10 years too late... However I think that Steve's rules can probably reduced to a simple formulation: the freezing of an entity declared in an instance freezes the instance. This takes care of successive instances that depend on each other. In the simplest case (pure packages) it means that instance bodies will be elaborated at the end of the private part, as you suggest. **************************************************************** From: Randy Brukardt Date: Wednesday, October 21, 2008 6:49 PM > I agree that this proposal is attractive (and in my mind has higher > priority than ASIS work, which I am unconvinced will have any impact) You're probably right about the impact, but it is way to late to argue with priorities set by WG 9 long ago. In any case, we've promised to deliver a finished ASIS standard by the June WG 9 meeting, and that will have the effect of freeing up the resources to work on things that are certainly more interesting. That is, the sooner we get done with ASIS, the sooner we can move on to other things. **************************************************************** From: Dan Eilers Date: Wednesday, October 22, 2008 8:51 PM > I believe it is quite important that the instantiation can be followed > immediately by type derivations making the types defined by the > instance visible in the enclosing package. Hence: > > package I is new G(T); > type Coll_Of_T is new I.Coll [with null record]; > > I am concerned that this will force the freezing to happen right away > anyway, which defeats the purpose. There is some discussion in AI95-00391 about possibly adding new syntax to directly support this idiom. Maybe such new syntax would be helpful with regard to freezing as well. ****************************************************************