Hitting the wall

In my last post, I translated the first part of Data types a la carte into Scala. I decided to push ahead into the next section, just for fun. The summary is: Scala's implicits are a very poor man's type classes, at least using the obvious encoding, and I am as always humbled by the cleverness of GHC.

Things start out ok:

trait Less[Sub[_],Sup[_]] {
  val subF: Functor[Sub]
  val supF: Functor[Sup]
  def inj[A](sub: Sub[A]): Sup[A]
  def prj[A](sup: Sup[A]): Option[Sub[A]]
}

implicit def ReflLess[F[_]](fF: Functor[F]) =
  new Less[F,F] {
    val subF = fF
    val supF = fF
    def inj[A](sub: F[A]): F[A] = sub
    def prj[A](sup: F[A]): Option[F[A]] = Some(sup)
  }

The other two instances, LeftLess and RightLess, are equally obvious. Recall that the point here is to treat Sum as a cons-list, so we'll have two more instances like:

implicit def LeftLess[F[_],G[_]](fF: Functor[F], gF: Functor[G]) =
  new Less[F,Apply2Of3[Sum,F,G]#It] { ... }
implicit def RightLess[F[_],G[_],H[_]](fF: Functor[F], gF: Functor[G],
    hF: Functor[H], fgLess: Less[F,G]) = 
  new Less[F,Apply2Of3[Sum,H,G]#It] { ... }

but I won't bother to show them.

The point of this exercise is to make it easier to write expressions like the last post's addExample. So we define:

def inject[F[_],G[_]](g: G[Expr[F]])(implicit gfLess: Less[G,F]): Expr[F] =
  Expr[F](gfLess.inj(g))

def value[F[_]](v: Int)(implicit less: Less[Val,F]): Expr[F] =
  inject[F,Val](Val(v))

def sum[F[_]](l: Expr[F], r: Expr[F])(implicit less: Less[Add,F]): Expr[F] =
  inject[F,Add](Add(l,r))

Unfortunately, this is pretty much where the fun ends. We'd really like to write something like:

val addExample2: Expr[Apply2Of3[Sum,Val,Add]#It] = 
  value(30000) |+| value(1330) |+| value(7)

But first, we can't define sum as an infix operator without an implicit conversion, so we'll try this first:

  sum(value(30000), sum(value(1330), value(7)))

It's not great, but it's workable, and we could try an implicit conversion if we really want the infix syntax. But in fact the problems are much worse. First, we need to add a type annotation to every single application:

type Tmp[X] = Apply2Of3[Sum,Val,Add]#It[X]
val addExample2 = sum[Tmp](value[Tmp](30000),
  sum[Tmp](value[Tmp](1330), value[Tmp](7)))

But then we have problems with implicits: Scala is incapable of chaining the implicit conversions necessary to compile this expression. So we need to write them by hand, and they're getting ugly:

implicit val Ugh1: Less[Val,Apply2Of3[Sum,Val,Add]#It] =
  LeftLess[Val,Add](ValFunctor, AddFunctor)
implicit val Ugh2: Less[Add,Apply2Of3[Sum,Val,Add]#It] =
  RightLess[Add,Add,Val](AddFunctor, AddFunctor, ValFunctor,
    ReflLess[Add](AddFunctor))

Now I enjoy writing proofs as much as the next guy, but this is becoming pretty tedious... But in any case, now our definition of addExample2 works as expected, and we can write:

  eval[Tmp](addExample2)

So, this is a little better than the definition of addExample in the last post. If I needed to write code in this style, I'd certainly prefer this version. On the other hand, the necessary implicit definitions are much worse, and the improved syntax isn't nearly what we hoped for. I'd say we're at (or beyond) the limit of what we can do in Scala in this style.

What would it take to do better? Just a couple of things, from the last post, and a concrete challenge for each:

  • Better inference for higher-kinded types. I want to be able to write the definition of addExample2 above with no type annotations inside the expression (of course I will have to annotate addExample2 itself).
  • Better inference of implicit conversions and parameters. I do not want to have to define Ugh1 or Ugh2 at all. These should be inferred from ReflLess, LeftLess and RightLess.

There may be a completely different approach to this problem which is much more natural in Scala. But this approach should be possible as well, and Scala is very close to being able to express it very naturally. Implicits and inference need to be strengthened only a little bit.

Finally, just in case you were inclined to try getting the infix syntax with an implicit conversion... You might try:

trait Addable[F[_]] {
  def |+|(x: Expr[F])(implicit fgLess: Less[Add,F]): Expr[F]
} 
implicit def exprAddable[F[_]](f: Expr[F]): Addable[F] =               
  new Addable[F] {
    def |+|(g: Expr[F])(implicit fgLess: Less[Add,F]): Expr[F] = inject[F,Add](Add(f,g))
  }

val addExample3: Expr[Tmp] =
  value[Tmp](30000) |+| value[Tmp](1330)

This seems reasonable, but we again receive the following incomprehensible error:

Tmp[_]'s type parameters do not match type F's expected parameters: type Tmp has one type parameter, but type F has one

So I'm forced to conclude that implicits basically can't be polymorphic in a higher-kinded type. This is frustrating, but it's not news. This is the same reason we have to annotate everything in addExample and addExample2: just another symptom of the lack of inference for these type constructors.

Good work

Submitted by Jesper Nordenberg on Tue, 03/11/2008 - 03:39.

Coming from a Java/C++ background I can't say I understand all the details of your implementation, the higher order typing is a bit over my head ATM, but I think it's cool that you push the Scala compiler to its limit. This really drives the language forward.

I suggest you report tickets for the problems you found. Maybe they are not fixed soon, but at least they are not forgotten :)

Thanks!

Submitted by matt on Tue, 03/11/2008 - 14:45.

Thanks!

There are already one or more open bugs related to inference of higher-kinded types. I'm wary of opening a bug for enhanced inference of implicits, for a couple of reasons: first, in this case it's closely related to the type inference issue, and second, I haven't thought about it enough to be sure of what I want, whether it's a conservative improvement, etc. So for now, I guess these are directions for future work, and nothing more...

Closing comments

Submitted by matt on Wed, 07/01/2009 - 07:42.

I've been getting a lot of spam comments on this particular post (not sure why it's just this one...), so I'm closing comments. Please feel free to email me.