Path: ...!feeds.phibee-telecom.net!news.mixmin.net!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: Mon, 24 Jun 2024 14:25:31 -0700
Organization: None to speak of
Lines: 64
Message-ID: <87v81yrq2c.fsf@nosuchdomain.example.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>
	<v59bhe$ch8p$1@dont-email.me> <86zfrbfsd6.fsf@linuxsc.com>
	<87msnbtes9.fsf@nosuchdomain.example.com> <861q4mflox.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Mon, 24 Jun 2024 23:25:31 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="0a690d6294358a2c4bce5879f14e083a";
	logging-data="1184163"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+YvqsonSvIgNIP+j8mv8OL"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux)
Cancel-Lock: sha1:6MySamcEi2m/wH+fkxtVeXG9zpY=
	sha1:Orf7JVV+dsrTE7binzKkMcqCHTs=
Bytes: 4683

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>> James Kuyper <jameskuyper@alumni.caltech.edu> writes:
>>> [on the requirements for qsort]
>>>> I certainly would favor improved wording that made this clearer.
>>>> In fact, simply explicitly mandating total ordering rather than
>>>> making a vague comment about consistency would probably be the
>>>> best approach.
>>>
>>> Clearly the C standard intends to impose a weaker requirement
>>> than that the comparison function be a total ordering.
>>
>> "That is, for qsort they shall define a total ordering on the
>> array".
>>
>> I presume you didn't intend to contradict that requirement, but
>> I can't figure out what you meant -- unless, as Ben suggested,
>> you're distinguishing between a total ordering of all possible
>> arguments and a total ordering of objects present in the array.
>> But even then, the standard explicitly imposes a total ordering.
>> (The requirements for bsearch might be weaker, but we're discussing
>> qsort.)
>>
>> Can you clarify what you meant?
>
> For starters, saying that the comparison function defines a total
> ordering of elements actually present in the array is already a
> weaker requirement than saying that the comparison function defines
> a total ordering of all values that might legally be present in the
> array.
>
> Now notice that the C standard isn't referring to the comparison
> function in the statement quoted above.  The standard does not say
> "the comparison function shall define".  What it does say is that
> "/they/ shall define".  Those two aren't the same thing.

OK, I see your point.  It's not the comparison function itself that's
required to define a total ordering.  It's the results of the actual
calls to the comparison function that must do so.

In another article, you've constructed an extremely contrived scenario
with a comparison function that, as written, is clearly incorrect (it
always returns -1), but the hypothetical qsort implementation only calls
the comparison function in a way that's consistent with a total ordering
of the array elements.

Practically speaking, it's obvious, I think, that a comparison function
*should* define a total ordering, but there are odd cases where buggy
comparison functions might not result in undefined behavior in a
particular implementation.  The only sane way to define a comparison
function that meets the requirements for qsort is to have it actually
define a total ordering for the elements that can appear in the array.
(In some cases it might be appropriate to take some shortcuts based on
knowledge that some things won't actually appear in the array.)

You're right.

Did it ever occur to you to explain this in the first place?  One
sentence in your original post would have been sufficient.

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