is the < operator transitive?


F

Francois Grieu

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

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

If not, what about a counterexample?

How far can we extend (or shrink) the kind of things
that a b c can be for this to hold?

In particular, what about unitialized variable such as

int foo(void) {
{
unsigned a,b,c;
return a<b && b<c && !(a<c);
}

What if unsigned is changed to int? To double?


Francois Grieu
 
Ad

Advertisements

S

Stefan Ram

Francois Grieu said:
Is it certain that ( a<b && b<c && !(a<c) ) is 0?

You should exclude preprocessor definitions for the names,
an abnormal termination of the evaluation (e. g. upon a trap
representation or a signaling NaN) and write accesses of
other processes to the objects of the variables and should
think about possible floating type values of »NaN« and
infinity.
 
E

Edward Rutherford

Francois said:
Is it certain that ( a<b && b<c && !(a<c) ) is 0?

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

If not, what about a counterexample?

How far can we extend (or shrink) the kind of things that a b c can be
for this to hold?

In particular, what about unitialized variable such as

int foo(void) {
{
unsigned a,b,c;
return a<b && b<c && !(a<c);
}

What if unsigned is changed to int? To double?


Francois Grieu

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.

// EPR
 
E

Edward Rutherford

Francois said:
Is it certain that ( a<b && b<c && !(a<c) ) is 0?

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

If not, what about a counterexample?

How far can we extend (or shrink) the kind of things that a b c can be
for this to hold?

In particular, what about unitialized variable such as

int foo(void) {
{
unsigned a,b,c;
return a<b && b<c && !(a<c);
}

What if unsigned is changed to int? To double?


Francois Grieu

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.

// EPR
 
J

jacob navia

Le 07/10/11 20:50, Edward Rutherford a écrit :
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.

// EPR


In C

a<b<c

means

a < 1
or
a < 0

depending on the value of b<c

How do you write that in python?
 
J

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), or have pointer type, be NaNs,
or have a trap representation.
If not, what about a counterexample?

For pointer types the behavior is undefined unless all three pointers
point into or one past the end of the same array object.

Any relation involving a NaN is required to have a value of false.

#include <math.h>

double a = 1.0;
double b = nan();
double c = 2.0;

Another type of counter-example involves expressions where the usual
arithmetic conversions (6.3.1.8p1) result in the same variable being
converted to two different values in the two different places where it
occur in that expression:

unsigned long a = 98765UL;
int b = -12345;
short c = 1;

The key here is that in a<b, unsigned long has greater rank than long.
As a result, the usual arithmetic conversions (6.3.1.8p1) call for b to
be converted to unsigned long, with the resulting value of
ULLONG_MAX-12344, which is guaranteed to be greater than 98765UL. The
same conversion occurs in a<c, but since c is positive, the conversion
doesn't change it's value. No such conversion occurs in b<c.
How far can we extend (or shrink) the kind of things
that a b c can be for this to hold?

In particular, what about unitialized variable such as

int foo(void) {
{
unsigned a,b,c;
return a<b && b<c && !(a<c);

An uninitialized object may contain a trap representation. If that's the
case, attempting to read it will render the behavior undefined. When the
behavior is undefined, then anything is permitted by the standard. foo()
could return 1, or 0, or -3.5, or "You did it wrong". Your program could
also abort(), or get stuck in an infinite loop, or send hate mail to
your boss.
}

What if unsigned is changed to int? To double?

The behavior of foo() may be undefined when using any type which is
allowed to have a trap representation. The types which are not allowed
to trap include char, unsigned char, signed char, and the exact-width
types from <stdint.h>.

However, even if you use only those types for a, b, and c, the value you
get by reading an uninitialized variable is unspecified; it's not
required to be the same unspecified value each time you read it.
Therefore, foo() could still return either 0 or 1.
 
Ad

Advertisements

K

Keith Thompson

Edward Rutherford said:
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.
 
E

Edward Rutherford

Keith said:
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!

//EPR
 
E

Edward Rutherford

jacob said:
Le 07/10/11 20:50, Edward Rutherford a écrit :


In C

a<b<c

means

a < 1
or
a < 0

depending on the value of b<c

How do you write that in python?

I would write it as
a < (0 if b < c else 1)

I think this Python is clearer about what's going on than C's a<b<c,
which is just plain misleading.

//EPR
 
J

James Kuyper

Actually, a<b<c is equivalent to (a<b)<c, which means that can be
described as:
1 < c
or
0 < c
depending upon the value of a<b
I would write it as
a < (0 if b < c else 1)

I think this Python is clearer about what's going on than C's a<b<c,
which is just plain misleading.

I agree that it's not particularly useful, but it's the same way the
rest of the C expressions work; each complex expression is made up of a
single top-level operation working on sub-expressions whose result does
not depend upon the which type of expression they occur in. You cannot
give a<b<c a new meaning, equivalent to (a<b) && (b<c) in terms of the
current syntax, while staying within that framework.

You could define '< <' as a special trinary operator like "?:". But then
you'd have to define a<b<c<d as a quaternary operator, etc. That way
lies madness.
 
P

Patrick Scheible

Edward Rutherford said:
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!

That's been C's behavior since K&R. It wouldn't be my choice if I were
making up a language from scratch, but it makes sense with C's use of
integers for booleans.

-- Patrick
 
Ad

Advertisements

B

Ben Bacarisse

James Kuyper said:
You could define '< <' as a special trinary operator like "?:". But then
you'd have to define a<b<c<d as a quaternary operator, etc. That way
lies madness.

The madness can be avoided. There's no need define tertiary or
quaternary (and so on) versions. In fact doing so either rules out a <
b <= c or it means you need < <= as yet another operator (and so on for
dozens of combinations).

If <, >, <=, >=, == and != all have the same priority, you can parse it
just like a + b - c + d and simply double the operand you have "in hand"
and add &&. The operators need to be marked as non-associative, but it
can be fitted into an operator precedence grammar very simply.

I've spent the last hour (not exclusively, you understand) trying to
remember what language it was that I've worked on that does this, and
I've come up with nothing. But I don't think I'm making it up, honest.
 
H

Harald van Dijk

If <, >, <=, >=, == and != all have the same priority, you can parse it
just like a + b - c + d and simply double the operand you have "in hand"
and add &&.  The operators need to be marked as non-associative, but it
can be fitted into an operator precedence grammar very simply.

I've spent the last hour (not exclusively, you understand) trying to
remember what language it was that I've worked on that does this, and
I've come up with nothing.  But I don't think I'm making it up, honest.

Python does this. Is that what you were trying to think of?
 
J

James Kuyper

On 10/07/2011 06:12 PM, Ben Bacarisse wrote:
....
If <, >, <=, >=, == and != all have the same priority, you can parse it
just like a + b - c + d and simply double the operand you have "in hand"
and add &&. The operators need to be marked as non-associative, but it
can be fitted into an operator precedence grammar very simply.

I'd like to see that explained more clearly. In particular I'd like to
see an explanation of how, with that modification, each of the following
expressions would be handled:

2 < 1 < 3
0 < 3
(2 < 1) < 3
 
H

Harald van Dijk

Python does this. Is that what you were trying to think of?

I see Python was already mentioned in the post you replied to, just
not part of the text you quoted.
 
B

Ben Bacarisse

Harald van Dijk said:
Python does this. Is that what you were trying to think of?

Thanks, but not what I was thinking of. It's something depressingly
old. Maybe Maxima? Or an extension to Algo68, maybe?
 
Ad

Advertisements

P

Patrick Scheible

Ben Bacarisse said:
Thanks, but not what I was thinking of. It's something depressingly
old. Maybe Maxima? Or an extension to Algo68, maybe?

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

Comparison operators are evaluated left to right and produced the value
of their right operand if they are true (succeed, in Icon terminology).
If they fail, the subsequent comparison fails also.

A < B < C is evaluated (A < B); if true, it produces B, which is then
compared to C.

If (A < B) is false, it fails and produces no result. Comparing to no
result fails in turn.

http://www.cs.arizona.edu/icon/

-- Patrick
 
B

Ben Bacarisse

James Kuyper said:
On 10/07/2011 06:12 PM, Ben Bacarisse wrote:
...

I'd like to see that explained more clearly. In particular I'd like to
see an explanation of how, with that modification, each of the following
expressions would be handled:

2 < 1 < 3
0 < 3
(2 < 1) < 3

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.

I am sure I've messed up some detail (writing in haste here) and the big
picture is missing. But if you've seen other recursive descent parsers
where expressions are handled by one parameterised parser function
(rather than one for each operator priority) it won't look too odd.
 
K

Keith Thompson

Edward Rutherford said:
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.

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.

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".
 
Ad

Advertisements

K

Keith Thompson

Edward Rutherford said:
jacob said:
Le 07/10/11 20:50, Edward Rutherford a écrit : [...]
In C

a<b<c

means

a < 1
or
a < 0

depending on the value of b<c

No, it means 0 < c or 1 < c, depending on the value of a < b.
I would write it as
a < (0 if b < c else 1)

I think this Python is clearer about what's going on than C's a<b<c,
which is just plain misleading.

I believe you could also write it in Python as

(a < b) < c

just as you'd write it in C.
 

Top