Scala Implicits: a dose of Magic | Part 2

In my previous post, I introduced implicits, mentioned some of the ways in which they can be used, and talked about one of their primary uses: view conversion.

Maybe you came away from that post thinking: 'hey, this looks pretty interesting, but this is too close to magic for my liking. I want to be able to write code that is understandable and maintainable, and all this under-the-covers stuff done by the compiler makes me uncomfortable'.

Well - fear not. Scala makes use of a bunch of safeguards to tame the magic of implicits. These are listed in the next section.

Rules/Safeguards for the application of Implicits

I will just mention the safeguards here; a detailed description of these rules is provided in the Programming in Scala book.

• Marking Rule: only definitions marked implicit are available for implicit conversion and parameter passing.
• Scope Rule: an implicit conversion/parameter must be in scope as a single identifier, or it must be available within the companion object of a source or target type for a conversion.
• Non ambiguity rule: an implicit conversion is used only if there is no other possible conversion available to be used.
• One at a time Rule: only one implicit is ever tried in an expression.
• Explicits first rule: implicits are tried only if there is a type error with the existing code.

Debugging Implicits

So - you have written your code with a tasteful smattering of implicits; but it does not quite do what you think it should do. Is there a way for you to figure out what's going on under the covers?

Yes. If you run scalac -Xprint:typer on your code, you will get to see exactly what's going on with implicit conversions. Let me demonstrate this with an example from my previous post. Back there, we looked at a method to find the max element in a collection:

/*
  * A module that provides aggregate operations on collections 
  */
object AggregateIterableOps {
   
   def max[A <% Ordered[A]](iterable: RichIterableOps[A]): A = {
     iterable.reduceLeft((x, y) => if (x > y) x else y)
   }
}

And the code to test it:

 @Test
   def testMaxForSet = {
     plainSet.add(18); plainSet.add(17); plainSet.add(16)
     assertEquals(18, AggregateIterableOps.max(plainSet))
   }

I spent a lot of words in the previous post trying to explain exactly what was happening under the covers with implicits in this example. This time around, let me just show you the output from scalac -Xprint:typer for the two code fragments:

  final object AggregateIterableOps extends java.lang.Object with ScalaObject {
    def this(): object implicits.AggregateIterableOps = {
      AggregateIterableOps.super.this();
      ()
    };
    def max[A >: Nothing <: Any](iterable: RichIterableOps[A])(implici
t view$1: (A) => Ordered[A]): A = iterable.reduceLeft[A](((x: A, y: A) => if (vi
ew$1.apply(x).>(y))
      x
    else
      y))
  };

And:

    @org.junit.Test def testMaxForSet: Unit = {
    TestImplicitHashSet.this.plainSet.add(18);
    TestImplicitHashSet.this.plainSet.add(17);
    TestImplicitHashSet.this.plainSet.add(16);
    org.junit.Assert.assertEquals(18, AggregateIterableOps.max[Int](this.RichCollections.toRichHashSet[Int](TestImplicitHashSet.this.plainSet))({
      ((eta$0$3: Int) => scala.this.Predef.intWrapper(eta$0$3))
    }))
  }
}

As an aside: it's pretty simple to run scalac -Xprint:typer from within Eclipse by using an 'External Tool'. This works well if you do not need to specify a classpath for scalac. If you do need to specify a classpath, things get a little tricky. I have not found anything obvious that will allow me to run an external tool with the classpath of the current Eclipse project. To do this, I make use of a little utility class that I have written; this class is available in the scrisca code repo. A screenshot of how this is used is shown below:

Let's talk next about the origins of implicits...

Origins

Implicits have their origin in Haskell type classes. I have only recently started learning Haskell, so I'm going to tread into relatively unknown territory here. But I think a comparison of implicits to type classes is instructive - so I am going to just forge on ahead and try to talk about this as well as I can.

Type classes were added to Haskell to make ad-hoc polymorphism less ad-hoc. Take operator overloading for example. With operator overloading, there are multiple versions of a function for different types, and the compiler inserts a call to the correct one based on the actual arguments to the function. As opposed to this, a generic (or parametrically polymorphic) function has just one implementation that works across a family of types.

Type classes within Haskell are a mechanism to tame ad-hoc polymorphism, bring it into the type system of the language, and to enable the writing of generic code based on the additional information provided by type classes in situations which would otherwise have required ad-hoc overloading. Let us look at an example:

class MyEq a where
    eql, neql :: a -> a -> Bool
    neql x y = not (eql x y)
    
instance MyEq Int where
    eql x y = x == y -- cheat and just use the (==) from the Eq type class

instance MyEq Char where
    eql x y = x == y -- cheat and just use the (==) from the Eq type class

member :: MyEq a => a -> [a] -> Bool
member x [] = False
member x (y:ys) | x `eql` y = True
                          | otherwise = member x ys

In the code fragment above, MyEq is a type class that defines the eql and neql operations. Int and Char are made instances of this class. Finally, member is a generic function that can work with lists of both Ints and Chars.

The same thing in Scala looks like this:

trait MyEq[a] {
  def eql(other: a): Boolean
  def neql(other: a): Boolean = !eql(other)
}

object MyEq {  
  implicit def fromInt(n: Int): MyEq[Int] = new MyEq[Int] {
    def eql(other: Int): Boolean = n == other
  }  

  implicit def fromChar(c: Char): MyEq[Char] = new MyEq[Char] {
    def eql(other: Char): Boolean = c == other
  }
}

object MyEqFuncs {
  def member[A <% MyEq[A]](a: A, as: List[A]): Boolean = as match {
    case Nil => false
    case (x::xs) => if (a.eql(x)) true else member(a, xs)
  } 
}

So how does Haskell implement type classes? Haskell translates the following code:

class MyEq a where
    eql, neql :: a -> a -> Bool
    neql x y = not (eql x y)
    
instance MyEq Int where
    eql x y = x == y

member :: MyEq a => a -> [a] -> Bool
member x [] = False
member x (y:ys) | x `eql` y = True
                          | otherwise = member x ys

Into:

data MyEqDict a = MkMyEqDict (a->a->Bool) (a->a->Bool)

eql (MkMyEqDict e _) = e
nel (MkMyEqDict _ n) = n

dEqInt :: MyEqDict Int
dEqInt = MkMyEqDict (==) (\x y -> not (x == y))

member :: MyEqDict a -> a -> [a] -> Bool
member d x [] = False
member d x (y:ys) | eql d x y = True
                             | otherwise = member d x ys

So basically, a type class is implemented via an implicit parameter, a dictionary of methods, which is passed to generic methods that work with the type class. The generic methods make use of the dictionary to work with their parameters as needed.

In Poor Man's Type Classes, Martin Odersky outlines the mapping of Haskell type classes to Scala:

type class = (trait/)^*class
instance declaration = implicit definition
context in a class = (trait) inheritance
context in a type = implicit parameter (or view bound)
dictionary = object (the target of a view conversion)
default method in (trait/)class = concrete member
method signature in (trait/)class = abstract member

^*: stuff in brackets added by me to provide additional information

Applicability to Scala

I think it is valid to ask: Scala already has a concept of traits, and an implicit this parameter/dictionary is already passed around for every (non-static) method invocation. Do we really need implicit parameters to mimic the type class context in the type of a Haskell method? Can't generic methods in Scala just make use of an upper bound on a type parameter to achieve similar functionality?

In my mind, the answer is very definitely: yes we need implicits. Implicits provide substantial additional value, over and above the OO facilites already present in Scala. My previous post talked about how implicits bring the Is-viewable-as-a relationship between objects to the table, and why this is important. This time around, let me just list some additional scenarios/problems for which the type-class/implicits approach provides good solutions:

• Object Adapters
• The problem of the tyranny of the dominant decomposition
• The expression problem
• Multiple dispatch
• Family polymorphism
• Framework integration

More information on each of these items is available in this excellent paper on type classes.

Other uses of implicits

These are based on sightings in the wild:

• Metaprogramming: http://michid.wordpress.com/code/meta-programming-with-scala-part-i-addition/ and http://matt.immute.net/content/scala-vs-skalleh
• Elegant use of Conversions to an expected type. Notice how an action listener is added to a Swing button: http://blog.tmorris.net/java-interop-errata/
• Method forwarding (when using Composition) without the pain: http://gertvanthienen.blogspot.com/2008/04/unwrapping-wrapper.html
• Default Arguments, kinda, sorta: http://cime.net/~ricky/tmp/Actor.scala
  
• Writing generic, Haskell style, code: http://www.scala-lang.org/node/114
  

Conclusion

Over the course of this (and the previous) post, I hope that I have been able to show you that:

• Implicits are an extremely powerful feature of Scala.
• Scala gives you good tools to control and diagnose the use of implements.

Have fun with Implicits! And use them (wisely) to write better code...

Relevant Reads

Programming in Scala; the chapter on Implicits
Poor Man's Type Classes
How to make ad-hoc polymorphism less ad hoc
Software Extension and Integration with Type Classes

Scala Implicits: a dose of Magic | Part 1

Implicits are an extremely powerful feature of Scala. In terms of mechanics, they are based on the following:

• Implicit definitions: these are method, val, or object definitions marked with the implict keyword.
• Implicit conversions (also called view conversions in this post): these can be further divided into:

• Conversions of a method call receiver: for this type of conversion, if a non-existent method m1 is called on an object of type X, the compiler makes an attempt to convert this source object to a target object of a type Y that contains m1. For this to succeed, a unique implicit method of type (X => Y) should be in scope at the point of call.
• Conversions to an expected type: for this type of conversion, if a method m2 takes a parameter type Y, and it is called with a parameter x of type X, the compiler makes an attempt to convert x to a target object of type Y, which is then passed along to m2. Again, for this to succeed, a unique implicit method of type (X => Y) should be in scope at the point of call.


• Implicit parameters: with this feature, a method definition can be marked as expecting implicit parameters; if these parameters are not supplied at the point of call of the method, the compiler supplies these parameters. For this to succeed, unique implicit methods, vals, or objects of the correct type should be in scope at the point of call.

Based on these fundamental constructs, implicits provide the following high level features:

• View conversions. These can be used for:

• Designing loosely coupled and highly cohesive software.
• Extending existing classes in a loosely coupled fashion. This is similar in spirit to what open classes accomplish in Ruby.
• Creating embedded DSLs.
• Implementing view bounds based on implicit parameters, to provide information about a type in a generic (i.e. parameterically polymorphic) method.


• Capability to write generic code.
• Capability to do type based meta-programming.
• Default method parameters.

Quite a list, isn't it?

In this post, I am going to talk about view conversions, which are a major use of implicits.

The next post will look at some of the other uses of implicits, safeguards within the Scala language to control the complexity of implicits, the relationship of implicits to Haskell type classes, and techniques for debugging implicits.

View Conversions

In this mode of operation, the use of implicits is based on the following idea:

It should be possible to view an object of a certain type as an object of another type - via a view conversion.

This is a very powerful idea. Traditionally, Object Orientation has been based on two major types of relationships between objects: Is-a and Has-a. Implicits bring another kind of relationship, with accompanying language-level support, to the table: Is-viewable-as-a.
Why is this important? Because it allows a class to focus on doing one thing well, without trying to cater to every possible scenario in which it might be used. So classes can stay tight and cohesive. But it's still possible to extend a class in different directions, and thus cater to different and unrelated usage scenarios, by defining traits that capture usage patterns in these scenarios, and then defining view conversions from the class to these traits.

To provide a different perspective on this...

Here's a link that argues in favor of big interfaces:
http://martinfowler.com/bliki/HumaneInterface.html

And here's a link that argues in favor of minimal interfaces:
http://martinfowler.com/bliki/MinimalInterface.html

Implicits allow us to balance these two forces. Core interfaces/classes can be minimal. Rich/Humane interfaces can be provided over these core classes via view conversions.

This is a good way to structure and develop new code that we write, because it encourages high cohesion and low coupling. This is also a very useful and powerful technique for extending existing third-party classes. In this scenario, we can add functionality to existing classes (for which we do not control the source code) by defining view conversions to rich wrappers that provide the desired functionality.

This also plays nicely with the Open closed principle: we just define a new view conversion, and existing code picks up this new functionality without any modifications at all.

Using trait based mixin-composition

At this point, you might well ask: why can't I just use trait based mixin-composition instead of implicits?
In other words, if you have:

class X 
trait RichX 

Why shouldn't you use:

class MyRichX extends X with RichX

to get the combined functionality of X and RichX? Why should you instead think of using a view conversion via:

implicit def toRichX(x: X): RichX

This is a good question. In my mind, the following thoughts are applicable here:

• It is a good practice to program to an interface, not an implementation. So if you have a family of classes that you access via an interface, prefer view conversions to roll in rich functionality. If you use trait based mixin-composition, your code will need to refer to the new mixed in class, as opposed to an abstract interface, to get access to the new functionality. If, on the other hand, you have a class that you are using directly in your code (because it is not part of a family hidden behind an interface), using mixin-composition is just fine.
  
• If you want to extend a final third-party class, mixin-composition will not work (because it requires subclassing). You will need to use view conversions in this scenario.

Enough talk. Let's see all of this in action.

Enriching HashSets

This section will show the following:

• Conversions of a method call receiver.
• Conversions to an expected type.
• View bounds (and conversions) based on implicit parameters.

I'm going to stick with the problem I have been playing with over my last couple of posts: that of providing rich operations to Java Collections; this is a case of extending existing classes to give them a friendlier interface to work with.

I'll focus on enriching HashSets to begin with. Here's some code that defines a couple of traits that contain the rich operations that we want:

/*
  * A trait that provides rich operations to Iterables/Collections
  */
trait RichIterableOps[A] {
   
   // required method for collections mixing in this trait
   def iterator: Iterator[A]
   
   def foreach(f: A => Unit): Unit = foreachWithIter(f)(iterator)
   def foreachWithIter(f: A => Unit)(iter: Iterator[A]): Unit = {
     while (iter.hasNext) f(iter.next) 
   }      
    
   def foldLeft[B](seed: B)(f: (B, A) => B): B = foldLeftWithIter(seed)(f)(iterator) 
   def foldLeftWithIter[B](seed: B)(f: (B, A) => B)(iter: Iterator[A]): B = {
     var result = seed
     foreachWithIter(e => result = f(result, e))(iter) 
     result
   }
   
   def reduceLeft[B >: A](f: (B, A) => B): B = {
     val iter = iterator
     if (!iter.hasNext) throw new RuntimeException("reduceLeft not valid on Empty container")
     foldLeftWithIter[B](iter.next)(f)(iter)
   }
}
   
/*
  * a builder for containers of type C with element A
  */
trait Builder[C[_], A] {
   
   def add(el: A): Boolean
   def build(): C[A]
   
   def using(op: Builder[C, A] => Unit): C[A] = {
     op(this); build() 
   }
}
   
/*
  * A trait that provides rich operations that transform collections 
  */
trait RichIterableXforms[A, Iterable[_]] extends RichIterableOps[A] {
   
   def builder[T]: Builder[Iterable, T] 
   
   def map[B](f: A => B): Iterable[B] = builder.using { b =>
     foreach(e => b.add(f(e)))
   }
}

The goal is to still be able to successfully run the tests (shown below) from the previous post, with the difference that instead of creating a RichHashSet as the class-under-test, I am now creating a plain old HashSet:

class TestImplicitHashSet {
 
   // val richSet = new RichHashSet[Int]
   val plainSet = new HashSet[Int]

   @Before
   def setupSet: Unit = {
     plainSet.add(1); plainSet.add(2); plainSet.add(3)
   }
 
   @Test
   def testFoldForSet = {
     assertEquals(6, plainSet.foldLeft(0)((x,y) => x+y))
   }
 
   @Test
   def testOriginalCollectionOpForSet = {
     assertTrue(plainSet.map(e => 2*e).contains(4))
   }
 
   @Test
   def testChainedRichOpForSet = {
     assertTrue(plainSet.map(e => 2*e).map(e => 2*e).contains(8))
   }
 
   @Test
   def testEqualityForSet = {
     val expected = new HashSet[Int]
     expected.add(2); expected.add(4); expected.add(6)
     assertEquals(expected, plainSet.map(e => 2*e))
   }
}

As expected, this does not even compile to begin with:

[WARNING] TestImplicitHashSet.scala:20: error: value foldLeft is not a member of java.util.HashSet[Int]
[WARNING]     assertEquals(6, plainSet.foldLeft(0)((x,y) => x+y))
[WARNING]                              ^
[WARNING] TestImplicitHashSet.scala:25: error: value map is not a member of java.util.HashSet[Int]
[WARNING]     assertTrue(plainSet.map(e => 2*e).contains(4))
[WARNING]                         ^
[WARNING] TestImplicitHashSet.scala:30: error: value map is not a member of java.util.HashSet[Int]
[WARNING]     assertTrue(plainSet.map(e => 2*e).map(e => 2*e).contains(8))
[WARNING]                         ^
[WARNING] TestImplicitHashSet.scala:37: error: value map is not a member of java.util.HashSet[Int]
[WARNING]     assertEquals(expected, plainSet.map(e => 2*e))
[WARNING]                                     ^
[WARNING] four errors found

What I need for this to work is an implicit method that will convert from a HashSet to a target class that contains these missing rich methods. So the first order of business is to create this target class:

/**
  * Rich wrapper for HashSets
  */
class RichHashSetWrapper[A](wrapped: HashSet[A]) extends RichIterableXforms[A, HashSet] {
     
   def iterator = wrapped.iterator
   def add(a: A) = wrapped.add(a)
   def builder[T] = new HashSet[T] with Builder[HashSet, T] {def build() = this}
}   

Some things to note in the above code fragment are:

• RichHashSetWrapper sits over a HashSet
• RichHashSetWrapper extends RichIterableXforms, but not HashSet. So there is no relationship between the source and target types of the intended view conversion
• RichHashSetWrapper implements the required methods for RichIterableXforms (iterator and add) by forwarding to the wrapped set.

Ok, now that I have the target class in place, I can go ahead and write the implicit conversion method:

/*
  * A module that provides implicits for Rich Collection view conversions 
  */
object RichCollections {
   
     implicit def toRichHashSet[A](set: HashSet[A]) = new RichHashSetWrapper(set)
}

Let's try things out now:

mvn clean test
   
[INFO] [scala:compile {execution: default}]
[INFO] Compiling 1 source file to target\classes
   
[INFO] [scala:testCompile {execution: default}]
[INFO] Compiling 1 source file to target\test-classes
   
[INFO] [surefire:test]
[INFO] Surefire report directory: target\surefire-reports
   
-------------------------------------------------------
  T E S T S
-------------------------------------------------------
Running implicits.TestImplicitHashSet
Tests run: 4, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0 sec
   
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESSFUL
[INFO] ------------------------------------------------------------------------

Good. The tests compile and run fine.

I think it's worthwhile to take a moment here to think about what we just saw. the tests are doing the following noteworthy things:

• calling non-existent methods like map and foldLeft on a HashSet
• calling HashSet methods on the collection returned from map
• calling RichIterableOps methods on the collection returned from map
• chaining RichIterableOps methods on a HashSet

All of this compiled and ran fine because of the ability of implicits to help in the conversion of a method call receiver. As an example of this, let's look at the following call:

plainSet.foldLeft(0)((x,y) => x+y)

Here plainSet, the method call receiver, is converted from a HashSet to a RichHashSetWrapper (which contains the called method) via a view conversion.

Let's now say that we want to be able to find the biggest element in a Set. Here's code that does this:

/*
  * A module that provides aggregate operations on collections 
  */
object AggregateIterableOps {
   
   def max[A <% Ordered[A]](iterable: RichIterableOps[A]): A = {
     iterable.reduceLeft((x, y) => if (x > y) x else y)
   }
}

Different aggregate operations on collections might depend on different constraints on the collection element type, so I have made max a generic method within an object.

And here's a test for max:

  @Test
   def testMaxForSet = {
     plainSet.add(18); plainSet.add(17); plainSet.add(16)
     assertEquals(18, AggregateIterableOps.max(plainSet))
   }

The code above features the two remaining things that I want to show in this section:

• A conversion to an expected type.
• A view bound (and conversion) based on an implicit parameter. This feature provides information to a generic method about the type that it is operation on, allowing it to do interesting things with this type.

Here's the code fragement that does a conversion to an expected type:

AggregateIterableOps.max(plainSet)

max expects a RichIterableOps; it is provided a plain HashSet. This works because RichCollections.toRichHashSet provides a view conversion between the two types.

And here's the code fragement that makes use of a view bound (and conversion) based on an implicit parameter:

def max[A <% Ordered[A]](iterable: RichIterableOps[A]): A  

Under the covers, Scala converts the view bound - A <% Ordered[A] - to an implicit parameter:

def max[A](iterable: RichIterableOps[A])(implicit f: A => Ordered[A]): A

Within the body of max, the less-than test:

if (x > y)

Gets coverted to :

if (f.apply(x).>(y))

And the same caller code that we saw earlier provides the implict paramater required by max. So:

AggregateIterableOps.max(plainSet)

Gets converted to:

AggregateIterableOps.max(plainSet)(n => Predef.intWrapper(n))

Enriching ArrayLists

The traits and implicits that I wrote have no dependence on HashSets, so I should be able to use the same code to enrich ArrayLists. Let me make sure that this works as expected.

Here are the tests that capture the required behavior:

class TestImplicitArrayList {
 
   val plainList = new ArrayList[Int]
 
   @Before
   def setupSet: Unit = {
     plainList.add(1); plainList.add(2); plainList.add(3)
   }
 
   @Test
   def testFoldForSet = {
     assertEquals(6, plainList.foldLeft(0)((x,y) => x+y))
   }
 
   @Test
   def testOriginalCollectionOpForSet = {
     assertTrue(plainList.map(e => 2*e).contains(4))
   }
 
   @Test
   def testChainedRichOpForSet = {
     assertTrue(plainList.map(e => 2*e).map(e => 2*e).contains(8))
   }
 
   @Test
   def testEqualityForSet = {
     val expected = new ArrayList[Int]
     expected.add(2); expected.add(4); expected.add(6)
     assertEquals(expected, plainList.map(e => 2*e))
   }
 
   @Test
   def testMaxForSet = {
     assertEquals(3, AggregateIterableOps.max(plainList))
   }
}

Here's the target class with the rich methods:

/**
  * Rich wrapper for ArrayLists
  */
class RichArrayListWrapper[A](wrapped: ArrayList[A]) extends RichIterableXforms[A, ArrayList] {
     
   def iterator = wrapped.iterator
   def add(a: A) = wrapped.add(a)
   def builder[T] = new ArrayList[T] with Builder[ArrayList, T] {def build() = this}
}

And here's the implicit conversion method:

/*
* A module that provides implicits for Rich Collection view conversions
*/
object RichCollections {
// snip
implicit def toRichArrayList[A](list: ArrayList[A]) = new RichArrayListWrapper(list)
}

I'm all set to run the tests now:

$ mvn clean test
 
[snip]
 
Running implicits.TestImplicitArrayList
Tests run: 5, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.016 sec

Great. That worked fine.

Till the next one...

That's it for today. This post introduced implicits, talked about the design space in which they play, and described the primary scenario in which they are meant to be used: view conversions. In the next post, I will talk about the remaining uses of implicits. I will also talk about the safeguards within the Scala language to control the complexity of implicits, the relationship of implicits to Haskell type classes, and techniques for debugging implicits.

Relevant Reads:

Programming in Scala; the chapter on Implicits
The Power of Type-classes with Scala implicit defs
Humane Interfaces
Minimal Interfaces
Program to an interface, not an implementation
The Open-closed principle