A case for intransitive operator precedence (2019)
11 points by habibalamin
11 points by habibalamin
I find this proposal deeply unconvincing.
APL-family languages tend to have a much larger collection of primitive operators than C-family languages. The example grammar makes a variety of arbitrary (if familiar) choices about relationships between operators. What is the elementary-school intution for the relative precedence of the addition operator and the tally operator, or the grade operator? There is none.
All programming language syntax and semantics must be taught and learned. Instead of hazily appealing to the familiarity of a notation optimized for writing polynomials (and hoping the programming language author made similar leaps of imagination to oneself), uniform operator precedence (whether polish, reverse-polish, or strictly RTL/LTR) offers a simple rule that is easy to explain and easy to implement. With a little practice, it’s perfectly natural to read and write, and avoids arbitrary design choices and memorization. Intransitive operator precedence may shave a handful of ambiguous constructions away from the possibility space of a C-like language, but it does nothing to simplify the description or implementation of the language.
I like Carbon’s approach of treating precedence as intransitive and as a DAG https://github.com/carbon-language/carbon-lang/tree/8ad08e34e2b4da15c778ff5db60023123577b085/docs/design/expressions#precedence.
I am also doing something similar in my own experimental language with a modified Pratt parser.
Can you write more about your modified Pratt parser, please? I know there are several regulars here (not just me!) who are interested in them.
Sure! Though I used some non-standard made-up terminologies (bear with me)
The basic idea is that instead of having precedence as a number, I have a ParseOrder enum to decide how to parse something like a $ b @ c. The enum has three possible values
(a $ b) @ c)a $ (b @ c))Each pair of precedence groups (e.g. additive (+ or -) or multiplicative (* or /)) can have one of those three “parse order” in the group. For example, (Multiplicative, Additive) will be “higher.” The relation is transitive, so (Additive, Multiplicative) will be “lower.” All the pairs not specified will have “ambiguous” by default.
In a build script, I specify the graph relationships of precedence groups and generate a ParseOrder[precedence_group_count][precedence_group_count] matrix from it.
Then, in the parser where one normally compares the precedence number, I will look up the ParseOrder matrix.