HN Explorer

Poll: Operator Precedence

16 points by daeken ↗ HN
I've been doing a lot of thinking about operator precedence (and the lack thereof) in highly programmable languages. When the entire language is defined via macros (all user-facing constructs and operators), it becomes very difficult to parse code using operator precedence. You have to defer the grouping of operands until well after the actual parse-time. In addition, you could have the same operator with different precedence depending on the macros in scope.

To alleviate these issues, I've been considering doing away with operator precedence entirely, and making everything left-to-right (with parentheses and other grouping operators). My concern is that this could make the language highly undesirable to many developers, so I'd like to get a general feel for how you guys feel about this idea.

(Thanks to the people who responded to http://news.ycombinator.com/item?id=1027796 , where I originally talked briefly about this idea)

19 comments

[ 2.8 ms ] story [ 40.8 ms ] thread
jey
People manage to use RPN languages like Forth. http://en.wikipedia.org/wiki/Forth_(programming_language)

Why do you want to have the whole language defined through macros?

daeken
It makes the language considerably more flexible. Instead of a DSL hacking around the existing syntax (e.g. in Ruby), you're able to define anything you want, within the bounds of the parser (which, in my case, is very freeform, a la Lisps). It also means that a new implementation is effectively just compiling a small subset of the language, then the rest of it comes along for the ride, due to the macros. This is similar to the way that Scheme is defined as a large set of functionality atop a small bit that's implementation-specific.
joe_the_user
I remember the J programming language as not having operator precedence. It seemed to make parsing trivial.
andreyf
People can't answer a question like this honestly. It would be a deal breaker for many more than will admit it here.

You have to defer the grouping of operands until well after the actual parse-time.

Why?

you could have the same operator with different precedence depending on the macros in scope.

But if your macros have scope, isn't this a problem independent of operator precedence?

I'd suggest defining higher-order macros, where you can have a something like infix(op, prec=0, assoc=LEFT), used like:

    infix('+', 0)
    infix('*', 1)
    ...
For a similar example, see Haskell's infixr/infixl: http://www.haskell.org/tutorial/functions.html#sect3.2.2

Also, whatever it is you are doing might be easiest to implement using Alex Warth's OMeta: http://tinlizzie.org/ometa/

daeken
> You have to defer the grouping of operands until well after the actual parse-time.

Why?

Well, in the case of my parser, I get back an S-expression corresponding to the groups (parentheses, braces, brackets) in the code, with each token inside that. So to group expressions, I then have to go over that, applying the macros in order of precedence. If I make operators purely left-to-right (with the exception of . , which has to be special-cased), I can do this grouping at the parser level and simplify things.

But if your macros have scope, isn't this a problem independent of operator precedence?

It's still a problem, as it is with any language with macros, but by letting operators have precedence that can change from file to file (or even worse, from function to function, if you're sadistic) would make it very difficult for people to track what's going on. With the pure left-to-right parsing, the behavior of operator grouping would be consistent regardless of anything else that's going on.

gizmo
It's a deal breaker, I think.

For example:

    if x > y and x < max_x
looks fine with parens:

    if (x > y) and (x < max_x)
but when it becomes slightly more complicated:

   if (x > (y + 1)) and (x - 1 < max_x)
it really looks awkward.

Or how about this?

    x = 5 + 10
is parsed as

    (x = 5) + 10
and I'd really hate to have to write simple assignments as

    x = (5 + 10)
just to avoid that kind of snafu.

I don't think your compiler should get much more complicated with operator precedence. Just have a precedence stack that always reflects the operator precedence in the current scope. Parse the expressions without operator precedence (e.g. always LtR), then at a later compilation stage, swap the subexpressions in the AST until the AST adheres to the precedence rules, and you're done.

daeken
I do agree on the if statements; they're fairly complex, although easily readable. I wonder how that'd end up feeling in the real world. It'd definitely irritate me at first, at the very least.

As for assignments, this would actually be a nonissue. For example, x = 5 + 10 would be parsed as:

  (x = (5 + 10))
Same with a = b = c + d:

  (a = (b = (c + d)))
Edit: Hmm, I was just thinking about this, and this order of parsing could potentially cause issues. It'd work for most arithmetic, but in the case of complex operations (specifically operator overloads on things like matrices) it could cause problems. I need to think a bit more on this issue.
gizmo
My bad, I assumed you would pick the opposite parsing order as default, because we read left to right.

I'm not sure if I could get used to

   3 * a + 1
getting parsed as

   3 * (a + 1)
It would also be really awkward when considering slots/accessors/etc

   person.name = "Jack"
surely should never be:

   person.(name = "Jack")
daeken
The more I think about it, the more I realize that parsing order just plain wouldn't work. I'm starting to think that while doing things left-to-right could generally work, implementing some sort of simple precedence would probably just be easier. Thanks for the insight. It's threads like these that make me love asking this community for input.
allenbrunson
kind of tangentially related: despite spending decades programming in C-family languages, i have no idea which operators have precedence over others. in my own code, i always use enough parentheses so that it doesn't matter. if i'm looking at somebody else's code that contains long strings of unparenthesized numbers and operators, i'll have only a vague guess at what the eventual outcome will be.

if i find myself having to maintain code like that, first i'll write unit tests, then add parentheses where i think they ought to go, and make sure the tests still pass.

gtani
+1; I think many devs that regularly rotate thru java, python, ruby, javascript, etc. have to over-parenthesize (and engage in other least common denom-type stuff like inserting line-ending semicolons and parens around method args even wehre optional (ruby);
cduan
Interestingly, this reminds me of two programming languages you probably never thought about: TeX and Metafont.

TeX is an entirely macro-driven language. It processes an input file by reading a token (usually a single letter or a backslashed \command), and then either executing the token if it is a builtin operator or replacing the token with its macro definition. Since it is always processing the first token on the list, it has no operator precedence concerns (in essence, everything is in prefix notation).

Metafont (the programming language Knuth created for drawing fonts) is also a macro language, but it allows for infix notation as well as prefix. When you define an infix operator macro, you can choose a precedence level (primary, secondary, tertiary). For example (I'm not sure if this is exactly right), addition might be a tertiary operator, multiplication a secondary operator, and exponentiation a primary.

Having used both of these languages fairly extensively in the past, I would say that the easiest way to avoid the issue of operator precedence is to disallow infix operators. However, if you do think that infix operators are worth keeping in your language, you might look to the Metafont parser implementation for ideas--if there is anyone who has something to say on parsing, it is Donald Knuth.

niyazpk
I don't remember having problems with the way operator precedence work in any languages I worked with. May be I don't write complicated programs as you guys do.

Most of the time operator precedence works according to the BODMAS rule. Doesn't it?

ntoshev
I think a poll is a bad way to make such a decision. First, the poll options seem written in a way that would skew the answers towards "no precedence" (too many good sounding options towards that end of the continuum).

Second, I have never programmed in an infix-notation language without operator precedence, and I imagine most programmers are like me. I can't possibly know if I will continue to make stupid mistakes due to my intuition about precedence for just a couple of days after learning the language, a couple of months, years, or forever.

That said, I would encourage you to try the language without precedence and ask early adopters about their experience. If it is at all possible to have precedence in your way of doing things and it turns out to be needed enough, you can implement it later.

10ren
Another way to do this is with Reverse Polish Notation (as in forth); it has an avid but non-mainstream following.

I'd say it's only a problem if you want to go mainstream.

wingo
S-expressions solve this problem in a consistent way that is intuitive at least to some people.
gtani
I think you haven't differentiated macro's in the algol-family sense (compile-time string substitution for the 3 purposes of #def inline functions, #ifdef conditional execution, and #def constants, with full-on CL/scheme/clojure-style macro's.
joe_the_user
Hmm,

Looking at the discussion it seems like you would have to formulate your language as a whole and have sample to show people before you could determine if operator precedence "brakes the deal". I mean, meaningful whitespace breaks the deal for me in python but it works for a lot of people but suspect it only works in the context of everything else in that language.