How to explain the abstract syntax tree of chained comparison operations?

Question

Comparison operators can be chained in python, so that for example x < y < z should give the result of (x < y) and (y < z), except that y is guaranteed to be evaluated only once.

The abstract syntax tree of this operation looks like:

>>> ast.dump(ast.parse('0 < 1 < 2'), annotate_fields=0)
'Module([Expr(Compare(Num(0), [Lt(), Lt()], [Num(1), Num(2)]))])'

Pretty printed:

Module
  Expr
    Compare
      Num
      Lt
      Lt
      Num
      Num

But it seems to parse as something like 0 < < 1 2 and I'm not sure how to reconcile that with the logical result of something like 0 < 1 and 1 < 2.

How can the ast for chained comparisons be explained?

Answer 1

The reasoning behind this is actually mentioned in the ast docs

-- need sequences for compare to distinguish between
-- x < 4 < 3 and (x < 4) < 3
| Compare(expr left, cmpop* ops, expr* comparators)

If it were evaluated as two separate compares, like this

Module(Expr(Compare(Compare(Num(0), [Lt()], [Num(1)]), [Lt()], [Num(2)]))])

Then it's actually comparing the boolean result of the first comparison with the integer in the second comparison.

Something like this wouldn't work

-5 < -4 < -3

Because it would be evaluated as

(-5 < -4) < -3

Which evaluates as

1 < -3

So instead, it's dealt with as a single expression. A python implementation of the Compare operation would look something like this

def Compare(left, ops, comparators):
    if not ops[0](left, comparators[0]):
        return False

    for i, comparator in enumerate(comparators[1:], start=1):
        if not ops[i](comparators[i-1], comparator):
            return False
    return True

Answer 2

I think that you need to think of it as a short-circuiting pipeline of things to do. e.g. if you zip the ops with the comparators, and then work on them one at a time:

result = left
for op, comparator in zip(ops, comparators):
    result = result and evaluate(result, op, comparator)
    if not result:
        break

Obviously, I'm leaving a bunch to the imagination here ... e.g. I didn't define evaluate. However, it's a pretty hard thing to define since we don't know what the comparator expression looks like in the general case.

Answer 3

I would like to complement Brendan Abel's answer with my version of the Compare() function, which IMHO is a little easier to comprehend:

def Compare(left, ops, comparators):
    for x, op, y in zip([left] + comparators[:-1], ops, comparators):
        if not op(x, y):
            return False
    return True