Re: Baby X is bor nagain

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.

Try a web search
>
    "consistent with" definition
>
for more explanation.

>
Seriously?

>
Yes, it's a serious suggestion, and I'm sorry if it came across as
condescending.  I did this search myself, and learned something from
it.  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.

>
I find that /inconsistent/ with what I've previously inferred about
your knowledge of English, but I have to take your word for it.

In many cases my knowledge of English that is on display here
comes only after the fact.  I routinely look up words and phrases
during the process of composing messages for the newsgroups.

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 suppose some people would
think that compare(A,B) < 0 and compare(B,A) > 0 are different
results, but at least for qsort I don't.)  If "consistent with
one another" doesn't mean "all the same", then "the same objects"
must not mean the same pairs over and over.  I'm guessing about
what happened because my thought process was not a completely
conscious one, but this line of reasoning seems plausible.

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.

>
The sentence in question has, to my mind, already stated what the
"one another" refers to -- the multiple calls between pairs
containing the same objects.  I get you think that's not the
intended meaning, but I get my reading so strongly that I struggle
to see the other.

>
Yes, I got that.  The incongruity between the first sentence and the
second sentence prompted me to re-examine the entire paragraph,
which is what eventually led me to my current reading.
>
>

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 still can't read it the way you do.  Every time I try, I find
the consistency is to be taken as applying to the results of the
multiple calls between pairs of the same objects.  Nothing more.
It starts with "When the same objects".  It seems so clear that
the consistency is all about the multiple calls with these same
objects.  I keep trying to see your reading of it, but I can't.

>
Yes, the phrase "the same objects" starts one down a wrong path.
What I think is meant is that "sameness" applies to objects
individually, without regard to what the object is being compared
to.  It's a tricky point because it isn't literally the same object:
what is meant is the same "logical" object, not the same physical
object.  If you think of "the same objects" as meaning a set of
individual logical objects, rather than pairs of logical objects,
that might be a way to dislodge the (unfortunately all too easy
to fall into) initial impression.

>
Can you express this mathematically?  I can't follow these
words at all.  I am clearly getting mentally old.

Something like this:  if we label values in the array with their
initial position in the array, where the label stays with the
value when array elements are exchanged, consider now the set of
labels whose corresponding objects are each passed to the
comparison function more than once;  this in turn induces a set
of ordering relationships on the labels.  Then the set of label
order relationships must obey the usual mathematical rules for
the ordering relations less than, equal to, and greater than.

Not the best writing I've ever done there.  It is at least a bit
more mathematical.

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.

>
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
comparison function are consistent with each other.

>
I understand the objection, and this is the point I was trying to
make in the paragraph about children in the Jones family.  The
phrase "one another" in "the results shall be consistent with one
another" is meant to be read as saying "all the results taken
together".  It is not enough that results not be contradictory taken
two at a time;  considering all the results at once must not lead to
an ordering contradiction.

>
So you agree that the first sentence in no way implies a total order?

Well, no, I wouldn't say that.  The first sentence does in /some/
ways imply a total order.  Unfortunately it can be read in other
ways that do not imply a total order.  But I can't say that in
no way does it imply a total order.

All the results of the dog-order comparison function, taken together,
are consistent with the circular order, which is obviously not a total
order.

If A<B, B<C, C<D, D<E, and E<A, we can infer from the transitivity
of the "less than" relation that A<A.  But A<A can never be true, so
this set of comparison results is no good.  So I guess what we have
discovered is that "consistent with one another" is intended to mean
"obeys the usual mathematical rules for ordering relations".

I must be missing something because you don't say anything else to
indicate a change of opinion.  Are you making what to me is a circular
argument that consistent means consistent with a total order, not some
other ordering relationship?

The qsort function takes a pointer-to-function argument to perform
comparisons between objects.  That function is obligated to return
an integer less than, equal to, or greater than zero if the first
argument is considered to be respectively less than, equal to, or
greater than the second argument.  "Consistent with" means that the
results indicating less than, equal to, or greater than must obey
the usual mathematical rules, as I tried to explain above, for those
relationships.  That these results define a total ordering is a
consequence of the results obeying the usual mathematical rules.

It occurs to me now to say that "consistent with" is meant to
include logical inference.  That distinction is a key difference
between "consistent" and "consistent with" (at least as the two
terms might be understood).  The combination of:  one, the results
of the comparison function are seen as corresponding to an ordering
relation;  and two, that "consistent with one another" includes
logical inferences considering all of the results together;  is what
allows us to conclude that the results define a total order.

I'm sorry if any of the above sounds like it's just stating the
obvious.  I'm strugging trying to find a way to explain what to
me seems straightforward.

Hopefully this has been helpful for you.  If it hasn't I'd like to
hear where the sticking points are.

>
I think I am a little more confused than I was.

I am confident that the click will happen.

On the other hand, I was surprised the other day
when I looked up "optimist" in the dictionary and
found a picture of myself. ;)