by Stephen Compall on Jul 06, 2014
technical
Also, the “fake covariance” trick.
Sometimes, Scala programmers notice a nice optimization they can use
in the case of a class that has an invariant type parameter, but in
which that type parameter
appears in variant or phantom position in the actual data involved.
=:=
is an
example of the phantom case.
sealed abstract class =:=[From, To] extends (From => To) with Serializable
scala.collection.immutable.Set
is an example of the covariant case.
Here is the optimization, which is very similar to
the Liskov
-lifting previously discussed:
a “safe” cast of the invariant type
parameter can be made, because all operations on the casted result
remain sound.
Here it is for Set,
an example of the “fake covariance” trick:
override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set[B]]
And
here it is for =:=
,
an example of the “singleton instance” trick.
private[this] final val singleton_=:= = new =:=[Any,Any] {
def apply(x: Any): Any = x
}
object =:= {
implicit def tpEquals[A]: A =:= A = singleton_=:=.asInstanceOf[A =:= A]
}
Unless you are using the Scalazzi safe Scala subset, which forbids referentially nontransparent and nonparametric operations, these tricks are unsafe.
Many people are confused that they cannot write functions like this:
def addone[A](x: A): A = x match {
case s: String => s + "one"
case i: Int => i + 1
}
Being given an error as follows.
<console>:8: error: type mismatch;
found : String
required: A
case s: String => s + "one"
^
<console>:9: error: type mismatch;
found : Int
required: A
case i: Int => i + 1
^
Let’s consider only one case, the first. In the right-hand side (RHS)
of this case, you have not proved that A
is String
at all! You
have only proved that, in addition to definitely having type A
, x
also definitely has type String
. In type relationship language,
x.type <: A
x.type <: String
All elephants are grey and are also animals, but it does not follow that all grey things are animals or vice versa. If you use a cast to “fix” this, you have produced type-incorrect code, period.
Under special circumstances, however, information about a type parameter can be recovered, safe and sound. Take this:
abstract class Box[A]
case class SBox(x: String) extends Box[String]
case class IBox(x: Int) extends Box[Int]
def addone2[A](b: Box[A]): A = b match {
case SBox(s) => s + "one"
case IBox(x) => x + 1
}
This compiles, and I don’t even have to have data in the box to get at
the type information that A ~ String
or A ~ Int
. Consider the
first case. On the RHS, I have
b.type <: SBox <: Box[String]
b.type <: Box[A]
In addition, A
is invariant, so after going up to
Box[String]
, b
couldn’t have widened that type parameter, or
changed it in any way, without an unsafe cast. Additionally, our
supertype tree cannot contain Box
twice with different parameters.
So we have proved that A
is String
, because we proved that
Box[A]
is Box[String]
.
This is very useful when defining GADTs.
Let’s consider a similar ADT with the type parameter marked variant.
abstract class CovBox[+A]
case class CovSBox(x: String) extends CovBox[String]
def addone3[A](b: CovBox[A]): A = b match {
case CovSBox(s) => s + "one"
}
This works too, because in the RHS of the case, we proved that:
b.type <: CovSBox <: CovBox[String] <: CovBox[A]
String <: A
The only transform in type A
could have possibly undergone is a
widening, which must have begun at String
. A similar example can
be derived for contravariance.
In our first example, there is one type that we know must be a subtype
of A
, no matter what!
def addone[A <: AnyRef](x: A): A = x: x.type
(Scala doesn’t like it when we talk about singleton types without an
AnyRef
upper bound at least. But the underlying principle holds for
all value types.)
Where x
is an A
of stable type, x.type <: A
for all possible A
types. You might say, “that’s uninteresting; obviously x
is an A
in this code.” But that isn’t what we’re talking about; our premise
is that any value of type x.type
is also an A
!
So if we could prove that something else had the singleton type
x.type
, we would also prove that it shared all of x
’s types! We
can do that with a singleton type pattern, which is implemented
(soundly in 2.11) with a reference comparison. Scala lets us use
some of the resulting implications.
final case class InvBox[A](b: A)
def maybeeq[A, B](x: InvBox[A], y: InvBox[B]): A = y match {
case _: x.type => y.b
}
To which you might protest, “there’s only one value of any singleton type!” Well, yes. And here’s where our seemingly innocent optimization turns nasty. If you’ll recall, it depends upon treating a value with multiple types via an unsafe cast.
def unsafeCoerce[A, B]: A => B = {
val a = implicitly[A =:= A]
implicitly[B =:= B] match {
case _: a.type => implicitly[A =:= B]
}
}
def unsafeCoerce2[A, B]: A => B = {
val n = Set[Nothing]()
val b = n.toSet[B]
n.toSet[A] match {
case _: b.type => implicitly[A =:= B]
}
}
Both of these compile to what is in essence an identity function.
scala> Some(unsafeCoerce[String, Int]("hi"))
res0: Some[Int] = Some(hi)
scala> Some(unsafeCoerce2[String, Int]("hi"))
res1: Some[Int] = Some(hi)
In our invariant Box
example we decided that, as it was impossible
to change the type parameter without an unsafe cast, we could use that
knowledge in the consequent types. In unsafeCoerce
, where ?
represents the value before the match keyword:
?.type <: a.type <: (A =:= A)
?.type <: (B =:= B)
A ~ B
In unsafeCoerce2
,
?.type <: b.type <: Set[B]
?.type <: Set[A]
A ~ B
There is nothing wrong with Scala making this logical inference. The “optimization” of that cast is not safe.
Let me reiterate: Scala’s type inference surrounding pattern matching should not be “fixed” to make unsafe casts “safer” and steal our GADTs. Unsafe code is unsafe.
For types like these, it is not possible to exploit this unsafety without a reference check, which is what a singleton type pattern compiles to. As the Scalazzi safe subset forbids referentially nontransparent operations, if you follow its rules, these optimizations become safe again.
This is just yet another of countless ways in which following the Scalazzi rules makes your code safer and easier to reason about.
That isn’t to say it’s impossible to derive a situation where the
optimization exposes an unsafeCoerce
in Scalazzi code. However, you
must specially craft a type in order to do so.
abstract class Oops[A] {
def widen[B>:A]: Oops[B] = this.asInstanceOf[Oops[B]]
}
case class Bot() extends Oops[Nothing]
def unsafeCoerce3[A, B]: A => B = {
val x = Bot()
x.widen[A] match {
case Bot() => implicitly[A <:< B]
}
}
The implication being
?.type <: Bot <: Oops[Nothing]
?.type <: Oops[A]
Nothing ~ A
Scalaz
uses the optimization under consideration in scalaz.IList
.
So would generalized Functor
-based Liskov
-lifting, as discussed at
the end of “When can Liskov be lifted?”,
were it to be implemented. However, these cases do not fit the bill
for exploitation from Scalazzi-safe code.
On the other hand, the singleton type pattern approach may be used in all cases where the optimization may be invoked by a caller, including standard library code where some well-meaning contributor might add such a harmless-seeming avoidance of memory allocation without your knowledge. Purity pays, and often in very nonobvious ways.
This article was tested with Scala 2.11.1.