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 <tr.17687@z991.linuxsc.com>
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: <v494f9$von8$1@dont-email.me> <v4rv0o$1b7h1$1@dont-email.me> <20240618184026.000046e1@yahoo.com> <v4sd75$1ed31$1@dont-email.me> <877celzx14.fsf@nosuchdomain.example.com> <v4u85k$1t2pu$2@dont-email.me> <v4ucmn$1u14i$1@dont-email.me> <v4v2br$22c0m$1@dont-email.me> <v4v5nu$230rh$2@dont-email.me> <v4vfrn$24rv6$1@dont-email.me> <v50n9s$2fkko$1@dont-email.me> <v50poh$2g4ha$1@dont-email.me> <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 <ben@bsb.me.uk> 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 <tr.17687@z991.linuxsc.com> writes:
>
>> Ben Bacarisse <ben@bsb.me.uk> writes:
>>
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>
>>>> Ben Bacarisse <ben@bsb.me.uk> writes:
>>>>
>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>>
>>>>>> Ben Bacarisse <ben@bsb.me.uk> writes:
>>>>>>
>>>>>>> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>>>>>>>
>>>>>>>> Ben Bacarisse <ben@bsb.me.uk> 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<B and B<C implies
>> A<C, A<B implies A!=B, A=B implies not A<B, A<B implies B>A, 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 ==========