Exponentiation operator and precedence group

Hi friends!

We have talked about exponentiation before, but the lack of an exponentiation operator that some users expect to exist has apparently been causing head-scratching diagnostics. After some discussion, it's apparent to me that one of the best ways to diagnose this specifically when operands of suitable type are used is to make a placeholder function. As that would end up actually adding an operator to the standard library, requiring Evolution approval, this gives us occasion to confirm the desire spelling of that operator and its precedence group.

I hope the pitch is...uncontroversial:


Exponentiation operator and precedence group

Introduction

We propose the addition of ** as the exponentiation operator, assigned to a precedence group named ExponentiationPrecedence that is higher than MultiplicationPrecedence.

Swift-evolution thread: [this one]

Motivation

Exponentiation facilities are currently available in Swift by importing the C standard library (via Darwin on Apple platforms or Glibc on Linux, or via Foundation). Additionally, protocol-based additions to floating-point types were proposed for addition to the standard library in SE-246, which is currently available as a separate library, Swift Numerics. As in C, all of these functions are named pow.

In many other programming languages, exponentiation is denoted by the operator ^ or **. Currently, no such operator exists in the Swift standard library, although its inclusion has long been discussed. With SE-77, the exponentiation precedence group to which bitwise shift operators belong was renamed BitwiseShiftPrecedence, anticipating a bifurcation in the operator hierarchy where true exponentiation is assigned its own precedence group higher than multiplication but unordered relative to bitwise shift operators.

Pending incorporation of exponentiation into the standard library, anecdotal evidence suggests sufficient attempts to use the ** operator which could justify the addition of a customized diagnostic.

What's required to provide such a tailored diagnostic that will guide users to the correct spelling pow is either (a) a hardcoded compiler routine; or (b) an unavailable, shadowable placeholder func ** in the standard library with the message: "use 'Foundation.pow' instead". The latter option has advantages in allowing the fullest set of diagnostics to be emitted for the rest of the expression in question because the operator itself would exist; however, such an operator would need to be assigned to some precedence group, either a definitive one or a magical placeholder.

Proposed solution

We propose to settle the spelling, precedence, associativity of the exponentiation operator in this proposal. The addition of actual exponentiation facilities is covered by SE-246, and is deliberately left out of the scope of this proposal.

Settling the spelling of the operator facilitates not only superior diagnostics pending the addition of exponentiation to the standard library itself, but it also permits third-party libraries to vend implementations of the operator without each having to define the operator or its precedence group, which could lead to clashes with one another if a user imports more than one mathematical library with such definitions.

Detailed design

We propose to use the spelling **, which is one of the two well-precedented spellings of this operator. The choice is made rather simple as we cannot repurpose the other well-precedented spelling, ^, since it is already a standard library operator (for a bitwise operation) which is assigned a precedence not suitable for exponentiation.

We propose that the precedence group to which ** will be assigned should be spelled ExponentiationPrecedence, in line with the spelling of MultiplicationPrecedence and AdditionPrecedence.

ExponentiationPrecedence would be higher-than MultiplicationPrecedence, as users expect based on mathematical tradition. Further, based on mathematical tradition and as precedented in other languages, ExponentiationPrecedence would be right-associative, so that x ** y ** z is equivalent to x ** (y ** z) and not (x ** y) ** z.

Note that this design fulfills the promise of SE-77 in permitting ExponentiationPrecedence to be deliberately unordered relative to BitwiseShiftPrecedence; this allows Swift to require parentheses in the rare cirumstance that bitwise shift operators are used adjacent to exponentiation operators.

By analogy with other mathematical assignment operators, we would also add the exponentiation assignment operator **= with AssignmentPrecedence.

Source compatibility

As Swift permits end users to shadow standard library operator declarations and even to assign them to custom precedence groups, this proposal will not affect source compatibility.

Effect on ABI stability

This proposal is intended to have no implications for ABI stability. Any placeholder func ** will be annotated as unavailable and emitted into clients, so that they have no ABI footprint.

Effect on API resilience

This proposal introduces an operator and its assigned precedence group as public API. By taking these changes through the Evolution process now, we ensure that a precedence group and operator appropriate for actual use are in place which will not need to be removed in the future as mathematical facilities in the standard library are filled out. Library authors benefit in being able to define implementations of this operator without having to vend potentially clashing operator definitions.

Alternatives considered

One alternative is not to add these operators at this point in time, leaving diagnostics to be implemented solely in the compiler. We feel that the design here offers a superior outcome in terms of diagnostic quality with a minimal addition of code, with the principal drawback that it requires the Swift community to expend effort in reviewing the proposed operator now rather than later. However, as the intention is to settle a permanent spelling for exponentiation, the effort is not wasted for a merely ephemeral change.

Acknowledgments

Thanks to @varungandhi-apple for thoughtful discussion on possibilities for improving exponentiation operator diagnostics.

17 Likes

It's a strange pitch really. You want to introduce a dummy exponentiation operator that doesn't work in order to provide a better diagnostic when people are trying to use the exponentiation operator.

When I read the title I imagine an exponentiation operator is going to be added, and starting from that idea I have to read carefully to realize it's going to be a fake one that can't do anything. I think this needs to be clearer in the proposal.

It'd also be nice to elaborate a bit about why leaving it unimplemented makes sense. If it's telling me to call pow, the question will be why it's not doing the obvious by calling pow itself.

4 Likes

Both the operator and its precedence group would be the real deal, and the proposal here is to add them; there is nothing temporary or fake about them. That is why Swift Evolution is required in the first place.

Any functions that are named ** are not a part of this proposal. Such functions fall into three categories:

  1. I do intend to roll in some placeholder functions for diagnostic purposes, but while they motivate this proposal, they are not a part of the proposal because no working API is exposed.

  2. Actual, working exponentiation functions are not a part of this proposal because they are already a part of SE-246, which is approved and exists in the form of Swift Numerics. Since these functions are not yet a part of the standard library, we cannot add implementations of ** to the standard library that call them.

  3. Third parties will (or already do) want to vend **. This proposal provides the necessary declarations so that Foundation can vend an implementation that calls its own pow if it so wishes, and Swift Numerics or third-party users can vend an implementation that calls their own pow, all without stepping on each other's toes by having to vend duplicative operator declarations. (It's kind of the same rationale as one of those for adopting Result in the standard library, so that multiple libraries don't have their own similar but duplicative Result types that step on each other's toes.) Foundation and Swift Numerics are loosely-inspired-by-but-not-really-subject-to Swift Evolution, so what they do is not really within the scope of our discussion. [Edit: Implied here is that, if @scanon will let me, I will add them to Swift Numerics once this proposal is accepted.]

So to clarify, this proposal is about the addition of the real, actual exponentiation operator and its precedence group, not a mock-up or placeholder. It is necessarily constrained to those parts of that task which are (a) subject to Swift Evolution; (b) not yet approved already; (c) implementable.

The intention is that no more Swift Evolution proposals are necessary after this one on the topic, excepting whatever the core team decides is necessary before migrating chunks of Swift Numerics into the standard library.

One alternative is to simply wait until those parts of Swift Numerics are migrated to the standard library; however, the work required to make the exponentiation operator a reality would be the same whether we do it now or later, and as the proposal argues, doing it now has the added bonus that we get better diagnostics while we wait [edit: and, potentially, a chance to try it out in Swift Numerics while we wait]. In light of that reasoning, I pitch this now because it is strictly an improvement over pitching it later.

11 Likes

This looks good to me.

Sounds sensible. However, just like @michelf I think this is a bit hard to grok if you don’t have the history of SE-246 fresh in mind. Whatever you can do to clarify in the text what’s being added when and where and why would be good.

Do I understand it correctly that the placeholder func ** in the stdlib can’t call the existing pow because the existing pow is in Darwin/Glibc/Foundation, and they’re ”above” the stdlib? So it’s not just that we want to wait for SE-246 to get merged because it’s already been accepted – we have to wait for it.

1 Like

Thanks—yes, I’ll flesh out this portion of the text to give sufficient context.

:+1:

1 Like

Do I understand it correctly that the placeholder func ** in the stdlib can’t call the existing pow because the existing pow is in Darwin / Glibc / Foundation , and they’re ”above” the stdlib?

This is not quite right; an exponentiation operator in the stdlib couldn't call pow from Darwin/Glibc, but it can still be backed by the math library pow function (we already do this for remainder, truncatingRemainder, addingProduct, and a few other operations). So adding this operation would not necessarily be blocked on landing ElementaryFunctions into mainline Swift.

However, it's worth noting that ElementaryFunctions has two different exponentiation functions; one with signature (T, T) -> T and one with (T, Int) -> T. The first is defined mathematically by exp(b * log a), the second is defined by repeated multiplication. The two definitions agree most of the time (which is why people tend to conflate them), but they are not actually the same function; they differ for a <= 0. If we were going to add an implementation in the standard library, we'd have to also pick which one (or both) we were going to implement (and we'd need to have the discussion about whether to provide the operator for integer types as well).

4 Likes

Correctly implementing an exponentiation operator that behaves consistently with ** in other languages requires changing the grammar, because -2**4 is -(2**4):

Python 2.7.16 (default, Dec  6 2020, 22:22:32) 
[GCC Apple LLVM 12.0.0 (clang-1200.0.30.4)
Type "help", "copyright", "credits" or "license" for more information.
>>> -2**4
-16

This means ** has to be parsed as a postfix expression with an operand. We'd need to figure out how to make that work within Swift's library-driven operator grammar—can other infix operators have postfix precedence? Are any of them able to bind tighter than exponentiation? The answers seem easier if the answer to those questions is "no", but I'm not sure what other languages do.

7 Likes

Mmm, that’s a wrinkle I wasn’t aware of. I guess technically prefix - has the wrong precedence relative to infix * as well, but it’s not a problem because -(x*y) == (-x)*y?

2 Likes

Linking to a very old discussion wherein I say "this is rare enough that it's not worth adding a special rule for": Proposal: Adding precedence option for prefix and postfix operators

2 Likes

Precedent from other languages like C seems like it's established (-x) * y as the way this parses in computer land too. The other languages I know of with ** operators all seem like they parse it as -(x**y) though.

1 Like

Right. Fortran (and languages that derive from it) give prefix - the same precedence as the binary - operator. Matlab and Octave and Julia give them different precedence, but give ^ greater precedence than prefix -. Languages that derive from C give all prefix operators higher precedence than all binary operators.

2 Likes

dear @Joe_Groff and @xwu and others, what about ^^ instead of ** ?

e.g 2^^4 = 16

I’m not sure I see the advantage of using a notation that’s less commonly used elsewhere; users look for ** even when it doesn’t exist yet, which is a good sign that it’s the more expected spelling.

Moreover, by analogy with & and &&, and | and ||, users may expect ^ and ^^ to be related in the same way. There is no such ambiguity with **.

1 Like

D uses ^^ so there is a precedent. But otherwise I think ** is a better choice because it is more common and, as @xnu mentioned, it isn't ambiguous with a hypothetical logical xor.

1 Like

This is interesting: among common languages that use **, JavaScript has opted to do something unique to square its C family heritage with mathematical convention:

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

I wonder if a reasonable thing to do here is to provide some way of making ** unordered relative to prefix operators.

When an infix operator doesn't use whitespace, and its first operand is prefixed but not parenthesized, could there be a compiler warning?

-2**4    // warning?
-2 ** 4  // OK
(-2)**4  // OK
-(2**4)  // OK

Whitespace or parentheses are already required, when the second operand is prefixed.

2**-4    // error: Missing whitespace between '**' and '-' operators
2 ** -4  // OK
2**(-4)  // OK

Ranges could be a special case, but partial ranges already need parenthesized operands.

-2...4   // warning or special case?
-2...    // error: Unary operator '-' cannot be applied to
         //        an operand of type 'PartialRangeFrom<Int>'
...-4    // error: Unary operators must not be juxtaposed;
         //        parenthesize inner expression

If we could give all range operators the same lower precedence, that might solve some issues.

postfix operator ... : RangeFormationPrecedence
prefix operator ... : RangeFormationPrecedence
prefix operator ..< : RangeFormationPrecedence
infix operator ... : RangeFormationPrecedence
infix operator ..< : RangeFormationPrecedence

But I don't think we would want to change the precedence of any other postfix or prefix operators.

1 Like

Changing existing precedence groups or inventing new one-off exceptions risks knock-on effects because all current precedence groups are ordered relative to each other. For the purposes of this proposal, it’s simply not necessary. No one has been harmed by the need to clarify order of operations with parens.

I’d strongly prefer formulating this in terms of rules that can be applied while observing general design principles already laid down, namely that (a) unary operator precedence is not less than any infix operator precedence; (b) the presence of absence of symmetric whitespace does not change the behavior of an infix operator, modulo any whitespace that causes two operators to crash into one another to form a single operator.

I will propose a principled addition to precedence groups that can be applied for the exponentiation precedence and is potentially generalizable.

2 Likes

If we choose to implement ** as an actual exponentiation operator, I think there's an unavoidable, long-term disaster whichever meaning it has (either in terms of precedence, or pow-equivalent semantics).

There will be, I believe, large numbers of Swift programmers who will assume they know what the meaning of "exponentiation" is, depending on what prior experience they have. Whatever the actual meaning is, many of these programmers will be wrong and therefore start writing buggy code, which it may not be trivial to debug.

I'd suggest there are only two rational ways to proceed here:

  1. Agree to never implement an infix exponentiation operator in Swift. The placeholder ** operator would exist as a source of diagnostics, and possibly fix-its pointing at math functions, but since it would never do anything there'd be no reason to resolve the precedence issues.

  2. Force the use of parentheses always to disambiguate expression with unary - and infix ** operators. This sounds ugly, but the ambiguity of unparenthesized expressions is far worse.

For #2, what I had in mind was adding some way to Swift to declare that pairs of operators were non-comparable in precedence. I'm guessing this would be straightforward to implement within expression parsing, and would lead directly to fix-its suggesting both parenthesizations as alternatives.

1 Like

As I comment above, that's precisely what JavaScript does, and it seems a very elegant solution. I will comment on some ideas as to how to achieve this within Swift's current operator precedence design shortly (I think there's a minimally invasive but reusable (i.e., not ad hoc) solution).

1 Like