Type Classes Make For Better Software Structure

When people usually talk about type classes in languages like Haskell and Scala they tend to be thinking of highly generic concepts like Ordering or Numeric operations. However, in some recent experiments with Haskell I have found that type classes can be very useful for more concrete things. When used appropriately they can lead to more loosely coupled software that is more flexible and easier to change.

I Just Met You, This Is Crazy, Here's My Number, Call Me Function?

As an example, let's consider a telephone number. Fairly simple right, it's a string of digits?

def sendMessage(toNumber: String, theMessage: Message)

Or perhaps we should create a type alias to give us some better info and scope for change:

type TelephoneNumber = String

def sendMessage(toNumber: TelephoneNumber, theMessage: Message)

But wait, I'm trying to build a library that sends messages to telephones and I need to know much more about a telephone number than this 'stringly' typed data is able to tell me. Things like:

• Is it in international format?
• What's the country prefix code?
• Is it a mobile number or a landline number?
• What is the area code?
• Is it some premium rate number?
• and so on…

The Naive Solution

It's clear that my 'stringly' typed representation is not sufficient for this task unless I want to encode a whole load of rules about the world's telephone numbering systems into my library (believe me when I say I don't!). So, a naive approach would be to introduce a new type that holds the information in a more usable format. Something like:

case class TelephoneNumber(countryCode: String, areaCode: String, number: String, isMobile: Boolean, isLandline: Boolean, …)

Unfortunately, this approach suffers from a whole host of problems, including:

• If I build my library implementation against this class then I can't easily change implementation details without breaking the API
• If I copy from an instance of this type into an internal representation then I have a lot of duplication and extra code to test
• If a client uses this type in their domain model they are tightly coupled to my library (and also a specific version of it)
• If a client copies from their own representation into an instance of this type there is more duplication and extra code to test

A More Object-Oriented Approach

So, how do we deal with this? Well what we need to do is separate the behaviour of a telephone number from its actual data representation. In an object-oriented language we would do this by introducing an interface (or in Scala, a trait):

trait TelephoneNumber {
  def countryCode: String
  def areaCode: String
  def number: String
  def isMobile: Boolean
  def isLandline: Boolean
  // and so on...
}

Internally in my library I write all my code against this interface without any care as to how the underlying telephone number data is structured. Client applications are free to implement telephone numbers in whatever way they wish, provided they also implement the interface that exposes the behaviour that my library needs. Yay, problem solved. Or is it? There's still one problem in this object-oriented approach: somewhere in the client code there must be a class that implements the TelephoneNumber interface. This is problematical in a number of ways:

• The class hierarchy of the client domain model is still quite tightly coupled to my library
• It might not be possible to modify an existing domain model to implement the TelephoneNumber interface (no access to source code, coupling restrictions etc.)
• If the client domain represents telephone numbers as Strings then this class can be extended to implement the interface

Both of the last two points would result in needing to implement the same sort of mapping layer to copy between representations that we already said lead to duplication and extra code to test.

How Haskell Does It

So, in a purely functional language that doesn't have the concept of interfaces how do we solve this problem. Enter the Type Class. These clever little beasties provide a mechanism whereby the required behaviour is captured as a series of function definitions (with possible implementations if available). For example:

class TelephoneNumber a where
    countryCode :: a -> String
    areaCode :: a -> String
    number :: a -> String
    isMobile :: a -> Bool
    isLandline :: a -> Bool
    ...

So far this looks pretty much like our interface definition above except that each method takes an instance of type 'a' as a parameter and returns the result. However, the clever bit comes in that we can implement the type class for any type in Haskell without needing to modify that type in any way. For example, we could easily implement it for Strings:

instance TelephoneNumber String where
    countryCode s = ...
    areaCode s = ...
    ...

Or our client code could define its own telephone number data type and an implementation of the type class along side it:

data UKTelephoneNumber = ...

instance TelephoneNumber UKTelephoneNumber where
    countryCode t = ...
    ...

The final change is then that we have our library function require that something implementing the type class is provided rather than some concrete data type:

sendMessage :: (TelephoneNumber t) => t -> Message -> IO ()
sendMessage to msg = do
    ...
    let cc = countryCode t   -- call function on the type class passing the instance we have
    ...

In this Haskell solution we have neatly decoupled the behaviour that our library requires of telephone numbers from the data type used to represent them. Also, any client code of our library does not need to couple its data structures/types directly to the library. They can define and modify them in any way they like. All they need to do is keep the instance of the type class up-to-date.

And Finally, A Better Scala Solution

As I have hopefully shown, the Haskell solution to the problem is both elegant and leads to cleaner, more loosely coupled code. So can we do something similar in Scala? Well, yes we can because Scala also supports type classes. They are a bit less elegant than Haskell, but they work just fine. First, we need to change the TelephoneNumber trait into a type class:

trait TelephoneNumber[T] {
  def countryCode(t: T): String
  def areaCode(t: T): String
  def number(t: T): String
  def isMobile(t: T): Boolean
  def isLandline(t: T): Boolean
  // and so on...
}

Note that all we have done is added a type parameter and modified all the functions to take an instance of that type. Notice that it's now almost identical in structure to the Haskell equivalent. Next we need an implementation of this type class. Let's define one for String:

object TelephoneNumber {

  object StringIsATelephoneNumber extends TelephoneNumber[String] {
    def countryCode(t: String) = ...
    ...
  }

  implicit def TelephoneNumber[String] = StringIsATelephoneNumber
}

I've put the implementation inside a TelephoneNumber object. If you are defining your own types, convention is usually that the type classes go in the companion object (e.g. for a case class UkTelephoneNumber the type class implementations would be in the UkTelephoneNumber companion object). This insures that the type class instances are always in scope when the type is used.

Finally, lets update our sendMessage function to work with type classes:

def sendMessage[T : TelephoneNumber](toNumber: T, theMessage: Message) = {
  ...
  val telNo = implicitly[TelephoneNumber[T]]
  val cc = telNo countryCode toNumber
  ...
}

Note the use of the context bound symbol ':' plus the implicitly function to define the need for and access to the correct instance of the type class.

So there we have it, an elegant Scala solution the overcome all of the coupling problems inherent with the object-oriented approach of implementing a required interface. When should you use this? My opinion is anywhere that two system components communicate, where that communication can be defined in terms of behavioural functions rather than actual data and where you want to minimise the coupling between them and the leaking of types from one component to another.

Encoding State Requirements in Types

In my previous post I looked at a simple way to eliminate conditional expressions by encoding them into the Scala type system. In this follow-up post I want to look at taking this further by using the Scala type system to encode state rules. The aim, as always, is to create code that fails to compile rather than code that fails at runtime. By doing this we also reduce the number of unit tests required.

The Problem

Consider a simple shopping workflow. I collect information about a Basket, the Customer and their Payment Method. Once I have all this in place I can create a processOrder function that completes the workflow process. As a naive starting point, lets encode this as a simple domain model holding optional values:

  case class CheckoutWorkflow(basket: Option[Basket], 
                              customer: Option[Customer], 
                              paymentMethod: Option[PaymentMethod])

  object CheckoutWorkflow {
    def empty = new CheckoutWorkflow(None, None, None)
  }                             

Then we need some functions that populate the workflow:

  def processBasket(workflow: CheckoutWorkflow): CheckoutWorkflow = {
    if ( workflow.basket.isDefined )
      throw new IllegalStateException("Basket workflow step already processed")

    // Do some processing...
    workflow.copy(basket = Some(basket))
  }

  def processCustomer(workflow: CheckoutWorkflow): CheckoutWorkflow = {
    if ( workflow.customer.isDefined )
      throw new IllegalStateException("Customer workflow step already processed")

    // Do some processing...
    workflow.copy(customer = Some(customer))
  }

  def processPaymentMethod(workflow: CheckoutWorkflow): CheckoutWorkflow = {
    if ( workflow.paymentMethod.isDefined )
      throw new IllegalStateException("Payment Method workflow step already processed")

    // Do some processing...
    workflow.copy(paymentMethod = Some(paymentMethod))
  }

Note that each of the above functions has a guard condition to stop them being called multiple times for the same workflow. Each of these guard conditions would require a separate unit test to ensure that it works and to avoid regressions should it be accidentally removed in the future.

Finally, we need the method to process the order. Given our domain model above, this class needs to contain some conditional check to ensure that all the workflow requirements are satisfied before processing of the order can commence. Something like:

  def processOrder(workflow: CheckoutWorkflow) = workflow match {
    case CheckoutWorkflow(Some(basket), Some(customer), Some(paymentMethod)) => {
      // Do the order processing
    }
    case _ => throw new IllegalStateException("Workflow requirements not satisfied")
  }

None of the above is obviously ideal as there are a number of places that have the potential to error at runtime. The conditionals pollute our code with non-business logic. Also, we have to write good unit tests to ensure all the conditionals are working correctly and have not been accidentally removed. Even then, any client may call our code having not met the requirements encoded in the conditionals and they will receive a runtime error. Let's hope they unit test as thoroughly as we do! Surely we can do better than this?

A Less Than Ideal Solution

Well, we could use the approach outlined in my previous post and use domain model extensions:

  case class WorkflowWithBasket(basket: Basket)
  case class WorkflowWithBasketAndCustomer(basket: Basket, customer: Customer)
  case class WorkflowWithAllRequirements(basket: Basket, 
                                         customer: Customer, 
                                         paymentMethod: PaymentMethod)

  def processOrder(workflow: WorkflowWithAllRequirements) = {
     // Do the order processing
  }                                         

While this does allow removal of all the conditionals and associated tests, it unfortunatley also reduces the flexibility of our model quite significantly in that the order that the workflow must be processed is now encoded into the domain model. Not ideal. We'd like to keep the flexibility from the first solution but in a type safe way. Is there a way that we can encode the requirements into the type system?

Levaraging The Type System

First, lets consider what we want to achieve. Our aim to encode unsatisfied and satisfied workflow requirements and only allow methods to be called when the correct combinations are set. So, let's first encode the concept of requirements:

  trait BasketRequirement
  case object UnsatisfiedBasketRequirement extends BasketRequirement
  
  trait CustomerRequirement
  case object UnsatisfiedCustomerRequirement extends CustomerRequirement
  
  trait PaymentMethodRequirement
  case object UnsatisfiedPaymentMethodRequirements extends PaymentMethodRequirement

Here we have defined requirement traits for each of the different workflow stages. We also defined case objects to represent the unsatisfied state of each requirement. Next we need to indicate the satisfied states, which are our actual domain object classes:

  case class Basket(items: List[LineItem]) extends BasketRequirement
  case class Customer(id: String) extends CustomerRequirement
  case class PaymentMethod(paymentType: PaymentType) extends PaymentMethodRequirement

Next job is to make sure that our workflow object can represent these requirements and be strongly typed on either the satisfied or unsatisfied state. We do this by adding type bounds to each of the workflow types. This also allows us to eliminate the need for the Option types. We also define an 'unsatisfied' instance as the starting point for our workflow:

  case class CheckoutWorkflow[B <: BasketRequirement,
                              C <: CustomerRequirement,
                              PM <: PaymentMethodRequirement]
                              (basket: B, customer: C, paymentMethod: PM)

  object CheckoutWorkflow {
    val unsatisfied = CheckoutWorkflow(UnsatisfiedBasketRequirement,
                                       UnsatisfiedCustomerRequirement,
                                       UnsatisfiedPaymentMethodRequirements)
  }

Now we need the functions that actually process each individual workflow stage. Note how each one defines type bounded parameters for the things it doesn't care about. However, for the stage that it actually manipulates it requires that it is called with the Unsatisfied type and returns the Satisfied type. Thus, you can no longer call any of these methods with a workflow that already has that stage satisfied: the compiler won't allow it:

  def processBasket[C <: CustomerRequirement, PM <: PaymentMethodRequirement]
    (workflow: CheckoutWorkflow[UnsatisfiedBasketRequirement.type, C, PM]): 
      CheckoutWorkflow[Basket, C, PM] = {

    // Do some processing...
    workflow.copy(basket = basket)
  }

  def processCustomer[B <: BasketRequirement, PM <: PaymentMethodRequirement]
    (workflow: CheckoutWorkflow[B, UnsatisfiedCustomerRequirement.type, PM]): 
      CheckoutWorkflow[B, Customer, PM] = {

    // Do some processing...
    workflow.copy(customer = customer)
  }

  def processPaymentMethod[B <: BasketRequirement, C <: CustomerRequirement]
    (workflow: CheckoutWorkflow[B, C, UnsatisfiedPaymentMethodRequirements.type]): 
      CheckoutWorkflow[B, C, PaymentMethod] = {

    // Do some processing...
    workflow.copy(paymentMethod = paymentMethod)
  }

Finally, our processOrder function becomes super simple. You just can't call it any more unless it has no Unsatisfied types:

  def processOrder(workflow: CheckoutWorkflow[Basket, Customer, PaymentMethod]) = {
    // Process the order
  }

One observation that was made to me by someone (a Java dev) who looked at my initial draft of the code was that the final solution looks more complex due to all the type bounds and that there's actually more classes due to the need to define the requirement traits and the Unsatisfied state objects. However, don't forget that this solution eliminates at least four conditional blocks and associated unit tests, simplifies others and also possibly reduces the number of tests that clients need to write on their code as well. Also, there's no possibility of runtime failure. If the code compiles then we have a much higher confidence that it will work. Well worth a tiny bit more type complexity in my book.

Life Without Objects

Over the last few years I have been learning and experimenting with a wider range of programming languages. In particular I have started using Scala as my primary development language, adopting a more and more functional style. I have also become very interested in Haskell (a pure functional language) and Clojure (a modern lisp dialect).

I have therefore been moving away from the object-oriented development principles that have made up the bulk of my 17 year career to date. More and more I am beginning to feel that objects have been a diversion away from building concise, well structured and reusable software.

As I pondered on this topic, I realised that this isn’t a sudden switch in my thinking. The benefits of objects have been gradually declining over a long period of time. The way I use objects today is very different to how I used them when they were new and shiny. In this post I explore this change in my thinking about object-oriented development.

The Promise of Objects

Back in the 1990s, objects were new and exciting. The promise of being able to create reusable classes built around common design patterns was seductive. The ability to then combine these classes into reusable and configurable business components seemed like the Mecca of software development. New languages like C++ and then, slightly later, Java held the promise of a new way of building great software.

Business Components Aren’t Reusable
It didn’t take us long to discover that the ability to create reusable business components was just a giant fallacy. Each business is significantly different from another, even in the same industry. Each similar project has very different business rules.

The only way to build reusable business components at this level is to make them hyper-configurable by adding such things as rules engines and embedded scripting languages. Hardly a component model and more like a bloatware model. This promise gone, people either buy into the big bloatware systems (suckers) or build their custom business objects on a project by project basis.

Patterns Don’t Build Well Structured Software
The next thing we learnt was that excessive reliance on design patterns doesn’t lead to the good software structure. Instead it leads to software that is overly complex, hard to understand and difficult to maintain. Some patterns even turned out to be anti-patterns (the singleton pattern makes software almost impossible to unit test, for example).

We soon learnt to use patterns judiciously. More often than not it’s just cleaner to code the software as you understand the model rather than try to abstract it into a more generalised pattern.

Frameworks for Class and Component Reuse Give Few Benefits
Another early promise of objects was rich, tightly coupled frameworks of classes which when used together would make building applications from reusable component a breeze by hiding all the technical complexity and implementation plumbing. Think EJB and similar. Experience soon showed that these just did not work. They were just too restrictive and cumbersome for what people were trying to achieve.

These heavy-weight frameworks soon died out to be replaced with more lightweight libraries and toolkit type approaches. Collections of more loosely coupled classes that you can pull together as needed are now the preferred way to build software. Take just what you need and nothing more.

Inheritance Creates Brittle Software
The ability to support interface and implementation inheritance was one of the key tenets of object oriented software development. We could spot common code and behaviour and push this down into a shared base class so that future abstractions could benefit from having this shared code available to build on.

Sadly, this just didn’t work out well. Each sub-class turns out to be subtly different from its peers, resulting in lots of overrides of base class behaviour or making the base classes even more generic. The net result was super-fragile software, where any small changes to a common base class would break most, if not all, of the sub-class implementations.

These days we don’t use inheritance much, and especially not for creating technical base classes. Its use is pretty much restricted to interface inheritance to indicate an object supports a certain behaviour or to occasional domain models where there is a true inheritance relationship. Other than that we tend to extract commonality in to separate ‘mixin’ type classes and compose them together through an aggregation approach.

Violation of Encapsulation
Another key feature of the object-oriented model was the ability to encapsulate state and then expose behaviours (via methods) that access and update this state. Unfortunately it turns out that there are a large number of cases, where we are actually interested in the vales of the state rather than the behaviour.

For example, asking an object to render itself as HTML turns out to be a pretty poor approach. Knowledge of HTML rendering gets spread across the code base and a small change in approach causes us to change many, many classes. Instead we tend to pass the object to a dedicated HTML rendering/template component, which pulls the data values from the object.

Anti-patterns have even emerged around this to allow us to have light-weight objects that just encapsulate state without behaviour (Java Beans, Data Transfer Objects and so on). If we are doing this, then why not just work directly with first-class structured data as opposed to objects?

Mutable State Causes Pain

Another perceived benefit of encapsulation was the ability to mutate the state of an object instance without impacting on the clients that use that object. However, anyone who has built a significant sized object-oriented system can tell you stories of trawling through many files of code to find the location that mutated the state of an object to an unexpected value that happened to make your software blow up in a completely different place (usually where you output or store the state of that object).

More and more we now favour immutable state and stateless services so that these problems do not occur. There’s also the additional benefit that immutable state is a much better model for building highly concurrent systems and for getting the most out of modern multi-core hardware. It’s also far easier and less error prone than trying to work with threads, locks and concurrency safe data structures.

Behavioural Interfaces Cause Code Complexity and Bloat
One of the things we do frequently in object-oriented languages is create small marker interfaces that have just a single method. Any class wanting to support this behaviour extends the interface and implements the method. We can also declare anonymous implementations for ad-hoc use.

However, we have found that neither of these approaches are particularly good. Implementing the marker interfaces often pollutes classes with implementations that are not their direct concern (thus violating the single responsibility principle). Anonymous classes are just unnecessary bolierplate that makes our code more difficult to understand and maintain.

Life Without Objects

So, is it possible to go back on 17 years of experience and contemplate a life without objects? I’m not sure that I’m 100% there just yet, but using a multi-paradigm language like Scala is allowing me to overcome many of the limitations of the object-oriented approach.

For example, Scala’s support for mixin traits makes it almost unnecessary to ever use implementation inheritance. It’s rich collections framework plus the ability to use case classes to create data structure like concepts obviates working around encapsulation issues. A recommendation to use immutable data and collections makes code easier to debug and reason about. The ability to use functions as general abstractions and type classes to extend behaviour while maintaining single responsibilities makes it much easier to build well structured, reusable software.

In fact, what I find I am doing more and more is using simple objects in the form of case classes to represent data structures, with a few behavioural methods to simplify working with this data. Then I’m just using mixin traits as a modular approach for grouping related functions together. Then I’m combining these together to form components in which I compose together various functions that transform data from one for into another.

Perhaps I’m further away from the pure object-oriented approach than I’d thought. I’m certainly building smaller, cleaner and better structured software than I ever was before.

Type Classes and Bounds in Scala

I've been doing some initial experiments with the Scalaz library (https://github.com/scalaz/). This is a great extension to the Scala standard library that adds a wide range of functional programming concepts to the language. Many of its features are based around the concept of Type Classes.

The type class concept originally comes from Haskell, and provides a way to define that a particular type supports a certain behavioural concept without the type having to explicitly know about it. For example, a type class may define a generic 'Ordered' contract and implementations can be defined for different types separate from the definition of those types. Any type that has an implementation of the 'Ordered' type class can then be used in any functions that work with ordering.

The Scala language provides a way to support type classes via its implicit mechanism. In order to get my head around this fully I created some examples to experiment with how this works. Now I fully grasp the mechanisms, the Scalaz library makes much more sense. I therefore thought I'd share my experiment in case it proves useful to anyone and as an aide-mémoire to myself for the future.

In addition, my examples also make use of the different type bounds mechanisms provided by Scala, so I will demonstrate these in my examples as well.

The full source code can be found in the following gist: https://gist.github.com/1247752.

Without Type Classes

In the first example, I built a simple solution that doesn't make any use of the type class concept. This solution is much like you would implement in Java, with an interface defining the behaviour and classes that implement this interface:

trait Publishable {  
  def asWebMarkup: String
}

case class BlogPost(title: String, text: String) extends Publishable {
  def asWebMarkup =
    """|
%s
       |
%s
""".stripMargin format(title, text)
}

Here we have a trait Publishable that indicates that something can represent itself as a web markup string. Then we have a case class that implements the trait and provides the method to return the markup. Next, we declare a class that can do the publishing:

class WebPublisher[T <: Publishable] {
  def publish(p: T) = println(p.asWebMarkup)
}

Note that we have defined this as a templates class and that we have used the <: bounds notation to require that our type T is only valid if it extends the Publishable trait. All we need to do now is use it:

val post = new BlogPost("Test", "This is a test post")
val web = new WebPublisher[BlogPost]()
web publish(post)

Ok, so that works fine. However, what happens when we either can't or don't want BlogPost to implement the Publishable trait? There can be many reasons for this: perhaps we don't have the BlogPost domain object source; perhaps the object is already quite complex and we don't want to pollute it with publishing knowledge; perhaps it's shared by multiple teams or projects and only ours needs publishing knowledge. So, what do we do?

Without type classes there are some options: we might extends the domain class to implement the trait; we might create a wrapper class or we might create a helper utility. However, all of these result in a level of indirection and complication in our code. Let me explain...

If we internalise the knowledge of the wrapper/helper/sub-class in our publishing code we end up with some horrific type matching:

class WebPublisher {
  def publish(p: AnyRef) = p match {
    case blogPost: BlogPost => BlogPostPublishHelper.publish(blogPost)
    case _ => …
  }
}

However, if we externalise the knowledge of publishing then our client code has to do the conversion:

class WebPublisher {
  def publish(p: Publishable) = ...
}

web publish(new PublishableBlogPostWrapper(blogPost))

Clearly, both solutions lead to fragile boilerplate code that pollutes our main application logic. Type classes provide a mechanism for isolating and reducing this boilerplate so that it is largely invisible to both sides of the contract.

Type Classes with Implicit Views

Fortunately, Scala provides a mechanism whereby we can declare an implicit conversion between our BlogPost and a Publishable version of our instance. So, let's start with the simple stuff:

trait Publishable {
  def asWebMarkup: String
}

case class BlogPost(title: String, text: String) 

So, we now have a blog post that doesn't implement the Publishable trait. Let's now define the conversion that can implicitly turn our blog post into something that supports publishing (we would typically add this into our publishing code rather than the domain object in order to isolate all knowledge of Publishable to just the area that needs it):

implicit def BlogPostToPublishable(blogPost: BlogPost) = new Publishable {
  def asWebMarkup =
    """|
%s
       |
%s
""".stripMargin format(blogPost title, blogPost text)
}

Our conversion just creates a new Publishable instance that wraps our blog post and implements the required methods. But, how do we make use of this? We have to change our web publisher very slightly:

class WebPublisher[T <% Publishable] {  
  def publish(p: T) = println(p.asWebMarkup)
}

All we have in fact changed is the <: bounds to a <% bounds. This new one is called a view bounds and defines that we can instantiate a WebPublisher with type T only if there is a view (in this case as implicit conversion) in scope from T to Publishable.

Our code to call this remains the same:

val post = new BlogPost("Test", "This is a test post")
val web = new WebPublisher[BlogPost]()
web publish(post)

Fantastic, our publish code gets objects that it knows are publishable, while our client code can just pass domain objects. We have all the boilerplate for conversion separated out from the main code.

However, while this all seems good, this approach does have its downsides. As you can see we are using the wrapper approach: creating a new instance of a Publishable class that wraps the original object. In a high volume system, the additional object allocations of new Publishable wrapper instances on each call to the publish method may have some less than ideal memory and garbage collection impacts.

The other problem with this approach is that is reduces our ability to compose methods in interesting ways. The reason for this is that once the publishing code has actually invoked the implicit conversion it now has the Publishable wrapper rather than the original object. If it passes this Publishable to other methods or classes than these are not aware of the original wrapped type or instance.

We can overcome this problem by modifying the Publishable trait to have a generic parameter type and support a get method to extract the wrapped value - but this then should really be called PublishableWrapper and some of the simplicity starts to break down.

I think the root of the problem here is that type classes are a very functional concept and implicit views tries to coerce these into a hybrid object/functional world. Fortunately, as of Scala 2.8 there is an additional way to implement the type class approach that leads to a more functional style of coding...

Type Classes with Implicit Contexts

An alternative to implicitly converting one class to a wrapper version of that class that adds additional behaviour is to follow more of a helper like approach. In this model we provide an implicit evidence parameter that implements the type class specific behaviour. This is a much more functional approach in that we don't alter the type we are working on. So, on with the code...

trait Publishable[T] {     
  def asWebMarkup(p: T): String
}

case class BlogPost(title: String, text: String)

This is our new Publishable trait and BlogPost class. Note that our Publishable is no longer intended to be implemented or used as a wrapper. Instead, it is now a contract definition of functional behaviour that takes a parameter of type T and transforms it into a String. A much cleaner abstraction. In fact, we can even create a single object instance that implements this behaviour for blog posts:

object BlogPostPublisher extends Publishable[BlogPost] {     
  def asWebMarkup(p: BlogPost) =
     """|
%s
        |
%s
""".stripMargin format(p title, p text)
}

We are also going to need our implicit. This time however, rather than being a conversion it becomes an evidence that we have something that implements Publishable for the type BlogPost:

implicit def Publishable[BlogPost] = BlogPostPublisher 

We also need to update our WebPublisher a bit:

class WebPublisher[T: Publishable] {  
  def publish(p: T) = println(implicitly[Publishable[T]] asWebMarkup(p))
}

There are two interesting things about this class. First, the bounds has now switched from view (<%) to context (:). The context bounds effectively modifies the class declaration to be:

class WebPublisher[T](implicit evidence$1: Publishable[T]) {  ...
}

The second change is the use of implicitly[Publishable[T]] which is a convenience for getting the implicit evidence of the correct type so that you can call methods on it.

Our code to call this remains exactly the same:

val post = new BlogPost("Test", "This is a test post")
val web = new WebPublisher[BlogPost]()
web publish(post)

One advantage that should be immediately obvious is that we are no longer creating new instances for each implicit use. Instead, we are using the implicit evident parameter (which is in this case an object) and passing our instance to it. This is more efficient in terms of allocations.

Also, we explicitly show where we make use of the implicit evidence, which is clearer. This also means that we are never creating a new wrapped type of T that we pass on to other code. We always pass on instances of type T that have implicit evidence parameters that allow T to behave as a particular type class instance.

Conclusion

We have looked at two different approaches to solving the problem of adding behaviour to an existing class without requiring it to explicitly implement a particular contract or extend a specific base class. Both of these make use of Scala implicits and type classes.

Implicit conversions with view bounds provides an approach where a type T can be converted into the type required by the type class. This works, but there are issues associated with the wrapping or transformation aspects of the conversion.

Implicit evidence parameters within context bounds overcome these problems and provide a far more functional approach to solving the same problem.

Cleaner Code with the Scala Type System

Last week I happened to be sitting with a colleague looking at some prototype Java code. We came across a method that neither of us was particularly happy with, but which represented the typical messy code that occurs when wanting to do anything involving types and classes in Java. My initial comment was that it "would be so much cleaner to do in Scala". I therefore thought I'd better have play with the code to prove (if only to myself) that I was right. This post discusses the result of my effort and my conclusions from having done this work.

The Problem

In order to understand the code, let's first look at the problem that it is tying to solve:

The domain is one related to content that can appear on a website. We have a persistent domain model representing this content. However, a number of the content items are sourced from and can be updated in external systems (e.g. a CMS system or a remote content provider). We therefore need to synchronise the state of these external systems into our domain model from time to time. The java code that we were looking at was inside this synchronisation component.

The content is retrieved from the external systems, wrapped in a subtype of ForeignObject. The subtype is based on where the content was obtained from. The ForeignObject implementations can examine the content they contain and return information about its type and its unique business identifier. The synchronisation code then uses this information to lookup the associated object in the persisted domain (which may or may not exist). The ForeignObject and domain object are then passed to a mapper that updates the domain object from data that it extracts from the ForeignObject instance.

The full source code and tests described below can be obtained from my Github account: http://github.com/skipoleschris/type-safe-sync.

The Java Code

Let's first take a look at the Java code that we were less than happy about. Firstly, the ForeignObject implementation that returns the detail about the type of content that it contains:

public class CMSForeignObject implements ForeignObject {
     // Other code removed

    @Override
    public Class getLocalClass() {
        if ("Story".equals(type)) return Story.class;
        else if ("Image".equals(type)) return Image.class;
        else if ("BinaryObject".equals(type)) return BinaryObject.class;
        else if ("RelatedLinks".equals(type)) return RelatedLinks.class;
        else throw new IllegalStateException("Unknown type: " + type);
    }
}

As we can see it looks at some string based type field that it extracts from the wrapped content and returns the associated domain class that represents that content. Perhaps not the nicest code and returning class instances always feels a bit wrong. However, I don't have too many problems with this approach. Where the messy code comes in is in the synchronisation logic that uses this class:

public class SynchronisationService {
     // Setup code remove for clarity

    @SuppressWarnings( { "unchecked" })
    public Content sync(final ForeignObject foreignObject) {
        return findById(foreignObject.getLocalClass(), foreignObject);
    }

    @SuppressWarnings("unchecked")
    private  T findById(final Class clazz, final ForeignObject foreignObject) {
        if(Story.class.equals(clazz)) {
            CMSForeignObject cmsForeignObject = (CMSForeignObject)foreignObject;
            return (T)repository.findStoryById(cmsForeignObject.getId());
        }
        else if(Image.class.equals(clazz)) {
            CMSForeignObject cmsForeignObject = (CMSForeignObject)foreignObject;
            return (T)repository.findImageById(cmsForeignObject.getId());
        }
        else if(BinaryObject.class.equals(clazz)) {
            CMSForeignObject cmsForeignObject = (CMSForeignObject)foreignObject;
            return (T)repository.findBinaryObjectById(cmsForeignObject.getId());
        }
        else {
            throw new IllegalStateException(
                "We have managed to try and synchronise an unsupported class. This is a bug.");
        }
    }
}

How's that for a nice bit of logic? Imagine when we have many different types! I know this is only prototype code and there's certainly plenty we can do to improve it. However, it's quite typical to see this sort of stuff in production code whenever you have to go down into type based logic in Java.

The First Scala Version

To come up with a better solution, the first thing I did was to just convert the Java code directly into Scala. Nothing special here, other than using Scala syntax and modifying to return Option[Story] rather than null. So, first the ForeignObject implementation:

class CMSForeignObject(typeName: String, val id: String) extends ForeignObject {
  def localClass[C <: Content]() = typeName match {
    case "Story" => classOf[Story]
    case "Image" => classOf[Image]
    case "BinaryObject" => classOf[BinaryObject]
    case "RelatedLinks" => classOf[RelatedLinks]
    case _ => throw new IllegalStateException("Unknown type: " + typeName)
  }
}

And the synchronisation code:

class SynchronisationService(repository: ContentRepository) {

  def sync(foreignObject: ForeignObject): Option[Content] = findById(foreignObject.localClass, foreignObject)

  private def findById[T <: Content](clazz: Class[_], foreignObject: ForeignObject) = {
    if ( clazz == classOf[Story] )
      repository.findStoryById(foreignObject.asInstanceOf[CMSForeignObject].id).asInstanceOf[Option[T]]
    else if ( clazz == classOf[Image] )
      repository.findImageById(foreignObject.asInstanceOf[CMSForeignObject].id).asInstanceOf[Option[T]]
    else if ( clazz == classOf[BinaryObject] )
      repository.findBinaryObjectById(foreignObject.asInstanceOf[CMSForeignObject].id).asInstanceOf[Option[T]]
    else throw new IllegalStateException("We have managed to try and synchronise an unsupported class. This is a bug.");
  }
}

Works fine, but not really much better than the Java code.

Adding Scala Type Goodness

Once I had an initial Scala version I then spent a couple of hours playing around with the code and some Scala type goodness. The resulting synchronisation code is:

class SynchronisationService(repository: ContentRepository) extends ContentFinder {

  def sync(foreignObject: ForeignObject): Option[Content] = findById(foreignObject)

  private def findById[C <: Content, FO <: ForeignObject](foreignObject: FO) =
    Option(finder(findStory) orElse finder(findImage) orElse 
           finder(findBinaryObject) apply foreignObject)

  private def findStory(foreignObject: CMSForeignObject) = repository findStoryById (foreignObject id)
  private def findImage(foreignObject: CMSForeignObject) = repository findImageById (foreignObject id)
  private def findBinaryObject(foreignObject: CMSForeignObject) = repository findBinaryObjectById (foreignObject id)

No nasty if/else block. No need to deal with Class instances. No nasty type casting. Much more readable. Hopefully this is much more friendly for developers and will be far easier to maintain in the future as we come to add more types of content to be synchronised. So, how did I manage to achieve this much more readable code?

The first piece of the puzzle was to eliminate the returning of Class instances from the ForeignObject. Instead we now return a new ContentType instance:

class CMSForeignObject(typeName: String, val id: String) extends ForeignObject {

  def contentType[C <: Content, FO <: ForeignObject] = {
    val contentType = typeName match {
      case "Story" => new ContentType[Story, CMSForeignObject]
      case "Image" => new ContentType[Image, CMSForeignObject]
      case "BinaryObject" => new ContentType[BinaryObject, CMSForeignObject]
      case "RelatedLinks" => new ContentType[RelatedLinks, CMSForeignObject]
      case _ => throw new IllegalStateException("Unknown type: " + typeName)
    }
    contentType.asInstanceOf[ContentType[C, FO]]
  }
}

The ContentType instance supports generics on both the type of content and the type of foreign object. It captures the actual erased types used via implicit manifests on its constructor:

class ContentType[C <: Content, FO <: ForeignObject]
        (implicit val mC: Manifest[C], val mFO: Manifest[FO]) {

  def compatibleWith(cClass: Class[_], foClass: Class[_]) = (cClass == mC.erasure) && (foClass == mFO.erasure)
}

It also provides a compatibleWith method that is used internally within the finder code that we will look at below.

This final piece of the puzzle is the implementation of theContentFinder trait that is mixed in to the synchronisation code. This is where most of the type magic occurs in order to simplify the actual synchronisation code:

trait ContentFinder {
  implicit protected def finderToPartialFunction[FO <: ForeignObject, C]
        (handler: LookupHandler[FO, C])(implicit mFO: Manifest[FO], mC: Manifest[C]) =
    new PartialFunction[AnyRef, C] {
      def apply(foreignObject: AnyRef) =
        if ( isDefinedAt(foreignObject) ) handler(foreignObject.asInstanceOf[FO])
        else throw new IllegalStateException("We have managed to try and synchronise an unsupported class. This is a bug.")

      def isDefinedAt(foreignObject: AnyRef) =
        foreignObject.asInstanceOf[FO].contentType.compatibleWith(mC.erasure, mFO.erasure)
    }

  protected def finder[FO <: ForeignObject, C](lookup: FO => Option[C]) = new LookupHandler(lookup)

  protected class LookupHandler[FO <: ForeignObject, C](lookup: FO => Option[C]) {
    def apply(foreignObject: FO) = lookup (foreignObject).getOrElse(null).asInstanceOf[C]
  }
}

The first insight that I had when working with this code is that the if/else condition across classes is actually a partial function across content types. We have a ForeignObject that can return a ContentType instance that contains the type information about the type of content and the type of foreign object. We therefore just have to see if there is a partial function defined at that particular combination and if there is then we can apply it.

The resulting implementation therefore defines a finder method that takes a function containing the actual code that should be applied to the ForeignObject/Content pair. It returns this wrapped in a LookupHandler instance. The synchronisation code can then just define find functions for each type that it can deal with and pass them to the finder method. Finally we define an implicit conversion for the LookupHandler instances that convert them to partial functions so that we can compose them with the orElse method. The partial function captures the erased types from the handler using implicit manifests and compares these with those captured by the content type to see if the function can be applied.

Conclusion

We can clearly see that the resulting synchronisation code is significantly cleaner, more easily understood and more maintainable than the original Java code. However, this comes at the expense of slightly more lines of Scala code and some fancy logic around finders and implicit partial functions. Is the benefit really worth the extra?

I can see both sides of the argument. I can certainly understand that for the Scala novice that the ContentFinder is somewhat impenetrable. However, its the synchronisation code that is likely to be updated a number of times as more types of content are bought into the domain. The code to deal with all of the type goodness is unlikely to change that much and can be easily maintained by more experienced Scala developer. Therefore the readability and maintainability of the business code wins out in my mind over some extra, well abstracted complexity.

This tends to be the typical approach to the Scala language and one of the reasons that it can be so incredibly powerful. Use all the power of the language and its incredible type system in the framework and support code so that the actual application logic can be as minimal and simple as possible.

The Architecture Doesn't Work

I've been building web and other large-scale, enterprise type applications for many years, following the standard accepted approaches to application architecture. I've been increasingly feeling that these approaches are somewhat flawed and that we need something better. Over this series of three blog posts I'm going to talk about some new technologies and architectures that I have been having some great success with. In this first of the three posts I want to look at why...

The Architecture Doesn't Work

If like me you've been building enterprise style applications in Java (or pretty much most other similar languages) then you will be intimately familiar with this layered architectural pattern:

For those, who need a quick refresher, here's a quick summary of each layer:

• Presentation Layer - Deals with rendering the current state of the application to the user/client. Could be a web page, an GUI application or even some structured representation (e.g. XML, JSON). Usually renders the contents of the Domain Objects, often by some form of template system.
• Controllers - Handles events generated by the user/client and orchestrates the processing and Presentation. Typical approach is to accept an incoming request, extract any supplied request values, call a Service, pass the resulting Domain Objects to the appropriate Presentation component and finally return a result.
• Service Layer - Executes business logic and processes against the Domain Objects and returns the resulting objects. Typically stateless and transactional. Processing usually involves using the Persistence Layer to load Domain Objects from a Persistent Store, working with the Domain Objects to mutate state, using the Persistence Layer to save the changes and then returning the resulting Domain Objects for presentation.
• Domain Objects - The main objects representing entities in the business, their relationships and the business rules associated with each. Entities are usually persisted to a Persistent Store. Some people prefer anaemic Domain Objects, but I have argued that rich models are significantly better.
• Persistence Layer - Provides an interface between the Service Layer and the Persistent Store that talks the language of Domain Objects. Allows the Service Layer to undertake CRUD (Create, Read, Update Delete) and Find operations against the Persistent Store.
• Persistent Store - The storage for the data in the application. Usually a Relational Database Management System (RDBMS). Domain Objects are typically mapped to tables. Supports transactional semantics.
• Object-Relational Mapping (ORM) - A library that assists the mapping between Domain Objects and the Persistent Store. Tries to solve the impedance miss-match between object and relational structures. Used by the Persistence Layer. Modern solutions use annotations on the Domain Objects (e.g. JPA & Hibernate)
• Container Services - General services provided by a container. Supports features including: dependency injection; transactions; configuration; concurrency; service location; aop etc.

So, why doesn't this work?

It has become apparent to me over many projects that the above architectural approach suffers from a number of technical weaknesses. Often these have come about through the aim of simplifying the programming model for developers, but as we will see later the result is often the opposite. First, let's look at what I believe to be the main general technical problems that we find in this standard architecture. Later we will look at the impacts of these problems on the application and developers.

Thread-per-request model

Typically, in the above architecture, each request is handled in its own thread. Threads are usually managed in a pool and are then assigned to a request when it arrives. The thread and request are then linked until a response is returned, at which time the thread is returned back to the pool. This approach aims to simplify the development model by reducing the need for developers to have to think about concurrency issues - effectively giving them a single-threaded application path for handling each request.

Unfortunately, assigning a separate thread to each request is a very inefficient way of utilising system resources. Threads are fairly heavy-weight entities, having to maintain their own stacks, address space and so forth. The work involved in scheduling them is also quite large and given today's i/o intensive applications, many of them will be in a blocked state at any point in time. Additionally, most systems can only support a finite number of threads before suffering degradation in performance. (Some languages have tried to overcome the thread problem by introducing lighter weight constructs, such as fibers, but these still share many of the same problems for concurrent programming.)

The technical limitation of this thread-per-request approach is to actually stifle system scalability and impact application performance. Additionally, when the need to share state occurs, then developers must step outside their comfort zone into the world of concurrent programming: something the thread-per-request model has isolated them from.

Constant reloading from the persistent storage

Given a thread-per-request model, there is a natural approach to load all objects required to service a request from the persistent store on each request. Often this is completely unnecessary as a large percentage of the required data is unlikely to have changed from one request to another, or to be different between two separate running requests. However, with no convenient way to store state safely between requests or share infrequently changing state across threads we are forced down the load everything each time direction. The alternative is to drop down into shared state and concurrent programming - and we've already explored why that's not the best option! Techniques such as lazy loading try to minimise the overhead, but we have to accept that much of the data an application uses is being reloaded unnecessarily on each request.

Using database transactions for optimistic locking & concurrency control

Given each request is working with its own copy of application data kept in its own thread, how does the architecture handle multiple threads trying to update the same data at the same time? The general approach is to use database transactions to implement optimistic locking. Two requests can each load a separate copy of some data in their own threads and update it as they wish. When a thread's current transaction is committed, the state is written back to the persistent store. The database's transaction support ensures that each thread's changes are committed in an atomic and correctly isolated manner. Optimistic concurrency can follow a last-commit-wins model, or many ORM solutions offer a row versioning approach so the second transaction to commit changes to an object will fail with a stale data exception.

However, relying on the lowest level in the application stack to prevent concurrent updates isn't always the best solution. For a start, it allows both transactions to pretty much complete all their processing before one discovers that all its work is no longer valid. Secondly it causes problems when concurrency in the application layers above is required as some state would be shared across threads, and thus transactions - not nice to deal with. Finally, it doesn't actually simplify the problem because instead of having to deal with concurrency, the developer must now deal with the possibility of transaction rollback due to stale data, and the need for replaying of transactions. You'd be surprised how many applications I've come across that either don't address the problem (just raise a 500 error) or try to do something in this area and fail miserably!

Tight coupling between domain and persistent store through ORM

Another problem inherent in this architectural model is the tight coupling between the domain objects and the persistent store. This is caused by the need for the domain objects to be closely coupled to the object-relational mapping (ORM) solution. Why would we want to couple our domain objects this tightly? Well, it turns out that quite often we have to do this for performance reasons related to needing to reload from the persistent store for each request. Given that we are loading data so frequently we find that we have to tune our domain model not to make it optimal to our business model but to allow us to work most efficiently with the persistent store. And, don't even get me started on annotation based configuration (aka JPA) which forces us to consider and include all the details of our persistence strategy inside our representation of the business domain!

Scaling through adding servers

Once we have built our application using our architecture, we then have to deploy and scale it. Given that our thread-per-request approach doesn't make the best use of resources, the typical approach to scaling is to add additional servers, each running a separate copy of the application. Unfortunately this is not a particularly good way to achieve scale because we are still dependent on a shared database - and we are making heavy use of the database by loading data on each request and also using it for concurrency control.

Additionally, this approach to scalability also causes session based data sharing problems. With a couple of servers we can perhaps use session clustering with some success. As the number of servers grows we end up either having to use sticky sessions (i.e. tie each session to a single server - which means sessions are lost if that server crashes) or use some other way of persisting session data. This usually involves either adding session state into our already stressed database or introducing a whole new technology (distributed cache) to handle this data.

Static configuration

While not as significant as many of the above items, our standard architecture, and the libraries it is built upon, tends to push us towards a model of static configuration held in XML/YAML/Properties or other similar files. This increases the difficulty in managing our application at scale and in trying to make dynamic changes to values to tune the running system. When we want to support dynamic configuration we are often forced down the route of exposing properties to a management console (i.e. JMX) or pushing configuration down into the database or distributed cache, which we already saw above is not the ideal direction.

Poor approach to fault tolerance

Finally, we have the problem of fault tolerance. Typically, the approach to exceptions at any stage of processing a request is one of: catch the exception at the top level, log it and then display a generic "Oops, something went wrong!" message to the user. Hardly a great user experience. Unfortunately our architecture makes doing anything more than this prohibitively hard. For example, we might want to put some context information in the message. However, when the exception was thrown the developer might not have added this context information to the exception or, more likely, the exception was thrown by a library (such as the ORM) which is unaware of the context in the first place. We might also try to implement a re-try strategy, but implementing retries in a thread-per-request model is actually very difficult - you have to remember to throw everything you currently have away (because memory state in the thread may not be consistent with the database), clear all caches and so on. Try it, it's pretty hard!

And what is the impact?

So, given all of the above technical weaknesses with our current architectural approach, what effects do these have on our application?

Achieving performant applications is more difficult than it should be

The first major impact is that the architecture makes it hard to achieve application performance: the thread-per-request model makes poor use of resources and, loading unchanged data from the database for each request is inefficient and overloads the database.

Given these problems we generally find that we have to consider performance far earlier and in much greater depth than we really should. I'm not saying that we should never develop without considering performance (that would be negligent), but that the need to optimise our well written code and architecture for performance should be something we do rarely and in response to specific issues identified during performance testing. Designing a domain model so that it has the most efficient mapping to a database in order to achieve basic application performance is neither desirable nor the best way of capturing an accurate representation of the business domain. Compromising simple code for more complex but performant alternatives just to meet basic performance criteria is never desirable.

Another impact of the poor performance characteristics of our architecture is that we often end up having to circumvent the simplified thread-per-requets model in order to get a performant and usable application. What do we mean by this? We have to add some form of shared state - exactly what the simplified request model was put in place to avoid. Typically, we do this in one of two ways: adding caching or doing concurrent programming.

When an application proves to be less performant than required, most developers will initially suggest adding caches for data and results that don't change regularly. There are plenty of places in an application where caching can be applied. However, implementing caching is SIGNIFICANTLY more complex than most developers like to assume. Let's consider some of the things that need to be addressed: how do we keep the cache in sync with the database? what's the expiry strategy? what's the update strategy? do we pre-warm? do we block reads during an update or just block concurrent updates? is a cache per server fine or do we need a distributed solution? how will we ensure we don't get cache deadlock? As you can see, implementing a cache is actually a very complex option which requires great skill to get right. Caches should be reserved for special cases and should not be a catch-all for badly performing code and architecture.

The alternative approach to a cache is to introduce some form of shared state with concurrent access. Rather than loading all objects on each request, we keep common objects in memory and share them across and between requests. However, this comes with many of the same problems as using caching, plus the requirement of transaction management for updating this shared state. If done right, shared state with concurrent access can be simpler, more elegant and more flexible than caching, but it's the doing it right which is the challenge.

Now, this might be an over-generalisation, but my experience has shown that most 'average' developers can't write concurrent code using shared mutable state, multiple threads and synchronisation blocks. They usually end up with deadlocks, inconsistent state and difficult to track down bugs. Why? Because it is HARD and also because the single-threaded thread-per-requet model that they are used to programming to has isolated them from any considerations of concurrency. It's true that modern concurrency libraries (e.g. java.util.concurrent) have helped the problem, but most developers are using these without understanding exactly the reasons why. Just ask an average java programmer to explain the 'volatile' keyword and you will see what I mean!

Additionally, our dominant L-mode brain activity is optimised for linear, single-threaded thought. This in turn makes thinking about concurrency and all its implications a very unnatural process. I don't have any proof, but I have some very strong suspicions that a large proportion of the developer community is just unable to comprehend the real impacts of concurrent threads reading and writing in a shared state model.

Scaling applications is difficult

The other major impact of our current architectural approach is that it doesn't scale very well as application load increases. Firstly, the thread-per-request model just doesn't make good use of resources. Application servers have a finite set of threads that they are able to handle at any one time. Going beyond this limit significantly slows down the server - even though at any time many of the threads will be blocked on i/o. Once a server has reached thread saturation, the only solutions are to speed up performance (which we have seen is very hard) to free threads up more quickly, or add more application servers.

However, adding more application servers doesn't actually solve the problem. All it does is enable more concurrent threads to run, which in turn puts more load on the underlying database. Given the approach of re-retrieving data on each request we just end up overloading the database. We then need to scale the database to handle the extra load - and scaling databases is a VERY specialist job and VERY expensive as well. There's no way we can follow a path of continued scalability following this model. Clearly having an architecture based around cheap commodity hardware running app servers doesn't work if you need to massively scale databases to get any performance - so we are back to caching and shared state again, and we already explored what a nightmare these can be.

The final difficulty of scaling the application comes in the way configuration and shared session state is managed. At low scale, configuration by static config files is fine. Sharing session state through session clustering or sticky sessions is also acceptable. However, as the number of servers grows and infrastructure becomes more complex you soon end up in configuration hell - different versions of the application with slightly different configurations, massive challenges tuning parameters on running servers and so forth. Additionally, sticky sessions become less feasible and any form of session state clustering becomes impossible. Session state therefore needs to be pushed down into the database, increasing its overload and scalability issues or we start having to introducing distributed shared state solutions, with all the problems this entails.

So, it really doesn't work. Where do we go now?

We've seen that the current standard layered architecture that we are using to build applications causes a number of performance and scalability problems. Mostly these have come about from the desire to shield 'average' developers from the complexity of concurrent programming with shared mutable state. Unfortunately this simplicity causes performance problems and impedes scalability, requiring that developers must work around the restrictions in order to build something that works. There must be a better approach that solves these problems without needing developers to become shared mutable state concurrent programming gurus!

In the next post in this series I will look at a solution to these problems using lightweight asynchronous 'actors' and immutable messages. The final post will then look at some specific technology solutions that I have employed to implement this new approach.

Anti-Patterns and Rich Domains

At one of my customers we have been doing a lot of work on rich domain models, based on the principles of Domain Driven Design by Eric Evans. During this work we identified a particular anti-pattern in the existing code. I was trying to explain this to one of the developers on my team and it proved quite a subtle distinction. After thinking about it a bit more I decided to write this blog entry with some code examples to explain it in more detail.

Background

In the particular domain in question we have a (very simplified!) notion of Content and Metadata. Each piece of Content has some Metadata attached. However, the Content is sourced from one location (for example a CMS system) and Metadata is sourced from another (such as a remote web service). The challenge is combining the objects from these two different sources into a model that can be used by the higher layers of the application.

Anti-Pattern Solutions

The current solutions to this problem are based around the concept of an aggregator that pulls content from the different sources and merges them together into the returned objects. In all cases the returned objects follow the anaemic domain pattern of just fields with setter and getter methods.

Anti-Pattern 1: Transient Relationship

In this pattern, the aggregator pulls one object (the Content) from its source, uses an id field in this object to obtain the other object (the Metadata) from its source, and then sets the Metadata on the Content as a transient field:

public class Content {
    private String id;
    private Long metadataId;
    // Other fields

    private transient Metadata metadata;

    // Constructors, setters & getters
}

public class Metadata {
    private Long id;
    // Other fields

    // Constructors, setters and getters
}

public class Aggregator {
    // Fields, constructors and setters

    public Content getContent(String id) {
        Content content = cms.getContent(id);
        Metadata metadata = metadataService.getMetadata(content.getMetadataId());
        content.setMetadata(metadata);
        return content;
    }
}

The above code has a number of major problems:

• Clients of the Content class can use both the metadataId and metadata properties, possibly interchangeably. This makes for fragile client code that is not receptive to change.
• Any serialisation will result in the transient field being lost. How do we get it back?
• When we want to update the metadata relationship do we update the metadataId, metadata or both? How do we keep them in sync?
• What happens if we can't get the metadata, but successfully get the content? Do we throw an exception and prevent the content being used (even if it can)? or do we return content with a null transient field - requiring the client code to do null checking?

So, clearly having and id and a transient field representing the same relationship is not a good approach, can we do it without the transient?

Anti-Pattern 2: Decoupled Objects

In this pattern we avoid the transient object by keeping the two objects (Content and Metadata) separate and using the aggregator to retrieve each:

public class Content {
    private String id;
    private Long metadataId;
    // Other fields

    // Constructors, setters & getters
}

public class Metadata {
    private Long id;
    // Other fields

    // Constructors, setters and getters
}

public class Aggregator {
    // Fields, constructors and setters

    public Content getContent(String id) {
        return cms.getContent(id);
    }

    public Metadata getMetadata(Long id) {
        return metadataService.getMetadata(id);
    }
}

This code solves SOME of the problems of the first solution, but introduces problems all of its own:

• It is the total responsibility of the client code to manage the relationship between Content and Metadata - making the whole codebase more fragile
• It is very easy for client code to bypass the aggregator entirely and make direct calls to the metadata service, increasing complexity and coupling

So, what's the better way to do this?

The Rich Domain Solution

Our solution to the problem is to correctly model the relationship between Content and Metadata. We can introduce a Repository for Content that correctly sets up and manages the relationship, hiding the underlying management of ids and using real objects instead:

public class Content {
    private String id;
    private Metadata metadata;
    // Other fields

    // Constructors, setters & getters
}

public class Metadata {
    private Long id;
    // Other fields

    // Constructors, setters and getters
}

public class ContentRepository {
    // Fields, constructors and setters

    public Content getContent(String id) {
        Content content = cms.getContent(id);

        // We could proxy the metadata here for lazy loading or to delay exceptions being
        // thrown until the metadata is requested. However, in this simple example we will
        // build the relationship directly
        Metadata metadata = metadataService.getMetadata(content.getPrivateMetadataId());
        content.setMetadata(metadata);
        return content;
    }

    public void save(Content content) {
        // Persist changes and update the relationship if it has changed
    }
}

By hiding the management of the relationship between Content and Metadata in the core structure of the object model we prevent the details of how this is created and managed escaping from the domain model. Changes in the relationship between Content and Metadata can be correctly managed by the domain model. We also have options such as proxying the Metadata in Content to support lazy loading or delayed exception handling - something we can't do when details of the relationship are exposed to or managed by the client code.

Just goes to show how much a bit of good rich domain modelling can improve the structure and maintainability of software, even in very subtle ways.

Addendum

Just been thinking further on the subject. The above adequately addresses the technical aspects of the anti-pattern and the solution. However, there is also a huge cognitive element as well. The aggregator anti-pattern encourages a mental model of the domain as one of disconnected objets that are being forced together. Clients of the domain are therefore much more likely to create code that teats the model in this way: code that will be more complex and fragile. However, following the rich domain approach, clients have a mental model of a single object (Content) and it's relationship to other objects (such as Metadata) without being burdened with any of the separation knowledge. This cleaner mental model of the domain is much more likely to lead to clean, well architected client code that is easier to test, maintain and enhance.

From Java to Scala in O's and X's

I've been doing a lot of evangelising on the Scala language, mainly to Java devs that I work with. A number of the have become very interested in the language and have started making an effort to learn more about it. The most common questions that seem to come up relate to how to move from the Java to Scala language and the key differences (such as a functional approach, building apps though composition and mixins, the type system and so on).

With this in mind I decided to build a small application that starts as a typical Java development and over a number of versions becomes a full-blown Scala implementation. All versions of the application are maintained so that it becomes possible to step through and see each new level of progression into the Scala way of doing things. The progressions can be presented quickly in an hour or so, or it is possible to spend much longer on each one discussing design decisions and so forth. Even without the Scala focus, it's also a good application for discussing different design and implementation strategies with Java developers.

To have an application where the domain is easy to understand I picked the age old Noughts and Crosses game (Tic-Tac-Toe for my American readers). The advantages of this game are that it is very simple to learn and understand, it has some interesting data structures and interesting set of rules that can be explored for selecting the best move to make. It can also be implemented quite happily in a handful of classes and a few hundreds of lines of code. The particular approach I selected was to have the game played by two computer players who each take it in turns to pick the best move to make until one either wins or the game is drawn because the grid is full.

Aside: Initially the rules were so optimised that my implementation only ever resulted in a drawn game. The final solutions therefore ensure that the first couple of moves are randomly selected in order to introduce a bit of interest.

All of the source code that I'm going to discuss is available on my github account at: http://github.com/skipoleschris/OandX

Version 1 - Typical Java Code

After spending so much time writing Scala (and the most Scala like Java code possible) it was surprisingly difficult dropping back into the type of Java code that you find on most projects. For this version I tried to adopt the Java coding style of a typical average Java developer. Code is written in basic Java and tests in Java using TestNG. The solution works find but has a number of code and design smells, specifically:

• 'null' is used to represent empty positions on the grid
• The grid is represented in a Java Bean style and so all details of how to work with the contents of the Grid are actually outside the Grid class - leading to a pattern of utility classes that contain large amounts of domain logic
• There is a lot of duplication in the WinScanner and MoveFinder classes
• MoveFinder in particular makes it very difficult to separate the rules being applied from the complex code implementing them
• MoveFinder has the most fantastic if ( ... == null ) multi-repeated check method!

Version 2 - Slightly Improved Java Code with ScalaTest

The next version improves the Java code slightly. (It's still code way below the level I would normally write, but this is an exercise in converting from Java to Scala, not in producing perfect Java code!). In particular, the Grid class now contains more domain logic; the WinScanner and MoveFinder classes have duplication removed; and the MoveFinder is implemented with a chain of filters rather than the nasty if clause. The MoveFinder in particular is still WAY too complex.

The other main feature of this version is that tests have been ported over to ScalaTest. I went for the BDD style of tests using FeatureSpec, GivenWhenThen and MustMatchers as I feel this shows the full power of DSL-like test constructs. Most Java developers I have show this to seem to find it very readable. Typical tests now look like:

feature("The OnX grid") {

  scenario("can have a token added to it") {
    given("a new grid")
    val grid = new Grid

    when("a token is added at a given position")
    grid.addToken(Grid.MIDDLE, Token.nought)

    then("that position contains the token")
    grid.getToken(Grid.MIDDLE) must be (Token.nought)
  }

}

Hopefully much more readable!

Version 3 - Java Without Semicolons

The third version ports the Java code directly to Scala with minimal use of advanced Scala language features. All I did here was convert classes and data structures directly, remove boilerplate code and use Scala for loop syntax. At this point it just looks and reads pretty much like a Java application.

For example, here's the same method from the MoveFinder class implemented in both Java and Scala:

private static class DoubleWinPositionFinder implements PositionFinder {
    @Override
    public Position findPosition(final Grid grid, final Token token) {
        final Set positions = new HashSet();
        for ( final Line line : grid.getLinesWithMatchingTokenAndTwoSpaces(token)) {
            for ( final Position position : line.getEmptyPositions() ) {
                if ( positions.contains(position) ) return position;
                else positions.add(position);
            }
        }
        return null;
    }
}

private class DoubleWinPositionFinder extends PositionFinder {
  def findPosition(grid: Grid, token: Token): Position = {
    var positions = Set[Position]()
    for ( line <- grid.linesWithMatchingTokenAndTwoSpaces(token) ) {
      for ( position <- line.emptyPositions.toList ) {
        if ( positions.contains(position) ) return position
        else positions.add(position)
      }
    }
    null
  }
}

This approach is a great way to get working with Scala. Just bring all your Java knowledge and coding style with you, make use of the Scala tools, test frameworks and so on and gradually move towards advanced Scala when you feel comfortable.

Version 4 - Moving Forwards With Scala

In this version, I moved to a much more Scala like model. In particular:

• The Grid class is now immutable, returning a new Grid on each change
• The Option[T] concept is now used as a replacement for null to allow better representation of empty positions
• The code uses more advanced functional concepts such as map, flatMap, filter and so forth.
• Mixins are used to compose the Grid with traits representing line handling, win scanning and move finding. This gives a much better represented Grid concept and smaller API surface area while still allowing separation of concerns into separate traits and classes

While I think this is a much better implementation than version 3, I am still not happy with the implementation of some of the line building logic and the move finder is still too complex and makes it difficult to separate the rules being applied from how they are implemented. In particular code like this (which finds all the empty positions on a list of lines) is just way too messy:

def emptyPositions(lines: List[Tuple2[List[Option[Token]], Position]]) =
  lines.filter(_._1 contains None).flatMap(empties => empties._1 zip positions(empties._2)).filter(_._1 == None).map(_._2)

This leads me to believe that while I am using some of the more advanced language features that something is wrong with my underlying data structures if the code gets this complex. However, looking at our move finder function we can see some simplification starting to take place:

private case object DoubleFreePositionFinder extends PositionFinder {
  def findPosition(token: Token) = {
    val allEmptyPositions = emptyPositions(linesWithMatchingTokenAndTwoSpaces(token))
    if ( allEmptyPositions.contains(Position(1, 1))) Some(Position(1, 1))
    else if ( allEmptyPositions.isEmpty ) None
    else Some(allEmptyPositions.head)
  }
}

Version 5 - The Final Solution

For version 5 I decided to approach the problem from a much more functional perspective. By switching my thinking from the object approach (i.e. what is my state and how can I encapsulate it) to a functional approach (i.e. what functions do I want to perform) I was able to realise an important concept. Although the noughts and crosses game is represented as a grid, all of the functions we want to apply are either on an individual position on the grid or on one of the eight lines that can be made from the grid. By switching my data structure to one more appropriate for applying these functions we end up with a significantly simplified set of functions for evaluating the game state.

For example, we can take a list of tokens, zip them with a list of positions and then apply functions across either the token part or the position part of the pair:

class Grid(tokens: List[Option[Token]]) extends TokensWithPositions
                                        with Lines
                                        with LineQueryDSL
                                        with WinCheck
                                        with MoveFinder {

  require(tokens.length == 9)

  val positions = for (row <- 0 to 2; column <- 0 to 2) yield Position(row, column)
  private val values = tokens zip Grid.positions

Lines can therefore be represented in exactly the same manner:

type Line = List[Pair[Option[Token], Position]]

This new structure greatly simplifies the rest of the application code when it comes to building and working with lines:

def emptyPositions(lines: List[Line]) = lines.flatMap(_.filter(_._1 == None).map(_._2))

The other main change in this version is separation of the rules for finding the best position for a player from how those rules are implemented. This is achieved through a custom DSL that allows defining the rules in a highly readable way. For example, the rule we saw previously now becomes:

private def doubleFreePosition(token: Token) =
  find linesHaving 2 positions Empty and 1 tokenMatching token select First take EmptyPosition

The DSL is a fairly simple one, implemented as a chain of filtering functions that reduce the lines down and then a selector that pulls the correct result from the matching lines. It actually turns out that the DSL is pretty easy to read and follow through, which also significantly simplifies the code and reduces duplication.

Although version 5 is a much better solution, there is still room for improvement and some functions that could certainly be implemented in a better way. Let me know when you find them and send me your better solution :-)

Version 6 - Adding Some Actors

The final version takes the code from version 5 and wraps actors around the classes. One actor for the game coordinator, one for the grid and one for each player. These actors are loosely coupled through message passing.

Noughts and Crosses is not the best demonstration for actors and concurrency as it's turn based nature makes it a purely sequential game. However, version 6 does allow the concept of actors to be demonstrated in an easily understood way and leads on to more detailed conversations about using actors for concurrent problems.

Conclusions

The Noughts and Crosses example shows how a Java programmer can migrate to Scala in a gradual manner, adding new Scala concepts as they become more comfortable. However, it's important to point out that Scala is certainly not a silver bullet for good software. Like all development it requires careful thought, good design, solid programming practice, good testing and constant refactoring. Any Scala application will only be as good as the developer(s) building it.

Solving Polymorphic Problems using Scala Type Classes

Last week I attended Scala Lift Off London. There were a couple of sessions on Type Classes in Scala, which I found very interesting. In fact, they offer a great solution to a problem that I encountered recently on a Java project (although I'm using Scala code for this entire post).

This particular project had a number of domain objects that could be 'published'. In this particular case, published meant converted to an XML representation which was then passed to a remote server for processing. Multiple domain objects can be published at the same time in a 'publish package'. The challenge was that none of these domain objects had any particular similarities or common interfaces. E.g.

class Page {
  // Page attributes and methods
}

class Story {
  // Story attributes and methods
}

// Other domain objects: image, component etc.

Now, there are a number of ways that these classes could be handled for publishing. An initial suggestion might be to add a Publishable interface to each domain object. However, this is a bad idea for a number of reasons:

• It couples the knowledge of publishing into domain objects that are used for multiple different purposes
• The domain objects are complicated for all users who don't require publishing
• It may not be possible to change the domain objects if they are owned by another project.

So, how do we go about adding these domain objects into the publish package. Well, there are a number of approaches, none of which are ideal. The first is to add a separate method to the publish package for each class that can be published:

class PublishPackage {
  def add(page: Page) = ...  // convert to XML and add to package
  def add(story: Story) = ... // convert to XML and add to package
  ... // And so on
}

This creates a publish package that is very unstable and will soon grow beyond a maintainable size, not good. Another approach is to have some kind of dynamic class-based lookup:

class PublishPackage {
  private mappers: Map[Class, PublishMapper] = ...

  def add(obj: AnyRef) = ... // Lookup mapper by object class and call method on it
}

This is much better as the logic to map each domain object to its publish XML is now outside the publish package. However, it still has some issues in that we need to update the map of mappers each time we have a new domain object type to publish, which may involve changing publish code or configuration. There is also a runtime risk here in the the compiler will let us pass any object to the add method even if it can't be published, so we loose some level of type safety.We also have to write additional code in the add method to handle this case.

This general - I want to handle objects polymorphically but can't because they don't share a common base - problem occurs all too frequently in software, especially when dealing with legacy code bases or objects from external dependencies. Fortunately Scala Type Classes give us an elegant solution to the problem. What we will do is take the second solution described above, but use Type Classes to solve the problems of runtime safety and the need to update the map of mappers.

First, we change to publish package to support adding of publish-ready XML instead of any specific or general binding to domain objects:

class PublishPackage {
   def +(nodes: NodeSeq) = ... // Add nodes to publish package
}     

Next we declare a common trait that will be implemented by all the mappers:

trait PublishMapper[T] {
  def formatForPublish(content: T): NodeSeq
}

Next we declare the Type Classes (or Objects in this case) that implement each of the mappers. Note that they are defined as implicit, allowing the correct one to be implicitly selected for the type of domain object being used:

implicit object PagePublish extends PublishMapper[Page] {
  def formatForPublish(content: Page) = ...
}

implicit object StoryPublish extends PublishMapper[Story] {
  def formatForPublish(content: Story) = ...
} 

Next we need to declare the Type Class method that takes an implicit PublishMapper which it will call to convert the domain object into the NodeSeq for adding to the publish package:

implicit def objectToPublishXml[T](t: T)(implicit m: PublishMapper[T]): NodeSeq = m.formatForPublish(t)

Let's talk about this one in more detail. It's a parameterised function marked as being implicit so we can convert from any T to a NodeSeq, provided that there is a PublishAdapter instance available that is also of the parameterised type T. If all the conditions are met then the formatForPublish method is called on the mapper and the result returned.

Now that we have this in place, we can just write the following code:

val somePage = new Page
val someStory = new Story

val p = new PublishPackage
p + somePage
p + someStory

So, now we don't have to modify any existing code when we want to support a new publish type, we just implement a new PublishMapper for it and the compiler will notice that the new implicit conversion is available. Additionally, we are now fully typesafe as the compiler will error if we try to add add any domain objects to the publish package for which there is no publish mapper conversion.

As we have hopefully seen, Scala Type Classes are an elegant solution to a very common problem which gives us continued type safety for a minimal amount of extra code. In fact, I'd argue that the tiny amount of Scala complexity here saves way more code which we would have to write if we were doing class based dispatch and runtime type checking.

Simple and Elegant Property Model

In this post I talked about the need to create simple and elegant solutions to software problems rather than over engineer. I used as example a property mechanism that I have been working on for my new product. Having now got this to a state where I believe it is both simple and elegant I thought I'd share the evolution of the Scala code as a way of exploring this topic in more detail.

The goal of this particular set of classes is to provide a mechanism whereby a (super)user can define definitions for the properties that can be set against an item. The user creating the item then fills in values for these properties. Both users will be utilising a web interface for defining and setting properties. In addition properties may be mandatory and optional and can support default values.

Please note that all the code below was developed iteratively using a Test-Drive Development (TDD) approach. I'm not going to show the tests here, so please be aware that every iteration through the model was first backed by a test to define the required behaviour.

So, after my initial attempt at a solution that became far too complex and over engineered I rolled back to the simplest thing that I could possibly write:

case class PropertyDefinition(name: String)

case class Property(name: String, value: String)

object Property {
  def apply(definition: PropertyDefinition, value: String) = Property(definition.name, value)
}

This simple starting point meets the minimum requirements of a definition of a property and then a property that maps a name to a string value. While this is indeed simple, it's too simple in that it doesn't meet all the requirements and it's also not particularly elegant in the way it restricts values to be strings.

The next step was to add support for mandatory/optional functionality. The property definition was easy to change:

case class PropertyDefinition(name: String, mandatory: Boolean = false)

However, the property concept is more challenging as it is now possible to have properties with no value associated. With the general Scala goal of avoiding using null to represent no value, I instead modified property to hold and Option[String] instead:

case class Property(name: String, value: Option[String])

object Property {
  def apply(definition: PropertyDefinition, value: Option[String]) = value match {
    case None if !definition.mandatory => new Property(definition.name, None)
    case Some(_) => new Property(definition.name, value)
    case _ => throw new IllegalArgumentException("Value must be supplied for property")
  }
}

This is still a pretty simple solution. However it's still missing the requirement for default value support and it now seems less elegant because instead of creating a property with

Property(nameDefinition, "value")

I have to use

Property(nameDefinition, Some("value"))

Also, I'm still linked tightly to String value types. First I decided to deal with the default value requirement:

case class PropertyDefinition(name: String, mandatory: Boolean = false, defaultValue: Option[String] = None)

case class Property(name: String, value: Option[PropertyValue])

object Property {
  def apply(definition: PropertyDefinition, value: Option[String]) = value match {
    case None if definition.defaultValue != None => new Property(definition.name, definition.defaultValue)
    case None if !definition.mandatory => new Property(definition.name, None)
    case Some(_) => new Property(definition.name, value)
    case _ => throw new IllegalArgumentException("Value must be supplied for property")
  }
}

I now have the simplest solution that meets all my requirements. Many developers would stop at this point, but I still feed uncomfortable that the code is not particularly elegant. I don't want to over engineer additional complexity but I'd like to have a cleaner interface to the classes that I have created so far and I'd also like to leave more scope for future changes where possible.

My first improvement was to pull out the tight coupling to a String and instead introduce a PropertyValue class as a wrapper around a string:

case class PropertyValue(content: String) 

case class PropertyDefinition(name: String, mandatory: Boolean = false, defaultValue: Option[PropertyValue] = None)

case class Property(name: String, value: Option[PropertyValue])

object Property {
  def apply(definition: PropertyDefinition, value: Option[PropertyValue]) = value match {
    case None if definition.defaultValue != None => new Property(definition.name, definition.defaultValue)
    case None if !definition.mandatory => new Property(definition.name, None)
    case Some(_) => new Property(definition.name, value)
    case _ => throw new IllegalArgumentException("Value must be supplied for property")
  }
}

Now my property code is not fixed to a string, although my initial implementation of property value is still string based. This has the benefit of keeping the initial version simple but providing scope for someone to refactor the implementation of property value in the future to support different types or other requirements.

So, one element of elegance of the code is improved. Unfortunately it comes at the expense of another. To create a property you now have to type:

Property(nameDefintion, Some(PropertyValue("value"))

Yuk! I need a way to easily build an Option[PropertyValue] from a String in order to avoid all the boiler plate code. This is where Scala implicit conversions come to the rescue. I think their overuse can create code which can be very difficult to debug as you are never certain what implicit conversions are being applied. However in this case they are perfect for bringing the final level of elegance to the code:

object PropertyValue {
  implicit def wrapString(content: String) = content match {
    case "" => None
    case _ => Some(new PropertyValue(content))
  }
  implicit def unwrapString(value: Option[PropertyValue]) = value match {
    case Some(v) => v.content
    case None => ""
  }
}

Given these implicit conversions I can now type:

val property = Property(nameDefinition, "value')

val content: String = property.value

This ticks all my boxes for simplicity and elegance. The code is clean and simple; all the requirements are met. The interface to the classes is also clean and intuitive. However, the solution is also elegant in that it provides ways for future extension without adding excessive additional complexity. Future developers should be able to enhance this code to support more features (such as validation or type safe values) without having to rewrite it from scratch. Time to move on to the rest of my domain model...