When are two methods alike?

by Stephen Compall on Jul 16, 2015

technical

This is the second of a series of articles on “Type Parameters and Type Members”. If you haven’t yet, you should start at the beginning, which introduces code we refer to throughout this article without further ado.

In the last part, we just saw two method types that, though different, are effectively the same: those of plengthT and plengthE. We have rules for deciding when an existential parameter can be lifted into a method type parameter—or a method type parameter lowered to an existential—but there are other pairs of method types I want to explore that are the same, or very close. So let’s talk about how we determine this equivalence.

A method R is more general than or as general as Q if Q may be implemented by only making a call to R, passing along the arguments. By more general, we mean R can be invoked in all the situations that Q can be invoked in, and more besides. Let us call the result of this test $R <:_m Q$ (where $<:_m$ is pronounced “party duck”); if the test of Q making a call to R fails, then $\neg(R <:_m Q)$.

If $Q <:_m R$ and $R <:_m Q$, then the two method types are equivalent; that is, neither has more expressive power than the other, since each can be implemented merely by invoking the other and doing nothing else. We write this as $Q \equiv_m R$. Likewise, if $R <:_m Q$ and $\neg(Q <:_m R)$, that is, Q can be written by calling R, but not vice versa, then R is strictly more general than Q, or $R <_m Q$.

What the concrete method—the one actually doing stuff, not invoking the other one—does is irrelevant, for the purposes of this test, because this is about types. That matters because sometimes, in Scala, as in Java, the body will compile in one of the methods, but not the other. Let’s see an example that doesn’t compile.

import scala.collection.mutable.ArrayBuffer

def copyToZero(xs: ArrayBuffer[_]): Unit =
xs += xs(0)

TmTp2.scala:9: type mismatch;
found   : (some other)_$1(in value xs) required: _$1(in value xs)
xs += xs(0)
^


Likewise, the Java version has a similar problem, though the error message doesn’t give as good a hint as to what’s going on.

import java.util.List;

void copyToZero(final List<?> xs) {
}

TmTp2.java:11:  error: no suitable method found for add(CAP#1)
^


Luckily, in both Java and Scala, we have an equivalent method type, from lifting the existential (misleadingly called wildcard in Java terminology) to a method type parameter.

We can apply this transformation to put the method implementation somewhere it will compile.

def copyToZeroE(xs: ArrayBuffer[_]): Unit =
copyToZeroP(xs)

private def copyToZeroP[T](xs: ArrayBuffer[T]): Unit =
xs += xs(0)


Similarly, in Java,

void copyToZeroE(final List<?> xs) {
copyToZeroP(xs);
}

<T> void copyToZeroP(final List<T> xs) {
final T zv = xs.get(0);
}


The last gives a hint as to what’s going on, both here and in the compiler errors above: in copyToZeroP’s body, the list element type has a name, T; we can use the name to create variables, and the compiler can rely on the name as well. The compiler, ideally, shouldn’t care about whether the name can be written, but that one of the above compiles and the other doesn’t is telling.

If you were to define a variable to hold the result of getting the first element in the list in either version of copyToZeroE, how would you do that? In Java, the reason this doesn’t work is straightforward: you would have to declare the variable to be of type Object, but that type isn’t specific enough to allow the variable to be used as an argument to xs.add.

Scala’s type-inferred variables don’t help here; Scala considers the existential type to be scoped to xs, and makes the definition of zv independent of xs by breaking the type relationship, and crushing the inferred type of zv to Any.

def copyToZeroE(xs: ArrayBuffer[_]): Unit = {
val zv = xs(0)
xs += zv
}

TmTp2.scala:19: type mismatch;
found   : zv.type (with underlying type Any)

Java’s edge of insanity

Now we have enough power to demonstrate that Scala’s integration with Java generics is faulty. Or, more fairly, that Java’s generics are faulty.

Consider this method type, in Scala:

def goshWhatIsThis[T](t: T): T


This is a pretty specific method type; there are not too many implementations. Of course you can always perform a side effect; we don’t track that in Scala’s type system. But what can it return? Just t.

Specifically, you can’t return null:

TmTp2.scala:36: type mismatch;
found   : Null(null)
required: T
def goshWhatIsThis[T](t: T): T = null
^


Well now, let’s convert this type to Java:

public static <T> T holdOnNow(T t) {
return null;
}


We got away with that! And, indeed, we can call holdOnNow to implement goshWhatIsThis, and vice versa; they’re equivalent. But the type says we can’t return null!

The problem is that Java adds an implicit upper bound, because it assumes generic type parameters can only have class types chosen for them; in Scala terms, [T <: AnyRef]. If we encode this constraint in Scala, Scala gives us the correct error.

def holdOnNow[T <: AnyRef](t: T): T = TmTp2.holdOnNow(t)

def goshWhatIsThis[T](t: T): T = holdOnNow(t)

TmTp2.scala:38: inferred type arguments [T] do not conform
⤹ to method holdOnNow's type parameter bounds [T <: AnyRef]
def goshWhatIsThis[T](t: T): T = holdOnNow(t)
^


This is forgivable on Scala’s part, because it’d be annoying to add <: AnyRef to your generic methods just because you called some Java code and it’s probably going to work out fine. I blame null, and while I’m at it, I blame Object having any methods at all, too. We’d be better off without these bad features.

In the next part, “What happens when I forget a refinement?”, we’ll talk about what happens when you forget refinements for things like MList, and how you can avoid that while simplifying your type-member-binding code.