Intro

So far, in this series, you’ve seen plenty of comparisons between Functional and Object-Oriented Programming. In Part #3, in particular, I’ve presented a thorough overview of how the FP vs. OOP choice can affect the extensibility characteristics of your program.

You’ve seen how, by design, adding a new variant is easy in OOP and hard in FP. In contrast, adding a new operation is easy in FP, but hard in OOP. Easy and hard were defined with direct relation to the Open-Closed Principle. An easy change is when you extend the capabilities in your software without changing existing code. A hard change is when you need to modify the existing implementation to add new behavior.

I’ve stated several times that the FP vs. OOP choice is not binary. You can(should) have a healthy mix between the two. To achieve this mix, though, you need to be armed with the right toolset.

In this article, I’ll show you one of the tools to make your design more Functional, even in an OOP environment. Concretely, you’ll see how adding a new operation in OOP can become easy with the help of the Visitor Pattern.

Even though I believe you should be able to follow along with this article if you haven’t read the posts so far, I encourage you to do so. This will help you get the full context of the discussion. It will also broaden your perspective on the fundamental design advantages and limitations of FP and OOP.

Let’s start our journey with the Visitor Pattern.

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.

Starting Point

The starting point for my work in this article is where I ended up in Part #1. There, I’ve implemented the initial version of my small interpreter following OOP idioms. At this point, the interpreter supports two operations – evaluating expressions and converting them to a string. The expressions themselves can be either an Addition expression or an Integer constant.

In other words, I have implemented the following Operations Matrix:

You can find the full source code for Part #1 here.

Problem to Solve

As with every other Design Pattern, the Visitor exists to solve practical problems. Presenting it in isolation with some abstract description is not super helpful. This is why I will put it into action with a specific use case of extending my interpreter with an additional operation.

Recall that, in Part #3, I gave a very detailed comparison of the extensibility characteristics of Object-Oriented and Functional Programming. You’ve seen how adding a new operation is hard in OOP and easy in FP.

However, I’ve also stated that, with some upfront design, this problem can be mitigated. This is the role of the Visitor.

The new operation I’ll be adding is the same I introduced in Part #3. This is the “CountZeros” operation. Its purpose is straightforward – just to count how many zeros there are in an expression. This simplicity will allow us to focus on the new program design rather than on the specific implementation details.

OOP Challenges

First, let’s recall why we say it’s hard to add a new operation in OOP.

Remember that OOP defines each operation as part of the object itself. Operations can’t exist in isolation. They are always part of the enclosing objects’ context.

Pictorially, adding the CountZeros operation means changing each of the existing expressions – Integer and Addition:

Ad hoc implementation requires several changes to the existing codebase.

First, you need to modify the IExpression interface to include the new operation:

public interface IExpression
{
    // ...

    int CountZeros();
    
    // ...
}

Then, you need to edit the MyInt and Addition classes by implementing CountZeros:

public class MyInt : IExpression
{
    // ...

    public int CountZeros() => // Implementation

    // ...
}

public class Addition : IExpression
{
    // ...

    public int CountZeros() => // Implementation

    // ...
}

You see how several modifications to the existing codebase are required.

For some straightforward and infrequent use cases, this might be OK. But there are scenarios when you don’t have any idea how many and what sort of operations you will need in the future. You may even want to allow the clients of your library to define any operations they want.

In such cases, it’s impossible to modify your classes and keep adding new operations for every client request. You need to design your system in a way that would allow for adding new operations without touching the existing classes.

That’s the raison d ‘être for the Visitor.

The Visitor Pattern – Overview

In this section, I’ll give a brief overview of the Visitor Pattern from a higher-level perspective. I understand that such an abstract definition may not be very easy to absorb if you’ve never heard of the pattern before.

That’s why in the next section, you will see a step by step implementation of adding the CountZeros operation using a Visitor. You can also explore the final source code here.

Let’s move on with the overview.

When it comes to Design Patterns, it’s always handy to see what the classic GoF book has to say on the topic. If you go to the Visitor Pattern chapter, you’ll see the following intro description:

Visitor lets you define a new operation without changing the classes of the elements on which it operates.

That’s precisely what we are looking for, right? But how should we implement it in our expression example?

Another Level of Indirection

You may have heard the famous aphorism by David Wheeler, which states that “All problems in computer science can be solved by another level of indirection.” Let’s see what that means in our scenario.

We want to be able to define different operations over the expressions without touching the existing classes. This means that the expressions have to support some sort of plug-in architecture. The clients should implement something that represents an operation. They should plug in this something into the expression. Then, the expression would just delegate the external calls to this something.

Something here is the Visitor.

UML Diagram and the Program Flow

Here is a UML diagram for the Visitor Pattern in the context of our CountZeros operation:

Let’s say you are the Client, and you have an expression, e.g. you hold a reference to some IExpression object. You want to count the number of zeros in this expression.

You then create a new CountZerosVisitor class implementing the IVisitor interface. You’ll need to provide a “count zeros” implementation for every type of expression. In the current case, you’ll implement the Visit(MyInt) and Visit(Addition) methods.

Then you just pass your CountZerosVisitor into the expression you hold by calling the Accept(Visitor) method.

The expression just delegates the call to the accepted Visitor by calling its’ Visit method and passing this. Depending on the runtime type of the expression, it will end up calling either the Visit(MyInt) or the Visit(Addition).

The Visitor then performs his logic on the input expression and returns the result.

The Visitor and the Double Dispatch Technique

The described chain of polymorphic calls that builds up the Visitor workflow represents a fairly complicated OOP technique that has a name – Double Dispatch. I explained this somewhat advanced OOP trickery in detail in my previous post.

If you still find the Visitor program flow quite confusing, that’s normal. I’ll delve into the implementation details in the next section, which I hope will give you a thorough understanding of the pattern.

The Visitor Pattern – Implementation

It’s time to implement the CountZeros Visitor.

You can find the final version of the source code here.

First, we need the IVisitor interface. Any client that wants to define his own operation over the expressions will need to implement this.

public interface IVisitor<out T>
{
    T Visit(MyInt integer);
    T Visit(Addition addition);
}

The interface is generic, just to add more flexibility. Different operations(visitors) may require different return types. In the CountZeros case, it’s an integer. But a ToString operation, for example, will need to return a string.

The next change we need is in the IExpression interface. It has to declare a public method that accepts a visitor. This is the plug-in point for the clients where they’ll provide their own Visitor implementations.

public interface IExpression
{
    // ...

    T Accept<T>(IVisitor<T> visitor);
}

Next, we need to implement the Accept method in MyInt and Addition. This is very easy. They just delegate the call to the visitor passing this:

public class MyInt : IExpression
{
    // ...

    public T Accept<T>(IVisitor<T> visitor) => visitor.Visit(this);
}

public class Addition : IExpression
{
    // ...

    public T Accept<T>(IVisitor<T> visitor) => visitor.Visit(this);
}

It’s time for the actual implementation of the CountZerosVisitor:

public class CountZerosVisitor : IVisitor<int>
{
    public int Visit(MyInt integer) => integer.Val == 0 ? 1 : 0;

    public int Visit(Addition addition) => 
        addition.Operand1.Accept(this) + addition.Operand2.Accept(this);
}

The exact implementation details are not that important for the discussion, so I’ll leave it up to you to figure out how the CountZerosVisitor does its’ job.

And here is some driver code that creates a sample expression and applies the CountZerosVisitor.

var expression = new Addition(
    new MyInt(1), 
    new Addition(new MyInt(0), new MyInt(5)));

var visitor = new CountZerosVisitor();
var numberOfZeroes = expression.Accept(visitor);

// Output: "The expression 1 + 0 + 5 has 1 zeroes."
Console.WriteLine($"The expression {expression.Stringify()} has {numberOfZeroes} zeroes.");

If a client wants to execute a new operation on his expression, he would just need to provide some other IVisitor implementation and pass it into the Accept method – in the same manner as on line 6 above.

Note how the IExpression classes stay completely abstracted away from the concrete IVisitor implementation. This is the true power of the Visitor.

The Visitor Pattern enables you to adhere to the Open-Closed Principle by just creating a new Visitor any time you need a new operation without making any changes to the existing classes!

A Note on Encapsulation

As you’re aware, every Design Pattern represents an abstract definition of solving a common design problem. The exact implementation can vary between different use cases. This is, of course, true for the Visitor Pattern as well. Let’s discuss one such implementation detail that’s related to encapsulation.

There is a small(or not so small) problem with the current implementation.

Remember that, the Visit method receives, as an argument, the expression object itself:

public interface IVisitor<out T>
{
    T Visit(MyInt integer);
    T Visit(Addition addition);
}

For the Visitor to do its’ job, it needs access to the internal state of the expression. For example, if the expression is an Addition, it needs to get to the two operands. If it’s MyInt – it requires the underlying integer.

Therefore, we need to expose the fields from the MyInt and Addition classes by making them public/internal. This undoubtedly breaks the encapsulation of the current design.

What’s the alternative?

Instead of passing the object itself, we can directly give the Visitor the data it needs. This is what I mean:

public interface IVisitor<out T>
{
    T Visit(int operand);
    T Visit(IExpression operand1, IExpression operand2);
}

So, for the MyInt expression – we directly provide the integer value. For the Addition – we pass the two operands.

The Visitor doesn’t need to reach out to the expression object anymore as it has all the data it needs. Here is the new version of the CountZerosVisitor:

public class CountZerosVisitor : IVisitor<int>
{
    public int Visit(int operand) => operand == 0 ? 1 : 0;

    public int Visit(IExpression operand1, IExpression operand2) => 
        operand1.Accept(this) + operand2.Accept(this);
}

The cool thing is that we can now make the fields in MyInt and Addition private again:

public class MyInt : IExpression
{
    private int Val { get; } 
    
    public MyInt(int val)
    {
        Val = val;
    }

    // ...

    public T Accept<T>(IVisitor<T> visitor) => visitor.Visit(Val);
}

public class Addition : IExpression
{
    private IExpression Operand1 { get; }
    private IExpression Operand2 { get; }

    public Addition(IExpression operand1, IExpression operand2)
    {
        Operand1 = operand1;
        Operand2 = operand2;
    }

    // ...

    public T Accept<T>(IVisitor<T> visitor) => visitor.Visit(Operand1, Operand2);
}

These changes can improve the overall design of your program. It’s always better to be “shy” when it comes to your public interfaces and give your clients access to only what they really need.

Why is the Visitor Closer to the Functional Style?

Let’s make one more conceptual overview of how we structure our program when implementing the Visitor Pattern.

Although the Visitor is technically a class implemented in an OO language, the design it imposes is a lot closer to the Functional Programming paradigm.

Why is that?

Let’s have a look at the IVisitor interface once again:

public interface IVisitor<out T>
{
    T Visit(MyInt integer);
    T Visit(Addition addition);
}

Any class that implements IVisitor represents an operation. And it needs to define this operation for every possible type of expression – MyInt and Addition in our case.

If you’ve been following the series so far, the above description should sound familiar. This is precisely how Functional Programming encourages us to decompose our program.

Let me quote some definitions from Part #2:

With OOP, every expression type has an implementation for every operation.

With FP, every operation has an implementation for every expression type.

The second definition is very much related to the Visitor. It represents an operation, and it provides an implementation for every type of expression.

To get more concrete, recall the FP implementation of CountZeros:

let rec countZeros expression =
    match expression with
    | MyInt i -> if i = 0 then 1 else 0
    | Addition (op1, op2) -> countZeros op1 + countZeros op2

Similarly to the Visitor, the countZeros function also implements the operation for each expression type.

Of course, the F# implementation uses pattern matching while the C# solution utilizes the Visitor Pattern, but I hope you appreciate the fundamental similarity between the two approaches.

Summary

In this article, you’ve seen how to utilize the Visitor Pattern when you need a more Functional approach for a specific use case event if the core of your system is designed following the Object-Oriented paradigm.

Being able to switch between different styles of programming is essential for every elegant and maintainable system. As you’ve acknowledged, the Visitor Pattern is one of the tools that help you achieve this goal.

I believe that, at this point, you are able to look beyond the typical UML diagram presented in most of the Design Pattern textbooks and understand how the Visitor Pattern fills some of the gaps between FP and OOP.

In the next posts of these series, I’ll be presenting some more strategies for mixing Object-Oriented and Functional styles.

Stay tuned and thanks for reading!

Resources