xQuant - Visitor pattern is for compiler, not for human

I often hear that object oriented programming is just fundamentally easier.

Early on, OO programmers realize their world is not complete and they use patterns.

Many of those patterns are low level compiler steps. Not only those patterns do not offer you any extra power, but they only amount to manually do the work of a compiler, provably adding complexity, on top of all the useless syntactic noise to implement it.

Many object-oriented practicioners learned to live with such annoyances, but the cost is real, as we will see.

I will shamelessly reuse the example of Mark Seemann and add some abstract math twist, to highlight

how the extra complexity is really added at a fundamental level in OO.
why having a language respectful of fundamental constructs brings benefits

Sum types

Given some type PaymentService, the following sum type can be defined in, say, F#

type PaymentType =
 | Individual of PaymentService
 | Parent of PaymentService
 | Child of originalTransactionKey : string * paymentService : PaymentService

A value of type PaymentType can be either an Individual, or a Parent, or a Child. Each case is made of respectively, a PaymentService, a PaymentService, a string and a PaymentService.

It can be written algebraically as

P a y m e n t T y p e = P a y m e n t S e r v i c e + P a y m e n t S e r v i c e + (s t r i n g * p a y m e n t S e r v i c e)

$PaymentType = PaymentService + PaymentService + (string * paymentService)$

The language (F#) adds facility over that algebraic specification, by giving names to each cases (Individual,Parent,…), whereas an algebraic specification as such only allows to talk generically of “the first case”, “the second case”, etc…

It does not work against algebra, it naturally helps you work with it.

How does that relate to object oriented programming / C# ?

We could start with the C# implementation and show its equivalence to a sum type, but let’s derive this pattern instead.

That is, we could show this equivalence in code, or with some algebraic steps. In code, it would just require a lot of work, add some syntactic noise, and tie us to a particular language. Specifically, each step $A \equiv B$ bleow would be translated (or “witnessed”) by a pair of functions taking a value of type $A$ to a value of type $B$ , a value of type $B$ to a value of type $A$ , (informally) inverse of each other.

The algebra route, on the other hand, is language independant, and we can prove our steps are correct.

Algebraic trip

The previous algebraic specification is equivalent to

\begin{aligned} P a y m e n t T y p e \\ \equiv & \forall T . (P a y m e n t T y p e \to T) \to T \\ \equiv & \forall T . ((P a y m e n t S e r v i c e + P a y m e n t S e r v i c e + s t r i n g * p a y m e n t S e r v i c e) \to T) \to T \\ \equiv & \forall T . ((P a y m e n t S e r v i c e \to T, P a y m e n t S e r v i c e \to T, (s t r i n g * p a y m e n t S e r v i c e) \to T) \to T \end{aligned}

$\begin{align} &PaymentType \\ \equiv~ &\forall T. (PaymentType \rightarrow T) \rightarrow T \\ \equiv~ & \forall T. ((PaymentService + PaymentService + string * paymentService) \rightarrow T) \rightarrow T \\ \equiv~ & \forall T. ((PaymentService \rightarrow T, PaymentService \rightarrow T, (string * paymentService) \rightarrow T) \rightarrow T \end{align}$

Rephrasing this equivalence in plain english, it is the same to have

something which can be either one of 3 things
OR
to have a machine that, given arbitrary instructions producing value of some arbitrary type $T$ on what to do on each of those 3 cases, can perform those arbitrary given instructions.

Said otherwise, you either have something, OR the ability to do anything that it can do.

Notice that those principles have nothing to do with code, or, a fortiori, to any language. Those are just fundamental truth which you have to abide to. wether your language is C++ 98 or a new fancy javascript framework. If a language does not make it dead simple to write such transformation, it is a flaw.

If you think this is complex, here is the unabated truth : the resulting code does that plus the encoding of that. If you understand your code you understand both, although you might not know which is which. In any case, two things at once is provably a hell of a lot harder to grasp.

Back to code

The algebraic specification

\forall T . ((P a y m e n t S e r v i c e \to T, P a y m e n t S e r v i c e \to T, (s t r i n g * p a y m e n t S e r v i c e) \to T) \to T

$\forall T. ((PaymentService \rightarrow T, PaymentService \rightarrow T, (string * paymentService) \rightarrow T) \rightarrow T$

is encoded as a type in, say, C# as :

public interface IPaymentType
{
    T Match<T>(
        Func<PaymentService, T> individual,
        Func<PaymentService, T> parent,
        Func<ChildPaymentService, T> child);
}

In plain english, a value which implements the IPaymentType interface has the ability to be given arbitrary instructions for 3 cases, and execute such instruction.

How many possible implementations are there of such interface ?
It has 3 of course. Why ? the isomorphisms is saying just that.
Here’s one, the other are identical (cf Mark Seeman’s for details).

public class Individual : IPaymentType
{
    private readonly PaymentService paymentService;
 
    public Individual(PaymentService paymentService)
    {
        this.paymentService = paymentService;
    }
 
    public T Match<T>(
        Func<PaymentService, T> individual,
        Func<PaymentService, T> parent,
        Func<ChildPaymentService, T> child)
    {
        return individual(paymentService);
    }
}

A variation leads to the famous visitor pattern.

Where is the benefit coming from ?

Some language are not equiped to express the inescapable laws of nature.
In this case, the notion a coproduct.

Thus, we have to work hard to recover them in undirect ways.
To recover it, we have to use some other, more complicated, laws of nature, here the Yoneda lemma, to find an equivalence which is indeed supported in the crippled language.

The same secret power is behind many useful feature. For instance typeclasses are akin to static proofs of some logical predicates.

When your language works logically, reasoning is simpler.

Comparaison

F#,

type PaymentType =
 | Individual of PaymentService
 | Parent of PaymentService
 | Child of originalTransactionKey : string * paymentService : PaymentService

type PaymentJsonModel = 
  { Name : string,
    Action : string,
    StartRecurrent : Bool,
    TransactionKey : string Option} 

let ToJsonModel = function 
    | Individual(ps) ->  ..
    | Parent(ps) ->  ..
    | Child(s,ps) ->  ..

That’s 15 lines, no extra noise, and a child could understand the code

C#

You can find the code in Mark Seeman repo

Let’s just count the lines of code.

File	lines
Child.cs	26
ChildPaymentService.cs	23
IPaymentType.cs	13
Individual.cs	26
Parent.cs	26
PaymentJsonModel.cs	19
PaymentType.cs	41

26 + 23 + 13 + 26 + 26 + 19 + 41 = 174 lines of code spread in many files,
If we extract only the active bits, we get 100 lines of mostly syntactic noise, hiding the encoding of a hidden structure.

public interface IPaymentType
    {
        T Match<T>(
            Func<PaymentService, T> individual,
            Func<PaymentService, T> parent,
            Func<ChildPaymentService, T> child);
    }
    
public class Individual : IPaymentType
    {
        private readonly PaymentService paymentService;

        public Individual(PaymentService paymentService)
        {
            this.paymentService = paymentService;
        }

        public T Match<T>(
            Func<PaymentService, T> individual,
            Func<PaymentService, T> parent,
            Func<ChildPaymentService, T> child)
        {
            return individual(paymentService);
        }
    }
    
public class Parent : IPaymentType
    {
        private readonly PaymentService paymentService;

        public Parent(PaymentService paymentService)
        {
            this.paymentService = paymentService;
        }

        public T Match<T>(
            Func<PaymentService, T> individual,
            Func<PaymentService, T> parent,
            Func<ChildPaymentService, T> child)
        {
            return parent(paymentService);
        }
    }
    
public class Child : IPaymentType
    {
        private readonly ChildPaymentService childPaymentService;

        public Child(ChildPaymentService childPaymentService)
        {
            this.childPaymentService = childPaymentService;
        }

        public T Match<T>(
            Func<PaymentService, T> individual,
            Func<PaymentService, T> parent,
            Func<ChildPaymentService, T> child)
        {
            return child(childPaymentService);
        }
    }
    
public class PaymentJsonModel
    {
        public string Name { get; set; }

        public string Action { get; set; }

        public IChurchBoolean StartRecurrent { get; set; }

        public IMaybe<string> TransactionKey { get; set; }
    }
    
public static PaymentJsonModel ToJson(this IPaymentType payment)
        {
            return payment.Match(
                individual : ps =>
                    new PaymentJsonModel
                    {
                        Name = ps.Name,
                        Action = ps.Action,
                        StartRecurrent = new ChurchFalse(),
                        TransactionKey = new Nothing<string>()
                    },
                parent : ps =>
                    new PaymentJsonModel
                    {
                        Name = ps.Name,
                        Action = ps.Action,
                        StartRecurrent = new ChurchTrue(),
                        TransactionKey = new Nothing<string>()
                    },
                child : cps =>
                    new PaymentJsonModel
                    {
                        Name = cps.PaymentService.Name,
                        Action = cps.PaymentService.Action,
                        StartRecurrent = new ChurchFalse(),
                        TransactionKey =
                            new Just<string>(cps.OriginalTransactionKey)
                    });
        }
    }

Home

Visitor pattern is for compiler, not for human