Source
r/ProgrammingLanguages•
PL_Design

Precedence Rules And De-Facto Naming

Discussion

In our language we allow programmers to define whatever operators they like, and we allow operator overloading. This lead us to an interesting situation where we noticed that if the precedence is defined per overload, then parsing expressions is either undecidable, or you need some disambiguating strategy that's almost certainly not something the programmer can predict. Our solution was to try mostly flat precedence, and we found that worked very well for the most part. We had to make some exceptions to make the language's notation read properly. For example, we noticed that indexing into structs or arrays was awkward because of situations like this:

a + foo.bar@2

. and @ are our de-facto struct and array indexing operators, and we found that we intuitively wanted those to parse in such a way that you can treat things like foo.bar@2 almost like name refs. Like this:

(a + ((foo.bar)@2))

But with flat precedence rules you get this instead:

(((a + foo).bar)@2)

This lead us to the insight that precedence rules aren't about the order of operations as much as they are about having de-facto names bubble up out of the notation. Talking about precedence rules in terms of operators or eliding parens instead of de-facto naming effects seems like missing the forest for the trees.

You can see the de-facto naming effect in PEMDAS rules in the following examples:

x^2 + 1

a + bcd * e

It's common to use superscripts for exponentiation, which makes it immediately obvious that 2 in x^2 + 1 is part of a different concept in the expression, and thus should not be added to 1. Implicit multiplication does the same thing in the second example, where bcd is a tightly bound concept composed of b, c, and d, and should be treated that way regardless of whatever a and e are doing. Notably you can accomplish this same thing by controlling your whitespace usage, for example:

a + b*c*d * e

But this isn't nearly as strong as having superscripts or implicit multiplication, both of which are fairly awkward to do in most programming languages. Some artifact of how our editors work? Something to do with how precisely we need to manipulate code? Correctly parsing identifiers is a big issue with implicit multiplication. I'm unsure all of the reasons for why this seems so hard to do, but the de-facto naming effects you can get from PEMDAS don't seem nearly as useful as they could be. Also worth noting is that in many languages you're rarely doing algebra or calculus in code, but instead you're importing the results of algebra and calculus into your code. This domain mismatch also seems relevant. Regardless, my hypothesis is that, modulo any competing concerns, the precedence rules you use should be optimized, by whatever metric is important for your domain, to maximize the de-facto naming effect. I don't have any reasonable way to test my hypothesis, of course, but I'd be interested to hear if any of you have any insights on this line of thinking.

Posted Jun 14, 2022, 6:26 PM UTC · edited

1421
molecularTestAndSet•

I'll never understand the obsession against operator precedence this sub seems to have. Pick something that makes doing common things ergonomic. Such as giving . a higher precedence than other operators. Yes, you can do that. No, it's not a crime.

32
PL_DesignOP•

We don't object to precedence, which we noted from the start when we decided on mostly-flat precedence. Our rule is that, with the exception of classic comparison operators, like ==, any operator that ends in = has lowest precedence and binds right-to-left. That way things like += or >>|>>= just work like they should.

My point in talking about this is the same reason why people talk about love rather than talking about chemical processes in the brain: Knowing how a mechanism works doesn't mean you understand its consequences.

4
bruciferNomsu.org•

It's because parsing with operator precedence is kind of a pain in the neck to implement and programming language designers love simplicity and flexibility of design. It's this mindset of "if I just make users do <X>, then it makes my job much easier and it would let users define their own syntax, and everyone likes defining new syntax, right?" I've been guilty of this myself in the past, but now I try to focus more on "what is the most intuitive/convenient thing for the user?" and bend over backwards to make the compiler do that, even if it's inelegant from an implementation perspective.

There's also a totally fair and legitimate complaint that some operator precedence is confusing and leads to bugs when people have no preconceptions about relative precedence between operators. For example, bitwise OR vs. arithmetic add vs. modulus (a | b + c % d). And in those cases (i.e. operators other than PEMDAS, comparisons, and boolean logic) it does make sense to use a simpler set of rules like "the compiler will tell you to use more parentheses."

2
molecularTestAndSet•

operator precedence is kind of a pain in the neck to implement

If you manually write the recursive descent layer for each precedence you will face an incredibly bad time yes. But pratt parsing to the rescue, it really doesn't need to be elaborate:

https://gitlab.com/xmdr/ananke/-/blob/master/prototypes/pratt.py

2
Mathnerd314•

if the precedence is defined per overload, then parsing expressions is either undecidable, or you need some disambiguating strategy that's almost certainly not something the programmer can predict.

What about defining precedence per symbol? The you have a clear parsing/semantics distinction and there is no problem. For example Haskell's precedence declarations:

infixl 6 +
instance Num Integer where (+) = integerAdd
instance Num Double where (+) = plusDouble

I'm not clear on what "flat precedence" is but it looks from your example like it's always associating to the left, which would be what Smalltalk calls "parsing left-to-right".

As far as "de-facto naming", this sounds like a really vague concept, compared to precedence's really specific "should it parse as (a + b) * c or a + (b * c)?" It is about the operators: in your examples you talk about the operators: superscripts, addition, implicit multiplication, and so on. It's true that most systems of precedence are ordered so that there is a hierarchy of binding power, giving something like "bubbling up", but conceivably you could have a precedence cycle, parsing a + (b * c), a * (b ^ c), a ^ (b + c), so this is just a convention.

6
PL_DesignOP•

Setting precedence per symbol works fine.

The concept is vague right now, but it's something that popped out to me as notable. I'm talking about it because I want to explore the idea more.

2
-ghostinthemachine-•

I have a similar situation, my language allows syntax to be defined on the fly, inside of a single scope even. What I realized that people hate about operator precedence is the seemingly arbitrary nature of a strict ordering. In reality, for most operators the precedence just doesn't matter, and like you say arithmetic is an exception. The solution I employed (borrowed from a paper) was to make the operator precedence into a graph. If something has to be before another thing, you call it out, and if it doesn't matter then you don't. What this means is that you can selectively define precedence and then slice the graph topologically to get your level 0, level 1, level 2 precedence as needed during parsing, similar to a precedence table.

5
hum0nx•

I think this would be more convenient. It does allow for cyclical graphs that would break the system however. So errors or something would be needed to account for that side effect

1
-ghostinthemachine-•

Yeah, cycles are undefined and throw an error, and I'm just hoping that's enough to discourage people from being too clever.

2
Host127001•

This lead us to an interesting situation where we noticed that if the precedence is defined per overload, then parsing expressions is either undecidable, or you need some disambiguating strategy that's almost certainly not something the programmer can predict

Something that I like to use: The precedence is encoded in the first symbol of an operator. So, everything starting with * binds more tightly than something starting with +. That way, you can have a list of allowed first symbols with their precedence and allow arbitrary operators on top of that without having to deal with custom precedences at all.

But I don't think parsing becomes undecidable for custom precedences. Haskell does it just fine. Of the precedence declaration is a top-level element then there is no conditional execution of the code. You could have a simple 2-pass parsing step where you first collect the infix symbols and then do the rest.

4
till-one•

But I don't think parsing becomes undecidable for custom precedences. Haskell does it just fine.

Sure. But how about the poor humans who have to try and understand what an expression does?

You don't want to mess around with what is expected of + and *.

With operators specific to the language or invented by the user, say @ and and ¬, then, fine, let the priorities be configurable.

But once decided, they should be the same program-wide and only one instance of each should be allowed within a program. Anything else (say, if treated like any other named user-entities) brings a raft of other problems.

(Like, being unable to properly parse expressions until names are resolved, but you might not be able to resolve names until everything is parsed first.)

2
PL_DesignOP•

The undecidability comes from combining overloading and per-overload custom precedence. You can run into multiple valid parses that way, and either you have an undecidable problem, or you introduce disambiguation rules that are probably hard to reason about.

2
moon-chilledj, bonsai•

Some artifact of how our editors work? Something to do with how precisely we need to manipulate code?

I do find the current crop of editors and development environments remarkably deficient. Better tooling would help out with your problem. However, I think the more coherent approach is to forgo operator precedence entirely. I cannot speak for smalltalk, and I think forth has problems, but apl has no issues whatsoever with math, and was in fact originally designed as a language for doing mathematics. One thing to pay attention to is operand ordering; in some cases, the most natural operand ordering will be opposite the more common ordering. Which way you lean depends a great deal on which way you let your operators associate.

3
till-one•

Implicit multiplication does the same thing in the second example, where bcd is a tightly bound concept composed of b, c, and d, and should be treated that way regardless of whatever a and e are doing.

The idea in my downvoted and now deleted post was pretty much this, to consider foo.bar@2 as a tightly bound unit, unaffected by whatever precedence-controlled operators might be on either side.

I don't get what you mean by 'de-facto naming', so I can't comment on your proposal, other than to say that language source code is not mathematical notation.

That doesn't preclude it from being used, but it would have to be a syntax within a syntax, for example which uses only single-character names, uses implicit multiply, superscripts and subscripts. But it probably won't be full-on mathematics as you don't want to bring type-setting into it too.

Then something like say {x² + 2xy + y²} can be just a cute way of writing (x*x + 2*x*y + y*y) within a conventional syntax (italics are optional...). But you wouldn't want to have 50,000 lines of this stuff; having only 26 identifiers would be too limiting for a start.

2
PL_DesignOP•

I'm saying that "tightly bound units" have a name-like quality. I have noted in the past two relevant effects that influence cognition:

  1. Until something has a name it's much harder to reason about.

  2. Prematurely naming something is likely to pollute your concept of what it is.

So having a way to produce a meaningful de-facto name without needing to wait for the right name seems useful.

2
[deleted]•

[deleted]

1
hum0nx•

I've run into this as well. Some other options:

  • Define precedence on a per-file basis. This allows DSL - like behavior where a whole ordering of operators can be imported by a user, and then the user can just use it
  • Just require ()'s and then no precedence is needed
  • Use whitespace for a really weird system. Closer = higher precedence, and just always do left-to-right evaluation.

None are fantastic, but hopefully you'll enjoy considering them

1
brucejbellsard•

You are correct that most code has a lot less algebra going on than would be expected from the proportion of the language and standard library devoted to it in most popular languages. I believe this bias was set by the early success of Fortran, which was specifically designed for implementing algebra.

At this point, this kind of algebraic syntax is a major expectation from most existing programmers. Also, for cases where you actually need any kind of algebra, the algebraic syntax is painful to do without. However, if you really want to follow this up, you could consider a Lisp-like approach, where arithmetic primitives are syntactically no different from any other function.

If you are particularly interested in "implicit multiplication", try looking up the Fortress language. If I recall correctly, it is defunct, but it had implicit multiplication for full names instead of individual letters: a + bcd e would be parsed as a + (bcd * e).

In any case, it is easy to have PEMDAS-style algebraic arithmetic precedence alongside indexing operators if the two classes of operators have disjoint precedence: either conventionally, where the arithmetic operators have lower precedence than the indexing ones:

a + foo.bar@(i + 2)

or (unconventionally) vice versa, where indexing operators have lower precedence than arithmetic ones:

a+(foo . bar @ i+2)

In either case, you will often need parentheses somewhere, but generally in a way that helps clarify the code, instead of clutter it.

1
[deleted]•

[deleted]

0
L8_4_Dinner•

But "syntax" is all that operator precedence is.

1
[deleted]•

[deleted]

1
PL_DesignOP•

My post was not about parsing techniques. It was about notation design. The story about our operators was just to show where the ideas came from.

1
[deleted]•

[deleted]

1
till-one•

BTW every other top-level reply mentions 'precedence', as does your subject line.

1
PL_DesignOP•

What are you saying?

1