Can extension methods solve the expression problem?

14 March 2020

Let's explore how extension methods in C# can solve the expression problem. For an introduction to the expression problem, take a look at my first post in this series. Extension methods are essentially used to define operations over a given type without modifying the original definition of the type.

First, we define IExpr as a marker interface and implement it in the Const and Add types. The implementation of Const and Add here is identical to that in the previous post.

public interface IExpr { }

public class Const : IExpr
{
    public double Value { get; }

    public Const(double value) =>
        Value = value;
}

public class Add : IExpr
{
    public IExpr Left { get; }
    public IExpr Right { get; }

    public Add(IExpr left, IExpr right) =>
        (Left, Right) = (left, right);
}

The Eval operation is now defined as an extension method over the IExpr type. The implementation of Eval here uses a switch expression. Note that the class containing this extension method may or may not be in the same namespace as the IExpr, Const and Add types.

public static class IExprExtensions
{
    public static double Eval(this IExpr e) => e switch {
        Const c => c.Value,
        Add a => a.Left.Eval() + a.Right.Eval(),
        _ => throw new NotImplementedException()
    };
}

The View operation is also defined as an extension method, but in a different namespace.

public static class IExprExtensions
{
    public static string View(this IExpr e) => e switch {
        Const c => c.Value.ToString(),
        Add a => $"({a.Left.View()} + {a.Right.View()})",
        _ => throw new NotImplementedException()
    };
}

Now, let's try adding a new Mult type that implements the IExpr interface.

public class Mult : IExpr
{
    public IExpr Left { get; }
    public IExpr Right { get; }

    public Mult(IExpr left, IExpr right) =>
        (Left, Right) = (left, right);
}

Again, the definition of the Mult type is identical to that in the previous post. However, the extension methods defined previously are not aware of this type, and so new extension methods that wrap around the previous definitions will be needed.

public static class IExprExtensions
{
    public static double Eval(this IExpr e) => e switch {
        Mult m => m.Left.Eval() * m.Right.Eval(),
        _ => Operations.Eval.IExprExtensions.Eval(e)
    };
}

public static class IExprExtensions
{
    public static string View(this IExpr e) => e switch {
        Mult m => $"({m.Left.View()} * {m.Right.View()})",
        _ => Operations.View.IExprExtensions.View(e)
    };
}

While this does satisfy the compiler, the following code will raise an exception:

var constExpr1 = new Const(7);
var constExpr2 = new Const(2);
var constExpr3 = new Const(3);

var multExpr1 = new Mult(constExpr1, constExpr2);
var multExpr2 = new Mult(constExpr2, constExpr3);

var addExpr = new Add(multExpr1, multExpr2);

addExpr.Eval();    // throws NotImplementedException

This doesn't work as the Eval call above invokes the first extension method we defined, which is still unaware of the Mult type. We're also overlooking an important detail about switch expressions - they perform type casting at runtime! This violates the type safety requirement of the expression problem and unfortunately concludes that extension methods cannot solve the expression problem.

The code in this post can be found here along with relevant tests.

Tags: Solving the expression problem