Re: Baby X is bor nagain

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 */