Path: ...!feed.opticnetworks.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben@bsb.me.uk>
Newsgroups: comp.lang.c
Subject: Re: Baby X is bor nagain
Date: Tue, 25 Jun 2024 01:30:24 +0100
Organization: A noiseless patient Spider
Lines: 233
Message-ID: <87cyo5oodb.fsf@bsb.me.uk>
References: <v494f9$von8$1@dont-email.me> <20240618115650.00006e3f@yahoo.com>
	<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>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Tue, 25 Jun 2024 02:30:26 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="b2e0149f9e88712508ba5999d7ddf609";
	logging-data="1265544"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/6ABkAQC2sGq+CNcPTiEfBXTLiEHK/Jls="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:vjTfo0t53vi+9BRMreaoRVYcyQ0=
	sha1:7BUieuNoprUMZ7M5cMKEHHFQFV4=
X-BSB-Auth: 1.e8c39543ceaad9da0d9a.20240625013024BST.87cyo5oodb.fsf@bsb.me.uk
Bytes: 12677

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.  You interpret
"consistent" as "consistent with a total order" 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").

I could not do that because I was interpreting the text about multiple
calls differently.

>>> ... 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 <) and (b) the
(old) wording does not say that the objects are passed in the same order
and the result of cmp(a, b) can't be the same as cmp(b, a) but they can
be consistent.  This makes "consistent with one another" a perfectly
reasonable thing to say even in my limited view of what results are
being talked about.

....
>>>> I have a second objection that promoted that remark.  If I take the
>>>> (apparently) intended meaning of the first sentence, I think that
>>>> "consistent" is too weak to imply even a partial order.  In dog club
>>>> tonight, because of how they get on, I will ensure that Enzo is
>>>> walking behind George, that George is walking behind Benji, Benji
>>>> behind Gibson, Gibson behind Pepper and Pepper behind Enzo.  In what
>>>> sense is this "ordering" not consistent?  All the calls to the
========== REMAINDER OF ARTICLE TRUNCATED ==========