Many programming languages have infix expressions, but get associativity wrong | Hacker News Reader

Many programming languages have infix expressions, but get associativity wrong

jfm3-repl.blogspot.com

30 pointsblasdel33 comments

Rather than a number of languages getting associativity wrong, a simpler explanation is that the < operator is not associative.

Mathematically, studying associativity makes sense for mappings of type A x A -> A, where A is any set; < is not such a mapping.

That is quite correct. If you look up the mathematical definition of associativity, the behaviour of the "<" does not fit it. In fact associativity is only a property that can be possessed by functions or operations that operate on a particular set. Thus, both the inputs and the result of the function or operation have to belong to the set. For the "<" operation, the inputs are numbers and the result is boolean. A boolean value cannot be an input for the "<" operation (if you take the classical definition of "<"). Therefore, "<" does not operate on a particular set. Therefore "<" cannot be associative.

The behaviour of "<" the author refers to is not associativity. Therefore, the languages he criticises do not really get associativity wrong, he just needs to brush up on his math.

Now you can say "well, ok this behaviour is not associativity but it is a well know behaviour of "<" and ">". Why can't the languages get it right?" I think the answer is that this (a<b<c<d) is one of those notations that look ok in algebra class but are really problematic if you actually try to define and use a logically consistent function notation, so it is not a problem for me, if some languages do not perform (a<b<c<d) as expected in order to keep their semantics clean.

Even in a mathematics, "a < b < c" isn't an expression but merely shorthand for "a < b" and "b < c".

But... isn't that what the author says?

Haskell is right. Sugaring in the conjunction like Python violates non-associativity, which exists for predicate relations in human languages. And it's not a type error; it's a syntax error.

Note that in mathematics one sees things that look like "1 < i < n", which seems similar to what Python allows. But, if you ask a mathematician to read this aloud, they will say "some i between one and n", or in certain contexts "all i between one and n". This is an entirely different thing; it is not a predicate at all.

[...]

So with <, it's non-associative and bad to sugar up the error you get if you try to use it associatively.

Hmmm... but by the same argument, Ruby is also doing it right, by correctly crashing at runtime (there is no way for a language without a type-system and with redefinable operators to discover the error at compile time).

Somehow the author isn't clear on whether he wants "1 < 2 < 3" to return true or to be rejected; if it's the latter, then most languages get it right (except Python and Matlab, as far as I know).

I think he's actually quite clear on rejecting it as a syntax error. Ruby isn't doing it right in that it throws a type error: 1 < 2 < 3 becomes lt(lt(1, 2), 3), then lt(true, 3) which doesn't check.

I know nothing about Ruby so I don't know how its operator overloading works, but I think that could be a problem if < was redefined with an a -> a -> a signature, or a -> a -> b with b comparable to a, since in this case you wouldn't get the type error. The proper solution, according to the author, would probably be to simply refuse any expression with more than one < (or any other non-associative operator).

It doesn't seem possible to consistently make "1 < 2 < 3" a syntax error in a language powerful enough to redefine <. (Including Haskell, where you could easily hide the Prelude definition and define your own, also changing the fixity declaration.)

So I guess a fair compromise would be if the default implementation rejects "1 < 2 < 3" at either compile-time or run-time, whichever is possible.

But... isn't that what the author says?

Not really. As pointed out above, the author doesn't appear to understand that the associative/non-associative distinction is literally undefined unless we're talking about a binary operator from a set to itself. Saying that < is a non-associative operator is wrong, something like saying that a vector is a non-odd number; as long as we're complaining about parenthesization, I'd suggest the author rephrase his statement and say that < is a non-(associative operator), which at least means something.

An expression like a < b < c should be a type error - no possible parenthesization could make it a valid statement.

It's easy enough to come up with a way to make < work like this, though, by changing the signature of < so that it takes and returns a helper class instead of a numerical value, with automatic type coercions to that helper class from numerical values on both ends and booleans on the right edge. This should be easy in a language like Scala, probably a 10 minute exercise if you know what you're doing.

If we make this helper class hold both the left edges of the chain and the right edges, and use the appropriate edge for each comparison, then the thing is associative.

((a > b) > c) > d is the same as a > (b > (c > d)), since in either case, each element will at some point be checked with > against both of its neighbors, and only those neighbors, and the overall expression will be coerced to true if and only if the strict ordering is preserved at each check. Process left to right, and it works out. Even if we get messier and allow >, >=, <, <=, and == into the mix, we can mix and match everything, and the whole thing will only be true if every neighboring check is true. The author's worry in the blog comments about '1 < 2 > 1' evaluating to true strike me as odd: that should evaluate to true under any reasonable definition of those operators.

So even if we do make < into an operator such that it makes sense to talk about its associativity, it turns out to be associative. Which is why mathematicians don't bother parenthesizing their chained < expressions, there's just no ambiguity.

The article is plain wrong, IMO.

What about functions of type A x B -> A ?

An example would be C++ stream << operator which takes a stream on the left, a string on the right, and returns a stream (after writing the string into the stream). This is so that you can do chaining:

    cout << "Hello" << "World";

I don't think that there are any mathematical operators that work this way though.

It seems like, to have associativity in the sense of "(a+b)+c = a+(b+c)", you'd have to extend << to also become the string concatenation operator in C++. There are quite a few rules that need to hold to make it work...

One of the comments on the post (by Mathnerd314) says that Icon implements its comparison operators that way (if the comparison succeeds, it returns the 2nd argument).

The fundamental misunderstanding here is how we relate our parsing of mathematical expressions to the way a compiler parses expressions:

While we can parse the following expression properly:

    a < b < c

parses to:

    (a < b) AND (b < c)

obviously most compilers don't do that. As others have pointed out, the < operator should not be associative.

The misunderstanding, though, is that the original expression

    a < b < c

actually could be parsed (I'm making a bunch of assumptions about the grammar and parser type here) by treating ..<..<.. as a ternary operator, like ?: in C++.

Then, in the syntax tree, the compiler could re-organize the expression to be the correct an unambiguous:

    (a < b) AND (b < c)

If associativity and precedence are "natural", shouldn't there be near-universal agreement?

I mention that because the standard argument against lisp notation is ....

"Ruby, in an adorable little attempt to wear big-boy pants, is turning this expression into the following pseudo-code"

Is the condescending tone necessary?

An alternative:

"Ruby turns this expression into the following pseudo-code"

The author, in an adorable little attempt to wear big-boy pants[0], seems not to know that '<' is a message passed to a receiver. You can even redefine it if you like.

Better pseudo code would be

    1.lt(2).lt(3)

In fact, this is correct (albeit ungainly) ruby code

    1.<(2)  # true

and so

    1.<(2).<(3) # Say wha ... ?

makes no sense.

[0]: Yes, a cheap shot.

The underlying mechanism doesn't matter if it's wrong.

Those familiar with the mathematical notation would think:

     1. '1 < 2 < 3' parses to '(1 < 2) and (2 < 3)'.
     2. '3 - 4 - 5' parses to '(3 - 4) - 5'.
     3. '3 ^ 4 ^ 5' parses to '3 ^ (4 ^ 5)'.

Ruby's convention is clever, but ultimately wrong, and this is one of the cases.

Unfortunately Ruby is not wrong. Ruby is simply being strictly correct from a logic point of view, where < is R^2 -> {T, F}, as opposed to being strictly correct from a math-notation point of view, where < is treated syncategorematically. Neither is correct, sans qualification; given that Ruby is not aimed at mathematicians, it's not unsurprising to find that it's not going to go through the extra parsing effort to use math notation.

1 < 2 < 3 DOES evaluate to (1 < 2) < 3

And 1 < 2 evaluates to true. What else would it evaluate to?

That leaves (true < 3)

Which fails. This isn't a mistake by ruby. When you chain methods you have to think about what they return.

And the issue here isn't associativity.

The comment you're replying to was not asserting that Ruby fails to follow its own rules, but rather arguing with the rules Ruby follows; other languages have made an exception to their normal rules for this case, and apparently some people feel it would be better for Ruby to do the same.

> 3. '3 ^ 4 ^ 5' parses to '3 ^ (4 ^ 5)'.

I actually think that a trained mathematician would have no idea what to do with 3 ^ 4 ^ 5. It's a completely ambiguous statement and has no proper mathematical parsing.

The real cause of the Ruby problem in the article is the automatic conversion of "1" to "true". This is a language design bug, and has nothing to do with associativity.

As for associativity proper, I program in multiple languages all the time, but find remembering the various associativity rule differences in these languages a pain in the ass. So I always use parenthesis.

That way anyone reading my code (including myself a few months later) will find it easy to understand what I intended, and the right thing gets done no matter what the associativity rules are.

Is Python really pulling a syntactic trick?

I think < is simply left associative: True < 4 is True.

Similarly, I think > is right associative. (50 > 30) > 10 does not hold, but 50 > (30 > 10) holds.

Yes it is really pulling a syntactic trick and not comparing against bools. From the docs:

Comparisons can be chained arbitrarily, e.g., x < y <= z is equivalent to x < y and y <= z, except that y is evaluated only once.

http://docs.python.org/reference/expressions.html#notin

    randall@gulch:~$ python -c 'print 1 < 2 < 4'
    True
    randall@gulch:~$ python -c 'print 1 < 5 < 4'
    False

In Python True==1, unfortunatelly.

  >>> True + True
  2

Simple left-associativity would also make 3<4<2 evaluate to True.

So what does Perl do with "jfm" + 3 that's so enormously funny?

Try it:

    >>> perl -e 'print "jfm" + 3'
    3

My guess is that it coerces "jfm" to an int (0), and then adds that to 3 to get 3.

It's a bit of a low blow on the author's part, as in perl, "+" is not "a generic addition operator that can be overloaded to concatenate strings", it is literally the "numeric addition operator" and both sides of the + will be coerced as needed to turn them into numbers. The default for strings is to parse them as numbers ("10" + "20" yields the number 30), and a string that doesn't start with a number defaults to zero.

If Perl does anything wrong here, it is in not throwing a type error at runtime but just silently coercing the number. Compare with Python:

    Python 2.6.4 ... linux2
    Type "help", ...
    >>> "30" + 2
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: cannot concatenate 'str' and 'int' objects

(Using "use overload" may let you do further crazy things with +; I'm just talking about the default definition of the operator.)

Incidentally, the string equivalent of + is ".", the dot. There's a parallel hierarchy of operators in Perl for numbers vs. strings, which is part of why Perl has so damned many operators. Woe betide the developer that says "==" instead of "eq" accidentally....

I actually like the fact that it has different operators for numbers and strings. It somehow feels cleaner to me, this separation of contexts (contexts in the usual sense of the word, not strictly Perl contexts).

The fact that the string equivalents are all words (cmp, eq, ne, etc.) gives a useful mnemonic (strings usually contain 'words', so their operators are words), and also prevents ugliness from operator-proliferation - it's the symbol operators that usually make the code _look_ ugly and lead to claims of 'line noise'.

> It somehow feels cleaner to me, this separation of contexts (contexts in the usual sense of the word, not strictly Perl contexts).

I've made the argument that the intended type of an operation is as much a context as the amount (void/scalar/list) context. The relevant Perl 5 literature flirts with that phrasing, but Perl 6 goes much further to extend that metaphor. That has proven very useful in discussions of consistency.

>You might think a compiler could do several optimizations here, and you'd be right. But you'd only be right if the compiler could reorder the terms in A + B + C, or even if it could apply the notion that (A + B) + C == A + (B + C). But it ain't so in Java, at least not when I last looked at it.

Except Java is statically typed, so it's possible for the compiler to know if f returns an int, and it can rearrange the expression given that knowledge.

Java throws exceptions on overflow (and underflow), which presumably interferes with that, e.g.:

  int A = 3000000000;
  int B = 3000000000;
  int C = -3000000000;
  int D;
  D = A + B + C;

Depending on order of evaluation, this either throws an overflow exception or assigns the number 3 billion to D. There is a hard rule in the spec that defines what must happen here. In C or C++ there are no such exceptions, so the compiler can (and does) transform arithmetic expressions where it's advantageous. (this is obviously a trivial example which will compile down to a constant anyway)

But http://java.sun.com/docs/books/jls/second_edition/html/types... says

> The built-in integer operators do not indicate overflow or underflow in any way. The only numeric operators that can throw an exception are the integer divide operator / and the integer remainder operator %, which throw an ArithmeticException if the right-hand operand is zero.

Maybe it's true that subexpressions can't be reordered for other reasons, but offhand I can't find that restriction.

Reply on news.ycombinator.com