Scala: immutability and path-dependent type compatibility

4
votes

I have asked a few questions around this topic but this time I want to make it a more general discussion, since it seems to me that Scala is lacking some very important blocks.

Consider the following code (which is simplified from my real project),

trait World {
  type State <: StateIntf
  def evolve(s: State): State
  def initialState: State
}

class Algorithm(world: World) {
  def process(s: world.State) {
    val s1 = world.evolve(s)
    // ... do something with s and s1
  }
}

Everything seems so beautiful and mathematical, but

object SomeWorld extends World {...}
new Algorithm(SomeWorld).process(SomeWorld.initialState)  // incompatible type

Certainly you can do in the following way

trait World {
  type State <: StateIntf
  var s: State
  def evolve: Unit      // s = next state
  def initialize: Unit  // s = initial state
  def getState: StateIntf = s
}

But we are just back to the mutable world.

I am told that this is because Scala does not have flow analysis. If that is the problem, shouldn't Scala get that piece? I only need that compilor can be aware that values passed from val to val are the same so that their inner types must agree. This seems so natural to me, as:

  1. val is the most foundamental concept that involves immutability in scala
  2. Path dependent type compatability is needed to model things like World with complete immutability (which is highly desired from a mathematical perspective)
  3. Flow analysis of passing vals solve the problem

Am I asking for too much? Or is there already a nice way of solving it?

2
scalapath-dependent-type

2 Answers

5
votes

The compiler sometimes needs a little bit of help to prove that what you are doing is legal when using path dependent types. I.e., as you said, the compiler is missing flow analysis, so we must tell it explicitly that we aren't just using any World, we are using exactly SomeWorld so that we can use SomeWorld.initialState.

In your case, if you change Algorithm like so:

class Algorithm[W <: World](world: W) {
  def process(s: world.State) {
    val s1 = world.evolve(s)
    // ... do something with s and s1
  }
}

Then the following compiles:

object SomeWorld extends World {...}
new Algorithm[SomeWorld.type](SomeWorld).process(SomeWorld.initialState)
6
votes

I think that generics provides a simpler solution to this problem:

trait World[S <: StateInf] {
  def evolve(s: S): S
  def initialState: S
}

class Algorithm[S <: StateInf](world: World[S]) {
  def process(s: S) {
    val s1 = world.evolve(s)
    // ... do something with s and s1
  }
}