Passing around path dependent type fails to retain dependent value

Question

Consider the following:

trait Platform {
  type Arch <: Architecture
  def parseArch(str: String): Option[Arch]
}

object Platform {
  def parse(str: String): Option[Platform] = ???
}

trait Architecture

def main() {
  def exec(p: Platform)(a: p.Arch) = ???

  Platform.parse("ios")
    .flatMap(p => p.parseArch("arm64").map(a => (p, a)))
    .flatMap { case (p, a) => exec(p)(a) } // <----- This fails to compile
}

exec(p)(a) fails to compile with error message:

Error:(17, 40) type mismatch;
found : a.type (with underlying type A$A2.this.Platform#Arch)
required: p.Arch .flatMap { case (p, a) => exec(p)(a) }

From the error message, it seems that scalac fails to retain the value (p) on which Arch depends on and therefore it opts to type projection instead (although I'm not too sure what A$A2.this) means.

For what it's worth, substituting the last line with the following will compile:

.flatMap(p => exec(p)(p.parseArch("arm64").get))

Is this a limitation in scala compiler or perhaps I'm missing something here?

Gregson

Answer 1

The simple solution

Your best bet when dealing with path-dependent types is to always keep the owner value around, because Scala has very limited inference and reasoning power otherwise.

For example, your code example could be rewritten as:

Platform.parse("ios") flatMap {
   p => p.parseArch("arm64").map(exec(p))
}

It is generally possible to perform such rewritings, although the code will often become less concise and elegant. A common practice is to use dependent functions and parametric classes.

Using dependent types

In your example, the code:

Platform.parse("ios").flatMap(p => p.parseArch("arm64").map(a => (p, a)))

has type Option[(Platform, Platform#Arch)], because Scala's inference cannot retain the fact that the tuple's second element is dependent on the first element. (You get A$A2.this.Platform because you declared Platform in some inner context.)

In other words, Scala's Tuple2 type is not dependent. We could correct that by making our own class:

case class DepPair(p: Platform)(a: p.Arch)

However, Scala does not support dependent class signatures yet, and it will not compile. Instead, we set to use a trait:

trait Dep {
  val plat: Platform
  val arch: plat.Arch
}

Platform.parse("ios")
  .flatMap { p => p.parseArch("arm64").map { a =>
    new Dep { val plat: p.type = p; val arch: p.Arch = a }}}
  .flatMap { dep => exec(dep.plat)(dep.arch) }

Notice the ascriptions on val plat and val arch, as without them, Scala will try to infer a refined type that will make type-checking fail.

We are in fact at the boundary of what is reasonable to do in Scala (IMHO). For example, if we had parametrized trait Dep[P <: Platform], we would have gotten into all kinds of problems. Notably:

Error:(98, 15) type mismatch;
 found   : Platform => Option[Dep[p.type]] forSome { val p: Platform }
 required: Platform => Option[B]

Scala infers an existential function type, but what we'd like is actually to have the existential quantification inside the function type. We have to guide Scala to understand that, and we end up with something like:

Platform.parse("ios").flatMap[Dep[p.type] forSome { val p: Platform }]{
    case p => p.parseArch("arm64").map{case a: p.Arch =>
      new Dep[p.type] { val plat: p.type = p; val arch = a }}}
  .flatMap { dep => exec(dep.plat)(dep.arch) }

Now I'll let you decide which way is the best: stick with the owner val around (simple solution), or risk losing any sense of sanity you had left!

But talking about losing sanity and existentials, let's try and investigate a bit further...

Using existentials (failed)

The problematic type of the intermediate result in your code was Option[(Platform, Platform#Arch)]. There is actually a way to express it better, using an existential, as in:

Option[(p.type, p.Arch) forSome {val p: Platform}]

We can help Scala by specifying it explicitly, so the intermediate result has the intended type:

val tmp: Option[(p.type, p.Arch) forSome {val p: Platform}] =
  Platform.parse("ios")
  .flatMap { case p => p.parseArch("arm64").map { a => (p, a): (p.type, p.Arch) }}

However, we now touch a very sensitive area of Scala's type system, and it will often cause problems. In fact, I did not find a way to express the second flatMap...

Trying tmp.flatMap { case (p, a) => exec(p)(a) } gives the very helpful:

Error:(30, 30) type mismatch;
 found   : a.type (with underlying type p.Arch)
 required: p.Arch

Another trial:

tmp.flatMap {
  (tup: (p.type, p.Arch) forSome {val p: Platform}) => exec(tup._1)(tup._2)
}

Error:(32, 79) type mismatch;
 found   : tup._2.type (with underlying type p.Arch)
 required: tup._1.Arch

At this point, I think any reasonable individual would give up -- and probably stay away from Scala programming for a few days ;-)

Nakashima

Intersting. I guess path-dependent types are still pretty rough around the edges in scala. After reading your answer, I've gave up on passing them in tuples (trait solution is interesting but a little too verbose) and instead made inner trait to hold reference to outer trait as shown below. Thanks for approving my doubts. – Gregson

Great. Note that you could make your val platform a def platform, so you do not have to keep an additional pointer to the outer trait (Scala already stores pointers to outer traits in inner traits). – Nakashima

Didn't know the difference between def and val involved pointer. Wouldn't def equally create pointer to whatever it refers to within its closure (not sure if this is a thing in scala though)? Perhaps could you share a link? – Gregson

I was just referring to the fact that in Scala, inner trait/classes usually keep a reference to their outer trait/class (useful for things like path-dependent pattern-matching). If you use reflection, you can see this field as something like final private val p$1: Platform;. If you add a val with the same content, it's going to add a redundant field final private val platform: Platform, whereas if it's just a def it won't introduce any field and will return the private field generated by Scala directly. – Nakashima

Thank you. That makes perfect sense. – Gregson

Answer 2

I've learned to acknowledge the current limitation of scala compiler (as shown by LP's answer), and instead came up with this workaround:

trait Platform {
  trait Architecture {
    val platform: Platform.this.type = Platform.this
  }

  object Architecture {
    def parse(str: String): Option[Architecture] = ???
  }
}

object Platform {
  def parse(str: String): Option[Platform] = ???
}

def main() {
  def exec(a: Platform#Architecture) = {
    val p = a.platform
    ???
  }

  Platform.parse("ios")
    .flatMap(p => p.parseArch("arm64"))
    .flatMap(a => exec(a))
}

Thankfully, inner trait can refer to outer trait in scala. This way, there is no need for passing around p and p.Arch together, instead every a: Platform#Architecture holds reference to its own p: Platform.

Gregson