Re: Generic Package

[Markus E Leypold <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de>]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "Markus E Leypold"
> <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> wrote in
> message news:40irbbzm2t.fsf@hod.lan.m-e-leypold.de...
>> "Randy Brukardt" <randy@rrsoftware.com> writes:
>>
>> > "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.
>>
>> No. The only thing that is clear to me, is, that DK is splitting hairs
>> again, just to win the argument.

> Maybe, but that's just name calling and is never an appropriate way to
> conduct an argument. 

Well -- I admit being a tinsy bit annoyed here, since DK never
proved/argued any of his assertions: Either he falls silent or changes
the topic to just another "example" or some freely associated topic.

> Besides, you're going to claim the same about me in
> your reply to this message... ;-)

We will see. I'm usually rather patient (as my posts in other threads
have shown, I hope), when I want to make my point.


>> > It is impossible to implement a set with having some form of order. So,
> for
>>                       ^^^^^^^^^
>
>> Implement, yes. But it is possible to implement a set interface
>> without forcing the user to provide an order function to instantiate
>> the set. It is also possible to provide a mechanism for such an
>> implementation that gives you all the elements in this set in some
>> arbitary order/sequence which might change with every invocation. This
>> is called iteration.

> You're repeating the obvious. 

Sigh. Yes, it _is_ obvious. 

> But a set where you don't specify the order is
> still an ordered set: 

Here I don't agree. I think we are not talking about abstract
mathematical entities here, but about data types / containers. But
first a short word on the abstract mathematical entitity (just in case
we're straying mentally into that directions): I would find it
inappropriate to call the set of colors an ordered set, just because
there an order can be defined, which I haven't given. Mathematically
an ordered set is (a) a set plus (b) a relation (with the approriate
properties) on that set. If we have only a set it is only a set, not
an ordered set (though it could be made to an ordered set).

Now about the data type: The data type ordered set is defined as 

 (a) a base set B
 (b) an order on that base set
 (c) the type of all subsets of B

Note that the point of an ordered set data type is that you specify an
order up front which is then _constant_ for all subsets of B.

> there exists an order between the elements, even if
        ^^^^^^^

> you don't know what it is and don't have to describe it.

In which sense does that order exist? In the linked list example a
certain order of the elements in the subset (I prefer to call that
sequence) comes into existence: But ad hoc and it doesn't constitute
an order on the "set of all possible elements" (the set B).


>> DK originally stated, it is not possible to iterate over an unordered
>> set: It is.
>
> I actually agree with DK, using his definitions. The problem is that no such
> set could ever be constructed (even on a piece of paper, the elements have
> an order). So the fact is completely irrelevant: there is no such thing as
> an unordered set.

I repeat: There is a bit of confusion on 3 different things:

 (a) the way we write down sets (notation)
 (b) orders (binary relations with certain properties)
 (c) orderable sets, i.e. sets for which an order can be defined.

You (in my opinion) are confusing ordered sets (sets for which b is
given) with (c): Sets for which an order can be defined. I thing if
you write down the definition "An ordered set is ..." you'll see the
difference pretty fast: An ordered (in the mathematical sense) set is
a pair (M,R) where M is a set and R a relation with certain
properties. That is similar to the usual definition of a vector space:
A vector space is a tuple (K,V,*,+) with ... -- where K is a field, V
a set, * multiplication between vectors and scalars and + the vector
addition. The vector space is the compound structure, not V or
anything else. The _set_ V alone (i.e. the set R^3) is just a set,
nothing else. The same applies to the concept of ordered set: An
ordered set is a set plus an order relation. In mathematics AFAIK it's
even not defined as an extra structure, since ist suffices to give R:
M is just the domain of R, so in mathematics

But essentially the same kind of argument -- as far as terminology
goes -- has to be made for the abstract data type "ordered set" whose
definition I already have sketched above.

>> It is possible to specify the contract for this iteration without
>> referring to an order (I did it in one of my recent post). DK denied
>> this. He is wrong.

> Of course you can if you assume primitives that effectively give you an
> order. 

No. Have you read the functional spec I wrote? I just use set
operations and a suitable cursor abstraction. Of course the choice of
the next element is not deterministic in the specification but that is
as it should be: It indicates that the implementation has a certain
degree of freedom here.

> It's like specifying a contract for set inclusion: you certainly can
> do so, but it is unlikely to say anything interesting: it's mostly likely
> going to be a tautology.

?


>> Implementing a set as a linked list might not be efficient enough for
>> a large number of items -- still: It is a set in any sane sense and
>> one can provide an interface to iterate over the items. And it has
>> even been implemented without using an order defined on the elements
>> of the set.

> Yes, and so what? It still has an order between elements. That order doesn't

See above: The order needs to be constant for the data type "ordered set".

> have to be determined by the values of the elements, as you seem to be
> assuming. It could be determined by the address of the memory used or the
> ordering of some handle type, or by phase of the moon. But it isn't possible
> to have a set of elements without some order (at least on the sorts of
> machines that Ada was intended to program).
>
>> So the even the statement "one cannot implement a set (with or without
>> iteration) without providing an order over the elements" is plainly
>> wrong.
>
> A linked list sure;y provides an order for the elements. Why you insist on
> that order coming from the outside is beyond me. 

I hope my arguments from above make that clear. There is a lot of
confusion going on here, what "ordered set" means: Not anything that
occurs in a certain order at a given instance is ordered. Next time I
put the same elements in the linked list, they are there in a
different order: That is not what I understand would be an ordered
container / set / data type.

Esp. if you refer everything back to DKs original statement: "One
cannot iterate over relational tables, because they are
unordered". Since your interpretation says that implicitely an "order"
(in your sense of the word) exists anyway, one can iterate over
relational tables -- but that cannot have been what DK meant.

> Even as hashed set doesn't
> meet your requirements for "order", which is completely ridiculous.

Completely ridiculous? Is that name calling now? I mean, I've been
probably the only one even trying to achieve some amount of precision
in this discussion.

>
>> (And no: The linked list doesn't define an order on all possible
>> elements of the set.)
>
> An who cares about that? 

See the definition of the data type "ordered set".

> Any particular set of elements has an order. I
> don't much care if a different set object has a different order on the same
> elements. It's irrelevant. "An order" is not the same as "a defined order"
> or "the same order for any pair of elements with the same value".

An order in your definition just means: I can iterate over the
components or elements. In my opinion that is not what the discussion
was about (and more proof how skillfull DK got everyone confused).

> Indeed, any ordering between the values of the elements is completely
> unrelated to the abstract set properties. Any operations that depend on such
> an order are not set operations at all.

> In any case, this is an Ada forum, and abstractions that you cannot describe
> in Ada are simply not relevant (certainly not as the basis of containers).

I beg to differ. Ada is not a specification language. DK has been
bringing up the issue of "you cannot state the contract under this and
that circumstances". There are abstractions (and iterating over sets
is one of them) where you can indeed not state the contract in Ada
(but in any functional specification notation like VDMSL or Z), but
which you can implement in Ada. Without the help of the "outside
agency" of a formal specification language one can spent eons
discussing (a) wether the contract can be stated / makes sense and (b)
can be implemented.

> Any Ada implementation will have some implied ordering between the elements
> in the set.

Who cares about implementation? DKs arguments were about contracts and
interfaces mostly. Exactly since we're in an Ada news group, shouldn't
we separate them -- even in discussion?

> My contention always has been that "sets" are an irrelevant abstraction from
> a programming perspective. 

I disagree. If I just have a bag of thingies I need to process, I can
use a list or a set. Sets are sometimes nearer to the original
intention (no implied order, random access).

> They're too inefficient to use for any purpose.

The set operations might be. Personally I see a set data type as a
container with an unspecified order of iteration and for which I don't
have to provide a key.

> What Ada.Containers calls a set is really a map where the keys are included
> as part of the elements. 

That is implementation again. If it works as a set (interface) it is a set.

> Yes, they have some set operations because some people thought if
> they were called sets they should have those operations. I would
> have preferred choosing a more sane name, but whatever.

> And I would hope that I was done reading this bulls***, but I'm sure I'm
> not...

Sorry. I'll stop. No sense in annoying people. But I'm a bit pained
that you characterize my "contribution" as BS, whereas you tolerate
DKs prevarications pretty well. Never mind.


Regards -- Markus