Ben Bacarisse <
ben@bsb.me.uk> writes:
(I am lazily keeping everything so I don't have to
think about what to exclude. I have changed some
white space but otherwise it's all here.)
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:
>
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.
>
I would not introduce your new term, "an ordering contradiction",
since it still leaves exactly what kind of order vague.
My original thinking was that "ordering contradiction" would be a
good choice for your benefit, not that it would be good phrasing
for the C standard. Apparently my aim was not so good.
You interpret "consistent" as "consistent with a total order"
Actually I don't. More below.
so I'd use that phrase:
>
"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 be consistent with a
total order"
>
Presumably you came to interpret "consistent with one another" as
implying a total order rather because of the sentence that follows
("That is, for qsort they shall define a total ordering on the
array").
Actually not. To me the two sentences are not equivalent. More
specifically, the first is weaker than the second. More below.
I could not do that because I was interpreting the text about
multiple calls differently.
Yes, I understand that now, moreso than before.
... 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.
>
...
>
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 never thought they were the same. The trouble is that (a)
different results imply the same order (e.g. -1 and -34 all mean
<) and (b) the (old) wording does not say that the objects are
passed in the same order and the result of cmp(a, b) can't be the
same as cmp(b, a) but they can be consistent. This makes
"consistent with one another" a perfectly reasonable thing to say
even in my limited view of what results are being talked about.
It's interesting that our mental pictures here are so different.
To me there is no difference between a return value of -1 and a
return value of -34. To say that more generally, different
return values that have the same meaning are the same result.
That idea also applies changing the order of operands, so a
compare( a, b ) being positive is the same result as getting a
negative value from compare( b, a ). "Results" of a comparison
between a and b are either a<b, a==b, or a>b. The actual values
returned are incidental (and probably aren't even looked at
except to compare them to zero).
(That reminds me, I have a little challenge/puzzle exercise that
might be fun for people, and it is related to the previous
paragraph, so maybe that will get me to post it.)
Because I see "sameness of results" as being determined by
meaning, and not by what particular values come back, it wouldn't
have occurred to me to think "consistent with" was there just to
account for differences in the values. That difference in
viewpoint may account for much of the difference in our first
impressions of the "consistent with one another" sentence in the
C standard.
>
...
>
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.
>
...
>
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.
>
[Technical aside. The relation should be seen as <=. not <. You
can't conclude that I intended A < A from the informal
presentation -- no dog can be behind itself. However, this does
not alter your argument in any significant way.]
Different authors define "total ordering" differently. Also some
authors base the discussion on < rather than <=. I'm taking your
comment above narrowly in that it is meant to apply only to the
dog-order example, and not meant to be universal. However, if
the dog-order relation is meant to be <= rather than <, then the
dog-order example is consistent with "total orderings that allow
equality". The C standard uses "total ordering" in this sense,
because the comparison function can return an "equal" result for
distinct objects. For contrast, the integers have a "total
ordering that does not allow equality": for any two distinct
integers, it is always the case that one of them is less than the
other (and they are never equal). To me it's a little bit funny
to call a set "totally ordered" if equality is allowed, although
of course I understand what is meant in such cases.
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 would say this is backwards. You are assuming the usual rules
where I gave an order that is not at all usual with the purpose of
showing that some sets of comparisons between pairs can be
"consistent with one another" when the ordering is very peculiar.
I didn't understand before that you meant the "behind" relation
to be one that might not satisfy the axioms of "less than", but
rather just the axioms of "less than or equal". So I missed that
point earlier. Hopefully I'm caught up now.
On a more mathematical note, imagine that the text was describing
a topological sort function. Is there anything in your reading of
the first sentence that would make it inappropriate? If not, that
"consistent with one another" can't imply a total order.
I take up this question when it is raised again below.
...
>
It occurs to me now to say that "consistent with" is meant to
include logical inference.
>
Sure.
>
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;
>
But, according to you, only some ordering relations.
I am guilty of somewhat sloppy language there. Strictly speaking
an ordering relation is all the ordered pairs that define the
relationship. The results of all the comparisons done corresponds
(at least usually) to only a subset of the ordered pairs of an
ordering relation. The qsort function needs to do only enough
comparisons so that the closure of those results defines a total
ordering. As long as the set of comparisons actually done is a
subset of some totally ordered relation then the program is okay
and hasn't wandered off into the UB weeds. However, if the set
of all N*(N-1) comparisons (which includes reversing the argument
orders) would give results that are not a subset of a total
ordering, then which total ordering is determined (by a qsort
call that doesn't encounter UB) depends on which comparisons were
actually done. Considering all that I think my last sentence
above is better stated as "the results of the comparison calls
performed corresponds to a subset of some 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.
>
Could the sentence in question be used in the description of a
topological sort based (rather unusually) on a partial order?
Short answer: doing a topological sort requires a different
interface, and that change of context changes the meaning of the
phrase "consistent with one another".
Longer answer: the comparison function in the qsort interface is
specified as giving one of three results: a<b, a==b, a>b. The
returned value must indicate one of those three possibilities.
To do a (general) topological sort, there needs to be another
possibility, namely, that a and b are unrelated. There are now
four mutually exclusive possibilities. Note that "unrelated"
cannot be the same as "equal". The reason is that "equal" is
transitive but "unrelated" is not. In particular, we can have
a!=!b, b!=!c, but a<c rather than a!=!c (using !=! to mean
"unrelated"). That combination cannot occur for equal: if a==b
and b==c, then a==c. I expect you are already familiar with
these ideas; I'm going through them mainly as a check on my own
thinking.
A literal answer to your question is that the sentence about
being "consistent with one another" could also be used in a
different function that would do topological sorts. But the
meaning of the sentence would be different, because of changes in
how the comparison function would have to be specified. I guess
I should add, as I understand the meaning of these passages in
the C standard.
To me, the meaning of the phrase "consistent with one another" is
meant to be taken relative to the specifications of the comparison
function, whose results are three mutually exclusive cases: less
than, equal to, greater than. The C standard tacitly takes the
view that these operations behave like the ones we learned about
in grade school. As long as the results of comparisons done are
not in conflict with a logically valid deduction, under the usual
mathematical rules for these elementary relationships, with all of
the comparison results assumed as being true as a starting point,
then the condition of the first sentence is satisfied. But that
being true does not by itself show that the comparison results
define a total ordering.
To conclude that the comparison results define a total ordering,
we need to add what the standard says about the return value of
qsort, namely, that array elements are placed in ascending order.
This condition can be achieved only enough comparisons have been
done to determine a total order. The second sentence augments
the "consistent with" condition in the first sentence with a
tacit recognition of the qsort return condition to say comparison
results must define a total ordering. So a full statement might
be that the comparison results shall be consistent with one
another and they shall be sufficient to determine the total
ordering required by the output condition. The C standard
collapses those two parts down into the shorter second sentence.
In any case that's how I read this part of the standard. I hope
that clarifies my earlier statements.
Baby X is bor nagain
Mac users (Was: Baby X is bor nagain)