Should it be possible to implement trait with a member that uses general type projection?

Question
1

I raised Unable to implement trait with member that uses general type projection · Issue #12949 · scala/bug · GitHub but I mistakenly put a question in it which is not allowed and so it was closed.

This fails to compile in Scala 2.13.12:

trait QueryTaggedNode[I] {
  type Input = I
}

trait ThinQueryParams[TQuery <: QueryTaggedNode[_]] {
  val variables: TQuery#Input
}

object ThinQueryParams {

  def apply[TQuery <: QueryTaggedNode[_]](
    variables: TQuery#Input,
  ): ThinQueryParams[TQuery] = {
    val _variables = variables

    new ThinQueryParams[TQuery] {
      override val variables: TQuery#Input = _variables
    }
  }
}

It fails with:

type mismatch;
 found   : _variables.type (with underlying type _$2)
 required: _$2
type mismatch;
 found   : this.variables.type (with underlying type _$2)
 required: _$2

complaining about the types on both the left and right hand side of the variables definition.

There is definitely a bug here. Either:
a) It should compile, or
b) It should not compile and the error message should be improved to not be contradictory (there should also only be a single error about the signature being the wrong type instead of the value)

So which is it?

2

A very interesting question. Let’s minimize the code further, to:

trait MyTrait[I] { type Input = I }
class C[T <: MyTrait[_]](i: T#Input) {
  i: T#Input
}

                 i: T#Input
                 ^
On line 5: error: type mismatch;
                found   : C.this.i.type (with underlying type _$1)
                required: _$1

This brings the surprise into even sharper relief. If i has type T#Input, how can the compiler possibly reject i: T#Input?

If we replace the wildcard with a type parameter, the compiler accepts it:

trait MyTrait[I] {
  type Input = I
}
class C[U, T <: MyTrait[U]](i: T#Input) {
  i: T#Input
}

(though at this point we might as well just write U rather than T#Input)

So apparently the wildcard is crucial.

As per SLS 2.12 (Types | Scala 2.13), a wildcard is shorthand for an existential type:

trait MyTrait[I] { type Input = I }
class C[T <: MyTrait[U] forSome { type U}](i: T#Input) {
  i: T#Input
}

Now here’s where my remarks are going to get a bit more speculative, and where I’m hoping others on the forum might be able to answer more authoritatively.

Your intent in writing [T <: MyTrait[_]] was to refer to some concrete instantiation of MyTrait. Bu have we forced the elimination of the existential? Existentials are notoriously slippery: each time an existential type is referenced, the unknown type can be a different type. So if the existential on T isn’t eliminated, then T#Input can refer to a different type each time. I suspect that’s why it’s possible for i: T#Input to not compile.

Regardless, it’s possible the compiler is wrong here and this is some variant of Existential type does not conform to itself · Issue #2071 · scala/bug · GitHub (“Existential type does not conform to itself”)? Looking at SLS 3.5.1, it’s not clear to me that it offers any loophole by which T#Input could not be equivalent to itself.

Note that Scala 3 doesn’t allow projections on type parameters, so we can’t try this in Scala 3. The main reason Martin has offered for this is that they are unsound in some cases. But they’re also difficult both to reason about and to implement, so it’s a nice simplification for the language that this situation can’t even arise in Scala 3.

A final note: in my minimization, I got rid of the override aspect. It’s possible that even once we are convinced we fully understand my minimization, that could still leave at least one open question about your original code.

2 Likes
3

Thanks Seth, I appreciate you taking the time to answer this.

Existentials are notoriously slippery: each time an existential type is referenced, the unknown type can be a different type. So if the existential on T isn’t eliminated, then T#Input can refer to a different type each time. I suspect that’s why it’s possible for i: T#Input to not compile.

Ah right. Yeah this trips me up a fair bit. Usually I can get around it by using Type Parameter Inference in Patterns but given that it is referenced in the parameters it is already too late.

For example:

trait MyTrait[I] {
  type Input = I
  def input: Input
}
// Works
class C[U, T <: MyTrait[U]](i: T#Input) {
  i: T#Input
}
// Doesn't work
class D[T <: MyTrait[U] forSome { type U }](i: T#Input) {
  i: T#Input
}
// Doesn't work
class E[T <: MyTrait[U] forSome { type U }](t: T) {
  t.input: T#Input
}
// Works
class F[T <: MyTrait[U] forSome { type U }](t: T) {
  t match {
    case t2: MyTrait[u] => t2.input: u
  }
}

What I never understood is why is it the case that each time an existential type is referenced, the unknown type can be a different type? Why isn’t T only resolved once?

4

Ah good, I came back here to ask if you’ve considered workarounds involving this relatively little-known language feature, but I see you’re already in the know.

trait MyTrait[I] { type Input = I } looks just like something someone would try if they didn’t know about this language feature :slight_smile:

Yeah, that’s what I’m hoping somebody can enlighten us about.

5

This seems tantalizingly similar: Can scala abstract type can hold the type parameter? - Stack Overflow

Note that the accepted answer involves the same “add a type parameter to eliminate the wildcard” trick I suggested.

6

On Discord, Aly/s5bug shared this bit of code:

import java.{util => ju}
def l[X <: ju.List[_]](x: X): Unit = {
  val head = x.get(0)
  x.add(head)
}

which compiles on Scala 3 but is rejected by Scala 2:

On line 5: error: overloaded method add with alternatives:
                 (x$1: (some other)_$1(in type X))Boolean <and>
                 (x$1: _$1(in type X))Boolean
                cannot be applied to (Any)

where the error seems to indicate that the problem is that the existential gets skolemized twice. Here we have an abstract type upper bounded by an existential, but there’s no type projection, so the issue seems more fundamental, yet might share a root cause with steinybot’s thing.

It’s reassuring that Scala 3 does a better job here.

2 Likes
7

Worth noting that these kinds of projections are not allowed in Scala 3, so we no longer need to speculate what the correct behavior should be. And existentials are also disallowed, precisely because they behave so unintuitively for opening.

Some of the often overlooked type-systematic breakthroughs in Scala 3 is that we could replace existentials with dependent types and a general avoidance principle. That’s a tiny bit more limiting but much more robust.

3 Likes
8

I just happened to be reading SIP-56 and realised that this is possible in Scala 3.3.2 LTS:

trait QueryTaggedNode[I] {
  type Input = I
}

type InputExtractorBase[x] = { type Input = x }
  
type InputExtractor[X] = X match
  case InputExtractorBase[x] => x

// Not quite the same thing but you would probably do this instead:
// type InputExtractor[X] = X match
//   case QueryTaggedNode[x] => x

trait ThinQueryParams[TQuery <: QueryTaggedNode[_]] {
  val variables: InputExtractor[TQuery]
}

object ThinQueryParams {

  def apply[TQuery <: QueryTaggedNode[_]](
    variables: InputExtractor[TQuery],
  ): ThinQueryParams[TQuery] = {
    val _variables = variables

    new ThinQueryParams[TQuery] {
      override val variables: InputExtractor[TQuery] = _variables
    }
  }
}

trait StringQuery extends QueryTaggedNode[String]

ThinQueryParams[StringQuery]("foo")
2 Likes