EXPR mathematical expression evaluator obeying ordinary precedence

[rebolbot]

Submitted by: fork

Reviewing the discussions and arguments on the internet, there are a few things people always say. Perhaps not number one, but certainly in the top 3 is "why does Rebol not use normal precedence, like the 'rest of the world' agrees upon". (_cough_they don't actually agreecough)

Debates quickly spiral out of control and become off-topic. Rebol-language defenders usually begin by arguing that simpler rules are actually better, and are central to the design of a system with interesting composition. Then people say that's out of touch, and going against convention means your language will always be obscure.

Then the argument becomes ever-more abstract. That one shouldn't be slaves to complexity just because everyone else is doing it. Or that when shifting around decisions in order to carve up "complexity space", it helps to be reasonable about the actual value preserving a specific convention has, for the cost it has on other areas of the design.

Right answer, wrong time to be presenting it. Forums of absolute beginners or JavaScript programmers, instead of being revealed the cool things, quickly fill up with noise. The number of people who have immediately set the "Bozo Bit" on Rebol for the response to this issue is probably in the thousands.

New answer. The FIRST response to someone showing a precedence example they don't like, is simple:

"Oh, you mean you want math precedence and not simplified precedence? Just use EXPR if you're doing math. Rebol is paradigm neutral; you can use and define what you want. In fact, want to see something else cool...?"

The fact that years of this debate happening and no one just sitting down and writing the EXPR implementation is ridiculous. Of course, there are a lot of questions about what it would do, besides obey mathematical precedence...

    values: [2 3 4]
    expr [1 + pick values 1 * pick values 2]  

You're probably going to ask how EXPR is supposed to know that it's not supposed to multiply 1 by 3 from the pick values 2... and then pick the 4 out of values and add it to 1 to get 5.

WHO CARES! Make it do one thing, the thing they asked for. Obey mathematical precedence. Do a pre-phase on the block passed in. Translation:

    expr [1 + pick values 1 * pick values 2]  
    =>
    (1 + ((pick values 1) * (pick values 2)))

If it generates something confusing, again: who cares? Just don't do your additions before your multiplications and stuff like that:

    expr [1 + pick values 1 + 2 * pick values 2]  
    =>
    (1 + ((pick values 1) + (2 * (pick values 2))))

If they want to be more explicit, let them parenthesize their function calls in the source. (That's the other top 3 question.)

    expr [1 + (pick values (1 + 2)) * (pick values 2)]  
    =>
    (1 + ((pick values 1 + 2) * (pick values 2))))

Just no more "deep" explanations until people know enough about the language to care enough to know why it's different.

To attack philosophy, start with easier things like carving up the lexical space. Get them to understand why being able to type a/b and get division is not as useful as having things like http://example.com not need quotes. That's concrete and has quick wow factors. Trying to come up with examples of the value of foregoing traditional precedence is way harder to knock out of the park quickly.

;-- Without EXPR

>> 1 + 2 * 3
== 9

;-- With EXPR

>> expr [1 + 2 * 3]
== 7

^{CC - Data [ Version: r3 master Type: Wish Platform: All Category: Mezzanine Reproduce: Always Fixed-in:none ]}

[rebolbot]

Submitted by: BrianH

"normal precedence, like the 'rest of the world' agrees upon"

The problem here is that the rest of the world most definitely does not agree on precedence rules. They vary widely even between programming languages, and are the subject of much heated debate between their communities. We can't just use the mathematical precedence rules, because the math rules don't have ASCII multiplication operators and does division with horizontal lines, and that's just for a start. Mathematical notation has been under debate for thousands of years with no signs of letting up soon.

I'm not discouraging you here, the rationale for this is good. Rebol-like precedence is rare outside of Rebol-like languages and we would benefit from a way to shut down complaints about that. We just need to be specific about the precedence rules you want here, and exactly which operators are to be supported, because there is no such thing as "normal" precedence rules. You have to specify the whole set of operators, and what precedence they are supposed to have relative to each other, and what precedence not-operator expressions have in all this.

As a suggestion, consider this treatment of the non-operator expressions: Have normal function arguments be taken at a lower priority than any operators (which would all have to be keywords). If an operator is seen in the input stream, that means you have run out of parameters, and if you didn't have enough this is an error. If you run out of parameters early, this is an error. Get-word arguments would be able to break these rules, letting the operator word just be a word value instead of a keyword (so you can use QUOTE). I'm leaning towards lit-word arguments having the same precedence rules as normal ones, with the operator keywords simply not being usable as lit-word arguments without quoting them in a paren, just to reduce ambiguity.

As for the operator precedence itself, the standard math operators tend to be pretty consistently mul/div first, add/sub next, but after that there is very little agreement between programming languages. You'd have to look at them and decide. Fortunately we just have equivalences, relative equivalences, and logical operators. At least we don't have to deal with anything postfix, and prefix are the function calls above.

We also have to decide what precedence set-words would have.

[rebolbot]

Submitted by: fork

These arguments are coming from JavaScript and C people... not Haskell/Lisp people. Copy JavaScript:

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Operator_Precedence

People coming back with feedback about "you could have done that better" aren't going to be Rebol people, because they won't use it. Modifications worth doing are anything which make them get off the topic.

The point isn't in the minutiae. It's "why don't you do ANYTHING close to what a REASONABLE person would expect". Show them you can be sort of what they think is reasonable, then immediately change the subject!

[rebolbot]

Submitted by: BrianH

Oh, sorry to hear that, precedence in C-like languages tends to suck really bad. Hopefully we can do something a little closer to Modula-3, it has better precedence rules than the rest of the Pascal family and the entire C family. It's a good thing we don't have to do as many levels.

We might be able to do something simpler and just assume that only operators (that we know about) have precedence (that we decide on ahead of time), and just do a simple rewriting pass changing the operators to their corresponding prefix functions (they all have them), and have the rewriter put everything between the operators into parens, just in case. QUOTE would need to be a prefix operator. Then, we wouldn't have to rewrite DO while we're at it. This could be a static transform, even doable in a compiler like Red, even doable in a mezzanine function in Rebol if it comes down to that.

[rebolbot]

Submitted by: fork

I think most people will be happy if the rules for addition, subtraction, division, and multiplication work as they expect. It's a sticking point. If you have a better chart to copy which covers that, then it's probably fine.

People just really stick on this [1 + 2 * 3]. Might seem funny how the house of cards of their programming world collapses every day, yet they care about that. But maybe that's exactly why they react so strongly; in their languages that's the one thing they can count on. Using a language that breaks the one thing they trust might just be the last straw to send them screaming!

...

"There is something you need to understand about showing people Future Things. You have to be careful. It's a lot like if you are dealing with someone who has never had a grape before. When you give them their first grape you must be 100% sure it's not a sour one...because if it is sour, then every time they're asked if they want a grape after that they will say no." -æ-

[rebolbot]

Submitted by: abolka

Here's two references for Modula-3's precedence rules;

• http://radx.ru/images/1.html#idx.153 (that's from the original language definition)
• http://monet.cs.columbia.edu/modula3/tutorial/www/m3_56.html

[rebolbot]

Submitted by: BrianH

OK, so based on the numbering of that last link, we can do levels 6 through 11, and put QUOTE in at number 5. The rest would be handled by normal Rebol precedence simply by not being rewritten. We need to handle parens too, because if we don't the stuff in parens would have normal Rebol precedence. Parens would be lower precedence than anything, except parens after a QUOTE would not be rewritten.

[rebolbot]

Submitted by: fork

If I wrote it, it wouldn't be as good as if you wrote it, but so does that mean I have to write something crappy for you to correct before it happens?

If that is the case, please look forward to my terrible pull request implementation of EXPR... designed solely to provoke you into making a good one :-)

[rebolbot]

Submitted by: BrianH

Already working on it, in my head at least. With the precedence rules decided on above. Not my next PR though.

[rebolbot]

Submitted by: fork

There is an implementation that exists to possibly borrow from, pointed out by @rebolek

http://rebol2.blogspot.cz/2013/07/mathematical-expression-dialect-parser.html

[hostilefork]

:o: Ren-C has this satisfied well enough for now as "MATH" (code borrowed from Gabriele Santilli)

https://github.com/metaeducation/ren-c/blob/f9014ce2298aed45a638fa89c2a86077e0c38b17/src/mezz/mezz-math.r#L129

[giesse]

The fact that years of this debate happening and no one just sitting down and writing the EXPR implementation is ridiculous.

Funny people would say that, it's one of the first things I wrote when PARSE came out in R2, 1999 or so. I never used it and I'm not aware of anybody using it, hence most people don't know. (I see you've found it and used it.) My conclusion is that contrary to what I believed at the time precedence rules are a waste of time. But it's good that you guys are giving people the option to do things that way, I guess.

[hostilefork]

I see you've found it and used it.

Well...I haven't "used" it myself per se, but put it in. Should have added some tests for it, too.

One aspect that comes up if one tries to use the dialect "for real" is that it's not easy to tell where expressions end without running them through the evaluator, so you wind up putting more things in parentheses than you might like. There doesn't seem to be a good answer to that.