Ocean of Awareness

Jeffrey Kegler's blog about Marpa, his new parsing algorithm, and other topics of interest

Jeffrey's personal website


Marpa resources

The Marpa website

The Ocean of Awareness blog: home page, chronological index, and annotated index.

Wed, 16 Feb 2011

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:


What is Precedence?

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


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:


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.

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.


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.

posted at: 09:15 | direct link to this entry

§         §         §