#589 Negation operator causes infix operators to the right to have higher precedence

[David Costanzo]

The negation operator can, in some cases, cause operators in expressions to its right to have higher precedence than they should, violating the expected order of operations.

Here's a normal case

show 2 * -1 + 100
98

That's expected. It's like (SUM (PRODUCT 2 (MINUS 1)) 100).

Here's the bug

show 2 *-1 + 100
198

This expression should be equivalent to the first one and evaluate to 98, but the absence of the space in *- seems to make -1 + 100 get evaluated before the multiplication, as in (PRODUCT 2 (SUM (MINUS 1) 100)).

This was reported in the Discussion Forum by Masao.

[David Costanzo]

I see the problem but not the solution.

When the expression is runparsed, the * and - remain together. The logic for determining that - is for negation is in runparse_node

  else if (wcnt == 0 && *wptr == '-' && !monadic_minus &&
           wcnt+1 < wlen && !white_space(*(wptr + 1)))
  {
      /* minus sign with space before and no space after is unary */
      tnode = make_intnode(0);
      monadic_minus = true;
  }

Then the treeifier sees it as minus and also has a special case to map it to negation (faking it as 0 - X), as in

  else if (first == Minus_Sign)
  {
      // pretend that -X is really 0 - X
      deref(first);
      push(Minus_Tight, *expr);
      retval = paren_infix(make_intnode(0), expr, -1, inparen);
  }

The problem is that paren_infix keeps iterating, parsing the expression on the right as long as the infix operator has a higher precedence that what was originally passed in (the -1), not the precedence of the previous operator. So this might be a more general problem whenever infix operators go from low to high to medium precedence as you read left to right. So far, I can reproduce it without the *- but not without a negation operator

show 2 * - 3 + 100
194

I think the original problem could be fixed in any of three ways:
1) Make runparse_node treat the - in 2*-1 as negation.
2) Make paren_infix uses the binding precedence of the previous infix operator instead of the first one when deciding when to stop.
3) Fix the special case in paren_expr for changing minus to negation

I don't know what the right way is.

[David Costanzo]

I have committed a rather invasive fix for this as [r6000]. It will be available in the next release of FMSLogo, which will be either 8.4.0 or 9.0.0. Even though this potentially changes the behavior of working programs, I consider this to be bug fix, not a breaking change, so a minor version increment is appropriate.

My explanation of paren_infix above is incorrect. The function is should iterate using the original priority. When it recurses, it uses the new priority. The bug was that parenthesizer processed infix operators in the expression twice, once in paren_expr, then again in the caller as if the negation has a low precedence.

My fix removes the duplicated logic that maps - to negation that existed in the runparser. I figure that this shouldn't be done in two places and the runparser doesn't have enough information to decide between subtraction and negation (for that, it needs a parse tree, which is the responsibility of the parenthesizer).

There were several of vestiges of failed handling of subtraction vs negation in the code base, so I assume that this was difficult for the UCBLogo authors and they tried a variety of approach. As such, I'm not confident that my fix is correct. In fact, I had a very simple fix that I was happy with and which passed all my tests, including some new ones that I added. Then I found it didn't handle --1 correctly and I couldn't figure out a simple fix for that.

I think the new code is conceptually cleaner, treating negation as a prefix operator instead of as an infix operator with 0 as the left argument. I'm also glad that the runparser is now a tokenizer and doesn't try to map - to subtraction or negation. I'm dissatisfied that there are multiple places within the parenthesizer that know that - can be an infix or a prefix operator.

[David Costanzo]

Fixing this is more of a breaking change than I had expected. Since the bug went for 20 years with no one reporting it, I thought fixing it wouldn't impact many programs, but it impacted my tests. For example, in test/bitmap.lgo, I have

SETYX -:width/2   -:height/2

In FMSLogo 8.3.0, this ran as you'd expect. After fixing this bug FMSLogo throws a "not enough inputs" error because the second - is treated as subtraction and what was a second input becomes part of the expression of the first input.

I like the new simplification of what - means...

- is binary subtraction unless there's no expression before it, in which case it's unary negation.

I like that spaces don't influence in interpretation of the -, that 1-2 , 1 -2, and 1 - 2 all mean the same thing.

However, I dislike that this is no longer valid

SHOW SUM 1 -2

By the simplified rules, you'd have to do something unnatural (use parentheses a zero) whenever you wanted to use - as negation on a non-first input. Fixing this might make FMSLogo's syntax easier to explain, but it violates the guiding principal that FMSLogo is a better MSWLogo, not a better LOGO.

[David Costanzo]

I have reverted the part of the fix that removed the minus-to-negation translation in runparse_node with [r6003]. It's too bad, because that was the only part of [r6000] that I felt good about. This was necessary to make

SUM 1 -2

behave as expected. While the parenthesizer can know if there's an argument to the left of a -, it cannot know if there was a space before it because the spaces are removed before it is called. Since runparse_node, as the tokenizer, does know if there was a space before a minus sign, it's the only place that can do the minus-to-negation translation. Therefore, some minus-to-negation logic is necessary in both the tokenizer and the parser.