Sunday, June 20, 2010

Scala Implicits : Type Classes Here I Come

I was having some discussion on type classes in Scala with Daniel on Twitter the other day when I suddenly discovered one of my unfinished posts on the same topic. Not that there's anything new that you will get to know from this rant. But these are some of my thoughts on the value that type class based thinking adds to your design space. I started this post when I published my thoughts on orthogonality in design some time back.

Let's start with the GOF Adapter pattern .. the object adapter that uses the highly recommended composition technique to bind abstractions. The example is also the same which I used for discussing orthogonality in design ..

case class Address(no: Int, street: String, city: String, 
  state: String, zip: String)

And we want to adapt this to the interface of a LabelMaker .. i.e. we would want to use Address as a LabelMaker ..

trait LabelMaker[T] {
  def toLabel(value: T): String

the adapter that does the interface transformation ..

// adapter class
case class AddressLabelMaker extends LabelMaker[Address] {
  def toLabel(address: Address) = {
    import address._
    "%d %s, %s, %s - %s".format(no, street, city, state, zip)

// the adapter provides the interface of the LabelMaker on an Address
AddressLabelMaker().toLabel(Address(100, "Monroe Street", "Denver", "CO", "80231"))

Now what's the incidental complexity that we introduce in the above design ?

As a client our point of focus has shifted to the adapter class AddressLabelMaker, which wraps our original abstraction, the Address instance. This leads to an identity crisis of the Address instance itself, a typical problem with any wrapper based idiom. The identity of the adaptee is now lost within the identity of the adaptor. And if you are brave enough to have the adaptee as an aggregate member of another object, then obviously the entire composition of the adapter idiom breaks down.

Conclusion : Object adapters don't compose. And the class variant of the adapter pattren is worse in the sense that you have a wiring by inheritance right from start, which makes the entire design much more rigid and coupled.

Enter Type Class ..

In the above structure of the adapter pattern, the adaptee was wrapped into the adapter leading to the identity loss of the adaptee that we discussed earlier. Let's take a different approach and see if we can abstract the adapter away from the client usage. The type class approach does exactly offer this way of composing abstractions - the type system of the language selects the appropriate adapter instance during compile time, so that the user can program explicitly to the adaptee.

Consider this function printLabel, that takes an argument and prints the label using the LabelMaker that we supply to it ..

def printLabel[T](t: T)(lm: LabelMaker[T]) = lm.toLabel(t)

In order to make a label out of an Address, we need to define the adapter that does it. In Scala we have first class module support through the object syntax. Let's define a module that defines the semantics to convert an Address to a LabelMaker.

object LabelMaker {
  implicit object AddressLabelMaker extends LabelMaker[Address] {
    def toLabel(address: Address): String = {
      import address._
      "%d %s, %s, %s - %s".format(no, street, city, state, zip)

Note that we make the adapter a Scala object with an implicit qualifier. What this does is that the compiler supplies the implicit argument if it finds one appropriate instance within the lexical scope. But for that we need to have the LabelMaker argument to printLabel implicit as well.

def printLabel[T](t: T)(implicit lm: LabelMaker[T]) = lm.toLabel(t)

or using the Scala 2.8 context bound syntax, we can make the implicit argument unnamed ..

def printLabel[T: LabelMaker](t: T) = implicitly[LabelMaker[T]].toLabel(t)

We don't supply the implicit argument at all, instead use the context bound syntax where the compiler automatically picks up the appropriate instance from the enclosing lexical scope. In the above example the implicit object AddressLabelMaker needs to be in scope of the function where you call printLabel. It will complain if it doesn't find one - hence you are alerted during compile time itself. Look ma - No evil run time failures ..

Now if we want to print a label for an Address, we do ..

printLabel(Address(100, "Monroe Street", "Denver", "CO", "80231"))

No incidental complexity in the client code in the form of adapter objects, the abstractions are explicit, we only supply the object for which we want to print the labels. We get rid of indirections as well. Not only that, if you look at the various abstractions that constitute the surface area of the entire design, modularity speaks for itself. The client only programs on the type class definition while the type class instance is nicely abstracted away *only* for the eyes of the compiler.

Let's see how Haskell does it ..

We have come this far discussing type classes without mentioning Haskell once. Let's make amends and see how the above design fits in the pure functional world of Haskell.

LabelMaker is the type class - let's define it in Haskell ..

class LabelMaker a where
    toLabel :: a -> String

This corresponds to our LabelMaker trait definition in Scala.

We want to make Address as a LabelMaker. Here's an instance of the above type class for Address ..

instance LabelMaker Address where
    toLabel (Address h s c st z) = show(h) ++ " " ++ s ++ "," ++ c ++ "," ++ st ++ "-" ++ z

This corresponds to the implicit object AddressLabelMaker definition in Scala that we did above. Scala's first class support for executable modules is an added feature that we don't have in Haskell.

Oh BTW here's the Address definition in Haskell record syntax ..

type HouseNo = Int
type Street = String
type City = String
type State = String
type Zip = String

data Address = Address {
      houseNo        :: HouseNo
    , street         :: Street
    , city           :: City
    , state          :: State
    , zip            :: Zip

And now we can define printLabel that uses the type class and generates the String for the label ..

printLabel :: (LabelMaker a) => a -> String
printLabel a = toLabel(a)

This corresponds to the Scala definition of printLabel that we have above.

A little observation ..

Note that one place where Haskell is much less verbose than Scala in the above implemnetation is the instance definition of the type class. But here the added verbosity in Scala is not without a purpose and offers a definite advantage over the corresponding Haskell definition. In Scala's case we name the instance explicitly as AddressLabelMaker, while the instance is unnamed in case of Haskell. The Haskell compiler looks into the dictionary on the global namespace for a qualifying instance to be picked up. In Scala's case the search is performed locally in the scope of the method call that triggered it. And because it's an explicitly named instance in Scala, you can inject another instance into the scope and it will be picked up for use for the implicit. Consider the above example where we have another instance of the type class for Address that generates the label in a special way ..

object SpecialLabelMaker {
  implicit object AddressLabelMaker extends LabelMaker[Address] {
    def toLabel(address: Address): String = {
      import address._
      "[%d %s, %s, %s - %s]".format(no, street, city, state, zip)

We can choose to bring this special instance in scope instead of the default one and generate a label for our address in a very special way ..

import SpecialLabelMaker._
printLabel(Address(100, "Monroe Street", "Denver", "CO", "80231"))

You don't get this feature in Haskell.

Type classes in Scala and Haskell ..

Type classes define a set of contracts that the adaptee type needs to implement. Many people misinterpret type classes synonymously with interfaces in Java or other programming languages. With interfaces the focus is on subtype polymorphism, with type classes the focus changes to parametric polymorphism. You implement the contracts that the type class publishes across unrelated types.

A type class implementation has two aspects to it :-
  1. defining the contracts that instances need to implement
  2. allow selection of the appropriate instance based on the static type checking that the language offers
Haskell uses the class syntax to implement (1), though this class is a completely different concept than the one we associate with OO programming. For Scala we used traits to implement this feature and an extension of the trait into an object to implement instances of it.

As I mentioned earlier, Haskell uses a global dictionary to implement (2), while Scala does it through a lookup in the enclosing scope of invocation. This gives an additional flexibility in Scala where you can select the instance by bringing it into the local scope.


Tom said...

A crucial distinction between type classes and interfaces is that for class A to be a "member" of an interface it must declare so at the site of its own definition. By contrast, any type can be added to a type class at any time, provided you can provide the required definitions, and so the members of a type class at any given time are dependent on the current scope. Therefore we don't care if the creator of A anticipated the type class we want it to belong to; if not we can simply create our own definition showing that it does indeed belong, and then use it accordingly. So this not only provides a better solution than adapters, in some sense it obviates the whole problem adapters were meant to address.

Another interesting point is that the particular implementation of a type class instance depends on scope. So, for example, you could feasibly define, in different scopes, two or more different implementations of the same type class for the same type.

Eric said...

Very useful post on the applicability of type classes (as was Daniel's last post on the subject too). I've been bitten several times by the toXml, toHtml methods polluting my domain and I think this offers a good solution.

2 more thoughts about that:

- I think that Lift could benefit from this idea in its Records framework. I always found weird that a Record object had a toXhtml method

- That may be a good way to implement the DCI architecture ( where the type class is a specific role


Debasish said...

@Tom : regarding interfaces and type classes - interfaces do a subtype polymorphism while type classes do a parametric polymorphism. +1 on your thoughts and that's what I indicated in the post as well.

Also your observation regarding the scope of a type class instance is true for Scala, which also I have detailed out.

Debasish said...

@Eric : +1 on your thoughts. I think I penned my observations on Twitter the day List Records was announced. I also wrote a follow up blog post on the same topic. And here's a mail thread on my observations on the Lift ML .. ..

In short I don't like the concept of bloating a domain object with accessory functionalities. You have nailed it absolutely right .. It's weird to have a Record object with a toXhtml method. This is a problem begging to be fixed with a type class.

MLeo said...

How would you capture something like JAXB (or Hibernate) using Type Classes? I'm not asking specifically for JAXB or Hibernate, but how you would "annotate" (perhaps "describe" is a better word here) a class as a type class instance.

MLeo said...

I think I may have found my own answer. Have the Type Class Instance define a constant (method with no parameters) that returns a meta object describing the class.

Which is rather more similar to the pre-annotations Hibernate *.cfg.xml files. *shudder*
So going that way would not improve type safety.

snk_kid said...

"@Tom : regarding interfaces and type classes - interfaces do a subtype polymorphism while type classes do a parametric polymorphism. +1 on your thoughts and that's what I indicated in the post as well."

This is incorrect, type-classes do not provide parametric polymorphism, type varibles do.

Type-classes provide ad-hoc polymorphism in a totally type inferred language such as Haskell and bounded quantification of parametric polymorphism.

You can write polymorphic functions in Haskell without type-classes constraints but without them you can not do much on values of a type variable.

missingfaktor said...

I wrote up another good (according to me :-) typeclass example here:

Joseph Abrahamson said...

The upside of Haskell's global "implicits" namespace is that there is a notion of uniqueness of a type class instance for a given type. This means that we can talk about "the" equality of Ints or "the" order of, I dunno, free abelian groups.

The important part of this is that we often do operate with certain properties like order as being fixed and depend upon that fixture in our programs. The classic example here is that in Scala you cannot be guaranteed that the sense of order you use to build a set is the same as the one you use to query it... and so you lose efficiency.

Stable implicits can be annoying, though, when unicity isn't needed. For instance, it's not meaningful to pick "the" monoid underlying a ring although Haskell would ask you to.

So I don't think either feature dominates the other.