The Visitor Pattern and Pattern Matching

by Phil Freeman on 2013/10/02


For many developers using Object Oriented programming languages, the Visitor Pattern is one of the first design patterns to provide a major roadblock in terms of understanding. It doesn't help that the typical examples are not particularly enlightening, but in my experience, it can be very difficult to explain to a beginner what is going on and why the design pattern is useful, especially with all of the syntactic noise that comes with a language like Java or C#.

I find it much easier to explain the visitor pattern by taking a detour through pattern matching, which can provide useful motivating examples.

Motivating Example

Suppose we want to write a method which calculates payroll for different types of employees. We're given the following business requirement: all employees are of one of two types:

  1. Hourly employees
  2. Salaried employees

One way to model this in an Object Oriented language would be to create an abstract class called Employee with three concrete subclasses HourlyEmployee, SalariedEmployee. Employee would be defined as an interface with a method for calculating the employee's monthly pay, and each employee class would be responsible for implementing it.

It might look something like this:

public interface Employee {

    double calculatePay();
}

public class HourlyEmployee implements Employee {

    public double hourlyRate;
    public double hoursWorked;

    public double calculatePay() {
        return hoursWorked * hourlyRate;
    }
}

public class SalariedEmployee implements Employee {

    public double salary;

    public double calculatePay() {
        return salary / 12;
    }
}

The Problem

You complete the assignment and the code is deployed. It works so well that other developers want to make use of your code as a library in their own work.

Now suppose another business requirement is given: the number of paid vacation hours will be determined by the employee type; hourly employees will be given paid time off depending on the number of hours worked, salaried employees will be given a fixed amount of time off, etc.

Now the problem with the original approach rears its head. The developer responsible for this change should use your code as a library, and will not have access to the original code or the means to modify it. Here's the issue:

Subclass polymorphism easily allows the addition of new types of object, but does not easily allow the addition of new methods

This is the problem that the Visitor Pattern solves.

The Visitor Pattern easily allows the addition of new methods, but does not easily allow the addition of new types of object

We know that the types of employees are not likely to change, but we would like to add new methods to the Employee type, so it seems as if the Visitor pattern would be more appropriate.

When deciding if subclass inheritance is the correct solution for a problem, as yourself "would I prefer the consumers of my API to be able to add new subclasses, or new operations more easily?"

A Non-Solution using Reflection

One anti-pattern which I sometimes see is to solve this problem by using reflection. In C#, the proposed solution might look something like this:

public int computeVacationHours(Employee employee) {
    if (employee is HourlyEmployee) {
        HourlyExployee hourlyEmployee = (HourlyEmployee) employee;
        return ...
    } else if (employee is SalariedEmployee) {
        SalariedEmployee salariedEmployee = (SalariedEmployee) employee;
        return ...
    } else {
        throw new ArgumentException("Unknown employee type!");
    }
}

But we can do better. It would be nice if we didn't have to throw an exception in the final line. What we would really like is to statically check that all cases have been handled. If we could somehow prevent additional subclasses of Employee from being defined elsewhere, we wouldn't need to throw an exception. This problem can be solved using the visitor pattern.

Solution Using Pattern Matching

When I am trying to explain the purpose and implementation of the visitor pattern to another developer, I like to show them how I would solve the problem in a language with pattern matching. I then attempt to sell them the Visitor Pattern as the OOP-ification of pattern matching.

In Haskell, I would define the type of employees as follows:

data Employee 
  = HourlyEmployee { hourlyRate :: Double, hoursWorked :: Double }
  | SalariedEmployee { salary :: Double }

Hopefully, this is self-explanatory, but in case it isn't: reading the vertical bar as "or", and the double colon as "of type", this would read as "An Employee is either an HourlyEmployee with an hourlyRate of type Double, or a SalariedEmployee with a salary of type Double.

Note that an Employee is either hourly or salaried, but never both, and an Employee constructed with the SalariedEmployee does not have an hourlyRate, for example.

With that, the original pay rate calculation, using pattern matching, would look like this:

calculatePay :: Employee -> Double
calculatePay (HourlyEmployee hourlyRate hoursWorked) = hourlyRate * hoursWorked
calculatePay (SalariedEmployee salary) = salary / 12.0

Notice how the code is structured: it is expressed as a series of cases, each of which matches its input data using a specific pattern. The pattern binds some variables such as hoursWorked, which can then be used in the remainder of the computation, on the right hand side of the equals sign.

Solution Using the Visitor Pattern

If the visitor pattern is just the "OOP-ification of pattern matching", then we should be able to derive it by attempting to translate the previous code into an object oriented language. I'll work in C#.

First, we encapsulate a computation which works by case analysis using an interface:

public interface EmployeeCaseAnalysis<Result> {

    Result matchHourlyEmployee(double hourlyRate, double hoursWorked);
    
    Result matchSalariedEmployee(double salary);
}

An implementation of EmployeeCaseAnalysis needs to provide two methods: one calculates the result for an hourly employee, and the other calculates the result for a salaried employee.

The Result type parameter here is used to indicate the type of the result of the computation. More commonly, you will see a version of this class with no type parameter, which would be used when simply performing an action on the data, not transforming it.

public interface EmployeeCaseAnalysis {

    void matchHourlyEmployee(double hourlyRate, double hoursWorked);
    
    void matchSalariedEmployee(double salary);
}

Now, we define the Employee interface. What is an Employee? Well, given any computation by case analysis, we want to be able to perform it and get a result. Here is the result:

public interface Employee {

    void performCaseAnalysis(EmployeeCaseAnalysis caseAnalysis);
    
    Result performCaseAnalysis<Result>(EmployeeCaseAnalysis<Result> caseAnalysis);
}

A concrete class of Employee must provide a way to perform a case analysis with no result, or a case analysis with a result, no matter what its result type.

In fact, there are only two sensible ways to implement this specification: we can either call the matchHourlyEmployee method on the provided EmployeeCaseAnalysis object, if we have an hourlyRate and a number of hoursWorked, or we can call the matchSalariedEmployee method if we have a salary.

Let's call these two implementations HourlyEmployee and SalariedEmployee:

public class HourlyEmployee implements Employee {

    public double hourlyRate;
    public double hoursWorked;

    public void performCaseAnalysis(EmployeeCaseAnalysis caseAnalysis) {
        caseAnalysis.matchHourlyEmployee(hourlyRate, hoursWorked);
    }

    public Result performCaseAnalysis<Result>(EmployeeCaseAnalysis<Result> caseAnalysis) {
        return caseAnalysis.matchHourlyEmployee(hourlyRate, hoursWorked);
    }
}

public class SalariedEmployee implements Employee {

    public double salary;

    public void performCaseAnalysis(EmployeeCaseAnalysis caseAnalysis) {
        caseAnalysis.matchSalariedEmployee(salary);
    }

    public Result performCaseAnalysis<Result>(EmployeeCaseAnalysis<Result> caseAnalysis) {
        return caseAnalysis.matchSalariedEmployee(salary);
    }
}

After some renaming, the code above looks just like code implemented using the visitor pattern. What I have called `EmployeeCaseAnalysis` might be renamed to `EmployeeVisitor`, and the `performCaseAnalysis` methods would most likely be renamed to `accept`. Here is the full version after the renamings:

public interface Employee {

void accept(EmployeeVisitor visitor);

Result accept<Result>(EmployeeVisitor<Result> visitor);

}

public interface EmployeeVisitor {

void visitHourlyEmployee(double hourlyRate);

void visitSalariedEmployee(double salary);

}

public interface EmployeeVisitor {

Result visitHourlyEmployee(double hourlyRate);

Result visitSalariedEmployee(double salary);

}

public class HourlyEmployee implements Employee {

public int hourlyRate;
public int hoursWorked;

public void accept(EmployeeVisitor visitor) {
    visitor.visitHourlyEmployee(hourlyRate, hoursWorked);
}

public Result accept<Result>(EmployeeVisitor<Result> visitor) {
    return visitor.visitHourlyEmployee(hourlyRate, hoursWorked);
}

}

public class SalariedEmployee implements Employee {

public int salary;

public void accept(EmployeeVisitor visitor) {
    visitor.visitSalariedEmployee(salary);
}

public Result accept<Result>(EmployeeVisitor<Result> visitor) {
    return visitor.visitSalariedEmployee(salary);
}

}

It is also common to pass along the entire subclass of Employee to the visitX methods in EmployeeVisitor.

public interface EmployeeVisitor {

    void visitHourlyEmployee(HourlyEmployee employee);
    
    void visitSalariedEmployee(SalariedEmployee employee);
}

But I will skip that here.

It is now possible to implement our original payroll computation as a subclass of EmployeeVisitor:

public class PayrollCalulator implements EmployeeVisitor<Double> {

    public double visitHourlyEmployee(double hourlyRate, double hoursWorked) {
        return hourlyRate * hoursWorked;
    }
    
    public double visitSalariedEmployee(double salary) {
        return salary / 12.0;
    }
}

However, now our coworker can implement the computation of the number of vacation hours without modifying the original code!

public class VacationCalculator implements EmployeeVisitor<Integer> {
   
    public int maxVacationHours;
    public int vacationHoursAccruedPerHourWorked;

    public int visitHourlyEmployee(double hourlyRate, double hoursWorked) {
        return Math.min(maxVacationHours, 
            Math.floor(hoursWorked / vacationHoursAccruedPerHourWorked));
    }
    
    public int visitSalariedEmployee(double salary) {
        return maxVacationHours;
    }
}

A Recipe for Visitors

That is the essence of the visitor pattern. We can summarise what we did in a number of bullet points which can be executed any time we'd like to be able to perform abstract case analyses in an object oriented language.

Suppose we'd like to perform case analysis on our new data type Foo:

  1. Add an interface called FooVisitor.
  2. Add a void interface method to FooVisitor for each possible case in a case analysis, whose method arguments provide the additional data which is available in that case.
  3. Optionally repeat steps 1 and 2 for a generic interface FooVisitor<Result>, in which all interface methods return a result of type Result.
  4. Add an interface called Foo.
  5. Add a void interface method visit to Foo which takes a FooVisitor.
  6. Optionally add an interface method visit to Foo which takes a FooVisitor<Result> and returns a Result.
  7. For each case, add a class implementing Foo, whose implementations of visit call the appropriate method on FooVisitor.

It's a lot of boilerplate (which can be automated), but which gives us the flexibility to define new methods without modifying the original code.

A Brief Type-Theoretic Detour

You may wish to skip this section as it is not really necessary for understanding the visitor pattern, but I have included it since it may be helpful.

A simple example of a type which supports case analysis in Haskell is the Either data type, defined as follows:

data Either a b = Left a | Right b

Either is what is known as a "sum type", because it corresponds to addition at the type level.

A value of type Either a b is either constructed using Left, in which case it contains a value of type a, or with Right, in which case it contains a value of type b. A value of type Either a b contains either an a or a b, but not both.

We cannot immediately define the type Either in C#, since its type system doesn't support sum types. However, Either is isomorphic to a data type which is constructed only using functions, rank-2 polymorphism and records, both of which are available in C#, so it is possible to emulate Either in C# using those features.

Define the following data types

data EitherVisitor a b result = EitherVisitor { visitLeft :: a -> result, visitRight :: b -> result }

data Either' a b = Either' { acceptVisitor :: forall result. EitherVisitor a b result -> result }

This code requires the PolymorphicComponents GHC extension.

The isomorphism between Either and Either' can be witnessed by two functions:

forward :: Either a b -> Either' a b
forward (Left a) = Either' $ flip visitLeft a
forward (Right a) = Either' $ flip visitRight a

back :: Either' a b -> Either a b
back = acceptVisitor (EitherVisitor Left Right)

One can verify that these functions are indeed inverse to one another.

It is this isomorphism that ensures that the visitor pattern is a sound embedding of sum types into C# using only functions, generics and records. Since the types are isomorphic, we can be sure (assuming we don't do anything too subversive) that the typechecker will verify totality in our case analyses.

Extending the Visitor Pattern

The idea behind the visitor pattern can be combined with other features of languages like C# to create new patterns and enable new forms of abstraction. Here are some ideas:

  1. Use generic functions to emulate existential types.
  2. Use generic type parameters to emulate generalized algebraic data types.

I will leave these as extended exercises for the interested reader, but details can be found in some of my previous posts.

The Expression Problem and Type Classes

We have seen that the visitor pattern is useful when we have a fixed set of subclasses and would like to extend the set of operations on those subclasses. This is in contrast to subclass polymorphism which allows the addition of new subclasses for a fixed set of operations.

This begs the question: can we have the benefits of both? That is, can we write an abstraction which easily allows the definition of new subclasses, and new operations, without modification to the original code, and with support from the compiler.

This problem is called the Expression Problem and has been the subject of a great deal of research. In Haskell, the problem is solved using type classes, also known in other languages as traits. New "subclasses" can be defined by adding new data types and writing associated type class instances, and new operations can be defined by writing new type classes and retroactively providing instances for all existing data types.

For example, we might have two different data types for our two employee types in one module:

module Employee.Types

data HourlyEmployee = HourlyEmployee { hourlyRate :: Double, hoursWorked :: Double }

data SalariedEmployee = SalariedEmployee { salary :: Double }

And we could define a type class which represents the operation of computing monthly pay, in a second module:

module Employee.Payroll

class Payable employee where
    pay :: employee -> Double

We can define type class instances for our existing employee types:

instance Payable HourlyEmployee where
    pay (HourlyEmployee hourlyRate hoursWorked) = hourlyRate * hoursWorked
    
instance Payable SalariedEmployee where
    pay (SalariedEmployee salary) = salary / 12.0

Now when a coworker would like to calculate paid vacation allowance, they can do so in another module by defining another type class and associated instances:

maxTimeOff :: Double
hoursOffPerHourWorked :: Double

class Vacation employee where
    timeOff :: employee -> Int
    
instance Vacation HourlyEmployee where
    timeOff (HourlyEmployee _ hoursWorked) = min maxTimeOff (hoursWorked / hoursOffPerHourWorked)
    
instance Vacation SalariedEmployee where
    timeOff (SalariedEmployee _) = maxTimeOff

Now, despite their previous advice, management hands down a third business requirement that there will be a new employee type, who is to be paid a lump sum on completion of the allocated work, and who receives no paid vacation:

module Employee.Contract

data ContractEmployee = ContractEmployee { workCost :: Double, wasWorkCompletedThisMonth :: Bool }

instance Payable ContractEmployee where
    pay (ContractEmployee _ False) = 0.0
    pay (ContractEmployee workCost True) = workCost

instance Vacation ContractEmployee where
    timeOff (ContractEmployee _ _) = 0

This time, an employee was able to implement a new data type supporting existing operations by implementing existing type classes, without the need to modify any existing code.

Type classes allow Haskell developers to do more while writing less code. They allow a form of ad-hoc polymorphism and enable a degree of separation which is not possible in other languages.


Comments powered by Disqus