Compilation issue in Scala with F-bounded types and existential types

Question

I'm using a F-bounded type in order to be able to return the current type

trait Board[T <: Board[T]] {
  def updated : T
}

And I'm trying to write a generic helper method that use it.

The question is : why the following do not compile ?

object BoardOps {
  def updated(board: Board[_]) = {
    board.updated.updated
  }
}

The error is value updated is not a member of _$1

I've figured out these 2 workarounds. Are they equivalent ?

object BoardOps {
  def updated(board: Board[_<:Board[_]]) = {
    board.updated.updated
  }
}

object BoardOps {
  def updated[T <: Board[T]](board: T) : T = {
    board.updated.updated
  }
}

Answer 1

why the following do not compile?

Using Board[_] as a parameter type tells the compiler "I do not care for the type of parameter inside board". Namely, this, to the compiler, is an existential type, it doesn't know any specifics about that type. As such, board.updated returns an "unspeakable", or opaque type, because we told the compiler to "throw out" that type information.

I've figured out these 2 workarounds. Are they equivalent?

Your former example uses an existential type with a constraint to be a subtype of Board[_], or more formally we write:

Board[T] forSome { type T <: Board[U] }

Where the compiler actually names T -> $_1 and U -> $_2

Again, we know nothing of the inner type parameter, only that it has an upper bound on Board[_]. Your latter example uses a universally quantified type named T, which the compiler is able to use to deduce the return type of the method to be of a particular type T rather than Any.

To answer your question, no, they are not equivalent. Existential and universally quantified types are dual to each other. More information on existentials can be found on What is an existential type? and https://www.drmaciver.com/2008/03/existential-types-in-scala/

Answer 2

It does not compile, because as soon as you write Board[_], the compiler does not infer anything useful about the anonymous type parameter _.

There are several work-arounds (which are not the same as you already proposed):

1. Use Board[X] forSome { type X <: Board[X] }
2. Use pattern matching to infer more information about the type

Using forSome existential quantification

This can be easily fixed with a forSome-existential quantification:

import scala.language.existentials

object BoardOps_forSome {
  def updated(board: Board[X] forSome { type X <: Board[X] }) = {
    board.updated.updated.updated
  }
}

This allows you to invoke updated an unlimited number of times.

---

Using pattern matching

You could actually work around it without changing the signature, using pattern matching. For example, this ungodly construction allows you to apply the method updated three times (works unlimited number of times):

object BoardOps_patternMatch {
  def updated(board: Board[_]) = {
    board match {
      case b: Board[x] => b.updated match {
        case c: Board[y] => c.updated match {
          case d: Board[z] => d.updated
        }
      }
    }
  }
}

This is because as soon as you bind the unknown type to type variables x, y, z, the compiler is forced to do some extra inference work, and infers that it must actually be x <: Board[_$?] etc. Unfortunately, it does the inference only one step at a time, because if it tried to compute the most precise type, the type computation would diverge.

---

Upper bounds and universal quantification are not the same

Notice that your first workaround works only twice:

object BoardOps_upperBound_once {
  def updated(board: Board[_<:Board[_]]) = {
    board.updated.updated // third .updated would not work
  }
}

Therefore, it is not equivalent to your second workaround, which also works an unlimited number of times, here example with three invokations of updated:

object BoardOps_genericT {
  def updated[T <: Board[T]](board: T) : T = {
    board.updated.updated.updated
  }
}