Solving the Expression Problem in any language

I was inspired by this excellent post about the Expression Problem. It is a great explanation of how both OO (object-oriented) and FP (functional programming) paradigms each solve half of the Expression Problem but not the whole thing. I encourage you to read that post.

But in case you didn't, here is my (probably inaccurate) paraphrase of the Expression Problem constraints.

1. Add a new data case to a type without changing existing behavior
2. Add a new behavior for a type without changing existing data cases

In the OO paradigm, you can achieve #1 but not #2. But in the FP paradigm, you can achieve #2 but not #1. Again, check the above linked post for excellent examples.

Come at the problem sideways

We have a common mantra around the office. If a problem becomes really difficult to implement in code, take a step back and look at it from a different perspective.

Usually the business perspective... but I digress.

After I read the post and reflected on the expression problem, I realized that we already solved it (because we had to)... in a way that could work in pretty much any paradigm... not using language-specific features like type classes or multi-methods, but using the Messaging pattern. Or rather, treating the data cases like messages that we might (or might not) handle.

Below I will show examples of how to solve the Expression Problem in both FP and OO languages by using this approach. I will use .NET languages, so you know they don't have any of the really cool tricks that we normally see to address the Expression Problem.

F# example

Let's start with the Shape type in the functional-first language F#.

type Shape =
    | Circle of radius:double
    | Rectangle of height:double * width:double
    | Triangle of base:double * height:double

Then let's define an area behavior on a Shape.

module ShapeCalc =
    let area shape =
        match shape with
        | Circle radius ->
            Some (Math.PI * radius * radius)
        | Rectangle (height, width) ->
            Some (height * width)
        | Triangle (base, height) ->
            Some (base * height * 0.5)
        | _ ->
            None

This is pretty close to the normal way you would express types and behaviors in F#. Except...

"Hold on there cowboy! This is functional programming, and you did not exhaustively match every case like the FP ivory tower principles say you have to do."

Well that's the key if you want to solve #1 of the expression problem. You cannot require all data cases to be matched... only the ones you know about. In fact, this currently does an exhaustive match but adds an extra _ match to deal with cases that haven't been implemented yet.

"You are returning an Option, but I don't want to be bothered with the None case!"

Didn't you just reference the FP ivory tower in the last question?... Ok, so here is an important point about solving the expression problem. When you really do need to add new cases without touching existing functions, you also have to expect that existing functions do not know how to handle every case. (And they probably didn't need to anyway.) So you have to be prepared to handle None or empty list or something like that, representing the result of ignored cases.

"Ha! I knew there was a catch!"

Right you are. Solving the expression problem does not lead to magical unicorn developer heaven land. It has its own set of trade-offs. The real problem is that normally the compiler forces you to handle every combination of data case and behavior. And if you miss one there is a compiler error waiting with your name on it. Because that is painful and undesirable in certain scenarios, we are getting around that by declaring only what we know how to handle and telling the compiler not to worry about the rest. But that also means the compiler can't warn us about missed combinations. Hence, trade-offs.

Alright, so let's hold questions for now and show what happens when we add new data cases. Hint: nothing.

type Shape =
    | Circle of radius:double
    | Rectangle of height:double * width:double
    | Triangle of base:double * height:double
    // we just added Ring
    | Ring of radius:double * holeRadius:double

We added a new case, but previously defined area function still compiles and keeps on working as before. We may actually want to handle the new Ring case in area but that can be done later and independently of adding the new data case. #1 achieved. So now let's add a new behavior without touching the type.

module ShapeCalc =
    let area shape =
        ... // same as before

    // we just added circumference
    let circumference shape =
        match shape with
        | Circle radius ->
            Some (Math.PI * 2 * radius)
        | Ring (radius, _) ->
            Some (Math.PI * 2 * radius)
        | _ ->
            None

In this case, the circumference function really only makes sense with round-ish shapes -- otherwise I'd have called it "perimeter". So I am only handling the round shapes I know about. And I did not have to touch the Shape type to make it compile. And adding new Shapes later will not break me. #2 achieved.

We solved the Expression Problem in F#. Now let's take a look at C#.

C# Example

First, let's define the shape types.

public interface IShape {}

public class Circle : IShape
{
    public double Radius { get; set; }
}

public class Rectangle : IShape
{
    public double Height { get; set; }
    public double Width { get; set; }
}

public class Triangle : IShape
{
    public double Base { get; set; }
    public double Height { get; set; }
}

I could have used an empty base class here, but instead I chose to use a Marker Interface called IShape. It is just an interface with no members. Much like inheriting from a base class it allows me represent multiple shapes behind a single base type.

Now let's look at how to make extensible behaviors, starting with Area.

public class ShapeCalc
{
    public static double? Area(IShape shape)
    {
        switch (shape)
        {
            case Circle c:
                return Math.PI * c.Radius * c.Radius;
            case Rectangle r:
                return r.Height * r.Width;
            case Triangle t:
                return t.Base * t.Height * 0.5;
            default:
                return null;
        }
    }
}

This relies on C# 7 -- now with Syntactic Sugar(tm) for type matching.

"This violates the OO blood oath principles! Flames!!1!"

Alright, you got me. OO principles say hide implementation details (aka fields). And don't let external objects depend on implementation details. However, proper OO principles cannot satisfy #2 of the Expression Problem. That is, in a proper OO implementation when I want to add a new behavior to a type with multiple subclasses, I have to go touch every subclass, even if it is just to add a cursory method which throws NotImplementedException.

So something has got to give. And in my rendition, this is what gives. Instead of using idiomatic "objects", we are using the DTO pattern to represent message data. Then instead of using mutation-based class methods, we are using static functions. After all, I did intend to solve the expression problem by using a Messaging style, regardless of language.

So now, we add a new data case.

... // previous classes

// we just added Ring
public class Ring : IShape
{
    public double Radius { get; set; }
    public double HoleRadius { get; set; }
}

Area still compiles without modification. We probably do want Area to be aware of Ring but it can be added later, independently of adding the Ring type. #1 achieved. So now let's add a new behavior for IShape.

public class ShapeCalc
{
    public static double? Area(IShape shape)
    { ... } // same as before

    // we just added Circumference
    public static double? Circumference(IShape shape)
    {
        switch (shape)
        {
            case Circle c:
                return Math.PI * 2 * c.Radius;
            case Ring r:
                return Math.PI * 2 * r.Radius;
            default:
                return null;
        }
    }
}

We added the new behavior without having to simultaneously modify any of the IShape types. #2 achieved.

What do I use this style for?

I use it for places where I already wanted to use Messaging patterns. Example: when my logic code makes a decision, it doesn't perform side effects. Instead it returns messages to represent the decisions. We actually store the decisions first and foremost. (Observe as I arbitrarily coin a new term: behold Decision Sourcing! 😆) We currently call these decision messages Events to distinguish them from other types of messages. Then we might also perform other side effects based on those decisions.

Later, other components read from the event database and process the events they care about to take care of their individual responsibilities. (Example: sending email). No existing behavior is bothered if I add a new event to the system. They don't need to know about it, so they just ignore it. And the event type doesn't break if I add a new listener.

Caveats

Having extensibility in both types and behaviors at the same time -- the answer to the Expression Problem -- does not transform the dev landscape into a Unicorn Utopia. Sometimes old functions should handle new data cases. But the compiler will not tell you about it anymore. So now it is on you, dear programmer, to know it needs doing and remember to do it. The horror!

I think that is why most languages developed since "the problem" was first brought up... well they have not bothered to try to address it. Most of the features that are brought forth to solve "the problem" are generally niche, rarely-used features. Perhaps it is one of those problems you probably don't want to solve unless you really have to.

Maybe in a similar vein to the First Law of Distributed Objects...

The First Law of The Expression Problem

1. Do not solve The Expression Problem.

I hope you enjoyed the article. ❤️

/∞

Comments

[Rafal Pienkowski]

Nice post. I started my journey into F# a few days ago, so the comparison between C# and F# is advantageous. I think that we always should use the right tool to achieve our goal. Functional programming is one of the availabilities. I hope I'll get familiar with the new approach to solving problems with FP instead of OO.

[Kasey Speakman]

Best wishes on your FP journey. The nice thing about F# is you can choose objects when they make sense or when you are not sure how to express something in idiomatically. Most pre-existing .NET libraries use objects, so integrations often must still use some level of object orientation.

Probably the largest benefit you will find is using FP in your core business logic, along with Dependency Rejection. This video has a "testimonial", if you will, on the benefit of this usage. Starting at 17:45. The speaker takes a very pragmatic approach and introduces F# in some parts, but sticks with C# in other parts of the existing system. The talk is overall about architecture, though.

[Rafal Pienkowski]

Thanks. I'll take a look on this video.

[Bohdan Stupak]

Hi. Thanks for a great post. Also thumbs up for F# as it's a language I enjoy and regret that it is not as popular in .NET world as Scala on JVM.
Still, I can't quite live with that

However, proper OO principles cannot satisfy #2 of the Expression Problem. That is, in a proper OO implementation when I want to add a new behavior to a type with multiple subclasses, I have to go touch every subclass, even if it is just to add a cursory method which throws NotImplementedException.

Maybe I'm not fully following but to me NotImplementedException indicates a violation of interface segregation principle. If we want to add behaviour only to several subtypes does this mean that they should also inherit other interface (ICircumferencable in our case) which contains new method whereas original interface (IShape in our case) will possess just Area property?

[Kasey Speakman]

Thanks for the comment. You are correct that my statement is for the case not following the ISP (The I in SOLID.) Typically, the comparison for the Expression Problem is between Union Types and subclasses of an abstract class. You could formulate the same with the ISP, but this still does not achieve #2, since you have to touch (add methods to) all classes that should have the behavior. Since the ISP cannot alleviate #2, for my purposes it just trades NotImplementedExceptions -- or alternatively the Null Object Pattern -- for another layer of abstraction to manage and navigate thru. For OO design ISP perhaps adds more value, but here it would just have implied more abstractions.

I believe the value of achieving #2 is having a holistic view of behavior across data cases. Whether base classes or ISP, using proper OO objects means coupling data and behavior. This distributes cross-object behavior into multiple containers (objects), directly at odds with understanding a behavior holistically. Not every problem needs to look at behavior this way, but when you do, organizing them with objects has a very high cognitive load for the developer. That is the primary reason why OO fails to achieve #2 regardless of other applied principles.