Covariance of a passed function argument

Question

I have made an attempt at implementing a StateMachine in Scala, however I have encountered an issue with the type system that has me rather baffled. In the code below, I need to have the guard function accept an argument of an expected sub-class of StateMachine. Unfortunately, as the type parameter for FunctionN arguments are contravariant, I am not sure how to pull this off.

 
class Transition[S, +M &lt: StateMachine[S]](start: S, end :S, var guard: Option[M => Boolean]) {
// COMPILER ERROR ABOVE LINE : ^^ covariant type M occurs in contravariant position in type => Option[M => Boolean] of method guard ^^
  val startState = start
  val endState = end

  def willFollow(stateMachine: M, withGuard : Boolean) = 
  // COMPILER ERROR ABOVE : ^^ covariant type M occurs in contravariant position in type M of value stateMachine ^^
    if (!withGuard && guard == None) true;
    else (withGuard && guard.get(stateMachine))
}

class EpsilonTransition[S, M &lt: StateMachine[S]](start: S,end :S) extends Transition[S, M](start, end, None)

class StateMachine[S](transitions: Set[Transition[S, StateMachine[S]]], initialStates: Set[S]) {
    private val stateDrains = transitions.groupBy(_.startState);
    private var activeStates = initialStates

    def act() = {
      var entryStates = Set[S]()
      var exitStates = Set[S]()

      stateDrains.foreach {drain =>  
        val (exitState, transitionsOut) = drain

        // Follow non-epsilon transitions
        transitionsOut.filter(_.willFollow(this, true)).foreach {transition =>
          exitStates += transition.startState
          entryStates += transition.endState
        }
      }

      // For all exit states we map the state to a set of transitions, and all sets are "flattened" into one big set of transitions
      // which will then filter by those which do not have a guard (epsilon transitions). The resulting filtered list of transitions
      // all contain endStates that we will map to. All of those end states are appended to the current set of entry states.
      entryStates = entryStates ++ (exitStates.flatMap(stateDrains(_)).filter(_.willFollow(this, false)).map(_.endState))

      // Exclude only exit states which we have not re-entered 
      // and then include newly entered states
      activeStates = ((activeStates -- (exitStates -- entryStates)) ++ entryStates) 
    }

    override def toString = activeStates.toString
}

object HvacState extends Enumeration {
     type HvacState = Value
     val aircon, heater, fan = Value
}
import HvacState._

object HvacTransitions {
    val autoFan = new EpsilonTransition[HvacState, HVac](aircon, fan)
    val turnOffAc = new Transition[HvacState, HVac](aircon, fan, Some(_.temperature  75))
    val HeaterToFan = new Transition[HvacState,HVac](heater, fan, Some(_.temperature > 50))
}
import HvacTransitions._

class HVac extends StateMachine[HvacState](Set(autoFan, turnOffAc, AcToHeater, HeaterToAc, HeaterToFan), Set(heater)) {
  var temperature = 40
}

Answer 1

Your transitions works only for a certain type of states, but also for a certain type of state machine, so the two type parameters S and M. For instance, at the end, you have transitions may depend on the temperature, which is a property of the StateMachine and not of just the State.

Somehow, a state machine should have only transitions that are compatible with it. A transition that needs access to temperature should not be allowed on a state machine without a temperature. The type system will enforce that. However, your code makes no provision for that.

Instead you have class StateMachine getting a Set of Transition[S, StateMachine[S]]. This works, but the consequence is that a StateMachine accepts only "standard" transitions, that will not require anything special from the machine. You can define transitions requiring special machines (with temperature) but there is nothing for a machine to accepts those special transitions even when they would be compatible with it.

Then comes your Hvac machine, which has temperature. You try to give pass it special transitions, transitions that can operate only on Hvac machine (accessing the temperature). But the ancestor constructor is written to accept standard transitions only. The compiler rejects that. It suggest that if Transition was covariant in M, it would be ok. This is true, except that Transition cannot be covariant in M. It takes a machine as an input. A covariant transition would mean that if it can operate on a very special machine, it must also be able to operate also on a less special machine. Not what you want.

What you need to do is have class StandardMachine accepts special transitions, which it now rejects, but of course only transitions that are compatible with the machine (if you don't give this guarantee, the compiler will reject the code). Probably the easier way to do that is to put the type M in the machine too, so that you can express the constraint properly.

Here is a possible way. First we add a type parameter to StateMachine

class StateMachine[S, M](

we need to add the M parameter everywhere StateMachine is referenced, for instance class Transition[S, M <: StateMachine[S, M]], or class Hvac extends StateMachine[HvacState, Hvac]

Of course, the constructor parameters become

class StateMachine[S,M](transitions: Set[Transition[S, M]]], ...

Here we states that the machine is ok for its transitions. Except that we did not. It still does not compile, each time we pass this, the machine to a transition, for instance:

transitionsOut.filter(_.willFollow(this, true)).foreach {transition =>
                                   ^^
type mismatch;  found   : StateMachine.this.type (with underlying type StateMachine[S,M])  required: M

Well, we introduced type M, but we are not passing some M to the machine, we are passing this. This is a StateMachine[S, M], it needs not be an M. We certainly intend M to be the type of the machine, but this needs not be the case. We hate to state that a StateMachine[S, M] must be an M. We do that with a self type :

class StateMachine[S, M](
   transitions: Set[Transition[S, M]], 
   initialStates: Set[S]) { this: M => 
 // body of the class

}

this: M => states that every instance of the class must be an instance of the generic parameter M. We force this to be an M, so the error disappears.

Then the constraint M <: StateMachine[S, M] in Transition comes in the way, we don't need it and we simply remove it : Transition[S, M]. Alternatively, we can put the same constraint on StateMachine.

This make full use of the type system with the problem as it was stated, but it might be simpler to isolate the machine state, that is, instead of having the self type this: M =>, have some def machineState: M, and pass that to the guard instead of this. In this case, Hvac would be a StateMachine[HvacState, Double] (or some more explicit encapsulation of the temperature than Double),

---

Summary of my changes :

• Transition: Removing the constraint on M, removing covariance :

  class Transition[S, M](...

• EpsilonTransition : removing the constraint on M

  class EpsilonTransition[S, M]

• StateMachine : Add type parameter M, use M as parameter for the transitions, and set M as self type :

  class StateMachine[S, M](transitions: Set[Transition[S, M]], initialStates: Set[S]) { this: M =>

• turnOffAcc : an operator is missing in the code you copied, added <

• HVac : added itself as second generic parameter : class HVac extends StateMachine[HvacState]. Also, some of the transitions, AcToHeater and HeaterToAc do not appear in the code you copied, so I just removed them.

Answer 2

You need to do something like this (it compiles for me):

class Transition[S, M <: StateMachine[S]](start: S, end: S, var guard: Option[M => Boolean]) {
  val startState = start
  val endState = end

  def willFollow[MM <: M](stateMachine: MM, withGuard: Boolean) =
    if (!withGuard && guard == None) true
    else (withGuard && guard.get(stateMachine))
}

Basically, Option[M => Boolean] will take any function that takes an M or greater and goes to boolean. For instance, Any => Boolean would work. This is contravariant. However, your willFollow method needs to take anything less than M since it's applying to a function of at least type M. Here's a better explanation, since you're probably looking for one: Why doesn't the example compile, aka how does (co-, contra-, and in-) variance work?