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:
Here we model with objects of types Add and Number following the arithmetic expression:
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.
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.
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.
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.
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.
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:
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:
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:
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:
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:
We see that the form of our expression has changed. Now it represents the following:
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.
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:
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!
