OOP vs. FP. The pursuit of extensibility part #2

In my previous blog post, I introduced the definition of the Expression Problem by Philip Wadler, along with two implementations of its solution. One of them is based on subtyping polymorphism (the so-called OOP solution); the other, which is implemented via functions with pattern matching, merits the title of a Functional Programming solution. We’ve seen that both solutions have some drawbacks when it comes to some specific ways of extending code. In the Expression Problem’s definition, we are specifically concerned with extending the data model (forms) and behaviours (operations).

In this blog post, I’ll show the Expression Problem’s real Functional Programming solution, which is based on the Type Class pattern.

Type Class 101

If you are not familiar with Type Class or you want to get to know more about its implementation details in Scala, I strongly recommend you read my article on how to build it from scratch in Scala.

Technically Type Classes in Scala are just traits parameterized with some type T. We provide the implementation of interfaces for types we would like to have an instance of. The difference between subtyping and Type Class is that we are not implementing an interface inside the class T itself, but instead supply an implementation that is defined outside the type T. Thus, we are even able to provide a Type Class instance for classes for which we don’t have access to the source code (such as external libraries available as jar packages).

Then we use our Type Class instances as implicitly provided references to objects for some type T, and we define functions parameterized with that type. In this way, we are not constrained to any specific type. The only requirement is to provide the Type Class instance for this type, as we see below:

def pairEquals[A](a: A, b: A)(implicit eq: Eq[A]): Option[(A,A)]

Here the method takes two arguments of some type A and requires the instance of Type Class Eq to be available in the implicit scope of the method invocation.

Expression problem initialization

Model definition

The vital feature of a Type Class is that a separation can be performed on the data and operations. Similarly to the FP approach in part# 1, we’ll start by defining the model that describes what our domain looks like.

case class Number(a: Double)
case class Add[A, B](a: A, b: B)

With the above data types, we are able to define the arithmetic expression like this:

1 + (1 + 2)

in the following code

Add(Number(1), Add(Number(1), Number(2))

Ok, we’ve implemented the domain of an arithmetic expression using the syntax of Scala, and now we need to implement a way of performing operations on the already defined forms.

First behaviours

As you know, the Type Class pattern has two sides: Type Class definition and Type Class instances for selected types.

Type Class definition can be implemented as a parameterized trait with a little help from the macro-based library Simulacrum, which generates necessary boilerplate to make using Type Classes in Scala effortless.

We’ll start with the implementation of the first operation, which is to evaluate our Expression into a single value of type Double. This evaluation is nothing more than applying arithmetic operations to numbers, thus ending up with a result in the form of a single value.

Type Class definition

@typeclass trait Eval[A] {
  def eval(expression: A): Double
}

The @typeclass annotation comes from Simulacrum and suggests that the following trait is a Type Class definition that should have generated methods which I described in my first article on this subject.

As I mentioned in the introduction, the Type Class definition comes in the form of Scala’s type-parameterized trait.

Type Class instances

Now that we have the definition of Eval in place, the next step is providing implementations for Expression’s forms: Number and Add:

implicit val numberExpr: Eval[Number] = 
  (expression: Number) =>  expression.a

We’ve created an EvalType Class instance for Number, which evaluates by unpacking inner field a.

This lambda expression is transformed into an implementation of an anonymous class (which extends trait Eval with one abstract method) thanks to the so-called Single Abstract Method feature of Java 8.

We have the implementation of Eval for the Number type, so the next natural step is to provide it for Add as well:

import Eval.ops._
implicit def addExpr[A: Eval, B: Eval]: Eval[Add[A, B]] =
(expr: Add[A, B]) => expr.a.eval + expr.b.eval

The body of this function is quite easy to understand and is not very interesting. We are able to invoke eval because of the feature called Extension Methods provided by import Eval.ops. generated by Simulacrum.

We just use the Eval[A] and Eval[B] Type Class instances (provided implicitly by the compiler thanks to Context Bounds):

implicit def addExpr[A: Eval, B: Eval]

We then delegate evaluation of both sides of the expression and result of the Add operation to the type class instances.

The interesting part here is that we don’t have to provide a Type Class instance for every type or type combination in this case, such as Add[Number, Add] and Add[Add[Number, Number], Number].

We might think that here we have a two-step Type Class derivation. We implement the Type Class instance for Add and assume that somewhere in its implicit scope there will be further instances of Eval for A and B.

Now we can use our helper method to evaluate an expression

Add(Number(1), Add(Number(1), Number(2))).eval

The ultimate extensibility of Type Class

Using Type Classes, I’ll now show how we can introduce extensibility into our code in terms of adding the new forms and the new operations.

New Operation

As in the previous part of this series, we aim to extend our arithmetic expression project with the ability to visualize expressions in a textual form.

To do so, we need an additional Type Class which is responsible for transforming an Expression to a single value of type String:

@typeclass trait Show[A] {
  def print(expr: A): String
}

Now we need to provide instances of Show for types Add and Number. As implementation of the instance for Number is trivial, I’ll show only the one for Add:

object Show {
  implicit def addShow[A: Show, B: Show]: Show[Add[A, B]] =
    (expr: Add[A, B]) => expr.a.print + “ + “ + expr.b.print
}

As you can see, there is no significant difference between the definitions of the Type Classes Eval and Show. Derivation of an instance for this Type Class follows the same mechanism of applying implicit parameters as previously, so if anything isn’t clear, please go back to the description of the implementation of Eval for Add.

We have already added a new way of interpreting our expression without modifying the existing code, so we have the proof that Type Classes are doing well in terms of extending code by adding new operations.

New Form

Now we need to check how our new implementation technique copes when new forms are added to the data model.

In line with the previous post, we will add the ability to express the multiplication operation in our arithmetic expressions system:

case class Mul[A, B](a: A, b: B)

We have implemented two operations represented by Type Classes Eval and Show; therefore, as we’ve just added the new form, we need to provide instances of these Type Classes for the type Mul:

import Eval.ops._
implicit def mulExpr[A: Eval, B: Eval]: Eval[Mul[A, B]] =
  (expr: Mul[A, B]) => expr.a.eval * expr.b.eval
implicit def mulShow[A: Show, B: Show]: Show[Mul[A, B]] =
  (expr: Mul[A, B]) => expr.a.print + “ * “ + expr.b.print

We’ve added the completely new form of our expression and we are able to implement every operation that we defined previously.

Conclusions

In the previous blog post, I showed that subtyping and pattern matching didn’t provide a solution for the problem of two-dimensional extensibility. When it comes to adding new implementations of an interface/trait, subtyping does the job; however, when we want to add a new operation to a trait, we have to make changes in all the existing implementations.

By contrast, the implementation based on pattern matching handled adding new operations well; however, when we introduced a new subtype, we needed to make a change in each function to avoid a MatchError.

Fortunately, in this article, we have seen that the introduction of Type Classes has solved both our problems with extensibility. We were able to extend our logic by adding new operations and forms, but without modifying anything in the existing code.