Re: Using Red-Black Trees

["Yannick Duchêne (Hibou57)" <yannick_duchene@yahoo.fr>]

Le Thu, 18 Nov 2010 11:47:03 +0100, <stefan-lucks@see-the.signature> a  
écrit:

> On Thu, 18 Nov 2010, Yannick Duchêne (Hibou57) wrote:
>
>> Formally speaking, you do not have multiple
>> implementations of a single specification. The closest thing actually is
>> generic package. But that is not easy to do with generics: you will  
>> have to
>> give the generic instance all of its custom implementation via generic
>> parameters (methods and others).
>
> Why is that a big deal? The instance of a polymorphic data structure must
> somehow be told which operations to use, anyway.
Yes, except that it should be in the implementation.

One of the matter with the use of generic in that purpose, is that you  
must re-create another package specification for the implementation  
package. You have the abstract interface, you have an implementation  
package, which come with an interface and a body, and you must bind this  
with another package, which is to be an instantiation of the first one  
with parameters provided by the second one. With SML (as I did a  
comparison with that language), you have an interface, ex.

signature MY_INTERFACE = sig
    ... (* some specifications *)
end

then an implementation among multiple others (if you wish, and typically,  
there will be multiple):

structure My_Interface_Implementation_1 :> MY_INTERFACE = struct
    ... (* implementation *)
end

( the “:>” is for opaque instance, you may use “:” for non-opaque)

No more, because it does not need more.

The abstract interface behave like a type definition, and you declare an  
implementation instance, just like an entity instance. You can have  
multiple instance simultaneously, so that if you want This implementation  
of a container for This purpose, and That implementation of the same  
container for That usage, you can.

Yes, this is feasible with generics (the closest thing available with  
Ada), or with static polymorphism (as do the ARM and as Jean-Pierre  
suggested). At least, the generic way do some checks and ensure  
consistency; the static polymorphism way does not at all (so I would  
recommend generics). What I feel is not clean with the generic way, is the  
need to create an un-useful second interface (un-useful duplication) for  
each implementation, a framework body for the generic (non-sense here),  
and the need for an explicit instantiation (this instantiation is a second  
un-useful copy of stuffs). All of this forms noise and weight the design,  
disturb the comprehension and does not express what it should express (too  
many steps for such a simple things does not help to understand what is  
important).

I am sure Ada could support this, as it already have all of what is needed  
for that (separation of implementation and interface, just not separated  
enough).

We may declare an interface like for any generic package; this generic  
would *not have any body*. We may declare the existence of an  
implementation instance in a terse way with something as short as a  
renaming package or package instantiation; this one would come *with a  
body* (which would be checked against the specification of the abstract  
interface) and the client side would reference this package which would  
implicitly import the interface of the first one (the abstract one). This  
would only use things which are already there with Ada, just the way to  
bind these together would need to be updated. This could be done in a way  
which could preserve compatibility, as this would touch nothing else.



-- 
Si les chats miaulent et font autant de vocalises bizarres, c’est pas pour  
les chiens.

“I am fluent in ASCII” [Warren 2010]