Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.lang.c Subject: Re: Baby X is bor nagain Date: Sun, 23 Jun 2024 23:30:55 +0100 Organization: A noiseless patient Spider Lines: 206 Message-ID: <87bk3rpa00.fsf@bsb.me.uk> References: <20240617002924.597@kylheku.com> <20240618115650.00006e3f@yahoo.com> <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> MIME-Version: 1.0 Content-Type: text/plain Injection-Date: Mon, 24 Jun 2024 00:30:57 +0200 (CEST) Injection-Info: dont-email.me; posting-host="2fe2b5b522b691828527b639c59887b1"; logging-data="584944"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19cAFcdzKDec6k9TbYgDyeledPwg2BJpN8=" User-Agent: Gnus/5.13 (Gnus v5.13) Cancel-Lock: sha1:4vj6Jqrp8jNyvy0jdHLWzVL3DjM= sha1:lBS0drNnzKDPmSYSk3RiDkkxBKE= X-BSB-Auth: 1.2f46db75818ebf80d52b.20240623233055BST.87bk3rpa00.fsf@bsb.me.uk Bytes: 11268 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. If cmp(&a, &b) == -32 then cmp(&a, &b) must always be negative (though not always -32) and cmp(&b, &a) must always be positive. To me, this reading is backed up by the remark about "regardless of where in the array they are". > 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? 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. > 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. >>> Try a web search >>> >>> "consistent with" definition >>> >>> for more explanation. >> >> Seriously? > > Yes, it's a serious suggestion, and I'm sorry if it came across as > condescending. I did this search myself, and learned something from > it. 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. I find that /inconsistent/ with what I've previously inferred about your knowledge of English, but I have to take your word for it. 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. >>> Also, for "one another", if we say the >>> children in the Jones family get along with one another, we don't >>> mean that each child gets along with at least one of the others, >>> but instead mean that every child gets along with every other >>> child, that is, that they all get along with each other. >> >> The sentence in question has, to my mind, already stated what the >> "one another" refers to -- the multiple calls between pairs >> containing the same objects. I get you think that's not the >> intended meaning, but I get my reading so strongly that I struggle >> to see the other. > > Yes, I got that. The incongruity between the first sentence and the > second sentence prompted me to re-examine the entire paragraph, > which is what eventually led me to my current reading. > > >>> Whether >>> or not some other reading (of that problem sentence in the C >>> standard) is sensible, surely the reading I have suggested is a >>> plausible one. Do you agree? It seems clear, given how the >>> second sentence is phrased, that this suggested reading is what >>> was intended. >> >> I still can't read it the way you do. Every time I try, I find >> the consistency is to be taken as applying to the results of the >> multiple calls between pairs of the same objects. Nothing more. >> It starts with "When the same objects". It seems so clear that >> the consistency is all about the multiple calls with these same >> objects. I keep trying to see your reading of it, but I can't. > > Yes, the phrase "the same objects" starts one down a wrong path. > What I think is meant is that "sameness" applies to objects > individually, without regard to what the object is being compared > to. It's a tricky point because it isn't literally the same object: > what is meant is the same "logical" object, not the same physical > object. If you think of "the same objects" as meaning a set of > individual logical objects, rather than pairs of logical objects, > that might be a way to dislodge the (unfortunately all too easy > to fall into) initial impression. Can you express this mathematically? I can't follow these words at all. I am clearly getting mentally old. >>> I don't mean to defend the quality of writing in this passage. >>> Certainly it would be nice if the meaning could have been stated ========== REMAINDER OF ARTICLE TRUNCATED ==========