Version 1.6 of ai05s/ai05-0048-1.txt

!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...

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