is the < operator transitive?

Discussion in 'C Programming' started by Francois Grieu, Oct 7, 2011.

  1. 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
    Francois Grieu, Oct 7, 2011
    #1
    1. Advertising

  2. Francois Grieu

    Stefan Ram Guest

    Francois Grieu <> writes:
    >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.
    Stefan Ram, Oct 7, 2011
    #2
    1. Advertising

  3. Francois Grieu wrote:
    > 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
    Edward Rutherford, Oct 7, 2011
    #3
  4. Francois Grieu wrote:
    > 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
    Edward Rutherford, Oct 7, 2011
    #4
  5. Francois Grieu

    jacob navia Guest

    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?
    jacob navia, Oct 7, 2011
    #5
  6. Francois Grieu

    James Kuyper Guest

    On 10/07/2011 01:10 PM, Francois Grieu wrote:
    > 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.
    James Kuyper, Oct 7, 2011
    #6
  7. Edward Rutherford <> writes:
    [...]
    > 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.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Oct 7, 2011
    #7
  8. Keith Thompson wrote:

    > Edward Rutherford <> writes:
    > [...]
    >> 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!

    //EPR
    Edward Rutherford, Oct 7, 2011
    #8
  9. jacob navia wrote:

    > 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?


    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
    Edward Rutherford, Oct 7, 2011
    #9
  10. Francois Grieu

    James Kuyper Guest

    On 10/07/2011 04:24 PM, Edward Rutherford wrote:
    > jacob navia wrote:
    >
    >> 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


    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.
    James Kuyper, Oct 7, 2011
    #10
  11. Edward Rutherford <> writes:

    > Keith Thompson wrote:
    >
    >> Edward Rutherford <> writes:
    >> [...]
    >>> 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!


    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
    Patrick Scheible, Oct 7, 2011
    #11
  12. James Kuyper <> writes:
    <snip>
    > 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.

    --
    Ben.
    Ben Bacarisse, Oct 7, 2011
    #12
  13. On Oct 8, 12:12 am, 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'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?
    Harald van Dijk, Oct 7, 2011
    #13
  14. Francois Grieu

    James Kuyper Guest

    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
    James Kuyper, Oct 7, 2011
    #14
  15. On Oct 8, 12:28 am, Harald van Dijk <> wrote:
    > On Oct 8, 12:12 am, 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'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?


    I see Python was already mentioned in the post you replied to, just
    not part of the text you quoted.
    Harald van Dijk, Oct 7, 2011
    #15
  16. Harald van Dijk <> writes:

    > On Oct 8, 12:12 am, 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'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?


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

    --
    Ben.
    Ben Bacarisse, Oct 7, 2011
    #16
  17. Ben Bacarisse <> writes:

    > Harald van Dijk <> writes:
    >
    >> On Oct 8, 12:12 am, 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'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?

    >
    > 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
    Patrick Scheible, Oct 8, 2011
    #17
  18. James Kuyper <> writes:

    > 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


    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.

    --
    Ben.
    Ben Bacarisse, Oct 8, 2011
    #18
  19. Edward Rutherford <> writes:
    > Keith Thompson wrote:
    >> Edward Rutherford <> writes:
    >> [...]
    >>> 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.

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

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Oct 8, 2011
    #19
  20. Edward Rutherford <> writes:
    > jacob navia wrote:
    >> 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.

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


    I believe you could also write it in Python as

    (a < b) < c

    just as you'd write it in C.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Oct 8, 2011
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jon Shemitz

    Transitive references

    Jon Shemitz, Feb 5, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    580
    Jon Shemitz
    Feb 5, 2004
  2. Jakob Bieling

    Q: operator void* or operator bool?

    Jakob Bieling, Mar 5, 2004, in forum: C++
    Replies:
    2
    Views:
    560
    Rob Williscroft
    Mar 5, 2004
  3. John Smith
    Replies:
    2
    Views:
    410
    Ivan Vecerina
    Oct 6, 2004
  4. Imre
    Replies:
    3
    Views:
    370
  5. Replies:
    11
    Views:
    814
    Tomás Ó hÉilidhe
    Dec 19, 2007
Loading...

Share This Page