Pre-SIP: Improve Syntax for Context Bounds and Givens

[odersky]

Further discussions have convinced me that we should strive to uphold the principle that

A: T and m member of T implies A.m is defined.(*)

So we need an object A defined alongside a context-bounded type A that supports that strategy. And it should work also for multiple context bounds and context-bounded type members. At the same time defining that object as a run-time value (aka aggregate givens) will probably not fly. Sometimes the object cannot be created. At other times we do not want an extra object creation since it could entail an inefficient allocation. Finally, it does not work for type members since we’d end up with multiple object members, all with the same name.

But we can do the fancy phantom object trick. Here’s how this might be implemented.

1. In Namer, when encountering a context bounded type parameter A: {C1, ..., Cn} add an abstract value val A: C1[A] & ... & Cn[A] in the same scope as the type parameter. This needs to be added only as a symbol, no actual definition AST is necessary. When encountering a context bounded type type A: C, also add an abstract val symbol val A: C[A] in the scope where the member is defined (and analogously for multiple context bounds). We call these synthetic symbols context bound companions. A context bound companion is not created if there is another value (not a method) defined in the same scope and with the same name as the companion (this includes explicitly named evidence parameters or members).

2. These symbols participate as usual in type checking and inference done by Typer.

3. After Typer, analyze every reference A.m or possibly p.A.m where A is defined. The reference will have a symbol. If that symbol is in a base class of several context bounds, emit an error, the selection is ambiguous. Otherwise let the bound deriving the symbol’s owner be Ci[A] and let w be the name of the evidence parameter or member corresponding to that bound. Replace the reference with w.m or p.w.m, respectively.

   Also, check that for every other accessible member named m in one of the other bounds Cj[A] we have one of the following:

   • the members are provably the same (i.e. type aliases of the same underlying type, or vals with the same singleton type), or
   • the type of m in Ci[A] is a strict subtype of the type of m in Cj[A].

   One purpose of this check is to show that member selection does not depend on the order in which the context bounds appear.

4. Also, after Typer check that no references to context-bound companions remain. Flag each such reference as an error with a message like “context bound companion A is not a value, use an explicitly named evidence or a summon instead.”.

5. After mapping and checking selections on context bound companions, remove all context bound companions from their scopes.

I believe this would be a workable strategy.

(*) Strictly speaking, that principle really holds only for context bounds based on Self-type members (which is another reason why these work so nicely). For context bounds as type constructors, we’d have to tie the knot explicitly:

A: C and m member of C[A] implies A.m is defined.

The analogy with term selection is a bit less clear. Still it’s a useful and intuitively appealing principle.

[Sporarum]

This seems like a very promising strategy

In some ways it solves the “shadowing context-bound companions” in a straightforward way: “You can’t shadow context-bound companions”.

However I believe this is not ideal, for example:

trait Composable[A]:
  def compose(x: A, y: A): A
  extension (x: A)
    infix def o (y: A) = compose(x, y)

def foo[A : Composable](f: A, g: B)
  def v1 = A.compose(f, g)
  def v2 = f o g            // v1 == v2

  given Composable[A] = ???

  def v3 = A.compose(f, g) // Not shadowed, v1 == v3 !
  def v4 = f o g           // Shadowed,     v4 != v2 !

Even if the case is rare, this seems like such a foot gun

[odersky]

I fail to see how this is a footgun, and it has nothing to do with A.compose. When you resolve an extension method you look for givens in scope, that’s all.

[Sporarum]

The other posts bring clearer explanations of why that is a problem

@Ichoran

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.

@alvae

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.

If we want to make type-classes as separate as possible from given/using, I think this is something to seriously think about outside of just “that’s how the underlying mechanism works”

[lihaoyi]

@odersky

Also, after Typer check that no references to context-bound companions remain. Flag each such reference as an error with a message like “context bound companion A is not a value, use an explicitly named evidence or a summon instead.”.

Could we loosne this restriction to allow scenarios where the A is used in a place where target typing would give it a clearly defined type? e.g. in the case I gave:

def foo[A: {Ordering, Monoid}](items: List[A]) = {
  items.sorted(A)
}

Here we know due to target typing that we want A as an Ordering[A] and not as a Monoid[A], and we can provide the relevant summon[Ordering[A]] automatically. In the general case of val a = A we cannot, and so reporting an error is fine, but in these narrow cases it feels like we should be able to do the right thing by default

[lihaoyi]

@odersky

After Typer, analyze every reference A.m or possibly p.A.m where A is defined. The reference will have a symbol. If that symbol is in a base class of several context bounds, emit an error, the selection is ambiguous

I’m not sure if I’m missing something, but isn’t this exactly what the implicit conversion approach provides, that we provide the member where possible, and emit and error if it is ambiguous? Earlier you argued that failing in the case of ambiguity is a blocker, so what’s different here that makes it not?

This feels like we are basically baking in the implicit conversion logic as a special case in the spec, just with slightly more specific error reporting. Which is fine, but seems unnecessary since the implicit conversion logic is already right there

[Ichoran]

@bishabosha

So if you want to make A.compare => summon[Ord[A]].compare, then we would need to essentially treat compare like an extension method

It’s a bit worse than that, I’m afraid. Given [A]...(using t: T[A]) vs. [A : T], I am worried that if there is a difference between A.m being equivalent to t.m and A.m being equivalent to summon[T[A]].m, then there will be confusion.

So ideally I would want A.m to act like it has something like (using ta: T[A])(using t.type =:= ta.type) as an extra context parameter. That is, even though normally we expect depth of scope to matter for givens, because we’re not actually using anything explicitly, we don’t want the difference between val A = t and opaque type A = Unit; given [A](using ta: T[A]): Conversion[A, T[A]] = _ => t to matter. If it does, it’s a footgun.

I think the latter is easier to explain in terms of the rest of Scala: A.m is the m from whatever context for T[A] is in scope, mostly because A feels typey because it is a type. (Edit: but I don’t think we should rely on people reading subtle explanations to avoid getting confused!)

But I think just reporting it as ambiguity would work for Martin’s scheme; it only needs one extra step, 3b, which is to summon a Ci[A] and make sure the instance is the context bound instance; otherwise it’s ambiguous and you emit an error.

[Ichoran]

@lihaoyi

This feels like we are basically baking in the implicit conversion logic as a special case in the spec, just with slightly more specific error reporting.

Inlining the implicit conversion logic in this case where there is no possible ambiguity about the type of the A term (it’s a unique singleton!) seems like it could be a big enough win to not unleash the entire implicit conversion machinery on the problem.

Especially since, as I mentioned while you were writing your reply, I think the safe / user-friendly way to do this is report ambiguity where normally you wouldn’t because of how non-explicit the leap from type to term is, and therefore how non-obvious is the reification of the lookup.

[lihaoyi]

@Ichoran

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.

TBH this seems fine to me. If context bounds bind A, and local given declarations do not, then the A is the one bound in the method signature

I understand it can be confusing, but having multiple anonymous implicits of the same type in scope is always confusing. If anything, I would argue that such scenarios should be warned against or even disallowed, and you should be forced to refer to them by names. Doesn’t implicit resolution already fail if there are multiple ambiguous implicits in scope?

[Ichoran]

@lihaoyi

If context bounds bind A,

Yeah, but this is the premise that I don’t think is obvious.

[lihaoyi]

It’s not the current semantics, so it’s definitely not obvious today, but it seems it could be pretty reasonable going forward

We already have the scoping and binding of the type parameter: the type A comes from the method signature, and not from the local anonymous given. With this proposal, the term A comes from the method signature, and not from the local anonymous given.

I don’t disagree that other semantic models are possible. We could say that the term A performs an implicit search to pick up whatever is in implicit scope. In that case, the alternate interpretation would be correct. But that doesn’t mean that the proposed semantics are problematic, it just means we need to choose one semantic model and stick with it.

And as I said, finding scenarios involving proposed features that are confusing when there are overlapping isn’t really noteworthy. Basically any subset of existing language features can become confusing when overlapping implicits are added. Doesn’t mean those language features themselves are problematic

[Ichoran]

@lihaoyi

Basically any subset of existing language features can become confusing when overlapping implicits are added.

Any time you have a default for a typeclass and have a method that takes a context parameter that is that typeclass, you have overlapping implicits. That doesn’t seem to be a big deal in practice. So I don’t think it’s always a problem.

Besides, we already paid for that level of confusion by virtue of having it as a core part of the language for years.

I’m simply arguing that we shouldn’t add deeper confusion by adding a feature that requires extra training to keep straight. If it “just works”, it’s a much easier case to make than “well you could shoot yourself in the foot occasionally, but you’ll shoot a lot more targets than feet so it’s cool”.

So: if in [A : T /* as t */], A.m is actually t.m but resolves to the same thing as summon[T[A]].m–because summon[T[A]] summons t–then we’re good. It just works. Ambiguity is flagged, and people can learn how to write the unsugared version.

If the two can end up disjoint from each other, then I think this feature is a substantially less sure bet. I think the summon[T[A]].m one is easier to explain than A-is-also-a-term.

But if, as Martin suggests, this doesn’t actually use the full implicit conversion resolution mechanism, then presumably we’re one summonFrom and match (if we were writing it in code) away from not caring about the underlying mechanics of A.m.

[yangbo]

@lihaoyi

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:

I think A: (Foo & Bar) expands to (given A: (Foo & Bar)[A]) currently. Could (Foo & Bar)[A] be a valid type?

[odersky]

I think A: (Foo & Bar) expands to (given A: (Foo & Bar)[A]) currently. Could (Foo & Bar)[A] be a valid type?

No, it cannot, at least not without major type system plumbing with unknown consequences. I think the way to go forward is to have instead Self-based type classes, which is exactly what Rust and Swift do. That’s going to be a follow-on Pre-SIP.

[odersky]

@lihaoyi

I’m not sure if I’m missing something, but isn’t this exactly what the implicit conversion approach provides, that we provide the member where possible, and emit and error if it is ambiguous? Earlier you argued that failing in the case of ambiguity is a blocker, so what’s different here that makes it not?

I was never arguing for implicit conversions. That’s a dead end. To illustrate just two problems of many:

trait A:
  type Elem = String
trait B:
  type Elem = String
given Conversion[C, A] = ???
given Conversion[C, B] = ???
val c: C

c.Elem // error: ambiguous

Even if there is only one conversion in scope, c.Elem would be rejected since c is not a path. That’s just skimming the surface, I am sure there are many more problems.

When I was talking about aggregates I was arguing that we have a problem where we cannot construct aggregates because some member clashes or some parent trait is sealed. We are blocked even if that member never gets selected. Now the problem is much smaller. We can always form the synthetic companions, it’s just when we select a member that is ambiguous that we report an error.

@lihaoyi

Could we loosne this restriction to allow scenarios where the A is used in a place where target typing would give it a clearly defined type?

Possibly. It would require somewhat different techniques to specify and implement though. So far, we did not need to refer to target types in the spec and therefore we could do the disambiguation after Typer. With a loosened restriction we’d have to somehow roll this into the typing rules, which looks a bit daunting.

[odersky]

Here is another implementation technique, which is more general than the previous one I came up with and that addresses @lihaoyi’s suggestion.

1. Create context bounds companions as before.
2. When typing a reference to a context bound companion with an expected type (which usually is a selection prototype, but might be something else), find all evidence references that the companion represents. Perform overloading resolution with each of these evidence references relative to the expected type. This might give a type error if none of the alternatives match the expected type, or an ambiguity error if several do and there is no most specific one.
3. After Typer, reject all remaining references to context bound companions as before.

This is a bit in the spirit of the implicit conversions idea, but it fortuntely does not use implicit conversions, and relies on overloading resolution instead.

There’s also the issue what happens if a class contains a context bound companion and a regular member with the same name. It might inherit these from different parent traits, for instance. In that case I believe the regular member should always win. A way to ensure that is to give context bound companions a synthetic type which is a true supertype of Any. That way, when there is a joint denotation, it will always be the other member that wins. Also, if there is an expected type, the direct subtype comparison would fail and we can do the overloading resolution as a fallback step in the adapt step of Typer. If the expected type is undefined, we will keep the reference to the companion object, which will be rejected after Typer.

Implementation-wise I think this would work nicely. The remaining task would be to come up with spec language that matches this behavior.

[lihaoyi]

@odersky

Perform overloading resolution with each of these evidence references relative to the expected type

Does Scala support return-type overloading like this? I know the JVM supports it, but I thought at a Java/Scala language level typechecking only allows overloading based on input parameters and not return type

The only way I’m aware of to do something similar to return-type overloading in user-land, is via an implicit parameter. Something like

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

Where A can take different implicits and return different types depending on target-typing. But somehow, A.unit is not sufficient to trigger target-typing in this scenario. However, somehow the A.unit is not sufficient to trigger the right target-typing of A(monoid_a), and an explicit (A: Monoid[A]).unit is required

Could an approach like this work? This would basically give us the return-type overloading behavior, without needing compiler support. Maybe we’d need some compiler support to allow A.unit to not require a type ascription but that seems like a smaller change than implementing the feature entirely in bespoke typechecking logic. But I’m not familiar enough to say for sure if it’s possible.

I suppose path dependent types like A.Element wouldn’t also work in this encoding because A is not stable, but I wonder if that’s fixable somehow

@odersky

There’s also the issue what happens if a class contains a context bound companion and a regular member with the same name.

Couldn’t we treat this as similar to having different regular members of the same name? If I’m not mistaken that is simply a double definition error right now.

Given type params and class members have different naming conventions, I feel like we don’t need to go out of our way to make this edge case work, and it’s fine to error out

[odersky]

@lihaoyi

Does Scala support return-type overloading like this? I know the JVM supports it, but I thought at a Java/Scala language level typechecking only allows overloading based on input parameters and not return type

There is return type overloading, but you are right, it would not be good enough for the scheme I outlined previously. Say we have a type A with witnesses a1, …, aN and a selection A.m. Then we need to map that selection into an overloaded denotation with alternatives a1.m, …, aN.m, and go from there. And even that is not enough, since a1.m and a2.m could refer to the same member in which case we should accept the program and not report an ambiguity. Maybe we can tweak the rules of overloading resolution to add that rule. In any case, standard overloading resolution on a1, …, aN alone is not good enough.

On the other hand, the previous scheme of doing a standard selection on a companion A of type C1 & ... & CN won’t work either since dependent typing means the companion reference A can appear in the result of the selection. We’d somehow need to eliminate it in a recursive process, which looks difficult.

So I think the overloading approach is the right one, but it has to be tweaked.

Given type params and class members have different naming conventions, I feel like we don’t need to go out of our way to make this edge case work, and it’s fine to error out

I am worried about the following: If we have a context-bound parameter A, we won’t create a synthetic companion if there is already a value parameter named A, so there won’t be any conflicts. But if we have a type member, we can get conflicts later:

trait S:
  type A: B //creates synthetic companion val A
trait T:
  object A
class C extends S, T:
  A // what is the meaning of A here? I think it should be the object in T.

EDIT: Turns out standard overloading does not work either since it does not apply to type references. So the disambiguation logic has to be custom-made.

[lihaoyi]

I know you’ve said before you don’t think implicit conversions are a good solution here, but I wanted to bring up another thing I discovered: you can use an implicit conversion to add a type member A.TypeMember to an unrelated type A, as long as the implicit conversion’s return type is a singleton type (e.g. : monoid_a.type instead of : Monoid[A]). See // THIS WORKS below:

trait Monoid[T]{
  def unit: T
  type TypeMember = Int
}
object Monoid{
  implicit object intM extends Monoid[Int]{ def unit = 0 }
}
object Main{
  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): ordering_a.type = ordering_a
    inline implicit def g(v: ABound): monoid_a.type = monoid_a
    val A: ABound = null.asInstanceOf[ABound]
    val i: A.TypeMember = 123 // THIS WORKS
    A.unit +: xs.sorted(A)

  def main(args: Array[String]): Unit = {
    println("Hello World")
    println(reduceSort(List(1, 2, 3, 2, 1)))  
  }
}

Honestly this is a bit surprising to me: that means the val i: A.TypeMember = 123 is able to apply the implicit conversion on A, even as part of the type ascription??? This only seems to work in Scala 3.4 and not in Scala 2.13. And trying to explicitly call g in the type ascription val i: g(A).TypeMember = 123 fails with a parse error, which is what I would expect.

Not sure if this is a bug or a feature, and it’s certainly unexpected to me. But at least in the case where there’s only one conversion target type with a type member, In Scala 3 you can in fact use A.TypeMember to refer to it while making use of the implicit conversion from A!

[sideeffffect]

I’d like to defend some of the decisions made in Scala 3.0. I think they’re very good and are good foundations to build upon.

Let me start with the using clauses.

@odersky

Proposal: Allow to name a context bound, like this:

  def reduce[A : Monoid as m](xs: List[A]): A =
    xs.foldLeft(m.unit)(_ `combine` _)

Why would that be better than this, which is already possible?

  // already possible in Scala 3.x
  def reduce[A](using m: Monoid[A])(xs: List[A]): A =
    xs.foldLeft(m.unit)(_ `combine` _)

---

@odersky

Proposal: Allow to combine several context bounds inside {...}, analogous
to import clauses. Example:

  trait:
    def showMax[X : {Ordering, Show}](x: X, y: X): String
  class B extends A:
    def showMax[X : {Ordering as ordering, Show as show}](x: X, y: X): String =
      show.asString(ordering.max(x, y))

Why would that be better than this, which is already possible?

  // already possible in Scala 3.x
  trait:
    def showMax[X](using Ordering[X], Show[X])(x: X, y: X): String
  class B extends A:
    def showMax[X](using ordering: Ordering[X], show: Show[X])(x: X, y: X): String
      show.asString(ordering.max(x, y))

---

@odersky

Here is a method run that runs a parser on an input of the required type:

def run[P : Parser](in: P.Input): P.Result

Or, making clearer what happens by using an explicit name for the context bound:

def run[P : Parser as p](in: p.Input): p.Result

With the current translation this does not work since it would be expanded to:

  def run[P](x: p.Input)(using p: Parser[P]): p.Result

Note that the p in p.Input refers to the p introduced in the using clause, which comes later. So this is ill-formed.

But this works, we could use just this:

  // already possible in Scala 3.x
  def run[P](using p: Parser[P])(x: p.Input): p.Result

Better Default Names for using parameters

But the point about better default names is good. I too think that it could be handy, at least in some cases, without being to burdensome on the readers of the code.

We could then have code like this

// hypothetical Scala feature
def reduce[A](using Monoid[A])(xs: List[A]) =
    xs.foldLeft(A.unit)(_ `combine` _)

or this

  // hypothetical Scala feature
  def run[P](using Parser[P])(x: P.Input): p.Result

TLDR: using clauses are already very very good. They are regular, work and look like method parameters and scale between anonymous and named variants continuously. Why would we need anything else? (And there’s small room for improvement: default names for them.)

Then let’s have a look at Given Syntax

@odersky

given [A](using Ord[A]): Ord[List[A]] with
  def compare(x: List[A], y: List[A]) = ...

It’s also very good. It’s regular. It works like a method (def). It scales between anonymous and named variants continuously. This is the named variant, for comparison

given listOrd[A](using Ord[A]): Ord[List[A]] with
  def compare(x: List[A], y: List[A]) = ...

@odersky

The : feels utterly foreign in this position.

Why would that be the case? It works like a method definition. Those do look like def f(a: A): B.

@odersky

It’s definitely not a type ascription

But it is. It’s the type of the returned given. It works just like with methods.

@odersky

Just as bad is the trailing with. Everywhere else we use braces or trailing : to start a scope of nested definitions, so the need of with sticks out like a sore thumb.

Maybe we could replace with with :?

// hypothetical Scala syntax
given [A](using Ord[A]): Ord[List[A]]:
  def compare(x: List[A], y: List[A]) = ...

Or let’s just use braces?

given [A](using Ord[A]): Ord[List[A]] {
  def compare(x: List[A], y: List[A]) = ...
}

Or just keep using with, it’s fine IMHO.

@odersky

given [A : Ord] => Ord[List[A]]:
  def compare(x: List[A], y: List[A]) = ...

To me this feels foreign to Scala. It’s other languages that have syntax for methods/functions like

def f(a: A, b: B) => C

But Scala notably does not, for better or worse (IMHO better, it’s more regular and sensical), it follows the ML pattern like

def f(a: A, b: B): C

I’m not a language designer by any stretch. But I hope that you, Martin, and the team will still find this feedback from a mere user valuable.
In short, I think you and the team have already set Scala 3 up for success. Now we just have to build on the good foundations (regularity, closeness of named/anonymous variants, intentional similarity to simpler constructs like def, etc) that have been already laid.