Re: Magic ordering

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

On Tue, 15 Mar 2005 13:53:50 +0000, Marius Amado Alves wrote:

> On 15 Mar 2005, at 13:16, Dmitry A. Kazakov wrote:
>>>> ... If I am denied access to information that
>>>> lets me  implement a < operator, am I supposed to be able to sort it?
>>>
>>> This is one of my favourites. There's always a way. Bit by bit
>>> comparison, an arbitrary index, 'Address comparison...
>>
>> All of which might appear wrong. The objects might be non-contiguous, 
>> have replicas etc.
> 
> Note that you *know* they are non-contiguous, have replicas, etc. then 
> you *have* the required information.

1. to know "<" is much cheaper than the above

2. with the above it is still a halting problem

The idea of contracts is exactly to avoid such semantic pitfalls. My part
of the contract is to tell you that the thing is ordered, yours is to
implement sorting.

>> Comparison should reflect the semantics of compared things.
> 
> If you mean *deep* semantics, then not necessarily. I've come across 
> many situations where the order does not (need to) reflect it.
> A strictly algebraic order is enough. For example ordering a set of 
> integers for search (e.g. in an Ada.Containers.Ordered_Set). The deep 
> meaning of the integers does not matter. They can be SS numbers, or IP 
> addresses, or the height of people. However you can still get something 
> useful from the container, e.g. "is it there?"

There could be many orders defined on the same objects, as Hyman rightfully
pointed out. But any of them have to be published in the contract. There is
nothing outside the contract.

>> There is no universal way to do it.
> 
> I don't claim there is an "universal" way, but that there is always one.
> 
> Ok, maybe theoretically any usable information may be missing. But in 
> practice this is an anomalous situation. If you need an order for some 
> type, then certainly you have same usable information. Either the 
> (deep) meaning of the type, or some structural property, or some 
> reliable representation. If all these are missing, and you still need 
> an order, the design must be at fault.

Yes it is a design fault not to provide "<" where it exists. When you
define one at the place of instantiation, you in fact create a subtype of
the type with an extended contract containing "<". 

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