Re: Baby X is bor nagain

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.  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.  Try a web search

    "consistent with" definition

for more explanation.  Also, for "one another", if we say the
children in the Jones family get along with one another, we don't
mean that each child gets along with at least one of the others,
but instead mean that every child gets along with every other
child, that is, that they all get along with each other.  Whether
or not some other reading (of that problem sentence in the C
standard) is sensible, surely the reading I have suggested is a
plausible one.  Do you agree?  It seems clear, given how the
second sentence is phrased, that this suggested reading is what
was intended.

I don't mean to defend the quality of writing in this passage.
Certainly it would be nice if the meaning could have been stated
more plainly.  But I think it's an overstatement to say that the
first sentence in no way implies a total order.