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