Monday, October 13, 2008

Polymorphism Using Implicit Conversions

In the Java implementation of one of my applications I had a few methods that accepted or returned null to indicate a missing value. These were originally designed this way because they were layered on top of some Swing calls which used the same practice. When I converted the app from Java to Scala, I decided to use Option for these interfaces in order to avoid nulls.

Contents

Motivation

To start with, I implemented some Scala methods that called the Java methods that might return null and converted their return values into an Option. I wanted to be able to pass these values directly to some other Scala methods, so I designed those methods to accept Option values as well.

In one case, the Java code included a class with two methods overloading the same name, one with an optional File argument and the other with an optional String argument (representing a file name). Simplified for expository purposes, the Java methods looked something like this:
//Java code import java.io.File; public class Foo { //name is optional, may be null public void bar(String name) { } //f is optional, may be null public void bar(File f) { } }
In my initial conversion attempt to Scala, I tried some code that looked something like this:
import java.io.File class Foo { def bar(fOpt:Option[File]):Unit = { } def bar(nameOpt:Option[String]):Unit = { } }
However, this did not compile, because the signature of the two methods is identical after type erasure, which makes Option[File] indistinguishable from Option[String].

Solution

After some discussion and suggestions from the Scala mailing list, I came up with a design using implicit conversions, and realized it is in fact another way to implement functions which are polymorphic on the type of one argument.

Rather than defining multiple functions with different signatures, I defined a single function which accepts a special type that I defined. That type is a sealed case class that can represent the set of types that my function understands.

Although the actual function implementation accepts a single type, the use of implicit conversions makes it effectively behave the same as if there were multiple functions, each accepting a value of one of the implicit conversion input types. The function receives enough information in the parameter to determine the type of the argument passed in, so it can arbitrarily modify its behavior based on the type of the argument, which is a requirement of true polymorphism.

In this case, since my original functions understood String, File and null arguments, my type definition looked like this:
import java.io.File sealed abstract class BarArg case class BarString(s:String) extends BarArg case class BarFile(f:File) extends BarArg case object BarNothing extends BarArg
There is now a single bar function that combines the functionality of the previous multiple functions of that name. For this example, the bar function looks like this:
def bar(b:BarArg) = { b match { case BarString(s) => println("Got a String "+s) case BarFile(f) => println("Got a File "+f) case BarNothing => println("Got a Nothing") } }
The BarArg class is sealed, so the Scala compiler can figure out that the cases in the match statement are complete, and we don't need a default case.

With the above definitions I can call bar(BarString("abc")), but I want to be able to pass it a String or File directly. I also want to be able to pass in an Option of either type and have it appropriately converted from None to BarNothing or from Some to BarString or BarFile. In order to do this, I created a set of implicit conversions:
object BarArg { implicit def stringToBarString(s:String):BarArg = if (s==null) BarNothing else BarString(s) implicit def fileToBarFile(f:File):BarArg = if (f==null) BarNothing else BarFile(f) implicit def optionStringToBarString(s:Option[String]):BarArg = s match { case None => BarNothing case Some(ss) => BarString(ss) } implicit def optionFileToBarFile(f:Option[File]):BarArg = f match { case None => BarNothing case Some(ff) => BarFile(ff) } }
The implicit conversions are packaged up in an object so that they can be imported into the application calling bar:
import BarArg._
With this set of implicit conversions in scope, the following all work:
bar("abc") bar(new File("f")) bar(BarNothing) bar(BarFile(new File("g"))) bar(BarString("def"))

Modifications

Unfortunately, bar(None) does not work because the compiler does not know if None is an Option[String] or an Option[File], so the implicit conversions are ambiguous and it is unable to apply one. The compiler gives the same complaint for bar(Some("abc")) (as of Scala version 2.7.2, although this may be a bug). We can work around this limitation in two ways: either by explicitly declaring the type on the None or Some we are passing in, or by setting the Some value into a variable (or setting the None value into a variable of the appropriate declared type) and passing that to bar. The following examples work:
bar(None:Option[String]) bar(Some("abc"):Option[String]) bar(Some[String]("abc")) val n:Option[String] = None; bar(n) bar{val n:Option[String] = None; n} val s = Some("abc"); bar(s) bar{val s = Some("abc"); s}
In addition, we can pass in Some("abc") directly if we modify slightly our implicit conversion functions to accept type parameters with an upper bound:
implicit def optionStringToBarString[T<:String](s:Option[T]):BarArg = s match { case None => BarNothing case Some(ss) => BarString(ss) } implicit def optionFileToBarFile[T<:File](f:Option[T]):BarArg = f match { case None => BarNothing case Some(ff) => BarFile(ff) }
Since the BarArg type is only used when calling our bar function, the implicit conversions will only be applied to those calls, so it is safe for those implicit conversions always to be in scope.

Summary

We can use this technique as an alternative to function overloading when we want a polymorphic function that accepts multiple types for one of its arguments. We do this with the following steps:
  • Define our own set of case classes for that argument that define the set of types we accept
  • Ensure that our function handles those types
  • Define a set of implicit conversions to those case classes
  • Import those implicit conversions into our calling application
This technique allows you to create a single method with a parameter that can accept one of a selected number of types, which can be disjoint (such as String, Int and Point), yet still have the compiler type check for you to prevent passing an unsupported type (such as Double) for that parameter. This is useful in situations where polymorphism by overloading can not be done because of type erasure. Although similar in some respects to ad-hoc type coercion polymorphism, in this case we are able to set things up so as to be able to detect the difference in the way the method was called and thus to behave differently based on that type.

Update 2008-11-04: Michael Dürig posted his solution to this problem (writing a method to accept two different types that are identical after type-erasure) back in January of this year. His approach is slightly different, but also uses implicit conversions.

Update 2009-03-12: Mitch Blevins has a better implementation that he calls stuttering-or, using "or" as a type infix operator to allow combining disjoint types.

2 comments:

Mitch Blevins said...

An alternate approach inspired by this idea:
http://cleverlytitled.blogspot.com/2009/03/so-i-read-both-jim-mcbeath-and-michids.html

Jim McBeath said...

Mitch: Very nice implementation. I am happy to have been the inspiration for your improved version.