Partial Order Precedence
51 points by liberty
51 points by liberty
Nice. The first time I encountered this idea was in Pony, and it felt so obvious in hindsight, especially after seeing a SQL query do a lot of damage in production due to or/and precedence not matching what the author expected. I adopted it for RCL as well. Great to see that Zig is adopting it too now!
If you check out the original proposal they explicitly cite Pony. Fun fact, that person submitted quite a few language proposals around that time, most of which had me scratching my head, but this one struck me as a good idea.
I think it's badass that Pony took it all the way, including + and *. Even I wouldn't dare to take it that far.
I am presently daring to take it that far in my private PL. We'll see if it was a good idea or not :P
I'm on iteration 13 in 7 years, but I think this one is the winner. I just get too greedy with adding features. comptime inspired by zig was especially the big time sink. It turns out that it's just not really a good idea to combine with subtyping based type systems (maybe an HM could do it because they have equality, but it gets very complicated). Type reflection in complex type systems is a nightmare. But I keep wanting to have my cake and eat it too.
Now that we live in the age of LLMs, I think I'm further emboldened to do it; for the opposite reason as most seem to be advocating, though. Because it's such a niche combination of ideas, LLMs absolutely suck at coding it or understanding it.
So I get to still program and see my potential, and so I might as well be as ambitious as possible. I want a language that I'll enjoy writing in until I die.
$Employer recently had a false alarm caused by misunderstood precedence between && and ||, so I'm in favour of Pony's stringency. If I had to write that many parentheses on a daily basis I might feel differently, though. No disrespect intended to lispers :)
Us Lispers tend to make use of tooling to disambiguate parentheses and avoid unpairing them. I wonder if plugins for editors will make more effort to add similar features for languages like Zig and Pony. Though maybe that's overkill in this case and the preference should be to separate more highly nested statements.
FWIW I remembered encountering the partial order idea from a talk by Guy Steele about the Fortress scientific computing language (I think it was a talk at JuliaCon)
https://en.wikipedia.org/wiki/Fortress_(programming_language)
But actually I just learned that Fortress goes even further than partial order -- it is not even transitive. And also the Rhombus Language (new syntax by the creators of Racket) uses pretty much this:
https://docs.racket-lang.org/enforest/Operator_Precedence_and_Associativity.html
Unlike a system based on numeric precedence levels, precedence in the Rhombus expander is not a complete or partial order. It’s not even transitive.
Hm looks like Zig is transitive? From my quick reading of the blog and https://ziglang.org/documentation/master/#Precedence
The difference may matter more in mathematical languages, with many operators. And also some operator combinations are disallowed by the type system, rather than by the syntax.
Just around a couple months ago I wrote up a proposal for Hare to do the same thing, which was mostly well-received by the community. It's cool to see that Zig is also making these changes! It's long overdue for programming languages to be more strict about this.
This is an extremely good idea that, I daresay, should become universal in all languages. Certainly I have followed similar rules informally, often using parens when not needed.
What I'm curious about is how this is actually implemented in the parser. Traditional op precedence is easy to implement: you have an expr[0], whose children are expr[1]'s, etc, each increment of prec level restricting the operators available. How do you adapt this idea to. a partial ordering?
You can see the Parsing Expression Grammar for this precedence stuff here: https://codeberg.org/ziglang/zig/src/commit/0084f08c30d91821e75cd0054100d751153576df/doc/langref/grammar.peg#L130-L159 (which I authored if you have any questions). Since it's a PEG, it's possible to directly translate that into a parser.
However, the Zig parser is handwritten for better error messages and recoverability (and fuzz tested against the PEG to ensure consistency). In the handwritten parser this is implemented with the following table: https://codeberg.org/ziglang/zig/src/commit/0084f08c30d91821e75cd0054100d751153576df/lib/std/zig/Parse.zig#L1733
You might also be interested in looking at ~seb's example implementation of their Hare proposal (see this comment for context):
https://git.sr.ht/~sebsite/harec/commit/e8e4941a585be80870872c00936e2c284b58e8fe
The Zig implementation is a bit obscured due to the logic needed to add notes about what the previous precedence was, so it currently looks more complicated than it really is.
Yeah, total order for operators which are just actually ambiguous has been a curse for a while. I implemented this in my PL via a precedence DAG since my syntax is user extensible. You can google precedence DAG for literature around it, but I'm guessing people can understand intuitively what it means for partial order.
And my user extensible grammar is decidable at installation time, meaning you can't construct an ambiguous grammar either.
Hm. What's the advantage compared to reducing the number of precedence levels?
Reducing the number of precedence levels would not reduce the amount of information the programmer would need to know, it would just change the information they need to know. It would also be a silent breaking change.
Also, consider where you would put bitwise operators: on the same level as addition/subtraction, the same level as multiplication/division, or put some on each level? In other words, how should a | b + c, a << b + c, a | b * c, a | b << c, etc be evaluated?
(for context here's what the precedence table looked like before this change)
I don't particularly think it matters where you put it -- languages like smalltalk have done well with just one left to right precedence level, for example.
You could also define bitwise as lower than arithmetic operators.
There's no real ambiguity, you just scan across the line of code.
There's no real ambiguity
There's no ambiguity in the rules, but there is ambiguity about whether or not the actual precedence rules match with what the programmer writing the code intended, since they could have misremembered the rules.
The approach here tries to find a happy medium: precedence rules for common operator combinations that you might expect from a C-like language, with fewer rules to remember, and with the less common operator combinations always being fully unambiguous about the programmer's intent.
Fun fact, JavaScript has this for "- x ** y" and "a ?? b && c" (that is, both are illegal). I think this is great, and is an obvious consequence of an "optimize for readers rather than writers" mindset.
A middle ground is to accept without parentheses, but for the canonical formatter to add them in confusing cases.