Odd Behavior with order dependent operators (- and /)

[wmiller848]

Take these two test for example

2 / 6 / 3 and 2 - 6 - 10 - 2, simple enough right?

Running those same expressions through nodejs, ruby, and go gives different results then this evaluator.

Node:

> 2 / 6 / 3
0.1111111111111111
> 2 - 6 - 10 - 2
-16

Ruby:

2.0.0-p645 :002 > 2.0 / 6.0 / 3.0
 => 0.1111111111111111
2.0.0-p645 :003 > 2 - 6 - 10 - 2
 => -16

Go:

/////////////////////////////
// main.go
/////////////////////////////
package main

import (
  "fmt"
)

func main() {
  t1 := 2.0 / 6.0 / 3.0
  fmt.Println(t1)
  t2 := 2 - 6 - 10 - 2
  fmt.Println(t2)
}
/////////////////////////////
/////////////////////////////

$ go run main.go
0.1111111111111111
-16

EvaluationTest{
  Name:     "Incorrect divide behavior",
  Input:    "2 / 6 / 3",
  Expected: 0.1111111111111111,
},
EvaluationTest{
  Name:     "Incorrect subtract behavior",
  Input:    "2 - 6 - 10 - 2",
  Expected: -16.0,
}

evaluation_test.go:877: Test 'Incorrect divide behavior' failed
evaluation_test.go:878: Evaluation result '1' does not match expected: '0.1111111111111111'
evaluation_test.go:877: Test 'Incorrect subtract behavior' failed
evaluation_test.go:878: Evaluation result '4' does not match expected: '-16'

The issue is the parser is moving right -> left NOT left -> right . I tried playing around with swapping the value vs rightValue orders but it gets messy. I'm sure this is a simple fix but I'm still trying to fully understand how the evaluate chain and the token stream all play together in respect to order of evaluation.

Cheers,
W

[Knetic]

For reference the parser just translates strings into an array of tokens, and the evaluation follows recursive descent parsing with backtracking achieved by the rewind of the token stream.

I remember writing tests way back to make sure these sorts of cases were handled, but it looks like I only did commutative operators and never bothered with the others, which explains why this didn't come up sooner.

Looking at it now, this behavior does seem endemic to LL parsers (which is what this is). There's no lookahead so it's not LL(k), but that seems to be the requirement to make it pass these tests.

It shouldn't be impossible to add lookahead, but since that's a nontrivial change I'm going to cheap out and ask if this is a blocking thing? - you ought to be able to get the result you're after with parenthesis.

[wmiller848]

Unfortunately the project I'm working on is a Machine Learning project, and it generates many 1000's of expressions to be evaluated. I evaluate the programs in go memory and then write the final program out as CoffeeScript programs, any discrepancy between go eval and coffee eval breaks the whole game as the results the outputted program give don't match what the go eval thought it would.

I've been chasing my tail with this one going from go's AST to some homebrew to your project and back around a few times.

I'm more then willing to hack on this to get it to work, but I thought I'd open an issue to get your expert opinion :)

For reference you can take a look at here to get an idea of how I'm using this project
https://github.com/wmiller848/GoGP

[Knetic]

Ah, that use case makes sense.

Actually upon re-reading, it looks like I misread the initial post, I thought that one would expect the correct order to move right-to-left, but that this library was doing left to right, and that was wrong. But actually manually walking through your test cases, it looks as if this library is going right-to-left, which... it really shouldn't be. Shouldn't require lookahead to accomplish left-to-right parsing, and that was my goal from the start. So there must be a bug somewhere.

I'm super confused as to how it's managing to do that and still pass the rest of the test cases. But now i'm looking at it for reals :P

[wmiller848]

Excellent!

For non order dependent operators like + * it wouldn't matter. But it is interesting that no ones seen this with - / % **/^ before.

My machine generated expressions are a great fuzzer for this project :)

[Knetic]

You're probably the first to create expressions with an unsupervised process! So yeah, it certainly explores different internal states much better than my hand-built tests!

I took a look at this, and found the behavior that's happening. This library basically makes a tree out of the expression, reading left-to-right, building the tree downward the further right it gets. However, because of how it does this (via recursion), it evaluates from the bottom of the tree back to the top. That usually works fine because the higher-precedence operators end up at the bottom of the tree, but for operators of equal precedence, the evaluation is done "right-to-left" since the right-most part is deeper in the tree (since it was appended last). I actually saw this without realizing it with the ternary operator a couple weeks ago; the ternary "else" (furthest-right) evaluated before the "if" case of the ternary, despite being equal precedence and in left-to-right order.

There's a few options, I'm going to have to try some things to see what works best.

[Knetic]

Found a pretty good solution that even adds a speed benefit to evaluation times. Planning on cleaning it up and releasing as part of 2.0 tomorrow night.

[Knetic]

Should be fixed as of 7653833. Master's got it now.

[Knetic]

Going to close this out, since all signs point to the behavior being fixed. Let me know if there's any lingering inconsistencies!