!standard A(3) 08-04-21 AI05-0048-1/03 !class binding interpretation 07-04-10 !status ARG Approved 9-0-0 06-11-10 !status work item 07-04-10 !status received 07-02-15 !priority Low !difficulty Easy !qualifier Clarification !subject Redispatching is not expected in language-defined subprograms !summary Redispatching should be forbidden in language-defined routines unless it is explicitly required. !question Some operations in children of Ada.Containers may be implemented partly or fully by calling other primitive operations on the container object. The Standard even defines some of the container operations by saying that they are "equivalent to" code that uses other operations. For example, A.18.7(93/2) defines Replace (Container, Key, New_Item) (where Container is a Set) by saying that it is equivalent to the call Replace_Element (Container, Find (Container, Key), New_Element) which uses two other operations on type Set: Replace_Element and Find. It is not unlikely that an implementor of Ada.Containers implements the Replace operation with the above call of Replace_Element. Is an implementation of Ada.Containers allowed, required or forbidden to use redispatching calls to the container operations? For example, may the implementor implement the Replace operation mentioned above as the call Replace_Element ( Set'Class (Container), Find (Set'Class (Container), Key), New_Element) ? If the Container object is actually of a type derived from Set, and Replace_Element or Find are overridden for the derived type, the redispatching call obviously has a different effect than the non-redispatching call. Which is right? (A statically bound call.) Are both allowed? (No.) !recommendation (See summary.) !wording Add the following after A(3/2): If a descendent of a language-defined tagged type is declared, the implementation shall ensure that each inherited language-defined subprogram behaves as described in this International Standard. In particular, overriding a language-defined subprogram shall not alter the effect of any inherited language-defined subprogram. AARM Note: This means that internally the implementation must not do redispatching unless it is required by the Standard. So when we say that some subprogram Bar is equivalent to Foo, overriding Foo for a derived type doesn't change the semantics of Bar, and in particular it means that Bar may no longer be equivalent to Foo. The word "equivalent" is always a bit of a lie anyway... !discussion Language-defined subprograms should behave as described in the Standard unless the user takes some explicit action to change that (such as overriding). It's also true that the Standard usually specifies when it expects dispatching to occur; the presumption is that dispatching does not occur elsewhere. Still, implementers and users could take the notion of equivalence too literally. The intent of equivalence is that it is a stand in for repeating the original definition of the equivalent code. We use equivalence to increase the clarity of the standard and reduce the chance of errors in the standard, not to suggest an implementation model. Therefore, we add a statement to this effect that is intended to cover all language-defined libraries, including those defined in future versions of Ada. !corrigendum A(3) @dinsa The implementation shall ensure that each language-defined subprogram is reentrant in the sense that concurrent calls on the same subprogram perform as specified, so long as all parameters that could be passed by reference denote nonoverlapping objects. @dinst If a descendent of a language-defined tagged type is declared, the implementation shall ensure that each inherited language-defined subprogram behaves as described in this International Standard. In particular, overriding a language-defined subprogram shall not alter the effect of any inherited language-defined subprogram. !ACATS test An ACATS C-Test should be created to ensure that redispatching is not occurring (obviously, testing all possibilities is impractical, so just a couple of cases should be tried.) !appendix !topic Redispatching calls from Ada.Containers !reference Ada 2005 RM A.18 !from Niklas Holsti 2007-02-15 !discussion All the Ada.Containers packages define the container type (Vector, List, Map, Set) as visibly tagged. The operations on containers are defined as primitive operations of the container type. The user can thus derive an extended type of the container type and override some of these operations, for example to perform some application-specific actions in addition to the basic (parent) actions on the container object as implemented in the (instances of) children of Ada.Containers. On the other hand, some such operations in children of Ada.Containers may be implemented partly or fully by calling other primitive operations on the container object. The RM even defines some of the container operations by saying that they are "equivalent to" code that uses other operations. For example, A.18.7(93/2) defines Replace (Container, Key, New_Item) (where Container is a Set) by saying that it is equivalent to the call Replace_Element (Container, Find (Container, Key), New_Element) which uses two other operations on type Set: Replace_Element and Find. It is not unlikely that an implementor of Ada.Containers implements the Replace operation with the above call of Replace_Element. My question is now: is an implementation of Ada.Containers allowed, required or forbidden to use redispatching calls to the container operations? For example, may the implementor implement the Replace operation mentioned above as the call Replace_Element ( Set'Class (Container), Find (Set'Class (Container), Key), New_Element) ? If the Container object is actually of a type derived from Set, and Replace_Element or Find are overridden for the derived type, the redispatching call obviously has a different effect than the non-redispatching call. Which is right? Are both allowed? I have not found any statement in RM A.18 that forbids such calls, nor statements that say that such calls may happen, or that the matter is not specified. This worries me because if such redispatching calls can happen they may cause some application-specific actions at unexpected times, perhaps leading to application-level errors. If the question is not yet decided, I suggest that redispatching calls from Ada.Containers should be forbidden. I think this is the simpler option and makes it clear what a user of Ada.Containers can expect. **************************************************************** From: Pascal Leroy Date: Friday, February 16, 2007 6:49 AM > If the question is not yet decided, I suggest that redispatching calls > from Ada.Containers should be forbidden. I think this is the simpler > option and makes it clear what a user of Ada.Containers can expect. I don't think we considered this possibility. I agree that redispatching should be forbidden, it seems safer. And if the user really wants redispatching, she can always redefine the operations herself. **************************************************************** From: Tucker Taft Date: Tuesday, February 20, 2007 7:51 AM I agree these should be forbidden. Using redispatching must be seen as part of the *specification* of the primitive operation of a tagged type, and none of these specify redispatching, and hence it should be disallowed. An important feature of Ada 95 (and Ada 2005) is that the default is static binding, which allows the implementation details of the primitive operations of a parent type to be opaque to descendants. Contrast this with Java, where significant extra effort would be required to prevent problems when a descendant overrides some but not all of the parent's methods, since Java provides no way to get static binding to non-private virtual methods (other than via "super" which doesn't apply here). C++ allows static binding, but it is not the default. **************************************************************** From: Robert A. Duff Date: Tuesday, February 20, 2007 8:58 AM > I agree these should be forbidden. Me, too. But why did we make these types visibly tagged, if clients can't usefully override the operations? **************************************************************** From: Pascal Leroy Date: Tuesday, February 20, 2007 9:56 AM Duh? They *can* be usefully overridden, you just cannot expect redispatching to happen. One compelling reason for making them visibly tagged was to allow prefixed notation. It's one of these good things that you only get with tagged types. (I know, it's kind of silly that you have to say 'tagged' in order to get all sorts of good things, but Ada is like that.) In retrospect we should actually have used interfaces here: a hashed set and an ordered set have a lot in common, and it would have made sense to reify this commonality through a set interface. Oh well. **************************************************************** From: Randy Brukardt Date: Tuesday, February 20, 2007 1:20 PM That was considered, but it doesn't work. (One of the reasons I think interfaces are nearly useless, but I digress.) Most of the operations of a container have an element parameter, which is necessarily generic. In order to have a shared interface, you'd have to have that interface declared in a separate generic, which would then have to be instantiated first and then passed as a formal package to the "real" set package. That would violate our "single instantiation" guideline, and altogether seems like too much mechanism. Note that such an interface wouldn't be useful for generic algorithms, because each element type would require a different interface. So it really wouldn't be useful for much of anything. (Signature packages have similar problems, but at least they can only be used in a generic anyway so at least you don't need *extra* instantiations to be able to do anything.) **************************************************************** From: Pascal Leroy Date: Wednesday, February 21, 2007 1:30 AM > That would violate our "single instantiation" > guideline, and altogether seems like too much mechanism. I agree that having to do two levels of instantiation would be a nuisance. It would be nice to have a way to instantiate a generic child in a single step (passing the parameters for its entire ancestry), rather than doing it piecemeal. > Note that such an interface wouldn't be useful for generic > algorithms, because each element type would require a > different interface. So it really wouldn't be useful for much > of anything. I disagree. First, you could write algorithms independent from the element type by passing a formal package corresponding to the topmost generic (the one which declares the interface). Second, an interface would actually be useful to ensure that you do not depend on a particular implementation of the set abstraction, perhaps to be able to easily switch implementation. Third, having an interface would help in building protected variants of the containers (assuming that the interface is limited). **************************************************************** From: Tucker Taft Date: Wednesday, February 21, 2007 2:13 PM The generic signature approach would also be useful, but alas, it depends on being able to instantiate a signature inside the generic that defines the container type. That is: generic -- Signature package captures commonality between Sets type Element_Type is private; type Set is tagged private; Empty_Set : in Set; type Cursor is private; No_Element : in Cursor; with function "="(Left, Right: Set) return Boolean is <>; with function To_Set(New_Item : Element_Type) return Set is <>; ... package Set_Signature is end; generic type Element_Type ... package Ada.Containers.Hashed_Sets is type Set is tagged private; type Cursor is private; ... private ... end private -- *** inventing new syntax here *** -- Include signature package so it gets -- instantiated automatically package Signature is new Set_Signature(Element_Type, Set, Empty_Set, Cursor, No_Element); ... end Ada.Containers.Hashed_Sets; generic -- Define a generic that needs some kind of set with package Signature is new Set_Signature(<>); package Generic_Using_Sets is ... end Generic_Using_Sets; package My_Sets is new Ada.Containers.Hashed_Sets(My_Int); -- Create an appropriate kind of set package Using_Sets is new Generic_Using_Sets(My_Sets.Signature); -- Instantiate second level generic using signature from -- set package >> That would violate our "single instantiation" >> guideline, and altogether seems like too much mechanism. > > I agree that having to do two levels of instantiation would be a nuisance. > It would be nice to have a way to instantiate a generic child in a single > step (passing the parameters for its entire ancestry), rather than doing > it piecemeal. That would somewhat defeat the purpose since presumably you might want multiple descendants of the same interface type, and if you did both instantiations at once, you would not be able to create both a hashed_set and an ordered_set, for example, with the same parent interface type. >> Note that such an interface wouldn't be useful for generic >> algorithms, because each element type would require a >> different interface. So it really wouldn't be useful for much >> of anything. > > I disagree. First, you could write algorithms independent from the > element type by passing a formal package corresponding to the topmost > generic (the one which declares the interface). Second, an interface > would actually be useful to ensure that you do not depend on a particular > implementation of the set abstraction, perhaps to be able to easily switch > implementation. Third, having an interface would help in building > protected variants of the containers (assuming that the interface is > limited). I think the generic signature handles at least the first two of these. **************************************************************** From: Pascal Leroy Date: Thursday, February 22, 2007 2:42 AM > That would somewhat defeat the purpose since presumably you > might want multiple descendants of the same interface type, > and if you did both instantiations at once, you would not be > able to create both a hashed_set and an ordered_set, for > example, with the same parent interface type. True, but I think you missed my point. In order to provide maximum flexibility (within the existing language) you would have to have two levels of generic, the topmost defining the set abstraction, and the bottommost defining a particular set implementation. During the design of the containers we discussed this several times, but we said "yeah, but in the common case where you do *not* need this flexibility, you'd have to do two instantiations, and that would be obnoxious". In retrospect, I think that it would have been better to provide a mechanism to do both instantiations at once. That way, we could have structured the containers with all the children we wanted, without requiring multiple instantiations in the common case. Of course, if you really wanted to take advantage of the hierarchical structure, you'd have to do several instantiations. Simple things should be simple, complex things should be possible... **************************************************************** From: Randy Brukardt Date: Thursday, February 22, 2007 11:12 PM That's an interesting idea. But I don't think that would really help that much. "Single instantiation" is more than just the instantiation itself; it also includes the understandability of the design. It's hard enough to get students to understand the simple instantiations of Text_IO (one reason that we provided pre-instantations in Ada 95). It surely would be harder to understand a multi-level containers solution than a single-level one. (How much harder would depend on John and other text book authors, of course). I suspect it would reach the level of magic incantations for many (most?) Ada programmers, and that would not be a good thing. I still think that the interfaces in question wouldn't be very useful for writing reusable code, as any such code would have to depend on the generic that defines the interface (either as a formal parameter or as a child), and so you'd still end up with a forest of instantiations. Understanding the result would be interesting, to say the least. Of course, this would have been a worthy area for discussion. But since you didn't have the multiple instantiation idea during the Amendment process, we never really discussed any of this. Too late now... ****************************************************************