Perl and Parsing 7: Do List Operators have Left/Right Precedence?

Chiral Operators

In actual usage, the syntax of Perl's list operators is quite natural. Descriptions of that syntax, however, tend to be awkward.

The current practice is to describe this syntax in terms of "left precedence" and "right precedence". In other words, list operators are said to be chiral. I have problems with the Chiral Interpretation of list operators. The most serious of these: the Chiral Interpretation does not actually account for the behavior of expressions that contain list operators.

In this post, I assume you have a working knowledge of one or more list operators (examples are join and sort). The most authoritative account of the Chiral Interpretation is in the perlop man page.

Our Example

The rest of this post will use a single example:

sub f { say $_[0]; return $_[0]; }
say join ';', $a = f(1), $b = join ',', $c = f(2),
    $d = join '-', $e = f(3), $f = f(4);

Here's the output:


1
2
3
4
1;2,3-4

What is Precedence?

Precedence is a concept familiar from ordinary arithmetic. In school we learned that, in the expression

   1+2*3+4


the 2*3 should be multiplied out first to yield 6, before either of the two additions are performed. Multiplication has higher prececedence than addition.

Precedence is a hierarchy. There is an order, from high to low, and each operator has a distinct place.

Some cases are tricky. The same symbol is often both a unary operator and a binary operator. It's very common for the ASCII hyphen-minus sign ("-") to act as both a unary negation operator, and as a binary subtraction operator. The precedence of the unary operator can be different from the precedence of the binary operator, and often is. But while the unary and binary operators may share the same symbol, they are considered to be distinct operators.

If we accept that list operators have a left and a right precedence, as the perlop man page does, that would be an outright exception to the hierarchical ordering of operators by precedence. This points to a potential problem in defining left and right precedence. But that is not the most serious issue with the Chirality Interpretation. So that I can go straight to my main point, let's assume that there are no issues in defining left and right precedence. For now, let's just say that "I can't tell you what the difference between left and right precedence is, exactly, but I know it when I see it".

Let's ask instead about the precedence of operators other than the list operators in expressions which contain list operators.

Comma Operators versus Assignments

Look at the assignment and comma operators in the example above. Ask this question: Does the comma have a higher or lower precedence than the assignment operator?

According to the perlop man page, assignment has a higher precedence than the comma operator. But in the example above, this is not always true. Here are values of the variables after the example is executed:


$a=1
$b=2,3-4
$c=2
$d=3-4
$e=3
$f=4

For the assignments to $a, $c, $e, and $f, things are as perlop says -- those assignment operators have higher precedence than all the commas.

But for the assigment operators in the assignments to $b, and $d, things do not behave as advertized. True, those assignments still have higher precedence than the commas to their left. But the assignment of $b has lower precedence than the commas to its right. The same is true of the assignment to $d.

Chirality is Contagious?

What seems to be happening is that not only are list operators showing chirality, but that chirality is spreading to other operators. The perlop man page does not really prepare us for this.

The Grouping Operator Interpretation

Now let's add parentheses, so that they clarify the syntactic groupings without changing them:


say join ';', $a = f(1), $b = (join ',', $c = f(2),
    $d = (join '-', $e = f(3), $f = f(4))); 

With this the conceptual problems disappear. Why? Because parentheses are recognized as a grouping operator. That is, we know that, regardless of the precedence hierarchy among operators, operations inside parentheses will take precedence over operations outside the parentheses. Parentheses also have two different precedences, but they are not chiral -- parentheses have an internal and an external precedence.

The parentheses suggest a better way to describe Perl's list operators. We can think of the list operators as a special kind of grouping operator.

  • Just as a grouping begins before a left parenthesis, a grouping starts just before the list operator.
  • Just as with parentheses, operations inside a grouping take precedence over those outside.
  • Unlike parentheses, the grouping begun by a list operator is not closed explicitly. The grouping started by a list operator ends just before the next operator which has a precedence lower than the internal precedence of the list operator.
  • If, in an expression, no operator after the list operator has lower precedence, then the grouping ends at the end of the expression.
  • The internal precedence of list operators is between the precedence of the Perl comma operator and the precedence of Perl's logical not operator. This is higher than the internal precedence of parentheses. In the current perlop man page this is said to be the "rightward precedence" of list operators.
  • The external precedence of a list operator is the same as the precedence of a Perl term. This is the same as the external precedence of parentheses. In the current perlop man page, this is said to be the "leftward precedence" of list operators.
  • List operators do not have chirality.

Other Problems with Chirality

Operator Chirality is Hard to Define

Above, I deferred the question of how to define left and right precedence. Now I'll come back to it.

Giving the same operator two different precedences violates the textbook definition of precedence. Precedence is a hierarchy. Chiral operators break that hierarchy.

Consider an operator which is to the right of one list operator, but to the left of another list operator. How do you assign it a precedence?

Grouping operators also break the hierarchy, but they do it in a well-defined way. You could modify the Chiral Interpretation so that it is equally well-defined. But I think, if you do so, you'll find you've reinvented grouping.

Operator Chirality is Hard to Describe

Find a Perl book that describes list operator precedence. There are several excellent ones, by experts. Ask yourself: If I were a newbie, and I carefully studied these paragraphs, would I know list operator syntax cold? Or would there still be a lot of cases where I was not sure? The answer to this must be subjective, but my own observation is that many a lucid account of Perl bogs down when it is time to describe the syntax of list operators.

Operator Chirality is not in the Textbooks

"Left precedence" and "Right precedence" certainly sound like academic terms, but to my knowledge they are nowhere in the academic literature. As far as I know, chiral operators are an "ad hoc" explanation invented and used exclusively in attempts to grapple with Perl's list operators.

Both the Chiral Interpretation and the Grouping Interpretation involve giving the same set of operators two different precedences. The difference is that the behavior of grouping operators is well understood and has been carefully documented in the academic literature.

The Perl tradition is not to fret excessively about theory. But when the descriptive going gets tough, it is nice to have theory to fall back on.

Notes

Note 1: The academic literature on parsing is large, and it is risky to assert that something is not "Out There" somewhere. But there's no sign of "left precedence" and "right precedence" in the very comprehensive Grune & Jacobs, Parsing Techniques: A Practical Guide - Second Edition.

5 Comments

Interesting - but is join an operator? 'perldoc -f join' finds the documentation - and this suggest that join is a function. So the example is in fact equivalent to:

say join ';', $a = f(1), $b = join( ',', $c = f(2), $d = join( '-', $e = f(3), $f = f(4)));

Hi, I'm a Perl newbie (don't kill me if I'm blabbering) and I had trouble understanding list precedence on pg:90 of the Camel book, which your article clarifies somewhat.

However I have a few doubts regarding what's in your article!

You said: 'The internal precedence of list operators is higher than the internal precedence of parentheses. The internal precedence of the list operator is the precedence currently described in the perlop man page as its "rightward precedence".'

Are you sure it's rightward precedence and not leftward??? My understanding of things was that: (listoperator)(operands) - This would be leftward precedence because the listoperator is leftwards to the operands. Similarly when you say, "internal precedence of the list operator" This means: listoperator1 operands1 listoperator2(operands2)
Here, listoperator2 is leftwards of operands2 BUT it is also rightwards of operands1. So!! operands2 is INTERNAL to listoperator2 and operands1 is external to listoperator2!

Therefore your line should read:
'The internal precedence of the list operator is the precedence currently described in the perlop man page as its "LEFTWARD precedence".'

[it being leftward from the point of view of its operands]

eg: (1, 2, 3, sort 4, 5, sort 6, 7)
Considering the second sort: it's both a leftward list operator AND a rightward list operator?

It will greedily gobble up(6,7) because it has very high leftward precedence:
| sort <-- (6,7) lies to the left of (6,7) |

But looking at it like this: sort 4, 5 --> sort(6,7), it is weakly rightward precedent??

So the end result would be 1, 2, 3, sort(4, 5, sort(6, 7)).

Is this interpretation what the Camel book is trying to say?

About Jeffrey Kegler

user-pic I blog about Perl, with a focus on parsing and Marpa, my parsing algorithm based on Jay Earley's.