Skip to content
Print

Implicit Conversions: More Powerful than Dynamic Typing?

15
Sep
2008

One of the most surprising things I’ve ever read about Scala came in the form of a (mostly positive) review article.  This article went to some lengths comparing Scala to Java, JRuby on Groovy, discussing many of its advantages and disadvantages relative to those languages.  Everyone seems to be writing articles to this effect these days, so the comparison in and of itself was not surprising.  What was interesting was an off-hand comment discussing Scala’s “dynamic typing” and how it aids in the development of domain specific languages.

Now this article had just finished a long-winded presentation of type inference and compilation steps, so I’m quite certain that the author was aware of Scala’s type system.  The more likely target of the “dynamic typing” remark would be Scala’s implicit conversions mechanism.  I have heard this language feature described many times as being a way of “dynamically” adding members to an existing class.  While it would be incorrect to say that this feature constitutes a dynamic type system, it is true that it may be used to satisfy many of the same design patterns.  Consider the facetious example of a string “reduction” method, one which produces an acronym based on the upper-case characters within the string:

val acronym = "Microsoft Certified Systems Engineer".reduce
println(acronym)            // MCSE

The immediate problem with this snippet is the fact that string literals are of type java.lang.String, a class which comes pre-defined by the language.  The only way to ensure that the above syntax works properly is to “add” the reduce method to the String class separate from its definition.  In a language such as Ruby or Groovy which have dynamic type systems, we could simply open the class definition and add a new method at runtime.  However, in Scala we have to be a bit more tricky.  We can’t actually add methods to an existing class, but we can define a new class which contains the desired method.  Once we have that, we can define an implicit conversion from our target class to our new class.  The Scala compiler sees this and performs the appropriate magic behind the scenes.  In code, it looks like this:

class MyRichString(str: String) {
  def reduce = str.toCharArray.foldLeft("") { (t, c) =>
    t + (if (c.isUpperCase) c.toString else "")
  }
}
 
implicit def str2MyRichString(str: String) = new MyRichString(str)

This contrasts quite dramatically with the Ruby implementation of the same concept via open classes (somewhat less-graciously known as “Monkey Patching”):

class String
  def reduce
    arr = unpack('c*').select { |c| (65..90).include? c }
    arr.pack 'c*'
  end
end
 
puts 'HyperText Transfer Protocol'.reduce       # HTTP

No visible type conversion is taking place here, all we did is add a method to an existing class and trust that the runtime can figure out the rest.  Indeed, for this application, we don’t really need anything else.  However, as anyone with experience implementing internal domain-specific languages will tell you, seldom is life as simple as adding a few methods to an existing class.  Consider a more complicated scenario where we need to overload the < operator on integers to operate on String values, returning true if the length of the string is less than the integer value, otherwise false.  In Scala, we would once again make use of the implicit conversion mechanism, this time with an even more concise syntax:

implicit def lessThanOverload(i: Int) = new {
  def <(str: String) = str.length < i
}

In fact, we don't even need to go this far.  It is possible to create an implicit conversion from String to Int defined on the length of the String.  This would allow existing method implementations within the Int class to operate upon String values:

implicit def str2Int(str: String) = str.length

As a matter of interest, this particular situation can be managed by one of the most convoluted and verbose languages on the market, C++:

bool operator<(const int &i, const std::string &str)
{
    return str.length() < i;
}

Despite the seemingly-dynamic nature of the problem, the statically typed language camp seems well represented in terms of solutions.  Ironically, this sort of problem is one which will be exceedingly difficult to solve in a language like Ruby.  This is primarily because method overloading is an innately static device.  That's not to say that overloading is impossible in a dynamically typed language (Groovy), but it's not easy.  To see why, let's consider the most natural implementation of our operator problem in Ruby:

class Fixnum
  def <(str)
    str.size < self
  end
end

Intuitively, this may seem like the right way to approach the problem, but the results of such an implementation would be disastrous.  At the very least, the first time anyone attempted to perform a < comparison targeting an integer, the interpreter will overflow the call stack.  In fact, any time any code uses the less-than operator on an instance of Fixnum, the interpreter will crash.  The reason for this is the invocation of < upon str.size within our "overloaded" definition.  This call creates a very tight recursive loop which will very quickly eat through all available stack frames.  We can avoid this problem by reversing the comparison like so:

class Fixnum
  def <(str)
    self >= str.size
  end
end

Now we don't have to worry about stack overflow, but in the process we have accidentally redefined integer-to-integer comparison in a very strange way:

irb(main):006:0> 123 < 'test'
=> true
irb(main):007:0> 123 < 123
=> true

Clearly, more effort is going to be required if we are to put to rest our little dilemma.  As it turns out, the final solution is surprisingly ugly and verbose:

class Fixnum
  alias_method :__old_less_than__, '<'.to_sym
  def <(target)
    if target.kind_of? String
      __old_less_than__ target.size
    else
      __old_less_than__ target
    end
  end
end

Whatever happened to Ruby as a "more elegant" language?  The unfortunate truth is that in order to emulate method overloading based on input type, we must hold onto the old method implementation while we implement a type-sensitive facade in its place.  The alias_method invocation literally copies the old less-than operator implementation and provides us with a way of referencing it within our later redefinition.  And what happens if someone else happens to monkey patch Fixnum and (for whatever reason) uses the identifier "__old_less_than__"?  Well, then we have problems.  It's like the old days of Lisp macros and endless identifier collisions.

It is true that this was an example specifically contrived to make Ruby look bad.  I could have implemented the overload using Groovy's meta-classes and been reasonably certain that everything would work out fine, but that's not the point.  The point is that there are a surprising number of situations where static typing serves not only to check for errors but also to allow extension patterns which would be otherwise impossible (or very, very difficult).  Dynamic typing isn't the panacea of extensibility that its proponents make it out to be, sometimes it isn't quite up to the task.

In fact (and this is where we come to my Digg-friendly point), I would submit that Scala (and to a lesser extent, C++) have created a mechanism for controlled extensibility which is more powerful than Ruby's open classes design.  That's not to say that there aren't situations which are easily solved using open classes and entirely intractable using only implicit conversions, but in my experience these scenarios are very rare.  In fact, I believe that it is far more common to run against a problem like my contrived overload which is greatly simplified through the use of static typing.

Ironically enough, some of Ruby's greatest pundits are starting to come around to the belief that a more controlled and well-defined model of class extension is required.  ParseTree is a Ruby framework which provides mechanisms for dynamically manipulating the AST of an expression prior to evaluation.  Conceptually, it is very similar to Lisp's macros and peripherally related to .NET's expression trees (used in LINQ).  ParseTree is used by a number of complex Ruby domain-specific languages, including Ambition, a fact which is extremely telling of how great the need is for just such a tool.  Having myself attempted a domain-specific language for constructing queries, I can state categorically that to do such a thing solely on the basis of open classes would be nearly impossible.  Even if successful, such a framework would be extremely volatile, sensitive to the slightest change in the Ruby core library, either caused by update or by other packages injecting their own meddlesome implementations into runtime classes.

Lex Spoon (co-author of Programming in Scala) once said that any language which seriously targeted domain-specific languages would have to create some sort of implicit conversion mechanism.  At the time, I was skeptical, convinced that Ruby (and similar) would always have the upper-hand in the area of class extension due to their dynamic treatment of modules and classes.  However, after some serious dabbling in the field of internal domain-specific languages, I'm beginning to come 'round to his point of view.  Implicit conversions are far from a weak imitation of Scala's dynamically typed "betters", they are a powerful and controlled way of extending types far beyond anything which can be easily accomplished through open classes.

Comments

  1. Your post reminds me of the proposed feature for Java 7 called “Extension methods”. It basically lets you add methods to an interface, without breaking it. Neal Gafter blogged about it here: http://gafter.blogspot.com/2007/11/closures-prototype-update-and-extension.html.

    import static java.util.Collections.sort;

    List list = …;
    list.sort();

    instead of

    import java.util.Collections;

    List list = …;
    Collections.sort(list);

    It doesn’t really extend anything, but it gives you the feeling you are using the same interface with new methods. I don’t thing it’s as nice and “dynamic” as Scala’s implicits, but it would serve the purpose of “extending” interfaces.

    David Linsin Monday, September 15, 2008 at 12:32 am
  2. I don’t think it’s correct to say that dynamically typed language can’t be as extensible as statically typed ones. You can certainly implement an extensible dynamic dispatch system that dispatches on all function argument types in a dynamic language, CLOS multimethods is an example.

    However, static polymorphism is a great tool for error checking and IMO a good, statically typed language should support both static and dynamic polymorphism. Dynamic polymorphism will always be required for those cases where the compiler don’t have enough type information, i.e. external input at runtime. Haskell does this through type classes and existential types/function values, Scala has implicits (not as powerful as type classes) and subtyping. Java only has a very limited form of static polymorphism, function overloading.

    Jesper Nordenberg Monday, September 15, 2008 at 12:58 am
  3. Actually scala implicits is exactly as powerfull as haskell typeclasses.

    Felicia Svilling Monday, September 15, 2008 at 3:40 am
  4. Implicit type conversions are actually far more powerful than extension methods. You can *emulate* the behavior of extension methods using implicits, but it is also possible to do much more. Specifically, the syntactically-transparent conversion from one type to another. This seems rather obvious even in the name of the language feature, but it is actually a terribly profound language feature, one which dynamic languages cannot easily emulate.

    Extension methods as proposed for Java 7 are really much closer to those available in C# 2.0: a static method which is imported into the scope and then implicitly available for dispatch on its first formal type. For most cases, this is sufficient. Unfortunately, there are some more difficult scenarios to handle with this sort of scheme, specifically higher-order type constructor polymorphism. Meijer has an interesting paper which discusses some of the weakness in C# extension methods and how it led to less-strict type checking in LINQ. It turns out that to be parametrically fully polymorphic using extension methods requires higher-kinds due to the added indirection of the formal parameter. Scala doesn’t have this problem since its “extension methods” have an enclosing instance which can manage the polymorphism in a lower-order setting. Ironically, Scala also has higher-kinds, which means that it *could* have extension methods alla C# and still satisfy all of the same cases.

    It is true that function overloading is possible in dynamically typed languages, but it isn’t a common thing to implement. Also, it tends to bring up some odd corner cases (ahem, Groovy). In any case, overloading is not the most compelling to favor static typing over dynamic for domain-specific languages, it’s just the most easily illustrated. The actual conversion facility is much more powerful than it is given credit for.

    Daniel Spiewak Monday, September 15, 2008 at 9:10 am
  5. Felicia, implicits as implemented in Scala are not as powerful as Haskell type classes. There are things you can’t implement in Scala using only implicits, for example HList. The reason for this is that type parameters are inferred before implicits are resolved (see my blog for details). This could potentially be fixed, but according to Martin it would be non-trivial to do.

    Jesper Nordenberg Monday, September 15, 2008 at 11:05 am
  6. the idea implicit conversion is a nice thing, however Scala’s implementation is not IMHO.

    For example the Ordered[T] trait and implicit conversion cry for programming errors

    def areEqual[T

    Michael Nischt Tuesday, September 16, 2008 at 9:31 am
  7. ok, I’m not able to post code so please have a look at the areEqual method and see why I dislike Scala’s implicit conversions:

    http://gestalt.monoid.net/stuffu/ImplicitOrdered.scala

    The problem is that a conversion takes place if and only if a matching method is not present. However in some cases it should convert, if the target type of the conversion has a matching method (even if the other has too).

    Michael Nischt Tuesday, September 16, 2008 at 9:53 am
  8. I think one of the key points, which you did not quite explicitly state, is that you can precisely control the scope of implicit conversions in Scala. Thus if you are creating an implicit conversion which could potentially cause problems in code not expecting it, such as your unusual less-than example, you can define the implicit conversions in (or import them into) only the class or block of code where you need them.

    Jim McBeath Wednesday, September 17, 2008 at 6:39 pm
  9. “One of the most surprising things I’ve ever read about Scala came in the form of a (mostly positive) review article.”

    Could we get a link to said article?

    David Gates Wednesday, September 24, 2008 at 5:02 am
  10. @David

    I wanted to provide a link right in the article, but I couldn’t find it. Seriously, I spent a good two hours Googling around to no avail.

    Daniel Spiewak Wednesday, September 24, 2008 at 10:11 am
  11. A good read, thank you. That being said, your Ruby example is not representative of how to go about overriding or extending methods. I would go so far as to say it is a very poor example of Ruby metaprogramming ,period. These comments are not the place for code examples, but if you care to google the subject for a few minutes, you will come up with several far superior ways solve this problem in Ruby.

    Still an interesting point about the benefits of static analysis, though.

    Reg Braithwaite Wednesday, October 1, 2008 at 5:04 am
  12. @Reg

    I spent some time Googling, and I’m afraid I still don’t know what you mean by “several far superior ways”. I am of course aware of ParseTree, but I wanted to show the problems with such overriding without tapping the power of rewritable S-expressions. I am truly unaware of any substantively different method for accomplishing the Fixnum < override.

    I will agree that it is a poor example of Ruby though. :-) I deliberately went after an example which had type-dependent behavior. Ruby is *never* going to behave as nicely as a static language in that case.

    Daniel Spiewak Wednesday, October 1, 2008 at 9:47 am
  13. If you google “ruby alias,” the very first hit is:

    http://blog.jayfields.com/2006/12/ruby-alias-method-alternative.html

    Which addresses the mess that is unhygienic method aliasing in a manner that is isomorphic to a very old way to deal with variable captures in Lisp macros. And quite honestly, there are other things you can do to solve the problem you are posing in a Rubyesque way without rewriting (although for some reason rewriting comes to my mind).

    But I think there’s an interesting point you are making about implicit conversions, so I really don’t want to go too far down the road of debating what I would do in Ruby if I wanted to accomplish the same thing. I am a fan of static typing for enforcing domain constraints on programs, and some of these metaprogramming-like concepts are delightful to explore.

    Reg Braithwaite Wednesday, October 1, 2008 at 5:03 pm
  14. Interesting, I wasn’t aware that you could capture a method reference in that fashion. It certainly does solve the problem of name collision. I don’t particularly like defining methods using define_method and a block (it’s a memory leak waiting to happen), but it makes sense here and I can’t think of any horrendous consequences. Thanks for the heads up! :-)

    Daniel Spiewak Wednesday, October 1, 2008 at 6:41 pm
  15. “I don’t particularly like defining methods using define_method and a block (it’s a memory leak waiting to happen)” => Funny thing, I have some issues with it as well, but from time to time I think about a hypothetical language called “R” where “R is to Ruby as Scheme is to Common Lisp.”

    In R, all blocks are full closures and that’s also the only way to define a method, no messy three and four ways to do the same thing :-)

    Reg Braithwaite Thursday, October 2, 2008 at 7:18 am
  16. I believe that the proposed Java extension methods are indeed similar to the C# equivalent that exists today. However, unless I missed something, I would think that extension methods are much more akin to method implementations in traits than to implicit type conversions.

    Both features can play well together of course.

    jmalcolm Tuesday, July 27, 2010 at 12:25 pm
  17. I don’t see the connection between using ParseTree and the earlier example you gave. Or were you just saying that the existence of ParseTree implies that Ruby needs “help” to handle DSL’s well?

    roger Wednesday, December 7, 2011 at 12:58 pm

Post a Comment

Comments are automatically formatted. Markup are either stripped or will cause large blocks of text to be eaten, depending on the phase of the moon. Code snippets should be wrapped in <pre>...</pre> tags. Indentation within pre tags will be preserved, and most instances of "<" and ">" will work without a problem.

Please note that first-time commenters are moderated, so don't panic if your comment doesn't appear immediately.

*
*