From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,229ea0001655d6a2 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit From: "Randy Brukardt" Newsgroups: comp.lang.ada Subject: Re: Generic Package Date: Wed, 2 May 2007 19:37:35 -0500 Organization: Jacob's private Usenet server Message-ID: References: <1177539306.952515.222940@s33g2000prh.googlegroups.com> <1177601484.444701.171560@r35g2000prh.googlegroups.com> <9eejm6rqip.fsf@hod.lan.m-e-leypold.de> <19qllkvm6ut42$.1iqo74vjgmsrv$.dlg@40tude.net> <1177801611.10171.32.camel@localhost.localdomain> <1woad6hn9idy2$.6otnwphc1o0h$.dlg@40tude.net> <1177929029.6111.34.camel@localhost> <1177944533.13970.17.camel@localhost> <2aq08qbvw0ym$.1rquampzo7o53.dlg@40tude.net> <1ieq3io2d6nnq$.13818v3y35gnr.dlg@40tude.net> <1178010142.6695.29.camel@localhost.localdomain> <1178026941.16837.88.camel@localhost.localdomain> <1ozvzzh59ebq8$.yeh9do8s3hig$.dlg@40tude.net> <40irbbzm2t.fsf@hod.lan.m-e-leypold.de> NNTP-Posting-Host: static-69-95-181-76.mad.choiceone.net X-Trace: jacob-sparre.dk 1178152533 19821 69.95.181.76 (3 May 2007 00:35:33 GMT) X-Complaints-To: news@jacob-sparre.dk NNTP-Posting-Date: Thu, 3 May 2007 00:35:33 +0000 (UTC) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2800.1807 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1807 Path: g2news1.google.com!news3.google.com!proxad.net!feed.ac-versailles.fr!news.ecp.fr!news.jacob-sparre.dk!pnx.dk!not-for-mail Xref: g2news1.google.com comp.lang.ada:15471 Date: 2007-05-02T19:37:35-05:00 List-Id: "Markus E Leypold" wrote in message news:40irbbzm2t.fsf@hod.lan.m-e-leypold.de... > "Randy Brukardt" writes: > > > "Dmitry A. Kazakov" 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. Besides, you're going to claim the same about me in your reply to this message... ;-) > > 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. But a set where you don't specify the order is still an ordered set: there exists an order between the elements, even if you don't know what it is and don't have to describe it. > 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. > 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. 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 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. Even as hashed set doesn't meet your requirements for "order", which is completely ridiculous. > (And no: The linked list doesn't define an order on all possible > elements of the set.) An who cares about that? 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". 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). Any Ada implementation will have some implied ordering between the elements in the set. My contention always has been that "sets" are an irrelevant abstraction from a programming perspective. They're too inefficient to use for any purpose. What Ada.Containers calls a set is really a map where the keys are included as part of the elements. 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... Randy.