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.





[ANN] Talking at Scala Days 2010 in Lausanne next Thursday

11 04 2010

I’ll be talking at Scala Days 2010 in Lausanne on April 15th about the Scala scripting engine for Apache Sling. While my talk at Jazoon 09 was mainly about using Scala from Sling, this session will be more focused on internals of the Scala scripting engine.

Unfortunately (or fortunately depending on the point of view) the conference is sold out already. Watch my Scala for scripting page for the session slides and other upcoming support material.





Scala type level encoding of the SKI calculus

29 01 2010

In one of my posts on type level meta programming in Scala the question of Turing completeness came up already. The question is whether Scala’s type system can be used to force the Scala compiler to carry out any calculation which a Turing machine is capable of. Various of my older posts show how Scala’s type system can be used to encode addition and multiplication on natural numbers and how to encode conditions and bounded loops.

Motivated by the blog post More Scala Typehackery which shows how to encode a version of the Lambda calculus which is limited to abstraction over a single variable in Scala’s type system I set out to further explore the topic.

The SKI combinator calculus


Looking for a calculus which is relatively small, easily encoded in Scala’s type system and known to be Turing complete I came across the SKI combinator calculus. The SKI combinators are defined as follows:

Ix \rightarrow x ,
Kxy \rightarrow x ,
Sxyz \rightarrow xz(yz) .

They can be used to encode arbitrary calculations. For example reversal of arguments. Let R \equiv S(K(SI))K . Then

R x y \equiv
S(K(SI))K x y \rightarrow
K(SI)x(Kx)y \rightarrow
SI(Kx)y \rightarrow
Iy(Kxy) \rightarrow
Iyx \rightarrow yx .

Self application is used to find fixed points. Let \beta \equiv S(K\alpha)(SII) for some combinator \alpha . Then \beta\beta \rightarrow \alpha(\beta \beta) . That is, \beta\beta is a fixed point of \alpha . This can be used to achieve recursion. Let R be the reversal combinator from above. Further define

A_0 x \equiv c for some combinator c and
A_n x \equiv x A_{n-1} .

That is, combinator A_n is the combinator obtained by applying its argument to the combinator A_{n-1}. (There is a bit of cheating here: I should actually show that such combinators exist. However since the SKI calculus is Turing complete, I take this for granted.) Now let \alpha be R in \beta from above (That is we have \beta \equiv S(KR)(SII) now). Then

\beta\beta A_0 \rightarrow c

and by induction

\beta\beta A_n \rightarrow \beta\beta A_{n-1} \rightarrow c.

Type level SKI in Scala


Encoding the SKI combinator calculus in Scala’s type system seems not too difficult at first. It turns out however that some care has to be taken regarding the order of evaluation. To guarantee that for all terms which have a normal form, that normal form is actually found, a lazy evaluation order has to be employed.

Here is a Scala type level encoding of the SKI calculus:

trait Term {
  type ap[x <: Term] <: Term
  type eval <: Term
}
  
// The S combinator
trait S extends Term {
  type ap[x <: Term] = S1[x] 
  type eval = S
}
trait S1[x <: Term] extends Term {
  type ap[y <: Term] = S2[x, y]
  type eval = S1[x]
}
trait S2[x <: Term, y <: Term] extends Term {
  type ap[z <: Term] = S3[x, y, z]
  type eval = S2[x, y]
}
trait S3[x <: Term, y <: Term, z <: Term] extends Term {
  type ap[v <: Term] = eval#ap[v]
  type eval = x#ap[z]#ap[y#ap[z]]#eval
}

// The K combinator
trait K extends Term {
  type ap[x <: Term] = K1[x]
  type eval = K
}
trait K1[x <: Term] extends Term {
  type ap[y <: Term] = K2[x, y]
  type eval = K1[x]
}
trait K2[x <: Term, y <: Term] extends Term {
  type ap[z <: Term] = eval#ap[z]
  type eval = x#eval
}
  
// The I combinator
trait I extends Term {
  type ap[x <: Term] = I1[x]
  type eval = I
}
trait I1[x <: Term] extends Term {
  type ap[y <: Term] = eval#ap[y]
  type eval = x#eval
}

Further lets define some constants to act upon. These are used to test whether the calculus actually works.

trait c extends Term {
  type ap[x <: Term] = c
  type eval = c
}
trait d extends Term {
  type ap[x <: Term] = d
  type eval = d
}
trait e extends Term {
  type ap[x <: Term] = e
  type eval = e
}

Eventually the following definition of Equals lets us check types for equality:

case class Equals[A >: B <:B , B]()

Equals[Int, Int]     // compiles fine
Equals[String, Int] // won't compile

Now lets see whether we can evaluate some combinators.

  // Ic -> c
  Equals[I#ap[c]#eval, c]
  
  // Kcd -> c
  Equals[K#ap[c]#ap[d]#eval, c]

  // KKcde -> d
  Equals[K#ap[K]#ap[c]#ap[d]#ap[e]#eval, d]
  
  // SIIIc -> Ic
  Equals[S#ap[I]#ap[I]#ap[I]#ap[c]#eval, c]

  // SKKc -> Ic
  Equals[S#ap[K]#ap[K]#ap[c]#eval, c]

  // SIIKc -> KKc
  Equals[S#ap[I]#ap[I]#ap[K]#ap[c]#eval, K#ap[K]#ap[c]#eval]

  // SIKKc -> K(KK)c
  Equals[S#ap[I]#ap[K]#ap[K]#ap[c]#eval, K#ap[K#ap[K]]#ap[c]#eval]

  // SIKIc -> KIc
  Equals[S#ap[I]#ap[K]#ap[I]#ap[c]#eval, K#ap[I]#ap[c]#eval]

  // SKIc -> Ic
  Equals[S#ap[K]#ap[I]#ap[c]#eval, c]
  
  // R = S(K(SI))K  (reverse)
  type R = S#ap[K#ap[S#ap[I]]]#ap[K]
  Equals[R#ap[c]#ap[d]#eval, d#ap[c]#eval]

Finally lets check whether we can do recursion using the fixed point operator from above. First lets define \beta .

  // b(a) = S(Ka)(SII)
  type b[a <: Term] = S#ap[K#ap[a]]#ap[S#ap[I]#ap[I]]

Further lets define some of the A_ns from above.

trait A0 extends Term {
  type ap[x <: Term] = c
  type eval = A0
}
trait A1 extends Term {
  type ap[x <: Term] = x#ap[A0]#eval
  type eval = A1
}
trait A2 extends Term {
  type ap[x <: Term] = x#ap[A1]#eval
  type eval = A2
}

Now we can do iteration on the type level using a fixed point combinator:

  // Single iteration
  type NN1 = b[R]#ap[b[R]]#ap[A0]
  Equals[NN1#eval, c]

  // Double iteration
  type NN2 = b[R]#ap[b[R]]#ap[A1]
  Equals[NN2#eval, c]

  // Triple iteration
  type NN3 = b[R]#ap[b[R]]#ap[A2]
  Equals[NN3#eval, c]

Finally lets check whether we can do ‘unbounded’ iteration.

trait An extends Term {
  type ap[x <: Term] = x#ap[An]#eval
  type eval = An
}
// Infinite iteration: Smashes scalac's stack
  type NNn = b[R]#ap[b[R]]#ap[An]
  Equals[NNn#eval, c]

Well, we can 😉

$ scalac SKI.scala
Exception in thread "main" java.lang.StackOverflowError
        at scala.tools.nsc.symtab.Types$SubstMap.apply(Types.scala:3165)
        at scala.tools.nsc.symtab.Types$SubstMap.apply(Types.scala:3136)
        at scala.tools.nsc.symtab.Types$TypeMap.mapOver(Types.scala:2735)




Implementing Java Interfaces and Generics

30 08 2009

In an earlier post I asked for an implementation of the following Java interface in Scala:

public interface Iterator2 extends java.util.Iterator {}  

The solution was to use a combination of self types and existential types. However, some comments made me aware of Ticket #1737 where a more general form of the problem is discussed. Given the following Java code:

public interface A<T> {
    void run(T t);
    T get();
}

public abstract class B implements A {}

How could B be implemented in Scala? My previous approach is not sufficient here since for implementing the run() method, one needs to be able to refer to the existential type in run()‘s parameter list:

class C extends B {
  this: A[_] =>
      
  def run(t:???) {} // What should go here for t's type?
  def get = "hello world"
}

So what we need is a way to name the existential type used in the self type (that is the type parameter to A) such that we can refer to it in the parameter list of the run() method. Here is my shot:

class D {
  type Q = X forSome { type X; }
}

class C extends B {
  this: A[D#Q] =>
      
  def run(t:D#Q ) {}
  def get: D#Q = "hello world"
}

Unfortunately this results in a compilation error with Scala 2.7.5

error: class C needs to be abstract, since method run in trait A of type (T)Unit is not defined

and in a AssertionError for Scala 2.8.0.r18604-b20090830020201

Exception in thread "main" java.lang.AssertionError: assertion failed: michid.iterator.A[T]
at scala.Predef$.assert(Predef.scala:107)
at scala.tools.nsc.symtab.Types$TypeRef.transform(Types.scala:1417)
at scala.tools.nsc.symtab.Types$TypeRef$$anonfun$baseTypeSeq$3.apply(Types.scala:1588)
...

I created Ticket #2091 for these problems.





Scala for Sling @ Jazzon 09

26 06 2009

Yesterday I gave a presentation at Jazoon 09 about using Scala for scripting RESTful web applications with Apache Sling.

In the session I showed how to take advantage of Scala to create RESTful web applications with Apache Sling. I demonstrated how to uses its DSL capability and support for XML literals to create type safe web site templates. In contrast to conventional web site template mechanisms (e.g. JSP), this does not rely on a pre-processor but rather uses pure Scala code.

There are Session slides and support material available here. The support material contains a fully workable demo application. A Scala scripting bundle for Sling is also included.





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?