Revisiting higher-rank impredicative polymorphism in Scala

I've been meaning to write this up for a while, but it seems like there has always been something else I really ought to be doing. So I expect this will be a bit more terse than I might like. Anyway, when I wrote about encoding higher-rank universal quantification in Scala back in March, I used a rather elaborate scheme involving the use of Scala's first-class existential quantifiers. While this was the point of the exercise, surprisingly, no one called me on the fact that if you just want higher-rank impredicative polymorphism in Scala, there is a much simpler encoding. Maybe it was obvious to everyone or no one read closely enough to think of raising the issue. So today, I'll explain the better way to encode them.

First we can define an infinite family of traits to represent n-ary universal quantification, much like Scala represents n-ary functions types:

  1.  
  2. trait Univ1[Bound1,Body[_]] {
  3. def Apply[T1<:Bound1] : Body[T1]
  4. }
  5.  
  6. trait Univ2[Bound1,Bound2,Body[_,_]] {
  7. def Apply[T1<:Bound1,T2<:Bound2] : Body[T1,T2]
  8. }
  9.  
  10. // ... so on for N > 2
  11.  

Really, the key to this encoding is the use of higher-kinded quantification to encode the binding structure of the quantifier.

Now it is possible to write some examples similar to what I gave previously, but more concisely:

  1.  
  2. object Test extends Application {
  3. def id[T](x : T) = x
  4.  
  5. type Id[T] = T => T
  6. val id = new Univ1[Any,Id]
  7. { def Apply[T <: Any] : Id[T] = id[T] _ }
  8.  
  9. val idString = id.Apply[String]
  10. val idStringList = id.Apply[List[String]]
  11.  
  12. println(idString("Foo"))
  13. println(idStringList(List("Foo", "Bar", "Baz")))
  14.  
  15. type Double[T] = T => (T, T)
  16. val double = new Univ1[Any,Double]
  17. { def Apply[T <: Any] : Double[T] = (x : T) => (x, x) }
  18.  
  19. val doubleString = double.Apply[String]
  20. val doubleStringList = double.Apply[List[String]]
  21.  
  22. println(doubleString("Foo"))
  23. println(doubleStringList(List("Foo", "Bar", "Baz")))
  24. }
  25.  

As I mentioned previously, this example would be much improved by support for anonymous type functions in Scala. I am pretty sure Scala will eventually support them, as they would not require any deep changes in the implementation. They could be just implemented by desugaring to a higher-kinded type alias with a fresh name, but depending on when that desugaring is performed, it is possible that it would result in poor error messages. Supporting curried type functions is also quite desirable, but given my current knowledge of the internals, that seems like adding them will require some more elaborate changes.

I think Vincent Cremet was the first person to suggest this sort of encoding, and I vaguely recall reading about it on one of the Scala mailing lists, but I could not find the message after a little bit of time spent searching.

4 Comments »

  1. Matt Hellige said,

    May 28, 2008 @ 12:16 am

    One thing that makes this a little more annoying than one would like is that one has to define a new Univ not just for each number of type parameters, but for each different combination of kinds as well:

    trait Univ1Again[Bound1,Body[Bound1[_]]] {
    def Apply[T1[_] <: Bound1] : Body[T1]
    }

    and so on… This makes the required family of Univs irritatingly large.

    But anyway it’s a very nice trick, and anonymous (and curried) type functions would make it even nicer.

  2. washburn said,

    May 28, 2008 @ 12:49 pm

    @Matt: True. The problem had occurred to me at some point, as well as the problem that this only gives you upper bounds for the quantified types, but I didn’t think of it when I wrote up the above. The latter could be fixed as

    trait Univ1[UBound1,LBound1<:ubound1 ,Body[_]] {
       def Apply[T1>:LBound1<:ubound1 ] : Body[T1]
    }
    

    Kind polymorphism could be used to address the problem of requiring n variations of Univ1, but it is something that I do not think is considered critical enough that it would be implemented in the near future. Virtual classes and dependent method types, among other things, are higher priority at the moment.

  3. Vincent Cremet said,

    November 20, 2008 @ 4:10 pm

    You wrote: “I think Vincent Cremet was the first person to suggest this sort of encoding, and I vaguely recall reading about it on one of the Scala mailing lists, but I could not find the message after a little bit of time spent searching.”

    I found the message you mention (it was in the old list called “scala-lounge”):

    http://article.gmane.org/gmane.comp.lang.scala.user/697

    The idea of your encoding is the same as mine (except you use the name “Univ” instead of “Forall”). But your blog article is more complete as it also describes how to treat bounds and how to quantify over more than one type variable.

  4. First-class polymorphic function values in shapeless (2 of 3) — Natural Transformations in Scala | Chuusai said,

    May 10, 2012 @ 8:36 am

    […] encoding of polymorphic function values in Scala has been around for quite some time — in fact more or less from the point at which higher-kinded types arrived in the […]

RSS feed for comments on this post · TrackBack URI

Leave a Comment