Re: Generic Package

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Tue, 1 May 2007 14:14:46 -0500, Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:1ozvzzh59ebq8$.yeh9do8s3hig$.dlg@40tude.net...
>> On Tue, 01 May 2007 15:42:21 +0200, Georg Bauhaus wrote:
> ...
>>> Yes, in the sense that the specifics of memory layout and such are
>>> unknown and irrelevant to the client; in particular, no order needs
>>> to be specified.
>>
>> Apart from obvious uselessness of contracts referencing to the memory
>> layout, the above is self-contradictory. Memory layout defines an order. It
>> also is a part of the contract. Hence the interface is ordered.
> 
> And now all is clear.
> 
> It is impossible to implement a set with having some form of order. So, for
> us practitioners, an "unordered set" is simply a set with no defined order.
> I can see that you are arguing about a idealized set unordered set that
> cannot actually exist - an abstraction that is irrelevant in practice. No
> wonder people are confused.
>
> There is a reason that Ada.Containers has ordered and hashed sets, but not a
> mathematically unordered one. That because the latter is impossible to
> implement without a suboptimal mapping into one of the other forms. The net
> effect is that even if you could use such a form, you would take a massive
> performance hit to do so (all operations being O(N)). As such, there is no
> reason to consider such forms or worry about their properties.

I definitely agree with this. And this is the answer to the OP question
about "generic collections," they would be close to useless.

Yet I think that this abstraction is not that irrelevant. One example is
distributed systems, like DB engines. There is a reason why relational
containers are defined unordered. It is not because no order could be
invented. It is because this abstraction forces the programmer either to
use snapshots (ordered mappings of an unordered set) or stored procedures
(foreach-magic) to get at an order. Making the interface ordered would
probably prevent efficient implementations of the DB engines.

This boils down to the question of the underlying hardware. DB engine is a
hardware from the application point view. It is a very strange hardware for
which the logic of being able to enumerate everything at once, here and
now, does not apply. It is likely so for any system with distributed
containers and distributed programs dealing with them. In such hardware
foreach-magic could be in order of magnitude more efficient than ordering
in situ. Or let's take Get_Pixel / Set_Pixel on the image containers of the
graphic accelerator. Further, if we looked into the future, on quantum
computing stuff, then there is a possibility that such hardware could
become rather normal.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de