is the < operator transitive?

[Eric Sosman]

Is it certain that ( a<b&& b<c&& !(a<c) ) is 0?
No.

First assume that each of a b c is a constant
per ISO/IEC 9899:1999 6.4.4 ?

None of the counterexamples that I was able to come up with could be
demonstrated using constants, since C constants cannot be negative (-1
is a unary expression, not a constant),[...]

Nitpick:

enum { MINUSONE = -1 };

Now MINUSONE *is* an `int' constant with negative value, hence

(MINUSONE < 0 && 0 < 1u && !(MINUSONE < 1u))

evaluates to 1.

Also, it is implementation-defined whether the constant '$'
is positive or negative. All characters in the "basic execution
set" are non-negative, but the dollar sign and many others one might
encounter are not in the BES.

We now return you to your regularly scheduled pedantry. Er,
I mean, "programming."

 

[James Kuyper]

I'll try. I should go find some code probably but I am a bit short of
time right now...

Operators are marked with a precedence and an associativity. This
latter can be "left", "right" or "none". The heart of the parser deals
with operators with left or no associativity and a priority that is
passed as an argument:

exp = parse_exp_with_prio(priority + 1);
last_right = null;
while (next_token.prio == priority) {
op = next_token;
advance_token();
right = parse_exp_with_prio(priority + 1);
if (last_right != null && op.assoc == none) {
e = make_exp(last_right, op, right);
exp = make_exp(exp, '&&', e);
}
else exp = make_exp(exp, op, right);
last_right = right;
}
return exp;

When called with maximum priority, parse_exp_with_prio matches only
constansts, names, and expressions in brackets. This nested case is
handled by calling parse_exp_with_prio(0).

So "0 < 3" goes round this loop once and builds one expression node
with a < operator.

"2 < 1 < 3" goes round twice. In the second iteration we notice that we
have seen a previous "right operand" of this priority (it will be the
constant 1) and we build (2 < 1) && (1 < 3) while setting last_right to
3 in case there are non-associative operators of the same priority.

"(2 < 1) < 3" parses as normal. The request for exp on the left will
eventually be matched by a call to parse_exp_with_prio with maximum
priority. That will return 2 < 1 after calling parse_exp_with_prio(0)
and matching the closing bracket. This nested call goes round the loop
once. Having get exp on the left, we loop once to build (2 < 1) < 3.

So 2 < 1 < 3 would be different from (2 < 1) < 3. That would bother me;
not because it's so important to allow the current meaning of 2<1<3 to
survive, but because it would be inconsistent with the way parentheses
work in most other C contexts.

 

[James Kuyper]

Is it certain that ( a<b&& b<c&& !(a<c) ) is 0?
No.

First assume that each of a b c is a constant
per ISO/IEC 9899:1999 6.4.4 ?

None of the counterexamples that I was able to come up with could be
demonstrated using constants, since C constants cannot be negative (-1
is a unary expression, not a constant),[...]

Nitpick:

enum { MINUSONE = -1 };

Now MINUSONE *is* an `int' constant with negative value, hence

(MINUSONE < 0 && 0 < 1u && !(MINUSONE < 1u))

evaluates to 1.

You're right, I missed that - so it is possible to demonstrate that '<'
isn't necessarily transitive just using constants:

(98765UL < MINUSONE ) && ( MINUSONE < 1) && !(97865UL < 1)

 

[Patrick Scheible]

[...]
Python comparisons have the cool feature, that a<b<c is the same as
(a<b && b<c). So you can use normal notation for multiple comparisons.

IMO it would be great if this could be backported to C.

The trouble is that ``a < b < c'' already has a meaning in C, so it
would be an incompatible chnage.

Just as ``a + b + c'' is equivalent to ``(a + b) + c'' ``a < b < c'' is
equivalent to ``(a < b) < c''. In other words, it evaluates ``(a <b)'',
which yields a value of 0 or 1, and compares that value to c.

This is just my point, Keith.

I find it hard to believe theres much existing code that deliberately
uses this unintuitive interpretation. However it must be a cause of many
bugs!

The point is that it could *potentially* break existing code, and the
committee is justifiably hesitant to make language changes that do that.

But you may well be right that it would fix more code than it would
break.

Doubtful. New C programmers learn fairly quickly that booleans are
integers. This particular bug should show up quickly in testing, in
most cases.

Another idea might be to *forbid* expressions like a < b < c. This
could still break existing code, but wouldn't quietly give it a new
meaning.

It would be really foolish to forbid a language construction that was
allowed for 40 years.

Some compilers in effect already do this, by issuing a warning. gcc,
for example, warns "comparisons like ‘X<=Y<=Z’ do not have their
mathematical meaning".

That would be more tolerable. Still, it's a bit like the compiler
issuing a warning every time you use = and might have meant ==.

-- Patrick

 

[Ben Bacarisse]

The Icon Programming Language does this, and it's not a special case but
a natural consequence of a well-designed set of operators.

Ah, yes, I'd forgotten that. It wasn't Icon I was thinking about, but
it does indeed do this naturally.

<snip>

 

[Ben Bacarisse]

So 2 < 1 < 3 would be different from (2 < 1) < 3. That would bother me;
not because it's so important to allow the current meaning of 2<1<3 to
survive, but because it would be inconsistent with the way parentheses
work in most other C contexts.

Well, that's an example, and I aimed to make it different deliberately
because I thought your point was that it would be hard to distinguish
between those two.

A simpler solution is to parse without creating the extra && nodes and
have the code generator (or some later parse tree re-writing) handle it.
Then (2 < 1) < 1 and 2 < (1 < 3) can easily mean the same as 2 < 1 < 3.

But none of this can be about C, surely, not even as an extension. In
that case (a < b) < c does not have to mean the same as a < b < c. The
relational operators (in this scheme) are non-associative, so the
programmer will know that the parentheses can change the meaning.

 

[BartC]

message

Python comparisons have the cool feature, that a<b<c is the same as (a<b
&& b<c). So you can use normal notation for multiple comparisons.

When the terms are not simple, then it's not quite the same:

a=1
c=4

def f():
global c
c=c-1
return 2

print (a < f() < c)
print (a < f() and f() < c)

These gives different results.

It's a question of whether the middle term is evaluated once or twice. If
twice, then the two forms are equivalent, but someone writing a<b<c might
not know b will be evaluated twice, with unexpected side-effects.

And if once, then a<b<c can give different results from a && b && c.

 

[Harald van Dijk]

Python comparisons have the cool feature, that a<b<c is the same as (a<b
&& b<c). So you can use normal notation for multiple comparisons.

When the terms are not simple, then it's not quite the same:
[...]
It's a question of whether the middle term is evaluated once or twice. If
twice, then the two forms are equivalent, but someone writing a<b<c might
not know b will be evaluated twice, with unexpected side-effects.

And if once, then a<b<c can give different results from a && b && c.

Isn't this just like saying that C's a+=1 is not equivalent to a=a+1,
because the evaluation of a might have side effects? In C, I don't
believe anybody considers that a problem. Why would it be a problem in
other languages for a<b<c?

 

[BartC]

Python comparisons have the cool feature, that a<b<c is the same as
(a<b
&& b<c). So you can use normal notation for multiple comparisons.

When the terms are not simple, then it's not quite the same:
[...]
It's a question of whether the middle term is evaluated once or twice. If
twice, then the two forms are equivalent, but someone writing a<b<c might
not know b will be evaluated twice, with unexpected side-effects.

And if once, then a<b<c can give different results from a && b && c.

Isn't this just like saying that C's a+=1 is not equivalent to a=a+1,

EPR was saying it *was* equivalent.

 

[Eric Sosman]

[...]
I find it hard to believe theres much existing code that deliberately
uses this unintuitive interpretation. However it must be a cause of many
bugs!

Can you cite instances of a few of those "many" bugs?

 

[Harald van Dijk]

messagePython comparisons have the cool feature, that a<b<c is the same as
(a<b
&& b<c). So you can use normal notation for multiple comparisons.
When the terms are not simple, then it's not quite the same:
[...]
It's a question of whether the middle term is evaluated once or twice.If
twice, then the two forms are equivalent, but someone writing a<b<c might
not know b will be evaluated twice, with unexpected side-effects.
And if once, then a<b<c can give different results from a && b && c.

Isn't this just like saying that C's a+=1 is not equivalent to a=a+1,

EPR was saying it *was* equivalent.

Yes, just as I might say a+=1 is equivalent to a=a+1 in C. It's really
slightly different, but for an explanation of the += operator it'll do
just fine.

 

[BartC]

EPR was saying it *was* equivalent.

Let me rephrase that: yes it is the same as a+=b and a=a+b!

But the problems of a<b<c (and a<b==c>d=e...) are a little harder to solve I
think.

 

[James Kuyper]

Well, that's an example, and I aimed to make it different deliberately
because I thought your point was that it would be hard to distinguish
between those two.

Not quite. I gave three expressions for an important reason. After I
sent that message, I've since realized that it would have been less
confusing to use an expression which would have a different value under
the current standard than it would have if the suggested change were made:

A: 3 < 2 < 1
B: (3 < 2) < 1
C: 0 < 1

Under the current standard, the first two statements have the same
meaning, and all three expressions have the same value. The fact that A
and B have the same meaning is needed for consistency with the rest of
the C language. The fact that B and C have the same value is needed for
consistency with the rest of the C language. You can change the meaning
of a < b < c to be (a<b) && (b<c), but only at the cost of breaking one
of those relationships. I don't care which one is broken, they're both
important, and I wouldn't like to see either one change.

In a new language that was otherwise similar to C, I'd favor having a
boolean type that was
a) Not treated as special kind of integer type
b) incapable of conversion to or from any other type.
c) the only type that could be used as a condition in #if preprocessing
directives; if(), while(), do while(), or for() statements; or ?:
expressions.

In such a language, the connection between B and C above would be
broken; and I wouldn't mind, but such a language could not be backward
compatible with existing C code, so I cannot favor any such change to C
itself.

But none of this can be about C, surely, not even as an extension. In

I'm in agreement about that, but Edward Rutherford said:

IMO it would be great if this could be backported to C.

And my comments have all been in the context of that comment.

 

[Ben Bacarisse]

A: 3 < 2 < 1
B: (3 < 2) < 1
C: 0 < 1

In a new language that was otherwise similar to C, I'd favor having a
boolean type that was
a) Not treated as special kind of integer type
b) incapable of conversion to or from any other type.
c) the only type that could be used as a condition in #if preprocessing
directives; if(), while(), do while(), or for() statements; or ?:
expressions.

In such a language, the connection between B and C above would be
broken; and I wouldn't mind, but such a language could not be backward
compatible with existing C code, so I cannot favor any such change to C
itself.

I think your conditions are not quite enough. I'd say that the boolean
type must not be ordered. If it is ordered, (false is usually < true)
there is a reasonable (C-like) meaning to A -- it means the same as B
and C. To fully break the connection between these expressions,
booleans should be unordered.

That's a step too far for lots of languages. For example, Haskell will
sort a list of bool values as happily as it will any type with an
ordering. It meets your conditions (a), (b) and (c) but the designers
chose to make < non-associative so that 3 < 2 < 1 is a parse error
rather than a type error.

<snip>

 

[James Kuyper]

I think your conditions are not quite enough. I'd say that the boolean
type must not be ordered. If it is ordered, (false is usually < true)
there is a reasonable (C-like) meaning to A -- it means the same as B
and C. To fully break the connection between these expressions,
booleans should be unordered.

I forgot a few additional item:
d) expressions containing the defined operator in #if directives, and
all relational, equality, and logical expressions have values of boolean
type.
e) Logical operators (&&, ||) require operands of boolean type.

There's no need to prohibit comparisons of boolean values with each
other for relative order, so long as they cannot be compared with
anything else. In the hypothetical language that I was describing, 1
cannot be converted to a boolean type, and the boolean value of 3<2
cannot be converted to an integer type; without a common type that both
can be converted to, "false < 1" would have to be a constraint violation.

 

[Ben Bacarisse]

I forgot a few additional item:
d) expressions containing the defined operator in #if directives, and
all relational, equality, and logical expressions have values of boolean
type.
e) Logical operators (&&, ||) require operands of boolean type.

There's no need to prohibit comparisons of boolean values with each
other for relative order, so long as they cannot be compared with
anything else. In the hypothetical language that I was describing, 1
cannot be converted to a boolean type, and the boolean value of 3<2
cannot be converted to an integer type; without a common type that both
can be converted to, "false < 1" would have to be a constraint
violation.

Maybe I've missed your point, but it seems to be that

a < b < c

is perfectly valid when a, b and c are of type bool (not C bool -- this
hypothetical language's bool) provided that bool is an ordered type. I
was not saying that an ordered bool type somehow effected 3 < 2 < 1,
just that it affects some syntactically similar expressions.

 

[BartC]

A simpler solution is to parse without creating the extra && nodes and
have the code generator (or some later parse tree re-writing) handle it.
Then (2 < 1) < 1 and 2 < (1 < 3) can easily mean the same as 2 < 1 < 3.

But none of this can be about C, surely, not even as an extension. In
that case (a < b) < c does not have to mean the same as a < b < c. The
relational operators (in this scheme) are non-associative, so the
programmer will know that the parentheses can change the meaning.

I've had a go at implementing a<b<c for one of my language projects.

The expression is modified in a subsequent pass, after already being parsed
as (< (< a b) c). When the left operand of a compare op is also a compare
op, the whole thing gets changed to (and (< a b) (< b c)).

('b' gets evaluated twice, but I don't care; not at this time of night
anyway.)

This works fine (also for long chains of relational and equality ops).

But I thought that by writing (a<b)<c, I could also turn a<b into a bool
result, and compare that against c (this is more useful when written as
(a<b)==c), but it doesn't work! The parentheses disappear. Which in fact is
as it should be:

If a<b<c is usually evaluated as (a<b)<c, then actually writing (a<b)<c
should do the same. (So some dummy op is needed to isolate the a<b bit - in
C that might be something like !!(a<b) - so that the conversion above is not
triggered.)

(Then I tried a<(b<c), which does compare a against the bool result of b<c;
that's OK, as there is no other meaning for that. The only niggle is that it
doesn't match the behaviour of a+b+c and a+(b+c), which are more or less the
same.)

 

[James Kuyper]

Maybe I've missed your point, but it seems to be that

a < b < c

is perfectly valid when a, b and c are of type bool (not C bool -- this
hypothetical language's bool) provided that bool is an ordered type. I
was not saying that an ordered bool type somehow effected 3 < 2 < 1,
just that it affects some syntactically similar expressions.

You're right, I'd forgotten to cover that possibility. It seems we must
sacrifice either sortability of boolean values, or the proposed new
meaning for a<b<c. Given those options, I favor sortability.

 

[Ben Bacarisse]

I've had a go at implementing a<b<c for one of my language projects.

The expression is modified in a subsequent pass, after already being
parsed as (< (< a b) c). When the left operand of a compare op is also
a compare op, the whole thing gets changed to (and (< a b) (< b c)).

('b' gets evaluated twice, but I don't care; not at this time of night
anyway.)

That should be fixed but I can see it's not a priority in an experiment.

This works fine (also for long chains of relational and equality ops).

But I thought that by writing (a<b)<c, I could also turn a<b into a
bool result, and compare that against c (this is more useful when
written as (a<b)==c), but it doesn't work! The parentheses
disappear. Which in fact is as it should be:

The simples options is to parse are I originally described, and then,
because the operators are non-associative, adding brackets to the left
or to the right will produce something new.

Once you have a parse tree of (< (< a b) c) there is no way to know if
it's from (a < b) < c or a plain a < b < c. There might be a kludge in
that could use a spare bit in the operator to indicate if it was
originally in parentheses, but that's, well, a kludge!

If a<b<c is usually evaluated as (a<b)<c, then actually writing
(a<b)<c should do the same. (So some dummy op is needed to isolate the
a<b bit - in C that might be something like !!(a<b) - so that the
conversion above is not triggered.)

I don't follow this. If a<b<c is usually evaluated as (a<b)<c that's
what you should do, and a<b<c can't have it's special meaning.

(Then I tried a<(b<c), which does compare a against the bool result of
b<c; that's OK, as there is no other meaning for that. The only niggle
is that it doesn't match the behaviour of a+b+c and a+(b+c), which are
more or less the same.)

Id say it's not a niggle at all -- it perfect. < is not symmetric, so a
better comparison is with a-b-c which changes meaning with brackets:
a-(b-c).

 

[Ben Bacarisse]

You're right, I'd forgotten to cover that possibility. It seems we must
sacrifice either sortability of boolean values, or the proposed new
meaning for a<b<c. Given those options, I favor sortability.

The "problem" (I am not sure i remember what it is) may be worse in the
I used < following your example, but the general idea would be to do
this for all relations operators, so

a == b == c

would be permitted to mean a == b && b == c (with b evaluated only
once). It would be a bog step to outlaw equality testing for bool.

Again, unless I'm missing the main point, I don't see the problem. If
this hypothetical language clearly states all the relational operators
and non-associative, chains of them must mean something other the usual
default pair-wise bracketing that associativity implies. Given that in
mathematics, (a < b) < c is at the very least odd, or rare, compared to
a < b < c, I'd be happy for it to have it's obvious meaning distinct
from the unbracketed version. In many non-C-like languages, things like
(3 < 2) < 1 will be type error anyway, so the only "silent" cases would
be the very rare examples of bracketed comparisons of booleans.