Monday, June 14, 2010

Working around Dependent Method Types with Structural Types

Until dependent method types move out of experimental status in the scala compiler (they can be enabled with -Xexperimental) we have been using Structural Typing to work around their absence.

Here's how were doing it:

First, Given:

trait AToB {
    type B
    def b : B
}

and an implementation:

trait AToInt extends AToB {
    final override type B = Int
}

object AToInt {
    def apply(x : Int) = new AToInt {
        final override val b = x
    }
}

We would like to write a function with given any AToB
returns the type of B specified by that A:

if we had dependent method types we could write this as

def bOf[A <: AToB](a : A) : a.B = a.b

however this gives the error:

error: illegal dependent method type
          def bOf[A <: AToB](a : A) : a.B = a.b

To work around this however and still preserve type safety we have been doing this:

def bOf[AA <: AToB {type B = BB}, BB](a : AA) : BB = a.b

Basically we are using a structural type to fix the abstract type B in AToB to a concrete
type BB. This will enforce the type constraint that we want. There is one annoyance that remains
however and I haven't figured out a solution for it yet, the compiler is inferring the wrong type
for BB.

val x : Int = bOf(AToInt(5))

gives the compiler error:

error: inferred type arguments [java.lang.Object with AToInt,Nothing] do not conform to method bOf's type parameter bounds [AA <: AToB{type B = BB},BB]

yuck, the work around is to say:

val x : Int = bOf[AToInt, AToInt#B](AToInt(5))

Which will compile correctly.

A few more examples which will not compile:

trait AToString extends AToB {
    final override type B = String
}

object AToString {
    def apply(x : String) = new AToString {
        final override val b = x
    }
}


//Will not compile
val x : String = bOf[AToInt, AToInt#B](AToInt(5))
//Will compile
val x : String = bOf[AToString, AToString#B](AToString("Good Times"))
//Will not compile
val x : Int = bOf[AToString, AToString#B](AToString("Good Times"))

2 comments:

missingfaktor said...

With dependent method types, I can write:

def identity(x: Any): x.type = x

which when passed an Int returns an Int, when passed a String a String, and so on.

How can we achieve the same with the workaround you've proposed here?

Ben Jackman said...

You don't need dependent method types to encode the identity function:

scala> def id[A](x: A) : A = x
id: [A](x: A)A

scala> id(5)
res2: Int = 5

scala> id("Foo")
res3: java.lang.String = Foo

Do you have a more complex example that mimics something you are trying to accomplish?