Pre-SIP: Improve Syntax for Context Bounds and Givens

Scala Improvement Process
42

You can’t do that because C or D might be sealed, and this would break the contract.

The implicit conversion from a synthetic opaque type that I gave before would accomplish the same thing, but without breakage.

1 Like
43

Yes, that makes sense. The implicit conversion approach is better also because you can trivially inline all the machinery, so it doesn’t need to leave any trace in the bytecode at all

44

Would this work for the type A: B declarations introduced in this proposal?

Not currently, but you are right, it should work. We could accommodate this in the existing scheme by giving the generated deferred given the name A. I.e.

  given  Monoid as A = deferred

But it’s probably better we go back to the drawing board for default names of context bounds so that we can handle multiple bounds that way. I think we can probably generate something like a synthetic object that contains all bounds as parents. It can’t be a real value because of sealed traits, double definitions, etc. But we can use it just to support selections and map each selection to the corresponding selection of the implicit parameter or given. That might work.

45

On second thought, I am no longer convinced treating multiple bounds specially in that sense is worth it. It’s a rare case, as @alvae has confirmed (who knows this area well from the Swift and Rust worlds who have been doing things like this for a while). And it would add considerable complexity to language spec and implementation, probably more than the rest of the proposal put together.

So, I propose the following:

  • We do the naming of deferred givens as outlined in the previous comment.
  • In A : C we use A as the name of the evidence for C.
  • Multiple context bounds produce evidence with synthetic names, as they do now.

Multiple context bounds are not only rare but easy to avoid. If multiple bounds, say B, C, D, are often used together, we can define an aggregate bound as follows:

  trait A[X] extends B[X], C[X], D[X]

  given [X: {B as b, C as c, D as d}] => A[X]:
    export b.*
    export c.*
    export d.*

That’s similar to the synthetic object @lihaoyi proposed, but now it’s in user code, so if there are clashes of names or we try to inherit sealed traits that just means we get regular type errors. No need for the spec or implementation to worry about it.

3 Likes
46

It’s already illegal in the current syntax to have given A => B = ???, or even given [T] => (t: T) => T = ???, you have to escape function types by using parentheses, so this is not ambiguous.

// illegal in 3.3.1
given [T] => (t: T) => String =
  [T] => (t: T) => t.toString

// ok in 3.3.1
given ([T] => (t: T) => String) =
  [T] => (t: T) => t.toString
47

I’m not sure I like this syntax for multiple bounds, it feels weird to use a surrounding syntax for it (moreso in the first example).

I’m not sure it’s better, but what about:

trait A:
    def showMax[X : Ordering & Show](x: X, y: X): String

Of course there is the potential confusion with type intersection, but the two concepts are very close:

val x: A & B // x is an A and a B

type X : A & B // X is an A and a B

Furthermore, it would not be so surprising to define the following:

infix type &[A <: _[_], B <: _[_]] = [T] => A[T] & B[T]

There is a potential interaction with the Self type proposal, where the bound could then be a proper type, on which type intersection is already defined, but I believe this would be even worse:

trait A:
    def showMax[X : {Ordering, Show}](x: X, y: X): String // using Ordering{..Self = X}, Show{...Self = X}

trait A:
    def showMax[X : Ordering & Show](x: X, y: X): String // using (Ordering & Show){...Self = X}

As a user, I’ll always wonder which one of the two to pick !

2 Likes
48

I feel like we should go the extra mile here. Multi-typeclass parameters aren’t the norm, but they aren’t rare either:

  • it would be very odd for the sugar to stop working abruptly when e.g. I replace a : upickle.default.Reader with a : {upickle.default.Reader, scala.math.Ordering} (to take an straightforward example from my own code).

  • The Typelevel folks who use typeclasses more heavily than I do use multiple context bounds all the time.

  • And if we hope that these changes will make typeclasses nicer and easier to use, we should anticipate their usage to become more common, including in multi-context-bound use cases

Having to up front declare “bundles” of typeclasses seems unsatisfactory. The whole point of typeclasses is that they can be composed ad-hoc. I don’t want to have to declare upickle.default.OrderedReader and other such things in order to make things ergonomic. It’s certainly doable, but it feels super inelegent

If we combine @Ichoran’s idea of using implicit conversions with @Sporarum’s idea of using & as an infix type, we may even be able to move the necessary machinery to the standard library instead of code-gening them for every context bound. Something like the following pseudocode:

// std lib
type &[A <: _[_], B <: _[_]] = [T] => A[T] AND B[T]
class AND[A, B](val a: A, val b: B)
object AND{
  implicit def makeAB[A, B](implicit a: A, b: B) = new &(a, b)
  implicit def convA[A](v: &[A, _]) = v.a
  implicit def convB[B](v: &[_, B]) = v.b
}

// def-site
def reduceSort[T : Monoid & Ordering](xs: List[T]) = {
  T.monoidMethod
  T.orderingMethod
}

// desugared def-site
def reduceSort[T](xs: List[T])(implicit T: (Monoid & Ordering)[T]) = {
  T.monoidMethod
  T.orderingMethod
}

// expanded def-site
def reduceSort[T](xs: List[T])(implicit T: AND[Monoid[T], Ordering[T]]) = {
  AND.convA(T).monoidMethod
  AND.convB(T).orderingMethod
}

// call-site
reduceSort(List(1, 2, 3))

// expanded call-site
reduceSort(List(1, 2, 3))(AND.makeAB[Monoid[Int], Ordering[Int]](intMonoid, intOrdering))

This way we don’t even need any compiler support for multi-context-bound type parameters at all! They would all be implemented in the standard library via type &/class AND/def makeAB/def convA/def convB.

If the name & doesn’t work we can choose something else, but the approach of moving all this complexity into user-land still applies

This would also mitigate some of the concerns about divergence between context bounds and given parameter lists: rather than having more special syntax that context bounds support and given parameters don’t, we have a user-land & type alias that could easily be used in both scenarios, and preserve the simplicity of the syntactic desugaring between them

There’s some performance overhead from boxing up the multiple context bounds into one parameter, but nothing some backend optimization can’t solve, if we decide that this is the right semantics that we want. The JVM may even do it for free and elide the AND instance automatically

I’ve actually used this technique to abstract over the arity of a method’s context bound before (link)

5 Likes
49

Supporting example from real code, in a service that I had open in my editor (point is that I barely had to look for this):

def setupServer[F[_]: Async: Parallel: Files: Network: GenFiberLocal: LoggerFactory: Random: Tracer](...)
1 Like
50

I confirm that it is rare but I want to qualify this statement.

A lot of care has been put in the Swift and Rust standard libraries to avoid creating overly specific abstractions. For example, Swift would prefer defining a single trait Collection over using the composition Iterable & Finite. Further, it’s generally considered an anti-pattern to declare a trait if it doesn’t contain any requirement in these languages. At the very least, it will ring an alarm for many reviewers because a trait without any requirement is as good as an unconstrained type in general (sealed traits are not a thing in Swift).

Like all rules, this one has its exceptions. Even Hylo’s standard library (which is written by a diligent student of the above school of thought) defines some umbrella traits. But it should be at the very least considered good practice to avoid the proliferation of arbitrary umbrellas like:

trait A[X] extends B[X], C[X], D[X]

I don’t know enough about the common usage of type classes in Scala to tell if libraries have been designed with a coinciding guideline in mind. If not, it may be way more common to want things like this:

def foo[T: {Equatable, Clonable}](x: T): U = ???
51

We should distinguish between multiple context bounds {A, B, C} and aggregate context bounds A & B & C. Aggregate context bounds are a special case of aggregate givens where we construct one evidence that works for the intersection of a set of traits.

Syntactically, givens for intersections are supported already today, the question is only how to construct evidence for them. This is an important but non-trivial problem. The evidence will probably not be free to construct. The best I could come up with was demonstrated in this file in the draft PR. Here we need

  • One proxy class per type class
  • One anonymous class describing the intersection at each point an aggregate given is formed.

Maybe some of the intersection classes can be cached. Having caches that work across compilation units is itself a not-yet solved problem. If some of you can show how to do better, this would be fantastic! I also looked at the conversion approach sketched by @Ichoran and @lihaoyi but fear that would be too brittle and inefficient.

The upshot is that aggregate givens are a possibility, but they will likely be opt in, since they will have some cost in runtime and code size, and also because the construction does not always work (e.g. sealed traits, or situations where A with B does not yield a subtype of A & B).

So we have the following choices:

  • Drop multiple context bounds altogether, replace them with aggregate givens. Accept the runtime cost and increase in code size and the limitations where aggregate givens don’t work. This will pose a problem of backwards compatibility since multiple context bounds exist today. Also, aggregate givens are way beyond the scope of this Pre-SIP. In this case, the default name scheme proposed in this Pre-SIP is all that’s needed.

  • Support both multiple context bounds and at some point in the future aggregate givens. Then we have two sub-choices:

    1. Keep the default name scheme of this SIP. This means you can use X as an evidence name only for X: A & B & C but still not for X: {A, B, C}.
    2. Implement the fancy phantom object approach for {A, B, C}, so that we can write X.m for both aggregate and multiple context bounds.

    My personal choice would be not to do the phantom object approach, since that would only muddle the distinction between multiple and aggregate context bounds.

In summary, I believe there’s not much speaking for the fancy phantom object approach today. Maybe the time and implementation effort is better spent on getting real aggregate givens instead. So my recommendation is to leave that all for later, and only implement the simple desugaring described here. This is compatible with any of the envisioned extensions.

3 Likes
52

I’m OK with deferring a final decision multiple/aggregate context bound support until later, but I think it’s definitely worth discussing as part of this proposal, even if we end up deciding it’s not worth it for now.

The main decision point is that if we think aggregate context bounds are feasible in the short/medium term, then we might be able to get away without the multi-context-bound syntax [T: {A, B, C}] syntax entirely. There’s definitely a use case ovelap between “multiple context bounds” and “aggregate context bounds”, even if the implementation details differ. If we can get away with one rather than both, that would be a simpler language spec and simpler user experience.

I’m curious why you say the implicit conversion approach is fragile? AFAIK we use implicit conversions regularly in the standard library and it works out ok, e.g. String => Seq[Char] or Array[T] => Seq[T]. In some cases there may be confusion when the TO and FROM types in the conversion have overlapping members (e.g. JavaConversions, or java.lang.String#lines vs scala.collection.StringOps#lines), or when conversions may need to be chained, but neither of those issues applies here:

  1. With @Ichoran’s approach, which supports multiple context bounds, the implicit conversion is from an opaque type with no members

  2. With my approach, which supports a variant of aggregate context bounds, the implicit conversion is from a class AND that we control, that can also have no members

  3. In both cases, there is ambiguity if multiple of the context bounds define the same member, but that’s unavoidable given the fact that we’re binding them to a single name, so even with that limitation it’s as good as it gets.

If we don’t want to go with aggregate context bounds, or are worried about bytecode footprint or runtime cost or overhead, then IMO @Ichoran’s desugaring is really good:

  • No bytecode bloat, no synthetic classes or objects
  • The Conversions can also be trivially inlined, whether by the compiler if we make them inline implicit defs, or by the JVM or JS/Native linkers if we don’t.

I tried it out locally, and confirmed that the approach results in completely lean bytecode:

  opaque type ABound = Unit
  def reduceSort[A](xs: List[A])(using monoid_a: Monoid[A], ordering_a: scala.math.Ordering[A]) =
    inline implicit def f(v: ABound): scala.math.Ordering[A] = ordering_a
    inline implicit def g(v: ABound): Monoid[A] = monoid_a
    val A = null.asInstanceOf[ABound]
    A.unit +: xs.sorted(A)

  public <A> scala.collection.immutable.List<A> reduceSort(scala.collection.immutable.List<A>, Monoid<A>, scala.math.Ordering<A>);
    Code:
       0: aconst_null
       1: astore        4
       3: aload_2
       4: invokeinterface #44,  1           // InterfaceMethod Monoid.unit:()Ljava/lang/Object;
       9: astore        5
      11: aload_1
      12: aload_3
      13: invokevirtual #50                 // Method scala/collection/immutable/List.sorted:(Lscala/math/Ordering;)Ljava/lang/Object;
      16: checkcast     #52                 // class scala/collection/SeqOps
      19: aload         5
      21: invokeinterface #56,  2           // InterfaceMethod scala/collection/SeqOps.$plus$colon:(Ljava/lang/Object;)Ljava/lang/Object;
      26: checkcast     #46                 // class scala/collection/immutable/List
      29: areturn

There’s some awkwardness of the placement of opaque type, since it has to be a class/trait/object member and cannot live in arbitrary code blocks like normal type aliases can, but that should be easily fixable

1 Like
53

That’s the blocker IMO. It will be very common that multiple traits define the same member, maybe an associated type, maybe an abstract method. When we combine traits with with there’s a lot of machinery to resolve that (several thousands lines worth of compiler code). When you do implicit conversions, all of these situations would result in unfriendly ambiguity errors. I think we should really put implicit conversions in the poison cabinet. They tend to cause a lot more problems than they solve.

54

I just realized the whole idea is on shakier conceptual ground than I realized, due to Scala embracing that context isn’t necessarily universal.

The problem is that the intuition for how A is scoped is not clear. I have no problem with someone saying “but my intuition is that it is this way”. My concern is that the other way is also likely to be intuitive to some unless they keep the entire machinery in their head.

I’ll illustrate the problem with an example.

Let’s look at the unsugared implemenation first:

def zigzag[A](xs: List[A])(using o: Ordering[A]) =
  val first10 = xs.take(10).sorted
  if xs.length <= 10 then first10
  else
      given r: Ordering[A] = o.reverse
      val rest = xs.drop(10).sorted
      if r.compare(first10.head, rest.head) < 0 then
        rest ++ first10
      else
        first10 ++ rest

Anyway, it does whatever it does. Now we try the shortcut / summon version as it exists now:

def zigzag2[A: Ordering](xs: List[A]) =
  val first10 = xs.take(10).sorted
  if xs.length <= 10 then first10
  else
      given Ordering[A] = summon[Ordering[A]].reverse
      val rest = xs.drop(10).sorted
      if summon[Ordering[A]].compare(first10.head, rest.head) < 0 then
        rest ++ first10
      else
        first10 ++ rest

This gives a warning in Scala 3.4, and for good reason: the naive version above is an endless loop. We actually needed the names.

But now let’s try it an obvious way with the new shorthand:

def zigzag3[A: Ordering](xs: List[A]) =
  val first10 = xs.take(10).sorted
  if xs.length <= 10 then first10
  else
      given Ordering[A] = A.reverse
      val rest = xs.drop(10).sorted
      if A.compare(first10.head, rest.head) < 0 then
        rest ++ first10
      else
        first10 ++ rest

This ought to compile, as everything is well-defined.

The only problem is that the very natural-looking A.compare, which we might think of as “compare according to the ordering on A at this point” is not that at all. A.compare is the compare that was passed in where A was bound. In the original example, it would be o.compare not r.compare.

Using A completely obscures which is which.

If I think: A: Ordering means wherever I use A, I can order it; the compiler handles the details, then my interpretation of A.compare will be wrong in the above example.

If I think: A: Ordering means A : Ordering as A which means I’ve created a new name for the term for the context’s Ordering[A] that happens to match the type name, then my interpretation of A.compare will be correct in the above example.

This seems exactly like the kind of head-scratcher that Scala puzzlers are built from, and company style of “don’t use implicits, they’re confusing” is prompted by. Not because it comes up often, but when it does it’s super weird if you were thinking about it in one of the natural ways to think about it.

So I think any proposal about sugaring the type parameter has to make sure this type of confusion is impossible. Scala trusts the programmer to manage the coherence of typeclasses, but it shouldn’t lay traps for them, and this would arguably be one.

This suggests to me that the context resolution should be tweaked so that if it doesn’t resolve to the original typeclass parameter, it throws an error instead of getting the “wrong one”.

Another possibility is that A.compare is always a lookup (i.e. it’s exactly summon[Ordering[A]].compare), which is easier to explain than “A looks like a type but is actually a term bound to the instance of the typeclass that we’re using”, but I’m not sure that solves the problem. It requires explanation, and “of course it’s the original one” is also a reasonable intuition, so if you miss the explanation you’d be wrong.

Anyway, one of the biggest weaknesses of typeclasses (traits) in Rust, and similar languages with a strong idea of coherence, is that when there is not simply one obvious way to do things, typeclasses fail to model the situation and end up provoking complex workarounds like wrapper types. I like that Scala will happily let you switch context whenever you need to.

But I think we then have to be more careful with features like this which kind of fall apart when strict ways to enforce coherence aren’t part of the language.

2 Likes
55

Not to argue with your point entirely, just to try to minimize it:

  1. The term A is introduced by the context bound. I’m not sure why someone would think it’s from the given.
  2. Why A.compare(...) < 0 rather than first10.head < rest.head? I realize that (1) that would require an import and (2) your point generalizes to cases where that isn’t an option, but that’s the thing: how often do you need to refer directly to the implicit value and have two in the same local scope?
56

I agree that it’s a corner-case that won’t be hit very often.

I think your point (1) just indicates that you didn’t read my explanation, however. Someone would think it was from the given because A.compare sure looks like it’s using the compare that’s appropriate for A, and we just told it what the appropriate compare was. If you don’t have firmly in mind how it is implemented, unsugared, with terms, then you don’t even think about “the term A”. Why would anyone think about terms at all, save that they know the desugared form (and are comfortable with the difference between types and terms)?

Anyway, my complaint is that it’s a sufficiently ugly corner that we shouldn’t allow people to wander into it at all. These things have a way of coming up when you start using feature heavily.

For instance, when I started using extension methods, I thought they were great, and used them a lot. Then, suddenly, everything was broken because the compiler interpreted them as ambiguously overloaded methods coming from different contexts. This was fixed in 3.4, but it illustrates that if you come up with a feature and people go, “Wow, this is great!”, things that initially seemed esoteric become commonplace.

57

deferred will be super useful. I implemented the same feature in Scala 2 called @inject.

@inject is used in DeepLearning.scala and Compute.scala.

With the help of @inject or deferred, library authors will be able to create plugins that depend on other plugins, and can be assembled together by users.

2 Likes
58

So if you want to make A.compare => summon[Ord[A]].compare, then we would need to essentially treat compare like an extension method, even though it isn’t - it could be possible but probably take a lot of engineering in the typer.

59

Very interesting use case! Thanks for bringing that up.

I think that treating A.compare as summon[Ordering[A]].compare is essentially the approach taken by Swift and Rust.

The twist in Scala is that one can declare a new evidence in any arbitrary scope. That isn’t possible in Swift (nor in Rust, I think), although it has been discussed because realistic use cases are seldom but very real. Having followed these discussions very closely, I am quite convinced that the approach you suggest is the right play in general and works just fine in a world with scoped conformances.

1 Like
60

I think it might be necessary to discourage the normal given syntax in those cases, as he said:

Therefore I propose to introduce a way to insert those kinds of overriden bounds.
The benefit being that they conform to the Swift/Rust expectations, while also having a desugarring that can be known by heart for those that think like that, and looks relatively clear.

For example:

given [A : Ordering] = ???

(Only one clause of one type parameter is allowed.)

Or even:

given override [A : Ordering] = ???

This explicitly mentions A on its own, so it makes sense it would modify accesses on A.
I’m also pretty sure that this does not conflict with existing syntax, as givens always need a return type.
It might however be confused with:

given [A : Ordering]: R = ??? // some value of type R, using Ordering[?]

(I intentionally left out the question of how do we refer to the previous value of A from the overriding given named A, as I believe it to be a separate concern)

61

Or we could even lean into the ambiguity:

given A : Ordering = ???
// of course the above is the same as
given A: Ordering = ???

Which would then be desugarred into

given A: Ordering[A] = ???

This does not work in cases there is a type constructor and a type of the same name in scope however.

This could be solved with the override idea (or another keyword):

given override A : Ordering = ???

The above has no conflict with given A: Ordering in case a (non-constructor) type Ordering exists, as override is not normally allowed in that spot.