Exponentiation operator and precedence group

Looks like I missed that post due to a scrolling mishap. :slightly_smiling_face:

I'm looking forward to your suggestion, because there are still some tricky questions. Does unary + need the same treatment? Arithmetically, it's harmless, but perhaps the possibility of custom overloads means it should be treated like unary -?


Anyway, I wanted to add a comment on the other aspect being discussed:

My preference for exponentiation operator semantics would be for the multiplicative version (where the exponent is Int), since I think that would be the much more likely guess (people seem to hate logarithms, maybe from high school trauma).

In that case, I don't immediately seen any harm in allowing negative Int exponents to be used for the operator to give reciprocals, even if pow doesn't accept them.

Unary operator precedence

In languages based on or inspired by C, unary (prefix and postfix) operators have higher precedence than all binary (infix) operators.

This widely adopted design is also observed in Swift: Infix operators are assigned to varying precedence groups, and precedence groups can be ordered higher-than, ordered lower-than, or remain unordered relative to one another. However, all of these precedence groups have lower precedence than prefix operators (which in turn have lower precedence than postfix operators).

Unfortunately, this design clashes with mathematical custom regarding the exponentiation operator.

In mathematical notation, −2² is equivalent to −(2²) = −4. To keep with this custom, any exponentiation operator would require higher precedence than the prefix operator -. Like some but not all programming languages, Python (for example) implements exactly this design:

#  Python
print(-2 ** 2) #  Prints "-4"

Besides that it is not possible in Swift to assign an infix operator to a higher precedence than that of a prefix operator, users have commented that it is not desirable to do so in the first place:

While a subset of users will expect an exponentiation operator to observe mathematical custom, others will expect that -2 ** 2 will be parsed unambiguously as (-2) ** 2 based on the behavior of existing infix operators both in Swift and in other "C family" languages.

These two expectations are diametrically opposing: no design which accepts the combination of prefix - and ** without parentheses (whether or not ** is surrounded by spaces) will behave intuitively to all users.

Fortunately, there is precedent for a solution reconciling these competing expectations in a "C family" language. In JavaScript, prefix - and ** are explicitly unordered relative to each other, requiring the use of parentheses to clarify user intent:

// JavaScript
print(-2 ** 2)
// Illegal expression.
// Wrap left hand side or entire exponentiation in parentheses.

The same feature would align well with the current design and direction of Swift: We explicitly allow for infix operator precedence groups to be unordered relative to each other, and for operators within a precedence group to be non-associative, precisely with the intent that combinations of such operators should require parentheses to clarify the order of operations.

Removing binary operator precedence relative to unary operators

Recall that all binary operator precedence groups have lower precedence than all unary operators, even as binary operator precedence groups can be unordered relative to each other.

Unary operators, taken as a notional precedence group, therefore sit atop every precedence hierarchy however bifurcated. If the name of this precedence group were utterable, the current design for precedence groups is equivalent to having an implied lowerThan: _UnaryOperatorPrecedence for every precedence group:

// ...
precedencegroup AdditionPrecedence {
  higherThan: RangeFormationPrecedence
  lowerThan: _UnaryOperatorPrecedence // Implied
}
precedencegroup MultiplicationPrecedence {
  higherThan: AdditionPrecedence
  lowerThan: _UnaryOperatorPrecedence // Implied
}
precedencegroup BitwiseShiftPrecedence {
  higherThan: MultiplicationPrecedence
  lowerThan: _UnaryOperatorPrecedence // Implied
}

There are a number of (possibly elaborate) changes to Swift's design for operators and precedence groups to allow for an "apex" precedence group such as the proposed ExponentiationPrecedence to be unordered relative to unary operators. However, conceptually, it suffices merely to suppress the implied lowerThan.

The underlying implementation would differ from the existing check for unordered precedence groups because unary operators are not involved in that checking, but it would not require an elaborate overhaul within the compiler.

One possible expression of this concept would be to add a declaration modifier explicitly for such "apex" precedence groups:

@apex precedencegroup ExponentiationPrecedence {
  higherThan: MultiplicationPrecedence
  // Not implied because we're declaring an 'apex' group--
  // lowerThan: _UnaryOperatorPrecedence
}

Apex precedence groups would have the following behaviors and restrictions:

  • An apex precedence group has no explicit or implied lower-than precedence relationships
  • Another precedence group cannot be declared higher-than an apex precedence group

Besides the proposed ExponentiationPrecedence, the unutterable _UnaryOperatorPrecedence would be conceptually an apex precedence group; this would be merely another way of describing the "C family" design that no binary operator can have higher precedence.

It is conceivable that users will want to create other custom operators, unordered relative to all standard library operators or bifurcating the standard library hierarchy, which they will want to make "apex" operators.

2 Likes

Exponentiation should not have this property. For example, a tetration operator could plausibly have higher precedence than exponentiation.

• • •

From a convenience standpoint, making x**2 and -x**2 produce opposite results would be nice.

However, when spaces are included, -x ** 2 very strongly suggests the negation applies first, and that is how existing Swift operator rules behave.

• • •

The simplest and most consistent answer is to leave the existing operator behaviors as they are. This requires people to learn that -x**2 parses as (-x)**2 though, which is both nonobvious and inconvenient.

If we can find a way to give exponentiation the same precedence as postfix operators when used without whitespace, but a normal infix precedence when used with whitespace, that might be ideal.

I'm not terribly familiar with notations for tetration. For example, if we use the Knuth notation ↑↑ for tetration, is a ↑↑ b ² always unambiguously read as (a ↑↑ b)² rather than a ↑↑ (b ²)?

In practice, I expect that we would want any plausible but uncertain precedence relations to require explicit parens for disambiguation. This would be achievable by defining an apex TetrationPrecedence above MultiplicationPrecedence and unordered with respect to ExponentiationPrecedence.

The point of foreclosing operators with higher precedence isn't to express axiomatic finality that there can be no operations imaginable which are plausibly appropriate for a higher precedence. Indeed, the whole discussion here is that we've found a situation where unary operators, which already do have the behavior of the proposed apex precedence group, aren't appropriate as such.

Rather, the point is that pragmatically--acknowledging the inherent limitations in how complex of a precedence graph users can be expected to hold in their head--we can expect no such further operations to be clear enough that we wouldn't prefer to have users clarify their intent with parens. Therefore, by allowing the concept of an apex precedence group to be expressible in Swift rather than limited implicitly to unary operators only, we create the possibility of more than one apex precedence group, unordered with respect to each other, to accomplish that goal.

Whether or not we could, it would be very much not ideal to allow operators to have different precedence based on the presence of surrounding whitespace. This is very much contrary to the existing design of operators and would cause astonishment, in my view.

Quite simply, there can be no consensus as to the relative precedence of prefix - and ** because of competing incompatible customs in C-family languages and in math, and for that reason I'm well satisfied that the two should be unordered relative to each other.

I'm not 100% certain that the concept of an "apex" precedence group is the best way about it, so it would be interesting to explore what alternatives there are that would achieve that. However, for the reasons given in the analysis above I do not think that either "leaving it as-is" or "giving it higher precedence" would be acceptable to a sizable proportion of folks.

1 Like

I haven’t fully though it through, but what about:

  • Add a fully accessible—not underscored—UnaryOperatorPrecedence, which all unary operators have.
  • Define the default, synthesized lowerThan as lowerThan: UnaryOperatorPrecedence.
  • Enable the nil keyword to be used as an argument to lowerThan. nil represents an abstract, non‐existent precedence at the very end of the graph. As a logical consequence of the rest of the system, any operator declared this way requires parentheses when used with any other operator—including prefix operators—unless otherwise resolved by higherThan or the other operator’s lowerThan.
  • Add ExponentiationPrecedence to the standard library:
    precedencegroup ExponentiationPrecedence {
        higherThan: MultiplicationPrecedence // Or UnaryOperatorPrecedence?
        lowerThan: nil
    }
    
  • Use it for the ** operator.

Like the apex idea, it would not be introducing any special cases or baked‐in quirks. All aspects of it can be put to use in other places as well if needed. Unlike the apex idea, it doesn’t introduce any new concepts for users to learn. And while “apex” operators would not be able to interact with each other—a logical impossibility under that term—operators released from the implicit relation to the unary precedence can still freely interact with one another, or even be hoisted above them.

One downside of both the apex and nil strategies is that by erasing the hard‐coded supersession of unary operators, it further degrades the accuracy of SwiftSyntax’s syntax tree and those of any similar parsers. Unary operators would become like infix operators in that they could only be interpreted as a flat list of tokens, and not a structured syntax tree, due to a lack of outside information.

That is similar to my own iterations of the "apex" precedence group idea. It suffers from the following issues:

Unary operators do not have one but two different precedence groups, prefix and postfix. OK, so why not create two such precedence groups? Because:

It is an explicit anti-goal to allow users to place operators above or between these precedence groups for the reasons given earlier. Moreover, because unary operators are magically "above" every binary operator hierarchy, it is also an non-goal to place operators below this precedence group (which would allow installing arbitrary operators above every other possible precedence group instead of one specific other precedence group).

Therefore, creating actual (rather than a conceptual) precedence groups for unary operators is a drawback: It suggests that you can define operators relative to them, and you really cannot.

For reasons articulated in the original precedence group proposal, it is not permitted to use lowerThan unless referring to other precedence groups outside the same module. We would need to relax this rule, but then only for an implicit statement that's never written, which is weird.

This is a third reason that making lessThan: _UnaryOperatorPrecedence actually expressible is not helpful: We would need to create special-case rules for expressing a thing that's never expressed, and forbid any variation of it that can be written explicitly.

This is equivalent to the "apex" idea, but expressed within the body of the precedence group. I'm certainly open to an alternative spelling such as that. However, as you write, such a spelling implies that the "apex-ness" of the operator can be overridden. That would be a mistake in my view--see next.

Yes, and that's exactly what I do not want to allow. For one, if a non-"lowerThan: nil" precedence group is slotted above a "lowerThan: nil" precedence group, then prefix operators are implicitly slotted above them too. This leads to the very subtle footgun that a third-party library could change the behavior of -2**2 simply by slotting a precedence group above ExponentiationPrecedence and forgetting to write lowerThan: nil.

It stands to reason that "lowerThan: nil" precedence groups would at least need to prohibit the addition of higher non-"lowerThan: nil" precedence groups. This would seem to favor hoisting the "lowerThan: nil"-ness of a precedence group into the declaration, since it modifies the declaration in a similar way that open or final does in affecting what's permissible in a hierarchy.

This leaves the only difference between an "apex" precedence group and a "not-ordered-with-unary-operators" precedence group that the latter can be made ordered relative to other "not-ordered-with-unary-operators" precedence groups.

Two reasons for preferring "apex" over the latter concept:

  • As you say, the term "apex" suggests very strongly its own semantics: it's very intuitive and not subject to much misinterpretation. I haven't yet come up with a good name for "not-ordered-with-unary-operators" that is as evocative and unambiguous. While it's fine to have a complex name for a rarely used feature, where an alternative exists which is much more easily explained, I tend to wonder if it's more easily explained not just because there happens to be an English word for it, but also because it fits better with our current model.

  • If the precedence of an operator should be so high that it's not ordered below unary operators, which have the highest precedence in Swift-land, then it also shouldn't be ordered below any infix operators. And I can't think of actual use cases that would clearly convince me otherwise (see above discussion about tetration).

I find the second point to be fairly persuasive to me, but it would not be for you if you don't buy that we should respect the current Swift/C-family design that explicitly does not allow binary operators with higher precedence than unary operators. But I am operating based on the prior discussion linked to by @jrose where several users stated very clearly that it is their expectation that this aspect of operator precedence be observed by all operators, and that allowing exponentiation to be an exception would not be acceptable to them.

Within those constraints, I weighed the "apex" idea against a version of what you've described here and ultimately found the "apex" idea to be the more consistent one.


Edit: I should add, if we reject the consensus of the previous thread that @jrose linked to and felt it was fine to revamp Swift's precedence groups so that unary operators don't have to be always above binary operators, then the design is simple:

  • We would assign unary operators to named precedence groups (and we would change unary range formation operators to have a different precedence to unary + and - while we're at it). They would cease to be magically above every binary operator hierarchy but instead sit above BitwiseShiftPrecedence.

  • We would place unary + and - above binary multiplication operators but unordered relative to or ordered below **.

But as I said, I do tend to agree with the critiques in that thread that suggests that breaking with this expectation common to C family languages could be unexpected and confusing.

Regarding this issue: one option is to restrict such a feature to the standard library only at least temporarily; this would allow SwiftSyntax to have a hardcoded list of exceptions to the current rule and preserve its ability to provide as accurate of a syntax tree as it does currently.

I do buy the idea that binary operators should uniformly precede unary operators, because it respects a clear separation between syntactic analysis and semantic analysis. (It might even be possible to convince me that independent precedence weighting of different infix operators should be removed from the language, but I don’t think about it because something that breaking is obviously so far from ever being on the table.)

The direction of this thread seemed to be about a perceived need to break that axiom. Do I want to break it? Not really. But if we have do, then I would rather do it in a consistent and useful way.

My real preference would be to just let -x**y play like Swift and not try to make it play like math. It is already both bad math (−xy) and bad Swift (-x ** y according to any style guide I have ever seen). Order of operations isn’t a property of the operations, it’s a property of the notation. Despite the way we often say it, exponentiation does not precede multiplication in any inherent way. Rather, in western mathematical notation, superscripts precede juxtaposition. If I said, “I got two apples and four bananas twice,” you probably wouldn’t assume I received a total of two apples and eight bananas, because even though it is math, it is expressed in English, not mathematical notation, and so the multiplication operation doesn’t come first. Since Swift owns the notation here, not math, I am perfectly fine with -x**y being governed by prefixes preceding infixes.

7 Likes

What you are proposing is, I think, an appropriate level of abstraction. I can imagine the possibility of making this more abstract and more intricate, but I can't see that the higher complexity would solve any problem we actually have.

If that were the only distinction, I'd agree 100%. However, there's also a distinction about making it "play like" Python (for example) — even allowing that Swift isn't really responsible for Python's choices.

What I mean is that most modern languages have basically the same arithmetic operator grammar. Having something like -a + b change meaning across language boundaries would be pretty bad. Having something like -a ** b change meaning across language boundaries isn't as bad, but still seems like it's worth avoiding.

FWIW, the math notation –xy might be "bad" stylistically, if you choose to think so, but it's not ambiguous in any way. It cannot mean (–x)y.

I meant that is what math dictates it should be instead. Math doesn’t use **, and Swift prefers spacing for infix operators. -x**y isn’t “rightest” for either system.

Most of the computer languages mentioned have a small, finite set of operators, so each operator can play by its own rules. It’s easy for syntax tree parsers and easy for users. Swift on the other hand has an infinite amount of definable operators. For the sake of both syntax tree parsers and users, it seems better to me to have a consistent, extensible pattern that they all play by. We make an effort to distinguish = from the term operator precisely because it doesn’t follow that pattern.

But as long the solution doesn’t interfere with the rest of the operator repertoire, it doesn’t matter all that much to me what the decision ends up being. We are talking about an operator I will never use and a diagnostic I will never see.

I've created a toolchain to test out the proposed behavior:

https://github.com/apple/swift/pull/36074

I can't figure out how to get Xcode to stop displaying (without enforcing) diagnostics from the unrelated shipping toolchain, which causes lots of noisy errors that don't actually reflect the toolchain in the PR.

One issue which presents another wrinkle into the discussion is that Swift actually lexes the minus sign in front of a literal value as part of the literal, not as a prefix operator. So, with all of our discussions on @Joe_Groff's -2**4 example, Swift literally sees only one operator. (This is not an insurmountable problem, but it does require a bit of a fudge.)

3 Likes

I see the proposed associativity is right. That’s certainly better than left, but have we considered none?

From a clarity-when-reading standpoint, sequential exponentials are non-obvious without parentheses.

This expression is immediately clear and unambiguous:

4 ** (3 ** 2)

Whereas this one is easily misunderstood:

4 ** 3 ** 2

A right-associative precedence group accords with behavior in other commonly used languages; more likely is that people won’t be sure of the order of operations than that they would confidently misunderstand.

(Indeed, if even an operator with historical precedent as this does shouldn’t be right-associative, then it argues against any new or custom operator having right associativity.)

The issue with a non-associative operator with the additional rules above about prefix operators is that, if you’re chaining operators (which is where the non-associativity part comes in), things become quickly ridiculous:

((-x) ** ((-y) ** ((-z) ** a)))
// All mandatory parens

The ergonomics of this would be poorer than just pow, at which point, why bother?

1 Like

I guess you’re right, forcing people to use extra parentheses is not a good thing. We have to trust programmers to write code in a readable way.

That means associativity should be right, and it also means the rules for unary operators should stay exactly as they are.

We’re not going to stop people from writing ugly code, and we shouldn’t penalize people who are trying to write good code, in a futile attempt to prevent ugly code.

Heck, even if the code looks nice, that still doesn’t mean it behaves as it appears to. Sure, you and I both know what the caret operator ^ does, but someone new to programming could easily write things like this:

5^3 + 6^3 == 12^3       // true
(5^3) + (6^3) == (8^3)  // true

• • •

If we had some way for IDEs to display exponents as superscripts, then it would make sense to use postfix precedence for, eg, -xy.

But we don’t, and that’s not being proposed here. So let’s leave the rules for operators alone, and consider ** on its own merits within the existing design for Swift operators.

2 Likes

In practice, though, nested exponentiation is extremely uncommon. There's a few common integer sequences (Fermat numbers, Double Mersenne numbers, number of k-ary boolean functions, uh, probably a few more?) but in practice all of those are better expressed as a shift (or some other special mechanism). In 20+ years of working on numerical computation, I can count the number of times I've seen a nested exponential in code on one hand, and some parentheses really wouldn't have caused any problem.

7 Likes

+1 from me regardless of associativity. I've defined this a couple times myself so it would be nice to no longer have the need.

I don't doubt it! But since associativity only comes into play here when exponentiation is nested, only the nested exponentiation scenario comes into play within the context of discussing what associativity the operator should have; its relative rarity doesn't change the calculus.

My point here is, if exponentiation--which is right associative in many (all?) other programming languages in accordance with mathematical custom--can't be made right associative without being confusing in Swift, could there be any new operator that would pass that bar? Or is the argument essentially that we shouldn't allow right associative operators anymore, basically?

I'd be totally fine with that set of rules.

I think you misconstrue the issue about unary operators though: it isn't at all to do with "preventing ugly code" but preventing inadvertently incorrect code. The argument against allowing -2 ** 4 isn't that people will find it ugly (although you may), it's that people who find it perfectly beautiful will also vehemently disagree as to what this beautiful (to their eyes) expression means.

And they would be encountering this issue not out of general inexperience with programming (as may be the case for someone who misuses ^ as you write) but precisely because they are an experienced and polyglot programmer. That would be...unfortunate not to prevent if we could help it, all else being equal.

I do suggest you give the toolchain a try to get a sense of the user experience (to get a true sense of things as they will be once exponentiation is fully implemented, add your own func ** ... { return pow ... } with that toolchain): I think it's a workable model (particularly since it's been proven out in JavaScript) and preserves Swift's general design for operators.

1 Like

After really digging into Swift's (sometimes unstated) operator precedence rules, I think we can really put to rest any possibility of parsing -x**y as -(x**y) in Swift. There are several reasons, which I will collate together:

  1. Swift's hierarchy places unary operators above all binary operators; this is a considered decision based on precedent in other C family languages and users have voiced that they intuitively expect this behavior (already discussed extensively on this list).

  2. Even if we break with (1), Swift lexes a negative number literal as a single literal, not as an operator in front of a positive number literal. That is to say, making ** have higher precedence than prefix - would cause let x = 2; let y = -x**4 to behave differently from let y = -2**4, because no precedence rule expressed in Swift would change that -2 is lexed as a literal value. So, we would have to "fudge" how Swift lexes literal values for ** to make -2**4 equivalent to -(2**4), which seems...unprincipled.

  3. Even if we break with (1) and (2), Swift has special rules for operators such as as. For instance, 2 as Int ** 2 means (2 as Int) ** 2 and never 2 as (Int ** 2). Therefore, -2.0 ** 4 and -2.0 as Double ** 4 would behave differently from each other if we fix (1) and (2), which is a delightfully inexplicable result (because - is higher than as, which is higher than **, but - is lower than **). I don't think this has been brought up before here.

All of this is to say that it's not only the users, but also Swift's grammar itself in various ways, which assume that no binary operator has higher precedence than a unary operator. Actually implementing an operator that breaks those rules would have all sorts of knock-on effects that are hard to explain.

I do think that warning about such use though (as in JavaScript's model and as I've prototyped in the PR toolchain) is a workable model.

7 Likes

If the warning is restricted to only the case where there is no whitespace around the exponentiation operator, then I suppose this is tolerable.

“-x ** y” should never warn. It parses exactly as it looks.

“-x**y” could warn, I guess, but I’m not convinced it’s really worthwhile.