Sunday, March 16, 2008

Implicit conversions - magical and demonic

Implicit conversion is a useful mechanism, because it lets you extend libraries retroactively, without actually changing them. Let's take a common example.

We would like to repeat some String, say "nice" three times. We could write it as:
def *(times: Int, original: String) = {
def multiply(times: Int): String = {
if(times > 1) original + multiply(times - 1)
else original
}
multiply(times)
}

As a bit of a sidenote, multiply is not tail-recursive, because its recursive call is not the last thing it does. So it will blow up the stack space. Here's how we can make it tail recursive:
def *(times: Int, original: String) = {
def multiply(times: Int, accumulated: String): String = {
if(times > 1) multiply(times - 1, accumulated + original)
else original + accumulated
}
multiply(times, "")
}

This technique is called accumulation. We use additional parameter 'accumulated' to pile up the result incrementally. Now the compiler can optimize the recursive calls, and stack won't grow every call.

With '*' method defined in some object, and imported in use-site, we could now multiply strings with *("nice", 3). However, it's not as nice as we would like it to be, e.g. "nice" * 3. But how can we get there, because obviously we can't go and put the '*' method to String class. Well, the first thing to do is to create a class StringRepeated that has that method.
class StringRepeated(original: String){
def *(times: Int) = {
def multiply(times: Int, accumulated: String): String = {
if(times > 1) multiply(times - 1, accumulated + original)
else original + accumulated
}
multiply(times, "")
}
}

Now if we create a StringRepeated, we can use the '*' like this:
val repeated = (new StringRepeated("nice")) * 3
// == "nicenicenice"


But we can't do this on normal Strings directly. The implicit conversion is what comes to rescue; it makes the conversion from String to StringRepeated.

implicit def string2repeated(x: String) = new StringRepeated(x)

That's it. Now when compiler sees a "nice" * 3, it first concludes that there is no '*' method defined in String. Then it looks for implicit conversion that would give a new object that has a '*' with correct parameter type. If there is no ambiguouty in choosing what implicit conversion to apply, the compiler will insert the conversion.

So "nice" * 3 will be statically translated to something like (new StringRepeated("nice")) * 3.

Now as this small example shows, implicit conversion can be somewhat handy. For additional example, I have an application that prints text that is partly colorized or otherwise styled. I have taken advantage of implicit conversion so that I can write printWith("Hi," | "this" * Bold | " is " * Fore(RED) | "cool."). It will print sequentially "Hi, this is cool."

Now I like this feature, but I think it's a bit dangerous. It's not always easy to see what conversions are happening, because they are automatically inserted. Good news is that you can control their use scope by importing the implicit conversions only to places where you really want them. Next I give you an example that combined with another unfortunate feature makes my head steam.

In Scala == is structural equality test method, unlike in Java, where it is reference equality test. It takes one argument type of Any, which means you can compare your object against any object. I mean any, and compiler will allow you that. Doesn't sound too bad, you say? Well, if you have lots of inheritance, you might really want that ability, so that you can reveal whether two objects are the same even if their static type is not the same. But usually I just want to know two statically equivalently typed objects to be tested against each other, not arbitrary objects.

I have had problems with this simply, because you don't always compare things you should. Humans do mistakes (I sometimes wonder, am I ever doing something *right*). For example, I might have a tuple of Ints, which has name 'boom'. And i have another tuple 'doom', and I'd like to compare their first elements, i.e. boom._1 == doom._1. But I might be a bit sleepy, and write "boom == doom._1", i.e. comparing a tuple against an Int. Compiler won't say that you are comparing completely different objects. It just sings logically incorrect bytecode. It might be very hard to notice that the comparison isn't ever going to give a true value just by testing it few times.

Ok, that's bad enough as it is, but when we mix implicit conversions with this magical soup, we are really doomed. An example: String has no reverse method. Therefore it has been extended with RichString in the same kind of way I described earlier for RepeatedString. When you say "yay" reverse, you get a RichString, not String. Guess what, "yay".reverse == "yay" won't give you true. Happy debugging times ahead, my friend. It isn't helping that with type inference in use, even with intermediate variables (val x = "yay" reverse) you might think you're dealing with a normal String. That might happen if you just forgot that there ever was a RichString class, and thought that reverse was defined in String.

My conclusion (temporary, as they always are) is that when you need concise syntax for some operations, give a thought about implicit conversions. But be sure to think carefully how it interacts with other types, and especially if you are dealing with multiple conversions.

True wizards use their magic sparingly.

4 comments:

Michael said...

Regarding "yay".reverse == "yay".
See http://lampsvn.epfl.ch/trac/scala/ticket/1495

naedyr said...

I can confirm that this is now fixed in scala 2.8.0.

It's interesting that the exact same bug is present in clojure however ...

naedyr said...

ie:
user=> (= (reverse (new String "ada")) (new String "ada"))
false
user=> (reverse (new String "ada"))
(\a \d \a)

Stuart Sierra said...

Clojure's reverse is defined to always return a sequence, regardless of the type of its argument. This has nothing to do with implicit type conversion, which Clojure does not do.

user=> (reverse "ada")
(\a \d \a)
user=> (apply str (reverse "ada"))
"ada"
user=> (= (apply str (reverse "ada")) "ada")
true