Adam Gajek

18 Mar 2019

â€¢

6 min read

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.

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.

**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**.

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.

```
@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.

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 `Eval`

Type 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
```

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.

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.

Did you like this article?

Adam Gajek

See other articles by Adam

hello@works-hub.com

Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ

108 E 16th Street, New York, NY 10003

Join over 111,000 others and get access to exclusive content, job opportunities and more!