Working around type erasure ambiguities (Scala)

14 06 2010

In my previous post I showed a workaround for the type erasure ambiguity problem in Java. The solution uses vararg parameters for disambiguation. As Paul Phillips points out in his comment, this solution doesn’t directly port over to Scala. Java uses Array to pass varargs, Scala uses Seq. Unlike Array, Seq is not reified so Seq[String] and Seq[Int] again erase to the same type putting us back to square one.

However, there is another way to add disambiguation parameters to the methods: implicits! Here is how:

implicit val x: Int = 0
def foo(a: List[Int])(implicit ignore: Int) { }
  
implicit val y = ""
def foo(a: List[String])(implicit ignore: String) { }

foo(1::2::Nil)
foo("a"::"b"::Nil)




Working around type erasure ambiguities

30 05 2010

In an earlier post I already showed how to work around ambiguous method overloads resulting from type erasure. In a nut shell the following code wont compile since both overloaded methods foo erase to the same type.

Scala:

def foo(ints: List[Int]) {}
def foo(strings: List[String]) {}

Java:

void foo(List<Integer> ints) {}
void foo(List<String> strings) {}

It turns out that there is a simple though somewhat hacky way to work around this limitations: in order to make the ambiguity go away, we need to change the signature of foo in such a way that 1) the erasure of the foo methods are different and 2) the call site is not affected.

Here is a solution for Java:

void foo(List<Integer> ints, Integer... ignore) {}
void foo(List<String> strings, String... ignore) {}

We can now call foo passing either a list of ints or a list of strings without ambiguity:

foo(new ArrayList<Integer>());
foo(new ArrayList<String>());

This doesn’t directly port over to Scala (why?). However, there is a similar hack for Scala. I leave this as a puzzle for a couple of days before I post my solution.





Puzzle: implement this (solution)

24 06 2009

Well, I wasn’t aware of Ticket #1737 when I was trying to find a solution to the problem from my previous post. Thanks to Jorge Ortiz for pointing this out. However, I reviewed my approach to solving this and didn’t find sever limitations. Maybe someone else does…

When I initially stumbled on this, I remembered that existential types where introduced into Scala for coping with Java’s raw types. But there is an additional twist here, we need to tell the compiler that our MyIterator implementation actually ‘is an instance of a raw type’. So combining existential types with self types led me to the following solution:

class MyIterator extends Iterator2 {
  this: java.util.Iterator[_] =>
  def hasNext = true
  def remove = throw new Error  
  def next = "infinity"   
}

We can now safely use instances of MyIterator.

  def test1(it: MyIterator) = {
    println(it.next)
  }
  
  def test2(it: java.util.Iterator[_]) = {
    println(it.next)
  }
  
  val it = new MyIterator
  val v: String = it.next
  println(v)
  
  test1(it)
  test2(it)

The approach using existential types in combination with self types makes sure that values returned from the next method always are typed correctly.





Puzzle: implement this

19 06 2009

This is something I stumbled on recently when trying to implement javax.jcr.NodeIterator in Scala.

Assume you are using a library which exports an Iterator2 interface:

public interface Iterator2 extends java.util.Iterator {}

Note that Iterator is a raw type and Iterator2 does not take any type parameters. So how would you implement Iterator2 in Scala?

Here is a start:

class MyIterator extends Iterator2 {
  def hasNext = false
  def remove = throw new Error
  def next: Nothing = throw new Error
}

But if the next method should return an actual value, what would be it’s return type? It turn’s out that any other type than Nothing results in a compiler error:

error overriding method next in trait Iterator of type ()E;
method next has incompatible type ()Any

So how would you implement Iterator2?





Puzzle: the depth of a type (solution)

12 03 2008

In my previous post I asked for a function depth, which takes an argument of type M and returns its structural depth.

Here is my solution:

object Puzzle {
class M[T]

abstract class Rep[T] {
def eval: int
}

implicit def toRep0[T](k: T) = new Rep[T] {
def eval = 0
}

implicit def toRepN[T](k: M[T])(implicit f: T => Rep[T]) = new Rep[M[T]] {
def eval = f(null.asInstanceOf[T]).eval + 1
}

def depth[T <% Rep[T]](m: T) = m.eval def main(args: Array[String]) { println(depth(0)) println(depth(new M[int])) println(depth(new M[M[int]])) println(depth(new M[M[M[int]]])) } } [/sourcecode] This is the same technique as discussed in my articles on implicit double dispatch. The function depth is applicable to any argument of type T which is implicitly convertible to type Rep[T]. Rep[T] instances implement a function eval, which returns the depth of the type this instance is representing. There are two function for implicit conversions: toRep0 and toRepN. The toRep0 function is responsible for the base case where the structural depth of the type of its argument is 0. The eval function thus returns 0 in this case. The toRepN function is responsible for the other cases where a Mn + 1[T] has to be converted into a Rep[Mn + 1[T]] (Mk[T] stands for M[M[…[T]]] having structural depth k). toRepN takes an implicit parameter f itself. This parameter is a conversion function for converting a Mn[T] into a Rep[Mn[T]] which is used for constructing Rep[Mn + 1[T]]. Since we can convert types of structural depths 0 and types of structural depth n + 1 when given a Rep[T] for T having structural depths n, we can – by induction – convert types of any structural depth.

The implementation of eval in toRepN is implemented in terms of the eval method of Rep[T]. However to access Rep[T] we need to apply f to a T. Since we don’t have an instance of T and since the actual instance does not matter, we simply pass null casted to T.

The technique employed here is a special case of the Code Follows Type pattern. The general idea is not to re-implement the structure of types in code, but to re-use the inherent information carried by types. While in Java this is only possible to a limited degree, Scala’s implicit conversions enable this technique even for recursive structures.

Credits are due to Henry Ware for pointing me to this paper about Scala’s higher kinds. Towards the end of the paper the authors show how to encode the church numerals as Scala types. The encoding plays nicely with the depth function. So – as I mentioned before in a comment – this might be a first, gentle step towards meta-programming with Scala. However, there are certain limitations I guess. I will write more about this later.





Puzzle: the depth of a type

4 03 2008

Here is a little Scala quiz I made up: say we have a type M[T]. Design a function depth which takes an argument of type M and returns its structural depth.

class M[T]

def depth ...

def main(args: Array[String]) {
  println(depth(0))
  println(depth(new M[int]))
  println(depth(new M[M[int]]))
  println(depth(new M[M[M[int]]]))
}

So with the right definition of depth in place the above code should print

0
1
2
3

I’m not sure if this can be done through pattern matching or using instanceOf. My solution does not rely on either of these.