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,f6c360ce344b2364 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Received: by 10.68.241.162 with SMTP id wj2mr3151549pbc.2.1340917172352; Thu, 28 Jun 2012 13:59:32 -0700 (PDT) Path: l9ni30824pbj.0!nntp.google.com!news2.google.com!goblin3!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail From: Simon Wright Newsgroups: comp.lang.ada Subject: Re: My Invention of "Bug Sort". Date: Thu, 28 Jun 2012 21:59:31 +0100 Organization: A noiseless patient Spider Message-ID: References: <3852c348-a728-44ed-b065-c8a596c1e235@googlegroups.com> <698085ff-6ca3-4a0e-b963-11bdcf11e6b5@googlegroups.com> <1u9ig9nnen59q$.ajozwlsekr7l.dlg@40tude.net> Mime-Version: 1.0 Injection-Info: mx04.eternal-september.org; posting-host="LMJhXS5IH0shMCju9uQ6VA"; logging-data="32029"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+PRrSHYlhstzND4gvcRJDYiM9w9SsIJgg=" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.1 (darwin) Cancel-Lock: sha1:MaazByb0kwMXD23MpmsmnB7Q6qE= sha1:a+Q0sSoQ4M4kxJ2xE5rnJMI9VtU= Content-Type: text/plain Date: 2012-06-28T21:59:31+01:00 List-Id: "Randy Brukardt" writes: > "Simon Wright" wrote in message > news:m2sjdnyrlh.fsf@pushface.org... > ... >> I notice http://www.ada-auth.org/standards/12rm/html/RM-A-18.html#p5 - >> the last part of this is very terse. Wikipedia suggests that "(or both)" >> should be added. But I'm still baffled; and this paragraph appears to be >> for users, not implementers! > > This is the definition of "strict weak ordering", it is described as > precisely as possible. There's nothing really here for users; I don't think > its possible to define this informally and have it make any sense. As Niklas has noted, the implementer doesn't provide the ordering function and can't control it. The only people who need to decide whether the ordering function is OK are the developers (which is the group I meant by "users"; the users of the compiler). It may be necessary to understand this definition if you are a compiler writer, but there are going to be a lot of developers who will have real trouble with it. Including me (I was a physicist, not a mathematician). I think the Standard would be better without the last sentence of (5); give us a reference if you like. The RM says 'if x < y for any values x and y, then for all other values z, (x < z) or (z < y).'. Wikipedia[1] says 'in which the relation "neither a < b nor b < a" is transitive", which seems a lot clearer to me. Wikipedia[2] lists as the fourth condition 'For all x, y, and z, if x is incomparable with y, and y is incomparable with z, then x is incomparable with z (transitivity of equivalence).' which is also clear, aside from the use of 'incomparable' to mean, I think, 'equivalent'. [1] http://en.wikipedia.org/wiki/Strict_weak_ordering [2] http://en.wikipedia.org/wiki/Strict_weak_ordering#Properties > I have no > idea where you are adding "or both", but if it is to the end of the > sentence, it's unnecessary as the truth table for "or" includes True or True > = True. "or" is not "xor"! (I realize that when writing English, there is an > ambiguity - "or" sometimes is taken to mean "xor". That might explain why > wikipedia would say that. But this is an Ada text, and "or" is well-defined > here - and it's not "xor"!!) Oh? so what about (3), "the desired average or worst case". > As to why you're baffled, I can't say; this is pretty straightforward > algebra. What else could this say? (Without the "strict weak ordering" > requirement, it's impossible to have a complete ordering and we cannot > expect implementations to do sensible things in that case.) I completely understand that ">" must have certain properties. I can;t grasp the formulation; maybe it's age.