Juxtaposing unary operators

Evolution Discussion
1

Is there a reason why unary operators cannot be juxtaposed?

I just encountered this error:

prefix operator √
prefix func √ <T: FloatingPoint> (value: T) -> T {
  return value.squareRoot()
}

let x = -√2
// error: Unary operators must not be juxtaposed; parenthesize inner expression

There is no ambiguity here, since there is no “-√” operator. And when I create one:

prefix operator -√
prefix func -√ <T: FloatingPoint>(value: T) -> T {
  return -(√value)
}

let y = -√3
// success, no error even though both `-` and `√` operators exist

Then it works fine.

Should we consider allowing the juxtaposition of unary operators? I think the simple approach of “greedily take the longest operator possible, starting from the position of the argument” would be sufficient to preserve source compatibility.

2 Likes
2

I think it is for the sake of computational sanity. Even the complexity needed to resolve whether > is an operator or a generic argument list marker has been stated to be unfortunate.

You are correct, but the tokenizer cannot know this without information from much later phases of compilation, and full knowledge of all files in the module and all its dependencies.

The longer the operator stack gets the worse the problem becomes:

let x: Angle = ∡∛−√∑[6, 1, 8, 3]

We humans can all probably all tell what that is supposed to do: sum the array, find its square root, negate it, find its cube root and wrap it into an Angle type using radians. But if we ignore our understanding of what the symbols mean, there are 16 different ways to parse that into separate operators that the compiler would have to wade through:

let x: Angle = ∡∛−√∑[6, 1, 8, 3] // 5 (Compiler’s current understanding.)
let x: Angle = ∡∛−√(∑[6, 1, 8, 3]) // 4, 1
let x: Angle = ∡(∛−√∑[6, 1, 8, 3]) // 1, 4
let x: Angle = ∡∛−(√∑[6, 1, 8, 3]) // 3, 2
let x: Angle = ∡∛(−√∑[6, 1, 8, 3]) // 2, 3
let x: Angle = ∡∛−(√(∑[6, 1, 8, 3])) // 3, 1, 1
let x: Angle = ∡(∛−√(∑[6, 1, 8, 3])) // 1, 3, 1
let x: Angle = ∡(∛(−√∑[6, 1, 8, 3])) // 1, 1, 3
let x: Angle = ∡∛(−√(∑[6, 1, 8, 3])) // 2, 2, 1
let x: Angle = ∡∛(−(√∑[6, 1, 8, 3])) // 2, 1, 2
let x: Angle = ∡(∛−(√∑[6, 1, 8, 3])) // 1, 2, 2
let x: Angle = ∡∛(−(√(∑[6, 1, 8, 3]))) // 2, 1, 1, 1
let x: Angle = ∡(∛−(√(∑[6, 1, 8, 3]))) // 1, 2, 1, 1
let x: Angle = ∡(∛(−√(∑[6, 1, 8, 3]))) // 1, 1, 2, 1
let x: Angle = ∡(∛(−(√∑[6, 1, 8, 3]))) // 1, 1, 1, 2
let x: Angle = ∡(∛(−(√(∑[6, 1, 8, 3])))) // 1, 1, 1, 1, 1 (What we meant.)

And every one of those combinations must also be run through type inference.

Thus the current rule...

error: Unary operators must not be juxtaposed [...]

...and the compiler’s advice...

[...] parenthesize inner expression

...which allow you to explicitly have used any of the above combinations were it really what you wanted, while keeping everything manageable for the tokenizer.

4 Likes
3

P.S. I do like your unified alias:

prefix operator -√
prefix func -√ <T: FloatingPoint>(value: T) -> T {
  return -(√value)
}

let y = -√3

It makes for a pretty clever readability improvement.

4

Do I understand then that you are supportive of the idea in principle, but wary of implementation complexity and/or compiler performance?

• • •

I don’t know how the tokenizer currently operates, but if I had to implement something to handle this, I would probably make a “prefix operator token” which represents a string of source characters that specify one-or-more prefix operators.

In your example, the token would be “∡∛−√∑”.

Then at a later stage, once all operator declarations have been found, any prefix operator tokens with more than 1 character can be greedily decomposed into a series of prefix operators.

In your example, this process would look at, in order, these strings:

∡∛−√∑
∛−√∑
−√∑
√∑
∑

As soon as it finds a valid prefix operator declaration, it stops (this is the greedy part). Presumably the first 4 lines are not valid operators, so it finds that ∑ must be the first operator.

The same process is applied to ∡∛−√ and presumably the first valid operator found there is “√”, and so forth. Thus the greedy decomposition yields, in order:

[∑, √, −, ∛, ∡]

During type-checking, the candidate functions for these operators can be evaluated in the standard way.

5

Be careful here, for each of the "greedy choice" you still need to parse the rest of the symbols, the "greedy choice" just setup the precedence among feasible solutions. It doesn't reduce the number of combinations you need to investigate in the worst case scenario. If the only feasible solution consists solely of single-character operator (worst case for this particular greedy algorithm), you'll still need to explore all possible cases (all outlined by @SDGGiesbrecht).

It would also easily lead to regression for multi-character unary operator.

6

But you don’t have to type-check them all. You only have to type-check one single sequence of operators, namely the sequence found by greedily matching the longest operator declaration possible.

No, it would not be a regression.

Today, the only valid sequence of multiple operator characters in prefix position, is a single prefix operator with a multi-character name. In other words, the operator matches the full string (because juxtaposition is currently disallowed).

With the greedy approach, matching the full string is the first thing that is attempted. If it succeeds, then the process stops and no other possibilities are checked, because the longest one has already been found. That is what “greedy approach” means.

Thus, in the case of currently-valid code, there is no additional overhead.

7

You still need to make sure that that sequence of operators form a coherent nesting of types, and if it does not, clean up and check the next match, no?

8

No, you would do that once, later on, during the type-checking phase, for the one specific sequence of operator names found by the greedy approach.

If it turns out that the sequence of operator names found by the greedy approach does not have a consistent set of implementing functions where the types line up, then type-checking fails for that expression. This scenario produces a type-checking error just like any other.

9

Hmm, I see.

In any case, it's gonna be quite an undertaking, since you're using knowledge of the declarations to construct (transform?) AST, and I'm not sure it's worth the effort. IIRC the status quo has been keeping them nicely separated.

10

Well, again, I am not an expert on the compiler implementation. I was just spitballing one possible approach that came to mind.

I moreso wanted to broach the idea of allowing juxtaposed unary operators, and see what thoughts other people might have on the subject.

11

Yes. Although I hadn’t thought about it that way when I posted. I hadn’t even noticed it was in the evolution category. I was only hypothesizing about the answer to your question:

Ultimately, if implemented, it would be the first case of something not expressible in the Backhus‐Naur‐like grammar, since it relies on the semantics of external declarations (even if that part is delayed until a later phase of compilation by leaving it as a single stand‐in token to start with).

Then adding a new operator could break both the tokenization and/or type checking of existing expressions whose operators happen to be subsequences. ----x would be four negations until you restore C‐style -- as a custom operator, after which it would be two decrements and possibly a compiler complaint about mutability. (But I concede the example is contrived.)

12

That would be brittle. Suppose library A has defined prefix operators <- and >, and that <->x type checks correctly. Suppose then library B defines a totally unrelated prefix operator -> that operates on values of totally different types. The original expression would stop compiling—even though library A and B deal with totally distinct concerns and do not vend duplicative and therefore clashing operators.

Consider also this issue: suppose library A and library B vend the operators above (and prefix operator <), but an expression is written that will typecheck either way. Suppose it is in a project which conditionally imports library B. Now we have a silent difference in behavior that will be a doozy to debug.

We should keep in mind that code has to be read by humans too. Operators can be hard to understand for a human as it is: introducing new rules like this, where how to interpret an expression requires knowing the complete set of declared operators, would make it even harder.

13

Parsing expressions in Swift is already somewhat complicated due to the ability to declare custom operators. For example, when the compiler sees a sequence of term binop term binop ... term during syntax parsing, it can't encode the precedence/associativity into the tree yet because it doesn't know what the operators are actually defined as (it hasn't loaded any modules). So all the parser gives back is a "sequence" of alternating terms and binary operators. Later, once modules have been loaded, these flat sequences are folded into an AST based on the precedence/associativity information that is now known.

But even in those cases, the compiler knows that when it sees a sequence of operator characters between two terms, the entire sequence is the whole binary operator. Juxtaposed unary operators wouldn't be able to parse the same way—the only thing the parser could return is "here are characters that make up some sequence of unary operators", and the folding algorithm would need to use the available unary operators to determine where to partition that string and fold it into expression subtrees.

I think that's probably not that hard of a problem to solve from a technical standpoint, but I agree with @xwu above that the opportunity for introducing brittleness would be too great. There are already issues based on the fact that custom operators aren't really scoped to their declaring module (if two modules define an operator with different precedence/associativity and you import both modules and try to use the operator, it's an error), but at least when dealing with that in the case of a single operator, the problem is localized. Juxtaposition of operators would allow the same sequence of characters to resolve as different operators depending on which modules were loaded, which would be harder for the compiler to diagnose.

It would also make writing syntax-based tools more difficult, since they would only be able to see the original sequence of unary op characters and not be able to resolve them unless they replicated the compiler's folding algorithm using external context (like swift-format recently did for binary operators, by hardcoding the stdlib operators).

2 Likes
14

Just MHO, but I'm pretty sure that this could be implemented in a reasonable way. The lexer would lex them as a single prefix (or postfix) operator and a single AST node would be created by the parser. When semantic analysis comes around to do name lookup, it could turn the +-(x) expression into two AST nodes to express +(-(x) if that were the thing that worked. As others have said, you could diagnose ambiguity etc.

The major question to me is whether or not this is a good thing in practice:

  1. I agree with @xwu's points about potential brittleness here when importing new libraries, though perhaps that could be handled by diagnosing ambiguous cases instead of picking a winner.

  2. If we did this, then people would start asking for disambiguation between binary and unary operators as well. For example, isn't it "terrible" that Swift doesn't allow you to move an integer with the speed bump operator (e.g. x-=-1) like C does? :-)

-Chris

3 Likes