Intro
So far, in this series, I’ve done a lot of OOP vs. FP comparison with plenty of examples around our quite primitive expression interpreter.
In Part 1, I introduced the Operations Matrix and implemented it using Object-Oriented Programming.
In Part 2, you’ve seen how the same requirements(the same matrix) can be implemented in precisely the opposite direction by leveraging Functional Programming.
In Part 3, I explored how the OOP vs. FP choice can significantly affect the extensibility characteristics of your program.
I believe that all the materials until now should’ve given you a fresh perspective and strengthened your understanding of the two programming paradigms.
However, the discussion so far has been a little idealistic. We know that in real life, we encounter all sorts of sophistication. In this and the next article, we will review one of them in the context of our interpreter.
In this post, you’ll see a case when even if we’ll be adding a new variant, the FP approach can still be quite convenient. In the next part, I’ll show you how solving the same problem in a pure OOP style can be a lot more complicated.
Note: This series of articles is very much influenced by some of the core ideas presented in the excellent three-part course “Programming Languages” on Coursera. I encourage you to read my review and pick up the course yourself.
Additionally, you can read through Chapter 6 – “Objects and Data Structures” of the bestseller Clean Code by Robert C. Martin. Some of the concepts presented here are also discussed in this great book. By the way, you should read the book anyway if you haven’t already.
Introducing the New Value Type
As a starting point, I will work with the Operations Matrix introduced in Part 1:
We have two variants – Integer Constant and Addition Expression, plus a couple of operations – Eval and Stringify.
In this setting, the value types for our interpreter, or the terminals of the expression tree if you like, are just integers. Which means we can only build expressions like the following one:
Now, I’d like to improve on that. Instead of supporting only integers, I will add another value type, called Rational, which will represent a rational number. This way, we’ll be able to build more rich expressions like this one:
The above expression, for example, will evaluate to the rational number 23/6.
Adding the new Rational variant to our program means adding a new row to the Operations Matrix:
In the previous article, you learned that in order to perform such kind of extension in Functional Programming, we need to modify the existing code in quite a few places. In the next section, I’ll quickly go through the necessary types changes until we get to the exciting part – changing the Addition evaluation to support the new type of value.
In case you find anything confusing, I encourage you to have a look at the final version of the code:
Add the “Rational” Value Type
So far, our Expression type was defined as a Discriminated Union over two named cases – an integer constant(MyInt) and an addition(Addition):
type Expression =
| MyInt of int
| Addition of Expression * Expression
With the new Rational variant, I prefer to introduce a new union type called Value to represent our primitive types – integers and rationals:
type Value =
| MyInt of int
| MyRational of int * int
Here MyRational is composed of two integers – for the numerator and denominator, respectively.
And the Expression type will be one of MyValue and Addition:
type Expression =
| MyValue of Value
| Addition of Expression * Expression
Generally, I could’ve just added MyRational directly as a case in the Expression type. However, I think that extracting the new Value type better conveys the semantics and the separation between composite types(Addition) and the primitive value types(MyInt and MyRational).
Now, as we have our types adjusted, let’s get to the more exciting part – the eval function.
Modifying the “eval” Function
As we’ve changed our data types, we obviously need to make the existing operations work with them. Those operations are Eval and Stringify. I will concentrate only on Eval as I think it’s more interesting. The same reasoning and programming style would apply to Stringify as well. Again, you can review the full code here.
Let’s first recall how the eval function looks like before the changes:
let rec eval expression =
match expression with
| MyInt i -> i
| Addition (op1, op2) -> eval op1 + eval op2
If you need a refresher on this implementation, please re-visit Part 2, where I provided a lot of details on Discriminated Unions, Pattern Matching, and the concrete eval implementation.
In summary, the behavior is as follows:
- If the expression is
MyInt, just return the underlying integer value. - If it’s
Addition– evaluate the left and right operand, which produces two integers, add them together, and return the result.
By extracting the new Value type and adding MyRational to it, we’ll need a few changes for eval:
- The return type will change to
Valueinstead ofint. We don’t need to do anything explicitly to deal with this as the compiler will infer the correct return type based on the other changes we’ll make. - In case the underlying expression is a
Value, we’ll just return it. - In case the underlying expression is an addition, we would evaluate the left and right operands so that we end up with two
Valuetypes, and pass them to a helper function to do the actual addition.
Here is the new version of the eval function:
let rec eval expression =
match expression with
| MyValue v -> v
| Addition (op1, op2) -> addValues(eval op1, eval op2)
You’ll see the addValues implementation in just a moment. But first, let’s discuss its’ required behavior from a high-level perspective.
addValues is a binary method. It has two parameters. Both are of type Value. Every Value is either an int or a rational. This means that it needs to cover four total cases presented in the following table:
Generally, we need to define what it means to add an int to another int, an int to a rational, and so on. This does not depend on the programming style we’re using. It’s just part of the requirements. However, FP and OOP implementations are certainly very different. In this case, the FP approach is arguably quite convenient, which you’ll see in the next section.
As a side note, extracting the addition logic to the helper addValues function is not mandatory. I could’ve written the implementation in place as a nested pattern matching, but I wanted a separate function so we could focus on it in isolation.
Let’s do that next.
The “addValues” Implementation
We mentioned that addValues needs to cover all of the combinations of the possible types for the input arguments. Being in the functional realm with F#, this yields a pattern matching expression with four cases:
let rec addValues(op1, op2) =
match (op1, op2) with
| (MyInt i1, MyInt i2) -> MyInt(i1 + i2)
| (MyInt i, MyRational(num, den)) -> MyRational(i*den + num, den)
| (MyRational(_, _), MyInt _) -> addValues(op2, op1)
| (MyRational(num1, den1), MyRational(num2, den2)) -> MyRational(num1*den2 + num2*den1, den1*den2)
The exact implementation details for each case are not too important. It’s just simple math.
One useful thing to mention, though. I am using a small trick to implement the (rational, int) case on line 5(highlighted). As you know, addition is a commutative operation, meaning that A + B = B + A. So, I can freely re-use the existing (int, rational) implementation if I call the function again with the arguments swapped.
Thoughts on the “addValues” Function
The addValues function is the focal point of this article. It is implemented in a purely functional style. To me, it is very clear and easy to comprehend what it does and how it does it. It’s a small and focused piece of code grouped together to define the addition of two values for our interpreter.
This is important to appreciate now. Following the strategy from the whole series so far, the next thing I’ll do in the following article is to go in the opposite direction and implement the exact same four cases with pure OOP.
Pure OOP “forbids” checking types and encourages us to present every operation as some behavior on an object. The capsulated and straightforward FP implementation will get spread across multiple classes with some pretty obscure communication between them. I think it will come up even more complicated than what you would expect. I’ll need to reach out for a quite advanced OOP trickery known as Double Dispatch that will probably make you scratch your head.
I will demonstrate the pure OOP solution, not because I’m a masochist, but because I want to show another example of the two paradigms accomplishing precisely the same thing by their own means.
More importantly, I want to demonstrate how, in some cases, one of the approaches can be much cleaner than the opposite one. This means that even if we’ve chosen a certain programming paradigm as central to our program, we should be able to use different approaches when it makes sense.
I hope this will convince you that OOP vs. FP choice is not “all or nothing.” It can be both, and in more cases than not, the best design ends up being a hybrid between the two.
Summary
In this article, I’ve added another type of value to our interpreter – the Rational type. I’ve made the necessary changes in the existing types to support it.
You’ve also seen how FP leads to a quite concise implementation for adding together two arguments of a Value type.
In the next article, you’ll compare that with the pure OOP implementation using a sophisticated technique called Double Dispatch.
In the upcoming articles, you’ll see different patterns that let you easily mix OOP and FP together. I will probably start with one of the most famous ones – the Visitor.
Stay tuned and thanks for reading!
