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

Over the last few years, I’ve been interested in the Scala programming language and I’ve heard a lot of criticism about its mixed Functional and Object-Oriented Programming nature. On the other hand, Functional Programming has recently become so popular that OOP is now considered an old-fashioned method that should be translated to FP as soon as possible.

In this blog post, I’ll try to compare both approaches in terms of extensibility based on the Expression Problem formalized by Computer Science Professor, Philip Wadler, who greatly contributed to the development of Functional Programming.

Extensibility

We all know that our code is evolving all the time. There is always some refactoring, bug-fixing and (hopefully) additions of new features. Moreover, the majority of bugs, and problems with the code in general stem from the fact that we constantly make changes.

Many of these changes might have been written by your teammates (present or former) a long time ago. There is no way to avoid modification of our code, but we can optimize the number of necessary amendments when adding new features by simply making our code extensible.

Software extensibility is vital so that one of the famous SOLID principles is dedicated solely to this subject, as is formulated by Bertrand Mayer’s Open-Close Principle

SOFTWARE ENTITIES (CLASSES, MODULES, FUNCTIONS, ETC.)
SHOULD BE OPEN FOR EXTENSION, BUT CLOSED FOR
MODIFICATION.

In simple words, we need to create code in such a way that when we want to add something new, we should not be obliged to touch anything written in past.

The Expression Problem

The Expression Problem focuses on one of the most important features of code: extensibility. This can be described as the ability to evolve without:

  • affecting the clarity of the existing code
  • putting much effort into adding new functionality
  • breaking code that works properly

For a long time I’ve been treating extensibility as a single, unidirectional virtue of code, but when I learned about the Expression Problem I realized that there are actually two separate ways in which we can extend the code.

According to professor Wadler, the first direction we can follow is the ability to extend our code by adding new forms. This can be simply described as providing brand new implementations of current interfaces.

The second direction is adding new operations. Operations, as you probably suspect, express functionality represented as a new method in the interface.

The first steps

To test the extensibility of our code, first we need to have something to extend. Our initial example will consist of one operation, represented as an evaluation of an arithmetic expression. We represent it as a recursive data structure of classes that encode expression at each level and tells us what to do with its operands:

val expression = Add(Add(Number(2), Number(3)), Number(4))

Here we model with objects of types Add and Number following the arithmetic expression:

(2 + 3) + 4

Our task is to evaluate or (in more mathematical terms) reduce our expression to a single value of a Double.

The Object-Oriented Programming approach

Let me start with the OOP way of performing polymorphism, so-called subtyping polymorphism.

Let’s start with the fact that an expression can have multiple forms (we can say it is polymorphic); to link these forms together we need to create a common abstraction interface, which in Scala is defined as a trait.

trait Expr {
def eval: Double
}

Our trait defines one operation that can be performed on each form of an expression. We’ve called this operation eval and its task is to reduce the whole expression to the final term of a value of a Double. A few paragraphs above we decided to handle two forms of expression: Number and Add.

case class Number(value: Double) extends Expr {
override def eval = value
}

case class Add(a: Expr, b: Expr) extends Expr {
override def eval = a.eval + b.eval
}

Number just returns its wrapped value and we can treat it as the terminal condition of our recursive schema.

Add evaluates its left and right sides and then sums the computed values. This is nice and easy: it’s just the usual recursion, but expressed in the method invocations rather than the functions.

We have everything we need to test our implementation. Let me remind you how our reference expression looks and try to check its result in REPL.

val expression = Add(Add(Number(2), Number(3)), Number(4))
expression.eval
//res0: Double = 9.0

Great! This seems to be a valid result, hence our implementation works. Now, it’s time to implement the same thing in the FP way.

The Functional Programming approach

In Functional Programming, we try to separate data and operations, so we start with a definition of our ADT (Algebraic Data Type), which defines the model of our arithmetic expression.

trait Expr
case class Number(value: Double) extends Expr
case class Add(a: Expr, b: Expr) extends Expr

Having the abstract definition in place, we need to implement operations that should be applied to the model. The implementation is almost the same as in OOP, so there is no need to explain much. We’ve just replaced the methods for each form with one function that matches one expression and determines what should be done now.

def evaluate(expression: Expr): Double = expression match {

case Number(a) => a
  case Add(a, b) => evaluate(a) + evaluate(b)
}

We have our starting point defined in terms of FP and OOP. Next, we’ll test the extensibility of each of these paradigms.

Extending by adding a new operation

Let’s imagine we want to add the ability to print our expression. To perform printing, we need to add not another form of representing the expression (we still have only Add and Number), but a completely new way of evaluating our expression’s ADT . It can be designed as follows:

val expression = Add(Add(Number(2), Number(3)), Number(4))
val printed = print(expression)
//res1: String = ((2.0 + 3.0) + 4.0)

The Functional Programming way of extending operations

This time we will start with the FP way. This can be done just by adding the new function (operation) below, defined at the beginning eval:

def print(expression: Expr): String = expression match {
  case Number(a) => a.toString
  case Add(a, b) => s”(${print(a)} + ${print(b)})”
}

And that’s it! We’ve just added a new function which accepts Expr objects. In FP, extending operations does not require the previously written code to be edited, so the amount of work and risk of introducing regressions in the code is very low.

We can see that Functional Programming has passed the Expression Problem test on the basis of the ability to extend in the operations direction. We’ve added a completely new operation which does not require modification of existing code.

The OOP way of extending operations

We want to add a new ability to our expression to print itself. We have already defined the expression behaviour by the trait Expr, which indicates that every form of the expression should have an implemented way of reducing itself to a single Double value.

Therefore, we need to add another constraint that our expression should be printable:

trait Expr {
def eval: Double
  def print: String
}

As you can see, this example requires much more changes in existing codebase because the nature of subtyping polymorphism requires that every abstract method that is inherited from its parents is implemented inside the extending class:

case class Number(value: Double) extends Expr {
  override def eval = value
  override def print = value.toString
}

case class Add(a: Expr, b: Expr) extends Expr {
  override def eval = a.eval + b.eval
  override def print = s”(${a.print} + ${b.print})”
}

So far, FP is ultimately more effective in terms of extensibility; however, as you might suspect, the reality is not so rosy as we need to test the second type of extensibility — forms.

Extending forms

Now, let’s check the extensibility within the second dimension by adding new forms of expression to our code. We want to add a new form to represent the ability to negate an expression.

In the previous section, we saw that when we want to extend by adding a new operation (print), FP works very well and fulfills the requirement of the Expression Problem, which is to extend code without performing any modification to the previously written functionality. Let’s see how FP will handle adding a new form of expression.

First, we will start as before with the specification:

val expression = Add(Add(Number(2), Neg(Number(3))), Number(4))

We see that the form of our expression has changed. Now it represents the following:

(2 + (-3)) + 4

So, now our result will be 3 instead of the previous 9. We have everything to start coding in the FP way:

case class Neg(a: Expr) extends Expr

def evaluate(expression: Expr): Double = expression match {
  case Number(a) => a
  case Add(a, b) => evaluate(a) + evaluate(b)
  case Neg(a) => — evaluate(a)
}

def print(expression: Expr): String = expression match {
  case Number(a) => a.toString
  case Add(a, b) => s”(${print(a)} + ${print(b)})”
  case Neg(a) => s”-${print(a)}”
}

I realise I might have disappointed many FP fans : Functional Programming is terrible at adding new forms. As with OOP, when adding new operations we need to modify every piece of our code to provide an additional way of representing our expression.

Let’s now check how OOP performs in this regard. We can start by just adding a new class and implementing the operations declared previously:

case class Neg(a: Expr) extends Expr {
  override def eval = — a.eval
  override def print = s”-${a.print}”
}

And that’s all. We added a new form without touching any existing code. In this case OOP wins, so it seems that we have a draw.

Conclusions

In this blog post, I’ve presented one of the most important problems in software development: extensibility. We all know how valuable it is to write good, extensible programs, and how it feels when we are adding a new feature and we don’t need to dig into the whole codebase. This example of the Expression Problem is simple, but it touches both aspects of extensibility and shows how the two major programming paradigms (FP and OOP) deal with this problem.

We’ve seen that there is no silver bullet for problems of extensibility in terms of FP and OOP development techniques. Hopefully, Scala allows the use of both paradigms and we can approach the problem of extending our code by just choosing the correct style when implementing features. However, it is very hard to predict future extensibility when starting development.

So, Scala itself is not a solution to this problem, but thanks to pattern known as Type Class we can entirely solve Expression Problem (introducing new forms and operations without touching existing code). I’ll introduce you to it in the next blog post!

But if you want to get to know about how Type Classes can be implemented in Scala you can find it in my previous blog post