How to avoid the Visitor pattern in C#
Tags: functional, csharp, dotnet
Published: 2020-05-29 19:19:21

# Arithmetic expressions

Let's say we want to represent a simple arithmetic expression in C#, and then evaluate it. For example, evaluating `1 + (2 + 3)` would produce `6`. What's the best way to do this?

The obvious approach is to define a class hierarchy. We start with a base interface that represents all expressions:

```csharp
interface IExpr
{
    int Eval();
}
```

The `Eval` method is what we'll use to evaluate an expression. For our simple case, we have two concrete implementations of this interface. The first represents a literal integer value (e.g. `5`):

```csharp
class Literal : IExpr
{
    public Literal(int n)
    {
        N = n;
    }

    public int N { get; }

    public int Eval() => N;
}
```

Evaluating a literal is trivial: we simply return the value of the literal itself.

Next, we can represent addition like this:

```csharp
class Add : IExpr
{
    public Add(IExpr a, IExpr b)
    {
        A = a;
        B = b;
    }

    public IExpr A { get; }
    public IExpr B { get; }

    public int Eval() => A.Eval() + B.Eval();
}
```

To evaluate an addition expression, we recursively evaluate both of its subexpressions and then add those two values together.

We're ready to try it out:

```csharp
// 1 + (2 + 3)
public static IExpr CreateTestExpr()
    => new Add(
        new Literal(1),
        new Add(
            new Literal(2),
            new Literal(3)));

public static void Test()
{
    var expr = CreateTestExpr();
    Console.WriteLine(expr.Eval());
}
```

This creates our `1 + (2 + 3)` test expression and then evaluates it, writing `6` to the console.

# Extensibility

That's great, but what if we want to extend our system? For example, let's add a new expression type that represents multiplication. This is easy - all we need is a new concrete implementation of `IExpr`:

```csharp
class Mult : IExpr
{
    public Mult(IExpr a, IExpr b)
    {
        A = a;
        B = b;
    }

    public IExpr A { get; }
    public IExpr B { get; }

    public int Eval()
        => A.Eval() * B.Eval();
}
```

But what if we want to add new behavior to our expressions instead? Let's say we want to be able to print an arbitrary expression by converting it to a string. For example, printing the expression `1 + (2 + 3)` would result in the string `"(1 + (2 + 3))"`. To make this work, we have to add a new `Print` method to the base `IExpr` interface:

```csharp
interface IExpr
{
    int Eval();
    string Print();   // NEW
}
```

But that means that we'd have to modify all the existing expression types (`Literal`, `Add`, etc.) to support printing. Our requirement instantly cascades through the entire code base. We might not even own all the code that has to change, in which case we'd be stuck. Is there any way to add printing ability without modifying existing code?

# The Visitor pattern

The typical way to solve this problem is with the [Visitor pattern](https://refactoring.guru/design-patterns/visitor). To make this work, we have to start over with a different `IExpr` interface:

```csharp
interface IExpr
{
    TResult Accept<TResult>(IVisitor<TResult> visitor);
}
```

Instead of exposing an explicit `Eval` method, this new interface now exposes a generic `Accept` method that supports any "visitor" that implements a separate interface called `IVisitor`:

```csharp
interface IVisitor<TResult>
{
    TResult VisitLiteral(Literal literal);
    TResult VisitAdd(Add add);
}
```

Each concrete `IExpr` subtype then invokes the corresponding visitor method inside its `Accept` method:

```csharp
class Literal : IExpr
{
    public Literal(int n)
    {
        N = n;
    }

    public int N { get;  }

    public TResult Accept<TResult>(IVisitor<TResult> visitor)
        => visitor.VisitLiteral(this);
}

class Add : IExpr
{
    public Add(IExpr a, IExpr b)
    {
        A = a;
        B = b;
    }

    public IExpr A { get; }
    public IExpr B { get; }

    public TResult Accept<TResult>(IVisitor<TResult> visitor)
        => visitor.VisitAdd(this);
}
```

Using this approach, different visitor implementations can implement different behavior. For example, here are two visitors - one that evaluates an expression, and a different one that prints an expression to a string:

```csharp
class EvalVisitor : IVisitor<int>
{
    public int VisitLiteral(Literal literal)
        => literal.N;

    public int VisitAdd(Add add)
        => add.A.Accept(this) + add.B.Accept(this);
}

class PrintVisitor : IVisitor<string>
{
    public string VisitLiteral(Literal literal)
        => literal.N.ToString();

    public string VisitAdd(Add add)
        => String.Format($"({add.A.Accept(this)} + {add.B.Accept(this)})");
}
```

That's terrific - we can now add behavior to our system without modifying existing code. But... what if we still want to be add a new expression type like `Mult` as well? In order to support that, we have to add it to the base `IVisitor` interface:

```csharp
interface IVisitor<TResult>
{
    TResult VisitLiteral(Literal literal);
    TResult VisitAdd(Add add);
    TResult VisitMult(Mult mult);   // NEW
}
```

But that means that we'd have to modify all the existing visitors (evaluation, printing, etc.) to support multiplication. Our requirement instantly cascades through the entire code base. We might not even own all the code that has to change, in which case we'd be stuck. Does this sound familiar?

# The expression problem

This conundrum is called the "[expression problem](https://en.wikipedia.org/wiki/Expression_problem)". Is there a good way to design a system so that it's easy to both a) add new subtypes, and b) add new behaviors, without modifying existing code?

It turns out that there is a rather nifty way to accomplish this, called "[object algebras](https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf)". We start with an "object algebra interface" that looks similar to the Visitor pattern:

```csharp
interface IExprAlgebra<T>
{
    T Literal(int n);
    T Add(T a, T b);
}
```

We're going to use this interface more like a Factory pattern than a visitor, though. For example, we can create the expression `1 + (2 + 3)` like this:

```csharp
public static T CreateTestExpr<T>(IExprAlgebra<T> factory)
    => factory.Add(
        factory.Literal(1),
        factory.Add(
            factory.Literal(2),
            factory.Literal(3)));
```

To create an expression we take a "factory" that implements our expression algebra, and ask it to construct an object of arbitrary type `T` that represents `1 + (2 + 3)`. This type can be whatever the factory wants it to be.

For example, to create an algebra that can evaluate expressions we define an `IEvalExpr` interface that represents any evaluable object:

```csharp
interface IEvalExpr
{
    int Eval();
}

class EvalExpr : IEvalExpr
{
    public EvalExpr(Func<int> eval)
    {
        _eval = eval;
    }
    Func<int> _eval;

    public int Eval()
        => _eval();
}
```

The `EvalExpr` class implements this interface by wrapping an arbitrary function. We can then use these to create a concrete algebra:

```csharp
class EvalAlgebra : IExprAlgebra<IEvalExpr>
{
    public IEvalExpr Literal(int n)
        => new EvalExpr(() => n);

    public IEvalExpr Add(IEvalExpr a, IEvalExpr b)
        => new EvalExpr(() => a.Eval() + b.Eval());
}
```

Note that each method returns an evaluable object of type `IEvalExpr`. We can then test this approach, as follows:

```csharp
IEvalExpr expr = CreateTestExpr(new EvalAlgebra());
Console.WriteLine(expr.Eval());
```

The first line creates an evaluation algebra and uses that as a factory to represent the expression as an evaluable object. The second line evaluates that object and writes the result to the console (`6`, as before).

# Extensibility, again

So far, so good. But how extensible is this approach? Can we implement printing without changing any of the existing code? Yes. As before, we first define an interface for printable objects:

```csharp
interface IPrintExpr
{
    string Print();
}

class PrintExpr : IPrintExpr
{
    public PrintExpr(Func<string> print)
    {
        _print = print;
    }
    Func<string> _print;

    public string Print()
        => _print();
}
```

And then implement a new print algebra that returns printable objects:

```csharp
class PrintAlgebra : IExprAlgebra<IPrintExpr>
{
    public IPrintExpr Literal(int n)
        => new PrintExpr(() => n.ToString());

    public IPrintExpr Add(IPrintExpr a, IPrintExpr b)
        => new PrintExpr(() => $"{a.Print()} + {b.Print()}");
}
```

And can we also create a new expression type, like multiplication, without modifying existing code? Again, the answer is yes. To handle this, we first extend our algebraic interface:

```csharp
interface IExprAlgebraExt<T> : IExprAlgebra<T>
{
    T Mult(T a, T b);
}

class EvalAlgebraExt : EvalAlgebra, IExprAlgebraExt<IEvalExpr>
{
    public IEvalExpr Mult(IEvalExpr a, IEvalExpr b)
        => new EvalExpr(() => a.Eval() * b.Eval());
}
```

This defines a new interface called `IExprAlgebraExt` that includes all of `IExprAlgebra` (i.e. `Literal` and `Add`) and also defines a new method called `Mult` that follows the same pattern. The implementation of this interface is `EvalAlgebraExt`, which similarly inherits from our existing `EvalAlgebra` while also implementing the new `Mult` requirement.

We can test it out on an expression like `4 * (5 + 6)` that contains literals, addition, and multiplication:

```csharp
public static T CreateTestExprExt<T>(IExprAlgebraExt<T> factory)
    => factory.Mult(
        factory.Literal(4),
        factory.Add(
            factory.Literal(5),
            factory.Literal(6)));

public static void Test()
{
    IEvalExpr expr =
        CreateTestExprExt(new EvalAlgebraExt());
    Console.WriteLine(expr.Eval());
}
```

Note that `CreateTestExprExt` takes the extended version of the algebraic interface, which ensures that it can handle multiplication, but still returns a plain old evaluable object of type `IEvalExpr`. We can expose this new interface to our entire system, or we can keep it local only - it's up to us. There's no cascade of changes that we're forced to make.

So, we've successfully solved the expression problem! This approach is more flexible than visitors, but doesn't add significant additional overhead or complexity. I'd call that a win!

# References

For more information:

* The original paper that introduced object algebras: [Extensibility for the Masses: Practical Extensibility with Object Algebras](https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf)
* [From Object Algebras to Finally Tagless Interpreters](https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-object-algebras-to-finally-tagless-interpreters-2/), which walks through this approach in Java and Haskell. I used this article as a basis for my post.
* My [GitHub repository](https://github.com/brianberns/ExpressionProblem) containing the code from this post.