If you have the expression 1+2*3 you have three elements with two operands. You need to choose a rule to pick one of them first.
In mathematics, the rule is "*/ then +-" and then from left to right. This means that usually first you do 2*3, then 1+.
But what if you do want to make 1+2 first?
There is another alternative, parenthesis. Those mean "do the thing inside first" so (1+2)*3 changes the precedence and now you do 1+2 first, then *3
The post is asking: with parenthesis you can increase the precedence of operations. What if you could decrease it?
Let's use «» as another operand (the blog uses parenthesis, but that makes it really confusing) this operand means "do the thing inside last". So the expression 1+«2*3» means "do 1+ first, then 2*3.
The issue is...this doesn't make sense, what the blog is really saying is to reduce the precedence of operators. Think the expression 1+2«*»3 or 1+2(*)3 and now the rule is "the parenthesized operators have one precedence less" so 1+2(*)3=(1+2)*3
I don't think that's even well-defined if you have arbitrary infix operators with arbitrary precedence and arbitrary associativity (think Haskell).
If $, & and @ are operators in that order of precedence, all right-associatve. Using your notation, what is:
a & << b $ c >> @ d
If $ is reduced below & but above @ then it's the same as:
((a & b) $ c) @ d
If it's reduced below both & and @ then it becomes:
(a & b) $ (c @ d)
I think conceptualizing parentheses as "increase priority" is fundamentally not the correct abstraction, it's school brain in a way. They are a way to specify an arbitrary tree of expressions, and in that sense they're complete.
This seems to be the best guess so far. But then I am wondering, how is
a (*) b + c
Parsed then? The precedence of '* is bumped down, but does that mean it has now strictly lower precedence of '+', or the same? In the first case the operation is parsed as
a * (b + c)
In the second case, the "left to right" rule takes over and we get
(a * b) + c
And what happens when there are more than 2 priority groups Taking C has an example, we have that '' has higher precedence than '+' which has higher precedence than '<<' [1]. So
a + b * c << d
Means
(a + (b * c)) << d
Now I could use the "decrease precedence" operator you proposed (possibly proposed by the author?) and write
a + b (*) c << d
Which then bumps down the precedence of '' to... One level lower? Which means the same level of '+', or a level lower, i.e. a new precedence level between '+' and '<<'? Or maybe this operator should end up at the bottom of the precedence rank, i.e. lower than ','?
The more I think about this, the less sense it makes...
Thanks indeed.
Using a simple left-to-right evaluation is the most logical solution.
You can reorder expressions to use less parentheses and make them easier to read. E.g.: Smalltalk :-).
But this requires everyone un-learning their primary school maths of e.g. multiply-before-add, so it's not popular.
Having hand-picked operator precedences complicates things further when you allow operator overloading and user defined operators. E.g. Swift has special keywords to specify precedence for these. Ick...
Thanks, writing it as 1+2(*)3 made it click for me.
Reminds me of the '$' operator in Haskell - it lowers the precedence of function application, basically being an opening parenthesis that's implicitly closed at the end of the line.
I'm not sure I'm following but I think what he means is that if normal parenthesis around an addition mean this addition must precede multiplication, these anti-parenthesis around a multiplication have to make addition take place before it.
The examples at the end show that it's syntax for "parse such that this expression is not grouped". Essentially I guess this could be modelled as an operator `(_+_)` for every existing operator `_+_`, which has its binding precedence negated.
Is it the same as flipping every parenthesis to the other side of the number it's adjacent to, and then adding enough parentheses at the start and end?
For example,
(1 + 2) * (3 + 4)
becomes
1) + (2 * 3) + (4
and then we add the missing parentheses and it becomes
(1) + (2 * 3) + (4)
which seems to achieve a similar goal and is pretty unambiguous.
I am in the middle of developing a parser for a new language with original representation vs. syntax issues to resolve.
Clearly, this was the worst possible time for me to come across this brain damaging essay.
I really can’t afford it! My mathematical heart can’t help taking symmetrical precedence control seriously. But my gut is experiencing an unpleasant form of vertigo.
If you do both (use flipped parentheses around the operators), it makes even more sense, and makes the parsing trivial to boot: just surround the entire expression with parentheses and parse normally. For instance:
1 + 2 )( 3
Becomes
(1 + 2 )( 3)
Which is actually just what the author wants. You might even want multiple, or an arbitrary numbers of external parentheses. Say we want to give the divide the least precedence, the multiply the middle, and the add the most. We could do that like:
1 + 2 )/( 3 ))(( 4
Surround it with two sets of parens and you have:
((1 + 2 )/( 3 ))(( 4))
I haven't just proved to myself this always does what you expect, though...
The concept of "inverse parentheses" that unbundle operators is brilliant! The tokenizer hack (friendliness score by parenthesis depth, inspired by Python INDENT/DEDENT) + precedence climbing for infinite levels is elegant – parsing solved without convoluted recursive grammar.
kellett
I love the twist: reversing the friendly levels gives you a classic parser, and it opens up crazy experiments like whitespace weakening. Have you tested it on non-arithmetic ops (logical/bitwise) or more complex expressions like ((()))?
Regarding the first two footnotes, I’m pretty sure that originally the singular form “parenthesis” just refers to the aside inserted (by use of brackets, like this) into a sentence. Because it sounds like a plural and because of the expression “in parenthesis”, people probably mistakenly applied the word to the pair of symbols, and when that became common, started using the real plural “parentheses”. This has staying power because it’s fancy and “brackets” is way overloaded, but historically it’s probably just wrong and especially nonsensical in math and programming, where we don’t use them to insert little sidenotes.
Instead of ordinary brackets, one can also use the dot notation. I think it was used in Principia Mathematica or slightly later:
(A (B (C D)))
would be
A . B : C .: D
Essentially, the more dots you add, the stronger the grouping operator is binding. The precedence increases with the number of dots.
However, this is only a replacement for ordinary parentheses, not for these "reverse" ones discussed here. Maybe for reverse, one could use groups of little circles instead of dots: °, °°, °°°, etc.
Based on this comment (https://news.ycombinator.com/item?id=46352389), I think I understood the missing first paragraph:
If you have the expression 1+2*3 you have three elements with two operands. You need to choose a rule to pick one of them first.
In mathematics, the rule is "*/ then +-" and then from left to right. This means that usually first you do 2*3, then 1+.
But what if you do want to make 1+2 first?
There is another alternative, parenthesis. Those mean "do the thing inside first" so (1+2)*3 changes the precedence and now you do 1+2 first, then *3
The post is asking: with parenthesis you can increase the precedence of operations. What if you could decrease it?
Let's use «» as another operand (the blog uses parenthesis, but that makes it really confusing) this operand means "do the thing inside last". So the expression 1+«2*3» means "do 1+ first, then 2*3.
The issue is...this doesn't make sense, what the blog is really saying is to reduce the precedence of operators. Think the expression 1+2«*»3 or 1+2(*)3 and now the rule is "the parenthesized operators have one precedence less" so 1+2(*)3=(1+2)*3
I don't think that's even well-defined if you have arbitrary infix operators with arbitrary precedence and arbitrary associativity (think Haskell). If $, & and @ are operators in that order of precedence, all right-associatve. Using your notation, what is:
If $ is reduced below & but above @ then it's the same as:((a & b) $ c) @ d
If it's reduced below both & and @ then it becomes:
(a & b) $ (c @ d)
I think conceptualizing parentheses as "increase priority" is fundamentally not the correct abstraction, it's school brain in a way. They are a way to specify an arbitrary tree of expressions, and in that sense they're complete.
This seems to be the best guess so far. But then I am wondering, how is
Parsed then? The precedence of '* is bumped down, but does that mean it has now strictly lower precedence of '+', or the same? In the first case the operation is parsed as In the second case, the "left to right" rule takes over and we get And what happens when there are more than 2 priority groups Taking C has an example, we have that '' has higher precedence than '+' which has higher precedence than '<<' [1]. So Means Now I could use the "decrease precedence" operator you proposed (possibly proposed by the author?) and write Which then bumps down the precedence of '' to... One level lower? Which means the same level of '+', or a level lower, i.e. a new precedence level between '+' and '<<'? Or maybe this operator should end up at the bottom of the precedence rank, i.e. lower than ','?The more I think about this, the less sense it makes...
[1] https://en.cppreference.com/w/c/language/operator_precedence...
Thanks indeed. Using a simple left-to-right evaluation is the most logical solution. You can reorder expressions to use less parentheses and make them easier to read. E.g.: Smalltalk :-). But this requires everyone un-learning their primary school maths of e.g. multiply-before-add, so it's not popular. Having hand-picked operator precedences complicates things further when you allow operator overloading and user defined operators. E.g. Swift has special keywords to specify precedence for these. Ick...
Thanks, writing it as 1+2(*)3 made it click for me.
Reminds me of the '$' operator in Haskell - it lowers the precedence of function application, basically being an opening parenthesis that's implicitly closed at the end of the line.
Thanks, this makes more sense, the blog post was written in a really confusing way.
Am I stupid if I don't get it? What is the intended end state? What does "ungroup operands" mean?
I'm not sure I'm following but I think what he means is that if normal parenthesis around an addition mean this addition must precede multiplication, these anti-parenthesis around a multiplication have to make addition take place before it.
> Have you ever noticed that lots of programming languages let you use parentheses to group operands, but none use them to ungroup them?
Since this doesn't exist in practice, shouldn't the article author first explain what they mean by that?
The examples at the end show that it's syntax for "parse such that this expression is not grouped". Essentially I guess this could be modelled as an operator `(_+_)` for every existing operator `_+_`, which has its binding precedence negated.
I'm all for terseness in blog writing, but I think the author forgot to add the content. I know nothing more than I did when I opened it.
And yet, this is the top entry on HN right now?! How does that happen??
Is it the same as flipping every parenthesis to the other side of the number it's adjacent to, and then adding enough parentheses at the start and end?
For example,
becomes and then we add the missing parentheses and it becomes which seems to achieve a similar goal and is pretty unambiguous.I am in the middle of developing a parser for a new language with original representation vs. syntax issues to resolve.
Clearly, this was the worst possible time for me to come across this brain damaging essay.
I really can’t afford it! My mathematical heart can’t help taking symmetrical precedence control seriously. But my gut is experiencing an unpleasant form of vertigo.
I was hoping the parentheses themselves would be flipped. Like this:
> 1 + )2 * 3(
(1 + 2) * 3
I think surrounding the operand would make slightly more sense, as in 1 + 2 (*) 3 as if it's a "delayed form" of the operation that it represents.
If you do both (use flipped parentheses around the operators), it makes even more sense, and makes the parsing trivial to boot: just surround the entire expression with parentheses and parse normally. For instance: 1 + 2 )( 3 Becomes (1 + 2 )( 3) Which is actually just what the author wants. You might even want multiple, or an arbitrary numbers of external parentheses. Say we want to give the divide the least precedence, the multiply the middle, and the add the most. We could do that like: 1 + 2 )/( 3 ))(( 4 Surround it with two sets of parens and you have: ((1 + 2 )/( 3 ))(( 4)) I haven't just proved to myself this always does what you expect, though...
Same.
That said if you try to use that with ordinary parentheses usage it would get ambiguous as soon as you nest them
The concept of "inverse parentheses" that unbundle operators is brilliant! The tokenizer hack (friendliness score by parenthesis depth, inspired by Python INDENT/DEDENT) + precedence climbing for infinite levels is elegant – parsing solved without convoluted recursive grammar. kellett
I love the twist: reversing the friendly levels gives you a classic parser, and it opens up crazy experiments like whitespace weakening. Have you tested it on non-arithmetic ops (logical/bitwise) or more complex expressions like ((()))?
It's not just brilliant, it's earth-shattering.
Regarding the first two footnotes, I’m pretty sure that originally the singular form “parenthesis” just refers to the aside inserted (by use of brackets, like this) into a sentence. Because it sounds like a plural and because of the expression “in parenthesis”, people probably mistakenly applied the word to the pair of symbols, and when that became common, started using the real plural “parentheses”. This has staying power because it’s fancy and “brackets” is way overloaded, but historically it’s probably just wrong and especially nonsensical in math and programming, where we don’t use them to insert little sidenotes.
Echoing the sentiment that I'm not really sure what I'm meant to be looking at here. A motivating example at the start would have helped, I think.
The core idea: normally, parentheses strengthen grouping:
1 + (2 * 3) forces 2 * 3 to happen first.
Without them, operator precedence decides. The post asks a deliberately strange question:
What if parentheses did the opposite — instead of grouping things tighter, they made them bind less tightly?
Parenthesis used to decrease precedence? Everything outside of the parenthesis will be done before what is in the parenthesis?
Where do stars live? Thats what I wonder.
Using Brave on MacOS, I cannot scroll the page to see the entire text. On Firefox, it scrolls fine.
Same in Safari. It has something to do with the
in the main CSS file: https://kellett.im/theme/main.cssCannot scroll on Safari on macOS, either. What also doesn't work is making the font smaller / larger.
Splendid. Someone found a way to break Browser Scrolling. (Firefox 115.16 for Win7)
Well done.
I don't understand
Slightly unrelated:
Instead of ordinary brackets, one can also use the dot notation. I think it was used in Principia Mathematica or slightly later:
would be Essentially, the more dots you add, the stronger the grouping operator is binding. The precedence increases with the number of dots.However, this is only a replacement for ordinary parentheses, not for these "reverse" ones discussed here. Maybe for reverse, one could use groups of little circles instead of dots: °, °°, °°°, etc.
Opened this excitedly, thinking I was going to get something related to S-expressions/Lisp, was disappointed...