Path: ...!feeds.phibee-telecom.net!3.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Baby X is bor nagain Date: Wed, 26 Jun 2024 12:59:28 -0700 Organization: A noiseless patient Spider Lines: 376 Message-ID: <86frszeaqn.fsf@linuxsc.com> References: <20240618184026.000046e1@yahoo.com> <877celzx14.fsf@nosuchdomain.example.com> <87iky3svqh.fsf@bsb.me.uk> <874j9nxsdy.fsf@nosuchdomain.example.com> <874j9ns382.fsf@bsb.me.uk> <86h6dlhb34.fsf@linuxsc.com> <8734p3rjno.fsf@bsb.me.uk> <868qyvhai4.fsf@linuxsc.com> <87bk3rpa00.fsf@bsb.me.uk> <86ikxyg1rs.fsf@linuxsc.com> <87cyo5oodb.fsf@bsb.me.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Wed, 26 Jun 2024 21:59:31 +0200 (CEST) Injection-Info: dont-email.me; posting-host="389a59347657690f81d51c7ad74582bc"; logging-data="2432835"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18fkQ8tjmjO+jzN+bmvhTGLsa8Noc3RAo8=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:N8cp0i+lKHwfQzs8uRLXDuR4+cU= sha1:laS1/qjN35e/RDP8nWLRsUeH/Gw= Bytes: 19811 Ben Bacarisse writes: (I am lazily keeping everything so I don't have to think about what to exclude. I have changed some white space but otherwise it's all here.) > Tim Rentsch writes: > >> Ben Bacarisse writes: >> >>> Tim Rentsch writes: >>> >>>> Ben Bacarisse writes: >>>> >>>>> Tim Rentsch writes: >>>>> >>>>>> Ben Bacarisse writes: >>>>>> >>>>>>> Keith Thompson writes: >>>>>>> >>>>>>>> Ben Bacarisse writes: >>>>>>>> [...] >>>>>>>> >>>>>>>>> On a C language point, I don't think the standard says >>>>>>>>> anything about sorting with non-order functions like the one >>>>>>>>> above. Is an implementation of qsort permitted to misbehave >>>>>>>>> (for example by not terminating) when the comparison >>>>>>>>> function does not implement a proper order relation? >>>>>>>> >>>>>>>> N1570 7.22.5p4 (applies to bsearch and qsort): >>>>>>>> """ >>>>>>>> When the same objects (consisting of size bytes, irrespective >>>>>>>> of their current positions in the array) are passed more than >>>>>>>> once to the comparison function, the results shall be >>>>>>>> consistent with one another. That is, for qsort they shall >>>>>>>> define a total ordering on the array, and for bsearch the >>>>>>>> same object shall always compare the same way with the key. >>>>>>>> """ >>>>>>>> >>>>>>>> That's a "shall" outside a constraint, so violating it >>>>>>>> results in undefined behavior. >>>>>>> >>>>>>> I think it should be clearer. What the "that is" phrase seems >>>>>>> to clarify in no way implies a total order, merely that the >>>>>>> repeated comparisons or the same elements are consistent with >>>>>>> one another. That the comparison function defines a total >>>>>>> order on the elements is, to me, a major extra constraint that >>>>>>> should not be written as an apparent clarification to >>>>>>> something the does not imply it: repeated calls should be >>>>>>> consistent with one another and, in addition, a total order >>>>>>> should be imposed on the elements present. >>>>>> >>>>>> I think you're misreading the first sentence. >>>>> >>>>> Let's hope so. That's why I said it should be clearer, not that >>>>> it was wrong. >>>>> >>>>>> Suppose we are in court listening to an ongoing murder trial. >>>>>> Witness one comes in and testifies that Alice left the house >>>>>> before Bob. Witness two comes in (after witness one has gone) >>>>>> and testifies that Bob left the house before Cathy. Witness >>>>>> three comes in (after the first two have gone) and testifies >>>>>> that Cathy left the house before Alice. None of the witnesses >>>>>> have contradicted either of the other witnesses, but the >>>>>> testimonies of the three witnesses are not consistent with one >>>>>> another. >>>>> >>>>> My (apparently incorrect) reading of the first sentence is that >>>>> the consistency is only required between the results of multiple >>>>> calls between each pair. In other words, if the witnesses are >>>>> repeatedly asked, again and again, if Alice left before Bob >>>>> and/or if Bob left before Alice the results would always be >>>>> consistent (with, of course, the same required of repeatedly >>>>> asking about the other pairs of people). >>>> >>>> Let me paraphrase that. When the same pair of objects is passed >>>> more than once to individual calls of the comparison function, >>>> the results of those different calls shall each be consistent >>>> with every other one of the results. >>> >>> No, only with the results of the other calls that get passed the >>> same pair. [...] >> >> Sorry, my oversight. That's is what I meant. "When the same pair >> of objects is passed more than once to individual calls of the >> comparison function, the results of those different calls shall >> each be consistent with every other one of THOSE results." The >> consistency is meant to be only between results of comparisons of >> the same pair. (This mistake illustrates how hard it is to write >> good specifications in the C standard.) >> >>>> To paraphrase my reading, when some set of "same" objects is each >>>> passed more than once to individual calls of the comparison >>>> function, the results of all of those calls taken together shall >>>> not imply an ordering contradiction. >>>> >>>> Are the last two paragraphs fair restatements of our respective >>>> readings? >>> >>> I don't think so. The first does not seem to be what I meant, and >>> the second begs a question: what is an ordering contradiction? >> >> A conclusion that violates the usual mathematical rules of the >> relations less than, equal to, greater than: A> AA, etc. >> >>> Maybe I could work out what you mean by that if I thought about it >>> some more, but this discussion has reminded me why I swore not to >>> discuss wording and interpretation on Usenet. You found the >>> wording adequate. I didn't. I won't mind if no one ever knows >>> exactly why I didn't. C has managed fine with this wording for >>> decades so there is no practical problem. I think enough time has >>> been spent on this discussion already, but I can sense more is >>> likely to spent. >> >> A small correction: I found the wording understandable. If the >> question is about adequacy, I certainly can't give the current >> wording 10 out of 10. I would like to see the specification for >> qsort stated more plainly. Although, as you can see, I'm having >> trouble figuring out how to do that. >> >>>> Is the second paragraph plain enough so that you would not >>>> misconstrue it if read in isolation? Or if not, can you suggest >>>> a better phrasing? >>> >>> Since I don't know what an ordering contradiction is, I can't >>> suggest an alternative. >> >> Now that I have explained that phrase, I hope you will have a go >> at finding a better wording. > > I would not introduce your new term, "an ordering contradiction", > since it still leaves exactly what kind of order vague. My original thinking was that "ordering contradiction" would be a good choice for your benefit, not that it would be good phrasing for the C standard. Apparently my aim was not so good. > You interpret "consistent" as "consistent with a total order" Actually I don't. More below. > so I'd use that phrase: > > "when some set of 'same' objects is each passed more than once > to individual calls of the comparison function, the results of > all of those calls taken together shall be consistent with a > total order" > > Presumably you came to interpret "consistent with one another" as > implying a total order rather because of the sentence that follows > ("That is, for qsort they shall define a total ordering on the > array"). Actually not. To me the two sentences are not equivalent. More specifically, the first is weaker than the second. More below. > I could not do that because I was interpreting the text about > multiple calls differently. Yes, I understand that now, moreso than before. >>>> ... The important point is the "consistent with" is something of >>>> an idiomatic phrase, and it doesn't mean "equivalent to" or "the >>>> same as". Maybe you already knew that, but I didn't, and >>>> learning it helped me see what the quoted passage is getting at. > > ... > >>> If you care to be less cryptic, maybe you will say what it was >>> about the meaning of "consistent with" that helped you see what >>> the text in question was getting at. >> >> I think the key thing is that "consistent with" doesn't mean the >> same. If we're comparing the same pair of objects over and over, >> the results are either the same or they are different. It would >> be odd to use "consistent with one another" if all that mattered >> is whether they are all the same. > > I never thought they were the same. The trouble is that (a) > different results imply the same order (e.g. -1 and -34 all mean ========== REMAINDER OF ARTICLE TRUNCATED ==========