Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Keith Thompson <Keith.S.Thompson+u@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: Baby X is bor nagain
Date: Thu, 20 Jun 2024 18:42:23 -0700
Organization: None to speak of
Lines: 76
Message-ID: <87frt7vzpc.fsf@nosuchdomain.example.com>
References: <v494f9$von8$1@dont-email.me> <20240613174354.00005498@yahoo.com>
	<v4okn9$flpo$2@dont-email.me> <20240617002924.597@kylheku.com>
	<v4pddb$m5th$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>
	<v52j9m$2qmmk$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Fri, 21 Jun 2024 03:42:23 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="27ab6fe7c7a579af676e0838983f63cb";
	logging-data="2969432"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/P45x2o5taWxJDjGEwZkez"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux)
Cancel-Lock: sha1:um7LPOBWAOF64yxOmN9KfJzqtn0=
	sha1:GyUMsffcFEDg3VfkztqtnNp7Bbc=
Bytes: 5092

James Kuyper <jameskuyper@alumni.caltech.edu> writes:
> On 6/20/24 17:39, Ben Bacarisse wrote:
>> 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.
>
> I don't think they were talking only about multiple comparisons of the
> same value producing the same result. I think that they were also
> talking about consistency between the result on different pairs of
> values. In order to sort a, b, and c, the results of comp(a,b),
> comp(b,c) and comp(a,c) need to be consistent with each other, or
> there's no well-defined sort order. "total order" is merely a more
> specific and precise way of specifying that consistency requirement, but
> it is a consistency requirement, and therefore the most plausible kind
> of consistency they could have been referring to with that comment.

That's the charitable reading, and certainly what was intended.

The problem is that if the authors had meant to say:

    1. For any objects A and B, two or more calls compar(A, B) shall
       return equivalent results and compar(B, A) shall return a result
       opposite to that returned by compar(A, B).

    2. Statement 1 implies that compar() shall implement a total
       order.

(where statement 2 is clearly incorrect), they could have used the exact
words in the standard to express that.

There's no doubt that the intent was to require a total order (more
precisely, qsort() has undefined behavior if compar doesn't implement a
total order), but the first sentence implies that only with a strained
reading, and only if we already know what the intent was.

Dropping the "That is" in the second sentence would make it clear that
the total order is a requirement and is not necessarily a consequence of
the first sentence.

I don't suggest that any implementer or programmer will be seriously led
astray by a painfully literal reading the current wording, only that it
can be improved.

It wouldn't hurt to explicitly talk about the relationship between
compar(A, B) and compar(B, A), but that's reasonably implied by the
current consistency requirement.

Oh, and why is the comparison function called "compar" rather than
"compare"?  Is it based on ancient limits on identifier lengths?

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */