Improved operator lookup semantics

Hi @rudkx,

I just saw this thread. I too have had the idea of looking up operators on the metatype of the result, and I think this idea has promise. But before we get to that, I think your proposal would benefit from the following first:

  1. It would be really helpful if we could agree on why operators have nonlinear type checking performance before we discuss potential solutions.
  2. It would be really helpful if we could agree on when operators should be used instead of normal functions and vice versa. This might simplify the problem space before in ways that don't require changes to operator lookup.

When it comes to operators, I'm reminded of a previous senior executive at Apple that used to argue during API review that "simple things should be simple, and complex things should be possible".

I think when it comes to operators and nonlinear type checking behavior, the fundamental mistake we made was for allowing heterogenous parameters/result types. In other words, if we required that the type of the parameters and the return type all be the same, then we could quickly converge on a solution, and the LHS type, if it known, would naturally speed the convergence.

Yes, this would mean that clever programmers might sometimes need to use normal functions instead of operators, but I think that is the right tradeoff, and the net result is a simpler language model.

Dave

2 Likes

Except that e.g. Strideable has + (Self, Self.Stride) -> Self which should still be valid. In addition, I would also like for e.g. PointProtocol with - (Self, Self) -> Self.Stride (or Self.Vector) and <T: Numeric> - (rhs: T) -> Negative<T> to still be valid.

We already require that type-defined operators use their surrounding type at least once in their signature, which would probably be more than some functional style programmers would care for, if we didn't permit non-type-defined operators to be arbitrary functions.

Also, without operators capable of returning arbitrary results, it may be impossible to construct an n-ary operator by chaining binary operators together.

Hi @Dante-Broggi,

I agree that the C-ish/pointer-arithmetic-like style is convenient and addictive. It's also not essential. My fundamental point is still the same: we should acknowledge the tradeoffs instead of letting it be implied from the discussion. :-)

Dave

I would not categorize that as a “mistake”. Mixed-type operators are important.

Multiplying a vector by a scalar (on either side) is properly represented by the “*” operator. The same goes for matrix-times-vector, scalar-times-matrix, and so forth (eg. with tensors).

7 Likes

We already have heterogeneous comparison and bit shift operators, so the notion of getting rid of heterogeneous operators is quite clearly a non-starter.

4 Likes

Here are some of the contributing factors, in no particular order:

  • We allow functions to be overloaded by type, instead e.g. of forcing different function names or different argument labels for functions with differently typed arguments and return values (e.g. imagine + for Int, +. for Double, ++ for String, etc.)
  • Overloading combined with the current lookup strategy results in many functions in the overload set of some operators (IIRC the < operator had the most operator overloads last time I looked, at something like ~60 variants just in the standard library)
  • The types of literals are inferred based on context, and that context can be several operations away in an expression, and the types they can be inferred to are infinite due to the ExpressibleBy*Literal mechanism.
  • The generics system places no restrictions on how operations can be combined, e.g. you can have the result of calling a function that has the type <T: Foo>(T, T) -> T be the argument of a function that has the type <U: Bar>(U, U) -> U
  • We cannot, at each point in expression evaluation, choose a single best overload as the winner; and in fact many expressions type check multiple ways, requiring a relatively complex "scoring" system and then "ranking" system to kick in and pick a winner

Generics are especially problematic because they result in our not being able to "fail fast" when attempting a particular overload in the same way that we could if we have a value of known type being passed as an argument to a function with a non-generic-typed argument. It's easy to tell that you cannot pass an Int where a Float is expected, and bail out of the intermediate solution involving the overload that takes a Float. You cannot do that if you're passing 1 to a function expecting T: Foo, because there may be some T somewhere that conforms to Foo and ExpressibleByIntegerLiteral, and similarly if you're passing a T: Foo where a U: Bar is expected, because there may be a type that conforms to both and works.

That might be an interesting discussion to have for what we want to put into the standard library, but we cannot control what other users do. We could provide some guidance, but that's not going to stop someone from adding many new operators with many new overloads. We also have a strong emphasis on source compatibility at this point, so we cannot easily revise the standard library to rename operators for different purposes or remove some of the overloads.

This certainly doesn't help if only because it leads to more overloads, but I don't think this is the biggest issue we have. Overloading by return type is definitely problematic since if any of the overloads that take the same argument types work for a particular step in solving, the others will work as well, so you at least need to explore each of those options one additional step.

2 Likes

Hi Mark,

I have many questions.

a) This wouldn't be changing the semantics of the language, right? It's just a strategy change.

b) How much of this algorithm can be cached for subsequent runs?

Maybe it doesn't matter that the type checker is non-linear (like, cubic for example) on the first run, as long as it can "cache" some of its knowledge for later runs. Later runs would have access to the information that the last run discovered, thus hopefully getting a kickstart on their own type checking process.

Of course this cache would need to be invalidated if the program changes drastically enough. But I think this could be done easily (famous last words) by feeding every cached bit to the type checker one by one as if they were a node value assignment in the regular type checking process. The algorithm naturally backtracks whenever it makes an assignment that leads to no solutions, so this would never produce an invalid positive result or anything like that (i.e. the cache is always invalidated if it should be).

c) Maybe type-checking can be done incrementally on a daemon process? While the user is working on their source code, the type checker could be running and trying to come up with good general conclusions s.t. it doesn't need to start from scratch. Then it wouldn't be such a long part of the compilation process.


My last question is about the algorithm itself and not related to this topic.

This ranking you're talking about here is one of the following?

  • A ranking for optimization, i.e., one that tries to pick the "best" type checked program under some criteria of simplicity or memory layout.
  • A ranking for backtracking, i.e. a node ordering strategy that tries to pick the "best" next type assignment x type value to explore in order to make the type checking step faster.

It would change the semantics. This is kind of hidden in the proposal, because the source compatibility part hasn't been written yet, but there is one example in there of where the semantics would change. In general, there's probably a way to address this in the general case without changing semantics (perhaps this is a scenario where the no free lunch theorem applies) and type-checking is currently NP-complete, though you can perhaps make improvements for commonly-used expressions.

I think the answer is neither. It's a ranking to choose the “best” of multiple valid solutions, according to the various disambiguation rules (some old documentation about this here).

1 Like

I would consider it a semantic change if things that type checked one way before this change could type check a different way (or not at all) after this change. I don't see a way around potentially type checking things differently. Depending on how we define the fallback behavior, it may or may not result in things that previously type checked no longer doing so.

I think it would be difficult to come up with a way to effectively cache anything useful. Although expression type checking only happens within a single expression, it relies on global information about the types involved, the protocols they conform to, etc.

The problem is that we really can be exponential in some cases. If you remove some hacks that we have, we're exponential in even more cases.

No, what I'm referring to when I mention the "scoring" system and "ranking" system are two pieces of the expression type checker algorithm. The scoring system keeps track of things like whether we've had to "inject" values into optionals as part of passing a parameter or returning a value, whether we needed to perform a function conversion for a closure, whether we needed to force an IUO, etc. It attempts to back out of partial solutions on-the-fly if the solution so far is worse than the best complete solution we've found.

The ranking system is implemented in CSRanking.cpp, and looks at all the solutions we find, compares them, and picks the best one based on the criteria it is using (which often boils down to comparing overloads to find the most specialized).

1 Like

Thanks for answering to my questions :slight_smile:

I don't think changing the semantics is too bad, as long as the justification for why now-failing-to-type-check expressions are not allowed now (e.g. brittle or ambiguous meaning). If this changes things that are "on the edge" of being considered correct right now, then it might be actually better with this change.

And what about large codebases? There has to be a line count for which this might be effective... right? I'm thinking about the StdLib, the Vapor framework, things like that.

Yeah... I've heard of those hacks. CSP solving is of course exponential, as @jawbroken pointed out (checking it is polynomial).

Isn't there some sort of incremental algorithm that we're missing? I dunno, something that allows us to lift some work from the compilation-time type checking step, doing it beforehand (I might be repeating myself here, if so, I'm sorry).

Ahh, I get it then. So the scoring prunes partial solutions, and the ranking compares found solutions. I imagine the scoring system does a ton of the speedup against a more naive approach. Any time I've worked with pruning in CSP it reduces the running time by orders of magnitude <3

Hi @rudkx,

Thank you for the thorough reply. It was really helpful.

As much as I like the idea of looking up operators in the metatype of the LHS, I worry that we'd just be substituting one performance problem for another. For example, the comparison operators would force Bool to have a lot of extensions on it. Is this a fair worry? Or is there something I'm missing?

Thanks,
Dave

I'm not sure if you're referring to my pitch, or @jrose's suggestion of using the type context as the scope for lookup.

In my pitch, I'm talking about doing lookup in the metatype of the operand that matches the associativity of the operator. @xwu suggested that it made more sense to just use the left operand, and I don't recall why I had originally thought it should be based on the associativity (I wrote the first draft of this in early March), and agree that for many examples it makes more sense to just use the left operand's type, so I plan on revising the pitch to specify that.

So in the newly revised pitch, something like:

  let i: Int = ...
  let j: Int = ...
  if i < j { ... }

would find the < by looking in Int, not Bool.

If you're arguing for finer grained-dependency tracking and less recomputation of information during compilation, then yes, on a broad scale we should be doing more of that in the compiler.

Does it make sense for expression type checking?

For most code we see expression type checking is not a bottleneck. The overhead of fine-grained dependency tracking and the associated bookkeeping may very well turn out to be expensive enough that it would completely negate, and even overwhelm, any benefit.

As one example, consider that this silly example takes about 2ms to typecheck:

let _ = (i * 1) + (i / 2) + (i % 3) + (i << 4)

As another example, I think someone recently mentioned to me that expression type checking currently takes nine seconds for the entire standard library build.

Interesting. Does the lookup need to happen on the lefthand side, or could it be looked up in both sides and diagnosed as an ambiguity if there is a conflict? By allowing either the lefthand or righthand sides, the common "1 / x" and "1 << y" cases would be handled directly, rather than via literal special logic.

To be clear, my suggestion wasn't to always look up operators in the result type, but only when the left-hand (or only) argument was a literal. I knew that this would break let x = 1.0; let y = 1 + x, but I thought that Mark's protocol-based idea would have the same problem, and it doesn't.

My idea could be moved to something more complicated like "if-and-only-if the left-hand argument is a literal, look at the right-hand argument instead; if both are literals, look at the result type", but now it's hard to explain and harder to implement, and probably would produce more unpredictable results.

I still don't like the protocols, though; at that point I'd rather just stick the fallback signature in the operator or precedencegroup and be done with it:

precedencegroup AdditionPrecedence {
  associativity: left
  higherThan: RangeFormationPrecedence
  defaultSignature: (Self, Self) -> Self
}

It's not like type-checking can actually produce a dynamic call through the protocol function. It's just using it as a template to describe which types are related.

If we want to maintain the full expressibility we have today (and remain as compatible as possible), we need more than just expressing a default signature. We also need this in order to ensure that we do not admit expressions that should not type check successfully. As a side note, there are no precedencegroup declarations for unary operators.

From the proposal:

Note that the type Float below does not conform to IntegerOperations, despite being ExpressibleByIntegerLiteral and despite the ability of expressions to begin with integer literals that are inferred to have floating-point type. This is an important detail which ensures that we will correctly reject an expression like 1 & x where x is of type Float.

public protocol BitwiseShiftProtocol {
  func << <T: BinaryInteger> (value: Self, amount: T) -> Self
}

infix operator  << : BitwiseShiftPrecedence, BitwiseShiftProtocol

public protocol BitwiseAndOrXorProtocol {
  func & (lhs: Self, rhs: Self) -> Self
  func | (lhs: Self, rhs: Self) -> Self
  func ^ (lhs: Self, rhs: Self) -> Self
}

infix operator   & : MultiplicationPrecedence, BitwiseAndOrXorProtocol
infix operator   | : AdditionPrecedence, BitwiseAndOrXorProtocol
infix operator   ^ : AdditionPrecedence, BitwiseAndOrXorProtocol

public protocol IntegerOperations : ExpressibleByIntegerLiteral, BitwiseShiftProtocol, BitwiseAndOrXorProtocol {
}

extension UInt : IntegerOperations {
  public func << <T: BinaryInteger> (value: UInt, amount: T) -> UInt
  public func & (lhs: UInt, rhs: UInt) -> UInt
  public func | (lhs: UInt, rhs: UInt) -> UInt
  public func ^ (lhs: UInt, rhs: UInt) -> UInt
}

My imagined implementation of this pitch would take a literal that leads a subexpression (e.g. 1 + x) and create a type variable that conforms to the associated ExpressibleBy*Literal as well as the "leading literal" protocol associated with the operator. The resulting expression would in fact have a dynamic call through the protocol witness, although we will eventually devirtualize this based on the final type we select (we do this even at -Onone today).

My original thought process for the pitch was that we would simply desugar infix expressions to member expressions after extending the language to allow instance member operators. The reasons I kept the notion of only looking in one place for operators after reworking the pitch to be one about how we perform operator lookups are:

  • It minimizes the risk of finding more operator overloads than may have been intended by the designer of the type(s) involved
  • It's easy to reason about and easy to teach (although these protocols for literals add slightly more to teach)

I'm not sure what you mean by "conflict" in this context, but in general we need to be able to support multiple overloads for different combinations of types, and we also currently allow operators that are generic on one of the operands (like <<), and it's reasonable to support multiple generic overloads of those operators found in both the left and right operands.

I'm sorry, but I feel compelled to point out that this is a choice that was made (and could be unmade!), it is not something inherent in the current design of Swift. This is trivially solvable by introducing a new protocol LessThanAble with a single requirement, and folding all of the implementations of < into conformances to that type, so we end up with exactly 1 operator implementation in the stdlib. Synthesized comparable conformances would be updated to do the right thing for the new design.

Doing so has several natural consequences:

  1. You'd have exactly one implementation of the operator, eliminating all the disjunctions from the (stdlib versions of) this operator, and the exponential compile-time behavior that comes from that.
  2. That implementation would enforce the "invariant" that we want from < that it is a (T,T)->Bool operation.
  3. Compile time would be much faster for users everywhere, even if they define a few of their own overloads. Definitely if they have lots of types with synthesized comparables and they are upgraded to the new approach.
  4. You'd likely get much faster incremental builds by having looser coupling between operator lookups across translation units.
  5. No changes to the swift language would be required, and AFAIK, there would be no source breakage from doing thing change to the stdlib.

In practice, literally naming this LessThanAble would be silly. You'd want to define this as something related to comparable, scope in the other comparison operators, and use conditional conformances.

So, why haven't we done this so far? Somewhere along the way, people started claiming that protocols are "not just bags of syntax". That's true insofar as it doesn't cause widespread exponential compile-time behavior in user code -- but the current design does. Beyond that, it turns out that operators aren't "bags of syntax" either. We don't want people to overload operators unless they have substantially the same behavior as the existing operators with the same spelling. Tying these together into unifying protocols with a good name seems like a reasonable and super desirable thing to do.

I think that lack of conditional conformances was perhaps the biggest reason we haven't pursued this path in the past, but now that that is done, I don't see why we wouldn't do it for Swift 5. Have you considered this direction?

-Chris

2 Likes

This was (in broad strokes) the original design for floating-point types, with operators as extension methods that called protocol requirements spelled isLess(than:), etc. It would seem that, as you state, adhering to this design would obviate many difficulties.

However, from my recollection, we abandoned this direction for at least two reasons, neither of which are specifically to avoid "bags of syntax." Rather, the first was that it was felt that this design was inelegant in that it requires us to come up with canonical names such as isLessThanOrEqualTo(_:) to correspond to each operator. Second, IIUC, it was felt that operators-as-static-methods would solve some of the same issues with overloading operators, although evidently they have not addressed these issues as thoroughly as one would have liked.

If we do go down this path, though, I do share @jrose's opinion that the protocols presented here aren't great. As you say, these operators aren't meant to be just bags of syntax, and they can properly be rolled into the design of Equatable, Comparable, Numeric, etc.

I'd like to get some clarification of what exactly you mean here before responding to the rest of your reply. It's not clear to me if you mean something like:

protocol LessThanAble { 
  static func < (Self, Self) -> Bool
}

foreach type T in stdlib that supports ordered comparison:
  struct %T : LessThanAble {
    static func < (%T, %T) -> Bool { ... implementation ... }
  }

or something like:

protocol LessThanAble {
  static func < (lhs: Self, rhs: Self) -> Bool
  static func lessThan(_ lhs: Self, _ rhs: Self) -> Bool
}

extension LessThanAble {
  static func < (lhs: Self, rhs: Self) -> Bool {
    return lessThan(lhs, rhs)
  }
}

foreach type T in stdlib that supports ordered comparison:
  struct %T : LessThanAble {
    func lessThan (%T, %T) -> Bool { ... implementation ... }
  }

or something else entirely?