6 ms·

Many programming languages have infix expressions, but get associativity wrong

30 points by blasdel 17y ago

scythe 17y ago
>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.
- pmjordan 17y ago
  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)
  - prodigal_erik 17y ago
    But http://java.sun.com/docs/books/jls/second_edition/html/typesValues.doc.html#29775 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.
brazzy 17y ago
So what does Perl do with "jfm" + 3 that's so enormously funny?
- nostrademons 17y ago
  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.
  - jerf 17y ago
    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....
    - sundarurfriend 17y ago
      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'.
enum 17y ago
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.
- jedi_stannis 17y ago
  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 http://docs.python.org/reference/expressions.html#notin
- randallsquared 17y ago
  randall@gulch:~$ python -c 'print 1 < 2 < 4' True randall@gulch:~$ python -c 'print 1 < 5 < 4' False
- beza1e1 17y ago
  In Python True==1, unfortunatelly. >>> True + True 2 Simple left-associativity would also make 3<4<2 evaluate to True.
johnbender 17y ago
"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"
- jamesbritt 17y ago
  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.
  - mikedouglas 17y ago
    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.
    - psygnisfive 17y ago
      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.
    - xenophanes 17y ago
      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.
anamax 17y ago
If associativity and precedence are "natural", shouldn't there be near-universal agreement? I mention that because the standard argument against lisp notation is ....
miloshh 17y ago
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.
- ramchip 17y ago
  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.
  - miloshh 17y ago
    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).
    - ramchip 17y ago
      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).
biotech 17y ago
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)
gnosis 17y ago
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.

30 points by blasdel 17y ago

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

pmjordan 17y ago
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)
- prodigal_erik 17y ago
  But http://java.sun.com/docs/books/jls/second_edition/html/typesValues.doc.html#29775 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.

brazzy 17y ago

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

nostrademons 17y ago
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.
- jerf 17y ago
  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....
  - sundarurfriend 17y ago
    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'.

enum 17y ago

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.

jedi_stannis 17y ago
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 http://docs.python.org/reference/expressions.html#notin
randallsquared 17y ago
randall@gulch:~$ python -c 'print 1 < 2 < 4' True randall@gulch:~$ python -c 'print 1 < 5 < 4' False
beza1e1 17y ago
In Python True==1, unfortunatelly. >>> True + True 2 Simple left-associativity would also make 3<4<2 evaluate to True.

johnbender 17y ago

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

jamesbritt 17y ago
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.
- mikedouglas 17y ago
  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.
  - psygnisfive 17y ago
    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.
  - xenophanes 17y ago
    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.

anamax 17y ago

If associativity and precedence are "natural", shouldn't there be near-universal agreement? I mention that because the standard argument against lisp notation is ....

miloshh 17y ago

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.

ramchip 17y ago
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.
- miloshh 17y ago
  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).
  - ramchip 17y ago
    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).

biotech 17y ago

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)

gnosis 17y ago

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.