Visitor as a sum type

Monday, 25 June 2018 14:31:00 UTC

The Visitor design pattern is isomorphic to sum types.

This article is part of a series of articles about specific design patterns and their category theory counterparts. In it, you'll see how the Visitor design pattern is equivalent to a sum type.

Sum types #

I think that the most important advantage of a statically typed programming language is that it gives you immediate feedback on your design and implementation work. Granted, that your code compiles may not be enough to instil confidence that you've done the right thing, but it's obvious that when your code doesn't compile, you still have work to do.

A static type system enables you to catch some programming errors at compile time. It prevents you from making obvious mistakes like trying to divide a GUID by a date. Some type systems don't offer much more help than that, while others are more articulate; I think that type systems inhabit a continuous spectrum of capabilities, although that, too, is a simplification.

An often-touted advantage of programming languages like F#, OCaml, and Haskell is that they, in the words of Yaron Minsky, enable you to make illegal states unrepresentable. The way these languages differ from languages like C# and Java is that they have algebraic data types.

In short, algebraic data types distinguishes between product types and sum types. All statically typed language I've seen have product types, which you can think of as combinations of data. Objects with more than a single class fields would be product types.

Sum types (also known as discriminated unions), on the other hand, are types that express mutually exclusive alternatives. Object-oriented programmers might mistake such a statement for sub-classing, but the difference is that object-oriented sub-classing creates a potentially infinite hierarchy of subtypes, while a sum type is statically constrained to a finite number of mutually exclusive cases. This is often useful.

In this article, you'll see that a sum type is isomorphic to a corresponding Visitor.

Church-encoded payment types #

In a previous article, you saw how to Church-encode a domain-specific sum type. That article, again, demonstrated how to rewrite a domain-specific F# discriminated union as a C# API. The F# type was this PaymentType sum type:

type PaymentType =
| Individual of PaymentServiceParent of PaymentServiceChild of originalTransactionKey : string * paymentService : PaymentService

Using Church-encoding in C#, you can arrive at this interface that models the same business problem:

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

In order to use the API, the compiler obligates you to handle all three mutually exclusive cases defined by the three arguments to the Match method. Refer to the previous article for more details and code examples. All the C# code is also available on GitHub.

While the C# code works, I think it'd be a fair criticism to say that it doesn't feel object-oriented. Particularly the use of function delegates (Func<PaymentService, T>, etcetera) seems off. These days, C# is a multi-paradigmatic language, and function delegates have been around since 2007, so it's a perfectly fine C# design. Still, if we're trying to understand how object-oriented programming relates to fundamental programming abstractions, it behoves us to consider a more classic form of object-orientation.

Introduce Parameter Object #

Through a series of refactorings you can transform the Church-encoded IPaymentType interface to a Visitor. The first step is to use Refactoring's Introduce Parameter Object to turn the three method arguments of Match into a single object:

public class PaymentTypeParameters<T>
{
    public PaymentTypeParameters(
        Func<PaymentServiceT> individual,
        Func<PaymentServiceT> parent,
        Func<ChildPaymentServiceT> child)
    {
        Individual = individual;
        Parent = parent;
        Child = child;
    }
 
    public Func<PaymentServiceT> Individual { get; }
    public Func<PaymentServiceT> Parent { get; }
    public Func<ChildPaymentServiceT> Child { get; }
}

The modified IPaymentType interface then looks like this:

public interface IPaymentType
{
    T Match<T>(PaymentTypeParameters<T> parameters);
}

Clearly, this change means that you must also adjust each implementation of IPaymentType accordingly. Here's the Match method of Individual:

public T Match<T>(PaymentTypeParameters<T> parameters)
{
    return parameters.Individual(paymentService);
}

The two other implementations (Parent and Child) change in the same way; the modifications are trivial, so I'm not going to show them here, but all the code is available as a single commit.

Likewise, client code that uses the API needs adjustment, like the ToJson method:

public static PaymentJsonModel ToJson(this IPaymentType payment)
{
    return payment.Match(
        new PaymentTypeParameters<PaymentJsonModel>(
            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)
                }));
}

From argument list isomorphisms we know that an argument list is isomorphic to a Parameter Object, so this step should come as no surprise. We also know that the reverse translation (from Parameter Object to argument list) is possible.

Add Run prefix #

I think it looks a little strange that the functions comprising PaymentTypeParameters<T> are named Individual, Parent, and Child. Functions do something, so they ought to be named with verbs. This turns out only to be an intermediary step, but I'll add the prefix Run to all three:

public class PaymentTypeParameters<T>
{
    public PaymentTypeParameters(
        Func<PaymentServiceT> individual,
        Func<PaymentServiceT> parent,
        Func<ChildPaymentServiceT> child)
    {
        RunIndividual = individual;
        RunParent = parent;
        RunChild = child;
    }
 
    public Func<PaymentServiceT> RunIndividual { get; }
    public Func<PaymentServiceT> RunParent { get; }
    public Func<ChildPaymentServiceT> RunChild { get; }
}

This doesn't change the structure of the code in any way, but sets it up for the next step.

Refactor to interface #

The definition of PaymentTypeParameters<T> still doesn't look object-oriented. While it's formally an object, it's an object that composes three function delegates. We've managed to move the function delegates around, but we haven't managed to get rid of them. From object isomorphisms, however, we know that tuples of functions are isomorphic to objects, and that's essentially what we have here. In this particular case, there's no implementation code in PaymentTypeParameters<T> itself - it's nothing but a group of three functions. You can refactor that class to an interface:

public interface IPaymentTypeParameters<T>
{
    T RunIndividual(PaymentService individual);
    T RunParent(PaymentService parent);
    T RunChild(ChildPaymentService child);
}

The implementations of Individual, Parent, and Child don't change; only the signature of Match changes slightly:

public interface IPaymentType
{
    T Match<T>(IPaymentTypeParameters<T> parameters);
}

Since this change removes the function delegates, it requires client code to change:

public static PaymentJsonModel ToJson(this IPaymentType payment)
{
    return payment.Match(new PaymentTypeToJsonParameters());
}
 
private class PaymentTypeToJsonParameters : IPaymentTypeParameters<PaymentJsonModel>
{
    public PaymentJsonModel RunIndividual(PaymentService individual)
    {
        return new PaymentJsonModel
        {
            Name = individual.Name,
            Action = individual.Action,
            StartRecurrent = new ChurchFalse(),
            TransactionKey = new Nothing<string>()
        };
    }
 
    public PaymentJsonModel RunParent(PaymentService parent)
    {
        return new PaymentJsonModel
        {
            Name = parent.Name,
            Action = parent.Action,
            StartRecurrent = new ChurchTrue(),
            TransactionKey = new Nothing<string>()
        };
    }
 
    public PaymentJsonModel RunChild(ChildPaymentService child)
    {
        return new PaymentJsonModel
        {
            Name = child.PaymentService.Name,
            Action = child.PaymentService.Action,
            StartRecurrent = new ChurchFalse(),
            TransactionKey = new Just<string>(child.OriginalTransactionKey)
        };
    }
}

The ToJson method now has to delegate to a private class that implements IPaymentTypeParameters<PaymentJsonModel>. In Java and F# you'd be able to pass an object expression, but in C# you have to create an explicit class for the purpose. The implementations of the three methods of the interface still correspond to the three functions the previous incarnations of the code used.

Rename to Visitor #

At this point, the Visitor pattern's structure is already in place. The only remaining step is to rename the various parts of the API so that this becomes clear. You can start by renaming the IPaymentTypeParameters<T> interface to IPaymentTypeVisitor<T>:

public interface IPaymentTypeVisitor<T>
{
    T VisitIndividual(PaymentService individual);
    T VisitParent(PaymentService parent);
    T VisitChild(ChildPaymentService child);
}

Notice that I've also renamed the methods from RunIndividual, RunParent, and RunChild to VisitIndividual, VisitParent, and VisitChild.

Likewise, you can rename the Match method to Accept:

public interface IPaymentType
{
    T Accept<T>(IPaymentTypeVisitor<T> visitor);
}

In Design Patterns, the Visitor design pattern is only described in such a way that both Accept and Visit methods have void return types, but from unit isomorphisms we know that this is equivalent to returning unit. Thus, setting T in the above API to a suitable unit type (like the one defined in F#), you arrive at the canonical Visitor pattern. The generic version here is simply a generalisation.

For the sake of completeness, client code now looks like this:

public static PaymentJsonModel ToJson(this IPaymentType payment)
{
    return payment.Accept(new PaymentTypeToJsonVisitor());
}
 
private class PaymentTypeToJsonVisitor : IPaymentTypeVisitor<PaymentJsonModel>
{
    public PaymentJsonModel VisitIndividual(PaymentService individual)
    {
        return new PaymentJsonModel
        {
            Name = individual.Name,
            Action = individual.Action,
            StartRecurrent = new ChurchFalse(),
            TransactionKey = new Nothing<string>()
        };
    }
 
    public PaymentJsonModel VisitParent(PaymentService parent)
    {
        return new PaymentJsonModel
        {
            Name = parent.Name,
            Action = parent.Action,
            StartRecurrent = new ChurchTrue(),
            TransactionKey = new Nothing<string>()
        };
    }
 
    public PaymentJsonModel VisitChild(ChildPaymentService child)
    {
        return new PaymentJsonModel
        {
            Name = child.PaymentService.Name,
            Action = child.PaymentService.Action,
            StartRecurrent = new ChurchFalse(),
            TransactionKey = new Just<string>(child.OriginalTransactionKey)
        };
    }
}

You can refactor all the other Church encoding examples I've shown you to Visitor implementations. It doesn't always make the code more readable, but it's possible.

From Visitor to sum types #

In this article, I've shown how to refactor from a Church-encoded sum type to a Visitor, using the following refactoring steps:

  1. Introduce Parameter Object
  2. (Rename Method (by adding a Run prefix))
  3. Refactor to interface
  4. Rename to Visitor terminology
All those steps are, I believe, isomorphic, in that they have reverse translations. Thus, since (according to Conceptual Mathematics) isomorphisms are transitive, the translation from sum type to Visitor must have a reverse translation as well. This also seems to me to be intuitively correct, as it's clear to me how to go the other way. Starting with a Visitor:
  1. Refactor the Visitor interface to a Parameter Object that composes functions
  2. Refactor the Parameter Object to an argument list
  3. Rename types and members as desired
You can, I think, read this article from the bottom towards the top to get an impression of what such a series of refactorings would look like, so I'm not going to explicitly provide an example.

Summary #

Algebraic data types enable you to make illegal states unrepresentable. Most programming languages have product types, so it's the lack of sum types that seems to make the difference between languages like C# and Java on the one side, and languages like F#, OCaml, or Haskell on the other side.

You can, however, achieve the same objective with object-oriented design. The Visitor design pattern is equivalent to sum types, so everything you can express with a sum type in, say, F#, you can express with a Visitor in C#.

That's not to say that these two representations are equal in readability or maintainability. F# and Haskell sum types are declarative types that usually only take up a few lines of code. Visitor, on the other hand, is a small object hierarchy; it's a more verbose way to express the idea that a type is defined by mutually exclusive and heterogeneous cases. I know which of these alternatives I prefer, but if I were caught in an object-oriented code base, it's nice to know that it's still possible to model a domain with algebraic data types.


Church-encoded payment types

Monday, 18 June 2018 12:04:00 UTC

How to translate a domain-specific sum type into a Church-encoded C# API. An article for object-oriented developers.

This article is part of a series of articles about Church encoding. In the previous articles, you've seen how to implement Boolean logic without Boolean primitives, as well as how to model natural numbers, how to implement a Maybe container, and how to implement an Either container. Common to all four examples is that they're based on sum types with exactly two mutually exclusive cases.

Three binary sum types, and their corresponding match methods.

You may already have noticed that all three translate to Match methods that take two arguments. The translation is so mechanical that you could automate it. Each case in a sum type becomes an argument in a Match method. In this article, you'll see an example of a domain-specific sum type with three cases, translated to Church-encoding.

A payment type model in F# #

In a previous article I described a particular business problem that was elegantly addressed with a discriminated union (sum type) in F#:

type PaymentService = { Name : string; Action : string }
 
type PaymentType =
| Individual of PaymentServiceParent of PaymentServiceChild of originalTransactionKey : string * paymentService : PaymentService

In short, this model enables you to model various payments against a third-party payment service. An individual payment is, as the name implies, a single payment. A parent payment can be used to authorise a series of recurring, automated payments, for example to pay for a subscription. A child payment is one of those recurring payments; it must have a parent payment to authorise it, as automation means that no user interaction takes place.

One task that is easily addressed with the above PaymentType discriminated union is that you can translate the data to JSON in a type-safe manner. The compiler will tell you whether or not you've handled all three cases.

Auxiliary C# classes #

You can Church-encode PaymentType just like Boolean values, natural numbers, Maybe, and Either. Before you do that, however, you need to define the input types involved in each case. These are normal classes, although I prefer to make them immutable:

public class PaymentService
{
    public PaymentService(string name, string action)
    {
        this.Name = name;
        this.Action = action;
    }
 
    public string Name { get; }
 
    public string Action { get; }
}

public class ChildPaymentService
{
    public ChildPaymentService(
        string originalTransactionKey,
        PaymentService paymentService)
    {
        this.OriginalTransactionKey = originalTransactionKey;
        this.PaymentService = paymentService;
    }
 
    public string OriginalTransactionKey { get; }
 
    public PaymentService PaymentService { get; }
}

These are straightforward translations of the F# PaymentService record type, and the tuple associated with the Child case. In a real code base, I'd override Equals for both classes in order to turn them into proper Value Objects, but in order to keep the size of the code down, I omitted doing that here.

Church-encoded payment type #

You can now translate the PaymentType F# discriminated union to a Church-encoded API in C#, starting with the interface:

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

Since there's three cases in the sum type, that turns into a Match method with three arguments, each corresponding to one of the cases. As was also the case for the previous articles' INaturalNumber, IMaybe<T>, and IEither<L, R> interfaces, the data associated with each case is modelled as a function from the data to the generic return type T.

Again, following the recipe implied by the previous examples, you should now add a concrete implementation of the IPaymentType interface for each case. It's natural to start with the first argument to the Match method, individual:

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

The Individual class adapts a PaymentService value, which it passes as the argument to the individual function argument when Match is called. As you've seen in the previous articles, a particular implementation uses only one of the method arguments, so the two other arguments, parent and child, are simply ignored.

The parent implementation is almost identical:

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

The Parent class also adapts a PaymentService value that it passes to a function when Match is called. The only difference is that it calls the parent function instead of the individual function argument.

The third case is handled by the following Child class:

public class Child : IPaymentType
{
    private readonly ChildPaymentService childPaymentService;
 
    public Child(ChildPaymentService childPaymentService)
    {
        this.childPaymentService = childPaymentService;
    }
 
    public T Match<T>(
        Func<PaymentServiceT> individual,
        Func<PaymentServiceT> parent,
        Func<ChildPaymentServiceT> child)
    {
        return child(childPaymentService);
    }
}

While the two other classes both adapt a PaymentService value, a Child object instead composes a ChildPaymentService value. When Match is called, it calls the child function argument with the composed value.

Using the IPaymentType API #

One important feature that I originally had to implement was to translate a payment type value into a JSON document. For the purposes of this example, imagine that you can model the desired JSON document using this Data Transfer Object:

public class PaymentJsonModel
{
    public string Name { getset; }
 
    public string Action { getset; }
 
    public IChurchBoolean StartRecurrent { getset; }
 
    public IMaybe<string> TransactionKey { getset; }
}

This is a mutable object because most .NET serialisation APIs require that the class in question has a parameterless constructor and writeable properties. Notice, however, that in order to demonstrate that all this code still doesn't rely on any primitive Boolean operators and such, the class' properties are defined as IChurchBoolean and IMaybe<string> values, as well as regular string values.

Writing a method that translates any IPaymentType object into a PaymentJsonModel object is now straightforward:

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)
            });
}

Because the Match method takes three arguments, you have to supply a 'handler' function for each of them, and they all have to have the same return type. In this case they all return a new PaymentJsonModel object, so that requirement is fulfilled. All three lambda expressions simply copy over Name and Action, but they differ in the values they assign to StartRecurrent and TransactionKey.

Tests #

In order to show you that it all works, here's a few examples I wrote as xUnit.net tests:

[Fact]
public void IndividualToJsonReturnsCorrectResult()
{
    var sut = new Individual(new PaymentService("MasterCard""Pay"));
 
    var actual = sut.ToJson();
 
    Assert.Equal("MasterCard", actual.Name);
    Assert.Equal("Pay", actual.Action);
    Assert.False(actual.StartRecurrent.ToBool());
    Assert.True(actual.TransactionKey.IsNothing().ToBool());
}
 
[Fact]
public void ParentToJsonReturnsCorrectResult()
{
    var sut = new Parent(new PaymentService("MasterCard""Pay"));
 
    var actual = sut.ToJson();
 
    Assert.Equal("MasterCard", actual.Name);
    Assert.Equal("Pay", actual.Action);
    Assert.True(actual.StartRecurrent.ToBool());
    Assert.True(actual.TransactionKey.IsNothing().ToBool());
}
 
[Fact]
public void ChildToJsonReturnsCorrectResult()
{
    var sut =
        new Child(
            new ChildPaymentService(
                "12345",
                new PaymentService("MasterCard""Pay")));
 
    var actual = sut.ToJson();
 
    Assert.Equal("MasterCard", actual.Name);
    Assert.Equal("Pay", actual.Action);
    Assert.False(actual.StartRecurrent.ToBool());
    Assert.Equal("12345", actual.TransactionKey.Match("", x => x));
}

All three tests pass.

Summary #

The major advantage of sum types in statically typed languages is that you can make illegal states unrepresentable (a maxim attributed to Yaron Minsky). Specifically, in the business example of payment types shown here, I need to be able to express that only three out of four combinations of start recurrent and original transaction key is legal. Specifically, I needed to express that the combination of start recurrent = true and the presence of a transaction key is illegal. Making such an illegal state unrepresentable is easy with a sum type, but as this article has shown, you can achieve the same goal in C#.

With the API shown here, there's only three possible states (Individual, Child, and Parent). Notice that all three classes hide their data as private class fields, so the only way to extract that data is to call Match. The compiler will make sure that you handle all three cases, because you must supply a function for all three method arguments.

The code shown in this article is available on GitHub.

This article concludes the little series on how to use Church-encoding in C# to create sum types. You may, however, think that it doesn't really feel object-oriented, with its heavy reliance on function arguments (e.g. Func<PaymentService, T>). It turns out, though, that with only a few refactorings, you'll come to the realisation that what you've seen here is isomorphic to a classic design pattern. Read on!

Next: Some design patterns as universal abstractions.


Church-encoded Either

Monday, 11 June 2018 15:43:00 UTC

Programming languages don't have to have a built-in notion of error handling. You can implement sane error handling from first principles. An introduction for object-oriented programmers.

This article is part of a series of articles about Church encoding. In this series, you'll learn how to re-create various programming language features from first principles. In previous articles, you learned how to implement Boolean logic without Boolean primitives, how to model natural numbers, as well as how to implement Maybe (a type-safe alternative to null). Through these examples, you'll learn how to model sum types without explicit language support.

Error handling without exceptions #

In a previous article, I've discussed how a language doesn't need to have built-in exceptions in order to support composable and type-safe error handling. In fact, exceptions are noting but glorified GOTO statements. A better approach is to use the Either abstraction, which enables you to model values that are either one or another thing.

In F#, this type is known as Result<'T, 'TError>, while in Haskell it's called Either. It enables you to model an outcome that is either something (like a success) or something else (such as an error).

Scott Wlaschin has already brilliantly described how this works in F#, but the Either type can be used for error handling in Haskell in exactly the same way. When we use the terminology related to either, we distinguish between left and right. Typically, right is used to indicate success, via the pun that 'right' is 'correct'.

Lambda calculus Either #

Church encoding is based on the lambda calculus, which defines a universal model of computation based entirely on functions (lambda expressions) and recursion. As far as I can tell, you can define Either in lambda calculus as an expression that takes two arguments, and where there's two fundamental 'implementations' of the contract:

 left = λa.λl.λr.l a
right = λb.λl.λr.r b

(I admit that I'm going out on a limb here, since I haven't found any source that puts either in the above form, so I'd appreciate feedback if I did it incorrectly.)

The contract is that, similar to Maybe, the l function argument represents the left case, whereas the r argument represents the right case. Contrary to Maybe, both l and r are used as functions. (Everything in lambda calculus is a function, but we don't always use the arguments as the function that they are.)

The left function is a function that takes three arguments (a, l, and r) and always returns l a. Recall that in lambda calculus, everything is a function, which includes l (and r). In other words, left unconditionally calls l with a, and that's the return value.

The right function works like the left function, with the only difference that it always returns r b.

The idea, as usual, is that you can partially apply left and right, by, for instance calling left three (where three is the lambda calculus representation of the number 3, as described in the article on Church-encoded natural numbers). Such a partially applied function is a function that still takes the two arguments l and r.

The same is true if you partially apply right with a value, like right one.

In both cases, you have a function of the form λl.λr.[...]. If you've been given such a function by an external source, you may not know if it's a left or a right expression, and that's the point. You must supply handlers (l and r) that cover all possible cases.

In the lambda calculus, expressions are always curried, so instead of viewing left and right as functions with three arguments, you can view them as functions that take a single element (a or b) and return functions that takes two arguments. This agrees with Haskell's Left and Right data constructors:

Prelude> :t Left
Left :: a -> Either a b
Prelude> :t Right
Right :: b -> Either a b

Haskell tells us that Left is a function that takes an a value and returns an Either a b value. Similarly, Right is a function that takes a b value as input, and returns an Either a b

Church-encoded Either in C# #

Both lambda calculus and Haskell relies on currying and partial application to make the contract fit. In C#, as you've previously seen, you can instead define an interface and rely on class fields for the 'extra' function arguments. Since Church-encoded Either is represented by a function that takes two arguments, we'll once again define an interface with a single method that takes two arguments:

public interface IEither<LR>
{
    T Match<T>(Func<LT> onLeft, Func<RT> onRight);
}

The Match method takes two functions as arguments, one that handles the left case, and one that handles the right case. They correspond to the l and r variables in the above lambda expressions. The intent, as with other Church-encoded discriminated unions, is that when client code is given an IEither<L, R> object, it can only interact with that object by telling the Match method how to deal with both cases. Only one of the functions will be called, but at compile-time, you don't know which one. Both functions, however, must return a value of the generic type T, and that's how you can translate an IEither<L, R> object to a T value.

Following the normal procedure for Church encoding, you must also supply two implementations of the IEither<L, R> interface: one for each case.

public class Left<LR> : IEither<LR>
{
    private readonly L left;
 
    public Left(L left)
    {
        this.left = left;
    }
 
    public T Match<T>(Func<LT> onLeft, Func<RT> onRight)
    {
        return onLeft(left);
    }
}

The Left<L, R> class is an Adapter of a value of the generic type L , making it appear as an IEither<L, R> object.

It always calls the onLeft method argument with the adapted value left, while it ignores the onRight method argument. Since onLeft returns a T value, you can return the value produced by the function call.

The right case is implemented in a similar fashion:

public class Right<LR> : IEither<LR>
{
    private readonly R right;
 
    public Right(R right)
    {
        this.right = right;
    }
 
    public T Match<T>(Func<LT> onLeft, Func<RT> onRight)
    {
        return onRight(right);
    }
}

The Right<L, R> class is the mirror image of Left<L, R>. Instead of adapting an L value, it adapts an R value. It implements Match by always calling onRight with the right value, which, again, produces a T value that can be immediately returned.

Notice that for both implementations, the adapted values left and right are private class fields not exposed as public members. The only way you, as a caller, can potentially extract these values is by calling Match, and that forces you to explicitly deal with both cases.

Here's an example of using the API:

> IEither<stringint> e = new Right<stringint>(42);
> e.Match(s => s.Length % 2 == 0, i => i % 2 == 0)
true

I've deliberately declared e as a an IEither<string, int> in order to highlight the scenario where, as a client developer, you're often given a value of such a type, and you don't know if it's a left or a right value. Had I, instead, used the var keyword, the compiler would have detected that e is, really, a Right<string, int> variable. You may consider this choice artificial, but the point I'm trying to get across is that, when writing client code, you're often given a polymorphic value, and you don't know the concrete type of the value. According to the Liskov Substitution Principle, your client code must be able to deal with any subtype without changing the correctness of the system. In the case of an Either value, the way you deal with all subtypes is by supplying handlers for both cases to the Match method.

In the above example, the return value is true because 42 is an even number. If, instead, the e object is a left case containing the string "foo", the return value is false because the length of "foo" is 3 - an odd number:

> IEither<stringint> e = new Left<stringint>("foo");
> e.Match(s => s.Length % 2 == 0, i => i % 2 == 0)
false

Notice that the e.Match method call is the same in both examples; the onLeft and onRight functions are the same in both cases. The results differ because the input values represent different cases.

If you've been following the overall series on Church encoding, you may think that it's cheating to use C#'s built-in string and int data types, but nothing prevents us from sticking to the data types we've built from scratch:

> IEither<IChurchBooleanINaturalNumber> e;
> e = new Right<IChurchBooleanINaturalNumber>(NaturalNumber.Seven);
> e.Match(b => new ChurchNot(b), n => n.IsEven())
ChurchFalse { }
> e = new Left<IChurchBooleanINaturalNumber>(new ChurchFalse());
> e.Match(b => new ChurchNot(b), n => n.IsEven())
ChurchNot(ChurchFalse)

For both the left and the right case, the Match inverts the Boolean expression if it's a left case, and evaluates if the number is even if it's a right case. In the first example, the return value is a ChurchFalse object because 7 is odd. In the second example, the return value is a ChurchNot object containing a ChurchFalse object (in other words, true), because the negation of false is true.

Either instead of exceptions #

You can use Either to signal the success or failure of an operation. By convention, the right case is used to signal success, so, by elimination, left means failure. You can signal errors in numerous ways, e.g. by using enum values, but another common strategy is to simply use string values.

Consider the following example. You receive a collection of values, where each element represents a vote for that element. For example, the list Sandra, Zoey, Sandra indicates two votes for Sandra, and one for Zoey. You need to write a method that returns the winner of a vote, but at least two distinct errors are possible: the input collection is empty, or there's a tie.

You can model the error cases with an enum:

public enum VoteError
{
    Empty = 0,
    Tie
}

This enables you to write a method to find the winners, with an explicit Either return type:

public static IEither<VoteErrorT> FindWinner<T>(IReadOnlyCollection<T> votes)
{
    var countedVotes = from v in votes
                       group v by v into g
                       let count = g.Count()
                       orderby count descending
                       select new { Vote = g.Key, Count = count };
    var c = countedVotes.Take(2).Count();
 
    if (c == 0)
        return new Left<VoteErrorT>(VoteError.Empty);
 
    var x0 = countedVotes.ElementAt(0);
    if (c == 1)
        return new Right<VoteErrorT>(x0.Vote);
 
    var x1 = countedVotes.ElementAt(1);
    if (Equals(x0.Count, x1.Count))
        return new Left<VoteErrorT>(VoteError.Tie);
 
    return new Right<VoteErrorT>(x0.Vote);
}

Notice that the return type of the FindWinner method is IEither<VoteError, T>; either you get a VoteError value, or you get a T value, but any client code doesn't know which it'll be, so it must handle both cases.

The method uses a C# query expression to group, count, and order the votes. If there's no elements, the return value is a left value containing VoteError.Empty. If there's only a single vote group (e.g. if the votes where all for Sandra), that value is returned in a right case. Otherwise, if the two highest ranked votes have the same count, a left value is returned containing VoteError.Tie. Finally, in all other cases, the highest voted element is returned in a right case.

Here's some examples in C# Interactive:

> FindWinner<int>()
Left<VoteError, int>(Empty)
> FindWinner(1, 2, 3, 1, 4, 2)
Left<VoteError, int>(Tie)
> FindWinner("Sandra""Zoey""Sandra")
Right<VoteError, string>("Sandra")

Instead of throwing two different types of exceptions on invalid input, the FindWinner method handles invalid input as left cases, and valid input as the right case. You can do that consistently, and thereby eliminate the need for exceptions. Errors are, instead, reported as left values.

Summary #

In this article, you saw how it's possible to define the Either container from first principles, using nothing but functions (and, for the C# examples, interfaces and classes in order to make the code easier to understand for object-oriented developers).

The code shown in this article is available on GitHub.

Like Maybe, you can also make Either a functor. This'll enable you to compose various error-producing functions in a sane manner.

Church-encoding enables you to model sum types as functions. So far in this article series, you've seen how to model Boolean values, natural numbers, Maybe, and Either. Common to all four examples is that the data type in question consists of two mutually exclusive cases. This is the reason they're all modelled as methods that take two arguments. What happens if, instead of two, you have three mutually exclusive cases? Read on.

Next: Church-encoded payment types.


Church-encoded Maybe

Monday, 04 June 2018 10:08:00 UTC

Programming languages don't have to have a built-in notion of null values. Missing or optional values can be created from first principles. An introduction for object-oriented programmers.

This article is part of a series of articles about Church encoding. In this series, you'll learn how to re-create various programming language features from first principles. In previous articles, you learned how to implement Boolean logic without Boolean primitives, as well as how to model natural numbers. Through these examples, you'll learn how to model sum types without explicit language support.

The billion-dollar mistake #

All mainstream programming languages have a built-in notion of null: a value that isn't there. There's nothing wrong with the concept; you often run into situations where you need to return a value, but in certain cases, you'll have nothing to return. Division by zero would be one example. Attempting to retrieve the first element from an empty collection would be another.

Unfortunately, for fifty years, we've been immersed in environments where null references have been the dominant way to model the absence of data. This, despite the fact that even Sir Antony Hoare, the inventor of null references, has publicly called it his billion-dollar mistake.

You can, however, model the potential absence of data in saner ways. Haskell, for example, has no built-in null support, but it does include a built-in Maybe type. In Haskell (as well as in F#, where it's called option), Maybe is defined as a sum type:

data Maybe a = Nothing | Just a deriving (EqOrd)

If you're not familiar with Haskell syntax, this is a type declaration that states that the parametrically polymorphic (AKA generic) data type Maybe is inhabited by Just values that contain other values, plus the constant Nothing.

This article series, however, examines how to implement sum types with Church encoding.

Lambda calculus maybe #

Church encoding is based on the lambda calculus, which defines a universal model of computation based entirely on functions (lambda expressions) and recursion. In lambda calculus, the contract of Maybe is defined as an expression that takes two arguments. There's two fundamental 'implementations' of the contract:

nothing =    λn.λj.n
   just = λx.λn.λj.j x

The contract is that the first function argument (n) represents the nothing case, whereas the second argument (j) represents the just case.

The nothing function is a lambda expression that takes two arguments (n and j), and always returns the first, left-most argument (n).

The just function is a lambda expression that takes three arguments (x, n, and j), and always returns j x. Recall that in the lambda calculus, everything is a function, including j, so j x means that the function j is called with the argument x.

A few paragraphs above, I wrote that the contract of maybe is modelled as an expression that takes two arguments, yet just takes three arguments. How does that fit?

In the lambda calculus, expressions are always curried, so instead of viewing just as a function with three arguments, you can view it as a function that takes a single element (x) and returns a function that takes two arguments. This agrees with Haskell's Just data constructor:

Prelude> :t Just
Just :: a -> Maybe a

Haskell tells us that Just is a function that takes an a value (corresponding to x in the above just lambda expression) and returns a Maybe a value.

Church-encoded Maybe in C# #

Both lambda calculus and Haskell rely on currying and partial application to make the contract fit. In C#, as you've previously seen, you can instead define an interface and rely on class fields for the 'extra' function arguments. Since Church-encoded Maybe is represented by a function that takes two arguments, we'll once again define an interface with a single method that takes two arguments:

public interface IMaybe<T>
{
    TResult Match<TResult>(TResult nothing, Func<TTResult> just);
}

In the first article, about Church-encoded Boolean values, you saw how two mutually exclusive values could be modelled as a method that takes two arguments. Boolean values are simply constants (true and false), where the next example (natural numbers) included a case where one case (successor) contained data. In that example, however, the data was statically typed as another INaturalNumber value. In the current IMaybe<T> example, the data contained in the just case is generic (it's of the type T).

Notice that there's two levels of generics in play. IMaybe<T> itself is a container of the generic type T, whereas Match enables you to convert the container into the rank-2 polymorphic type TResult.

Once more, the contract of IMaybe<T> is that the first, left-hand argument represents the nothing case, whereas the second, right-hand argument represents the just case. The nothing implementation, then, is similar to the previous ChurchTrue and Zero classes:

public class Nothing<T> : IMaybe<T>
{
    public TResult Match<TResult>(TResult nothing, Func<TTResult> just)
    {
        return nothing;
    }
}

Again, the implementation unconditionally returns nothing while ignoring just. You may, though, have noticed that, as is appropriate for Maybe, Nothing<T> has a distinct type. In other words, Nothing<string> doesn't have the same type as Nothing<int>. This is not only 'by design', but is a fundamental result of how we define Maybe. The code simply wouldn't compile if you tried to remove the type argument from the class. This is in contrast to C# null, which has no type.

You implement the just case like this:

public class Just<T> : IMaybe<T>
{
    private readonly T value;
 
    public Just(T value)
    {
        this.value = value;
    }
 
    public TResult Match<TResult>(TResult nothing, Func<TTResult> just)
    {
        return just(value);
    }
}

According to the contract, Just<T> ignores nothing and works exclusively with the just function argument. Notice that the value class field is private and not exposed as a public member. The only way you, as a caller, can potentially extract the value is by calling Match.

Here are some examples of using the API:

> new Nothing<Guid>().Match(nothing: "empty", just: g => g.ToString())
"empty"
> new Just<int>(42).Match(nothing: "empty", just: i => i.ToString())
"42"
> new Just<int>(1337).Match(nothing: 0, just: i => i)
1337

Notice that the third example shows how to extract the value contained in a Nothing<int> object without changing the output type. All you have to do is to supply a 'fall-back' value that can be used in case the value is nothing.

Maybe predicates #

You can easily implement the standard Maybe predicates IsNothing and IsJust:

public static IChurchBoolean IsNothing<T>(this IMaybe<T> m)
{
    return m.Match<IChurchBoolean>(
        nothing :   new ChurchTrue(), 
        just : _ => new ChurchFalse());
}
 
public static IChurchBoolean IsJust<T>(this IMaybe<T> m)
{
    return m.Match<IChurchBoolean>(
        nothing :   new ChurchFalse(),
        just : _ => new ChurchTrue());
}

Here, I arbitrarily chose to implement IsJust 'from scratch', but I could also have implemented it by negating the result of calling IsNothing. Once again, notice that the predicates are expressed in terms of Church-encoded Boolean values, instead of the built-in bool primitives.

Functor #

From Haskell (and F#) we know that Maybe is a functor. In C#, you turn a container into a functor by implementing an appropriate Select method. You can do this with IMaybe<T> as well:

public static IMaybe<TResult> Select<TTResult>(
    this IMaybe<T> source,
    Func<TTResult> selector)
{
    return source.Match<IMaybe<TResult>>(
        nothing:   new Nothing<TResult>(),
        just: x => new Just<TResult>(selector(x)));
}

Notice that this method turns an IMaybe<T> object into an IMaybe<TResult> object, using nothing but the Match method. This is possible because Match has a generic return type; thus, among other types of values, you can make it return IMaybe<TResult>.

When source is a Nothing<T> object, Match returns the object in the nothing case, which here becomes a new Nothing<TResult> object.

When source is a Just<T> object, Match invokes selector with the value contained in the just object, packages the result in a new Just<TResult> object, and returns it.

Because the Select method has the correct signature, you can use it with query syntax, as well as with normal method call syntax:

IMaybe<int> m = new Just<int>(42);
IMaybe<string> actual = from i in m
                        select i.ToString();

This example simply creates a just value containing the number 42, and then maps it to a string. Another way to write the same expression would be with method call syntax:

IMaybe<int> m = new Just<int>(42);
IMaybe<string> actual = m.Select(i => i.ToString());

In both cases, the result is a just case containing the string "42".

Summary #

In this article, you saw how it's possible to define the Maybe container from first principles, using nothing but functions (and, for the C# examples, interfaces and classes in order to make the code easier to understand for object-oriented developers).

The code shown in this article is available on GitHub.

Church-encoding enables you to model sum types as functions. So far in this article series, you've seen how to model Boolean values, natural numbers, and Maybe. Common to all three examples is that the data type in question consists of two mutually exclusive cases. There's at least one more interesting variation on that pattern.

Next: Church-encoded Either.


Comments

It's probably not your favorite thing to do anymore, but I thank you so much for continuing to provide C# examples for these concepts. It's invaluable for programmers wishing to adopt these concepts into the OOP languages they work with for a living. It's also a tremendous aid in briding the gap of understanding between OOP and FP.
2018-06-04 17:57 UTC

Church-encoded natural numbers

Monday, 28 May 2018 08:24:00 UTC

Natural numbers don't have to be built into programming languages. An introduction for object-oriented programmers.

This article is part of a series of articles about Church encoding. The previous article, about Church-encoding of Boolean values, concluded with the question: how do you determine whether an integer is even or odd?

That sounds easy, but turns out to be more complicated that you might think at first glance.

Built-in options #

How would you normally check whether a number is even? In some languages, like Haskell, it's built into the base library:

Prelude> even 1337
False
Prelude> even 42
True

In C#, surprisingly, I don't think it's built-in, but it's easy to implement a method to answer the question:

public static bool IsEven(this int i)
{
    return i % 2 == 0;
}

You could implement an IsOdd method either by using the != operator instead of ==, but otherwise copy the implementation of IsEven; or, alternatively, call IsEven and negate the result.

This works fine in normal C# code, but in this article, the agenda is different. We're investigating how programming with the previous article's IChurchBoolean API would look. The above built-in options use Boolean language primitives, so that's not really instructive.

Boolean conversions #

It's easy to convert between Church-encoded Boolean values and built-in Boolean values. For reasons I'll explain shortly, I still don't think that's instructive in this particular context, but for good measure I'll cover how to do it.

A method like the above IsEven returns bool. If you, instead, want an IChurchBoolean, you can use this simple conversion method:

public static IChurchBoolean ToChurchBoolean(this bool b)
{
    if (b)
        return new ChurchTrue();
    else
        return new ChurchFalse();
}

Alternatively, you can also use the ternary operator, but an ugly cast is necessary to make the C# compiler happy:

public static IChurchBoolean ToChurchBoolean(this bool b)
{
    return b ? (IChurchBoolean)new ChurchTrue() : new ChurchFalse();
}

Regardless of which implementation you choose, you'd be able to interact with the result as an IChurchBoolean values, as this small interactive session demonstrates:

> 42.IsEven().ToChurchBoolean().Match("Even""Odd")
"Even"
> 1337.IsEven().ToChurchBoolean().Match("Even""Odd")
"Odd"

Still, converting from bool to IChurchBoolean doesn't address the underlying question: is it possible to write programs without built-in Boolean primitives?

The conversion function ToChurchBoolean uses built-in Boolean values and functions, so it doesn't show whether or not it would be possible to make do without those.

Before we abandon that line of inquiry, however, I think it's only fair to share a conversion method that goes the other way:

public static bool ToBool(this IChurchBoolean b)
{
    return b.Match(truefalse);
}

This function enables you to convert an IChurchBoolean value into a primitive C# bool, because when b represents true, the first argument (i.e. true) is returned, and when b represents false, the second argument (i.e. false) is returned.

Peano numbers #

If we can't use built-in primitives or operators that return them (e.g. ==), we may not be able to move forward with built-in numbers, either. What we can do, however, is to follow the lambda calculus to implement natural numbers using Church encoding. This will enable us to determine if a natural number is even or odd.

Lambda calculus models natural numbers according to Peano's model. In short, a natural number is either zero (or one, depending on the specific interpretation), or a successor to another natural number. As an example, using the Successor class that I'll develop later in this article, the number three can be represented as new Successor(new Successor(new Successor(new Zero()))) - it's the number after the number after the number after zero.

Like Church-encoded Boolean values, a Church-encoded natural number is a function that takes two arguments, corresponding to zero, and a successor function:

zero = λf.λx.x
one = λf.λx.f x
two = λf.λx.f (f x)
three = λf.λx.f (f (f x))
...

Each of these functions takes an initial value x, as well as a function f. In the lambda calculus, neither x nor f have any implied interpretation; it's the number of applications of f that defines the number.

In most translations into programming languages that I've encountered, however, x is usually interpreted as zero, and f as the successor function. In Haskell, for example, a common way to model Peano numbers is to use a sum type:

data Peano = Zero | Succ Peano deriving (EqShow)

Basically, this means that a value of the Peano type can either be the atom Zero, or a Succ value. Notice that Succ contains another Peano value; the data type is recursive.

You can write Haskell values like these:

*Peano> zero = Zero
*Peano> one = Succ Zero
*Peano> two = Succ (Succ Zero)
*Peano> three = Succ (Succ (Succ Zero))

Alternatively, you can also define the numbers based on previous definitions:

*Peano> zero = Zero
*Peano> one = Succ zero
*Peano> two = Succ one
*Peano> three = Succ two

This variation of Peano numbers uses an explicit sum type, but as the lambda calculus representation suggests, you can also use Church encoding to represent the two cases.

Church-encoded natural numbers #

If you recall Church-encoded Boolean values, you may remember that they are functions that take two values: a value to be used in case of true, and a value to be used in the case of false. You can do something similar with natural numbers. Zero is like true and false, in the sense that it's nothing but a label without any associated data. Succ, on the other hand, contains another Peano value. The way to do that is to turn the successor case into a function. Doing that, you'll arrive at an interface like this:

public interface INaturalNumber
{
    T Match<T>(T zero, Func<INaturalNumberT> succ);
}

The first argument, on the left-hand side, is the case to use when an object represents zero. The second argument, on the right-hand side, is a function that will ultimately produce the value associated with a successor. The implied contract here is that the INaturalNumber passed as input to succ is the predecessor to 'the current value'. This may seem counter-intuitive, but hopefully becomes clearer when you see the Successor class below. The crucial insight is that a successor value has no intrinsic value; it's entirely defined by how many predecessors it has.

The zero implementation is similar to how Church-encoding implements true:

public class Zero : INaturalNumber
{
    public T Match<T>(T zero, Func<INaturalNumberT> succ)
    {
        return zero;
    }
}

Notice that the Zero class implements INaturalNumber by always returning zero, and consequently always ignoring succ.

Another class, Successor, handles the right-hand side of the Match method:

public class Successor : INaturalNumber
{
    private readonly INaturalNumber predecessor;
 
    public Successor(INaturalNumber n)
    {
        this.predecessor = n;
    }
 
    public T Match<T>(T zero, Func<INaturalNumberT> succ)
    {
        return succ(predecessor);
    }
}

Notice that Successor composes its predecessor via Constructor Injection, and unconditionally calls succ with its predecessor when Match is invoked.

Working with natural numbers #

What can you do with this INaturalNumber API, then?

Initially, you can define some numbers, like the above Haskell examples:

public static class NaturalNumber
{
    public static INaturalNumber  Zero = new Zero();
    public static INaturalNumber   One = new Successor(Zero);
    public static INaturalNumber   Two = new Successor(One);
    public static INaturalNumber Three = new Successor(Two);
    public static INaturalNumber  Four = new Successor(Three);
    public static INaturalNumber  Five = new Successor(Four);
    public static INaturalNumber   Six = new Successor(Five);
    public static INaturalNumber Seven = new Successor(Six);
    public static INaturalNumber Eight = new Successor(Seven);
    public static INaturalNumber  Nine = new Successor(Eight);
 
    // More memmbers go here...
}

Here, I arbitrarily chose to define the numbers from zero to nine, but you could go on for as long as you care.

You can also convert these Church-encoded numbers to primitive int values, like this:

public static int Count(this INaturalNumber n)
{
    return n.Match(
        0,
        p => 1 + p.Count());
}

Here are some examples from a C# Interactive session:

> NaturalNumber.Zero.Count()
0
> NaturalNumber.One.Count()
1
> NaturalNumber.Seven.Count()
7

The implementation of Count is recursive. When n is a Zero instance, it'll return the first argument (0), but when it's a Successor, it'll invoke the lambda expression p => 1 + p.Count(). Notice that this lambda expression recursively calls Count on p, which is the Successor's predecessor. It'll keep doing that until it reaches a Zero instance.

Recursion is a central part of the lambda calculus; you can't do anything useful without it. If you're a C# or Java programmer, you may be concerned, because recursion tends to be problematic in such languages. Deeply recursive functions will sooner or later crash because of a stack overflow.

You shouldn't, however, be concerned. First, I'm not trying to convince you to write all your future C# or Java code using Church-encoded numbers and Boolean values. The point of this article series is to investigate the fundamentals of computations, and to gain a better understanding of sum types. As such, the code examples presented here are only demonstrations of the underlying principles. Lambda calculus itself serves the same purpose: it's a universal model of computation; it wasn't intended to be a practical programming language - in fact, there were no programmable computers in 1936.

Furthermore, the problem with recursion causing stack overflow isn't universal. Languages like F# and Haskell support tail recursion, thereby enabling recursive functions to run to arbitrary depths.

Pattern matching #

In the previous article, I hinted that there's a reason I decided to name the interface method Match. This is because it looks a lot like pattern matching. In F#, you could write count like this:

type Peano = Zero | Succ of Peano
 
// Peano -> int
let rec count n =
    match n with
    | Zero -> 0
    | Succ p -> 1 + count p

This implementation, by the way, isn't tail-recursive, but you can easily refactor to a tail-recursive implementation like this:

// Peano -> int
let count n =
    let rec countImp acc n =
        match n with
        | Zero -> acc
        | Succ p -> countImp (1 + acc) p
    countImp 0 n

Both variations use the match keyword to handle both the Zero and the Succ case for any Peano value n. That's already close to the above C# code, but using the optional C# language feature of named arguments, you can rewrite the implementation of Count to this:

public static int Count(this INaturalNumber n)
{
    return n.Match(
        zero: 0,
        succ: p => 1 + p.Count());
}

This starts to look like pattern matching of sum types in F#. The argument names aren't required, but using them makes it clearer which cases the Match method handles.

Addition #

You can now start to add features and capabilities to the natural numbers API. An obvious next step is to implement addition:

public static INaturalNumber Add(this INaturalNumber x, INaturalNumber y)
{
    return x.Match(
        zero: y,
        succ: p => new Successor(p.Add(y)));
}

Again, the implementation is recursive. When x is zero, you simply return y, because zero + y is y. When x is a Successor, you recursively add y to its predecessor, and put the result in a new Successor. You can think of the predecessor p as one less than the successor. By recursively subtracting one from any Successor object, you'll eventually match the zero case, which will then return y. When the stack unrolls, each stack puts the previous result into a new Successor. This happens exactly the correct number of times corresponding to the value of x, because that's the size of the stack when Add hits zero.

Here are some examples:

> NaturalNumber.One.Add(NaturalNumber.Two).Count()
3
> NaturalNumber.Four.Add(NaturalNumber.Three).Count()
7
> NaturalNumber.Seven.Add(NaturalNumber.Six).Count()
13

You can also implement multiplication, but that's a bit more complicated, and not relevant to the topic of this article (which is how to determine if a number is even or odd).

Testing for zero #

In addition to basic arithmetic, you can also define functions that tell you something about a natural number. We'll start gently with a function that tells us whether or not a number is zero:

public static IChurchBoolean IsZero(this INaturalNumber n)
{
    return n.Match<IChurchBoolean>(
        zero: new ChurchTrue(),
        succ: _ => new ChurchFalse());
}

The IsZero method simply returns a ChurchTrue object when n is a Zero instance, and a ChurchFalse object for all other numbers.

You can see that this works in this C# Interactive session:

> NaturalNumber.Two.IsZero()
ChurchFalse { }
> NaturalNumber.Zero.IsZero()
ChurchTrue { }
> NaturalNumber.Three.IsZero()
ChurchFalse { }

You can also Match on the returned Boolean value to return e.g. a string:

> NaturalNumber.Nine.IsZero().Match(trueCase: "Zero", falseCase: "Not zero")
"Not zero"
> NaturalNumber.Zero.IsZero().Match(trueCase: "Zero", falseCase: "Not zero")
"Zero"

This already demonstrates that you can implement predicates and branching logic from first principles, without resorting to built-in Boolean primitives or operators.

Detecting even numbers #

Testing whether a natural number is even or uneven requires a bit more work. It's probably easiest to understand if we first consider an F# implementation:

// Peano -> ChurchBoolean
let rec isEven n =
    match n with
    | Zero -> ChurchTrue
    | Succ Zero -> ChurchFalse
    | Succ (Succ p) -> isEven p

Zero is even, so when n matches Zero, isEven returns ChurchTrue. Conversely, when the input is Succ Zero (i.e. one), the return value is ChurchFalse because one is odd.

The zero and one cases serve as exit cases for the recursive algorithm. Since we've handled Zero and Succ Zero (that is, zero and one), we know that any other case must be at least twice nested. This means that the Succ (Succ p) pattern matches all other cases. You can think of p as n - 2.

The algorithm proceeds to recursively call isEven with p (i.e. n - 2). Sooner or later, these recursive function calls will match either the Zero or the Succ Zero case, and exit with the appropriate return value.

C# doesn't have as sophisticated pattern matching features as F#, so we're going to have to figure out how implement this algorithm without relying on a nested pattern like Succ (Succ p). As an initial step, we can rewrite the function in F#, using two matches instead of one:

// Peano -> ChurchBoolean
let rec isEven n =
    match n with
    | Zero -> ChurchTrue
    | Succ p1 ->
        match p1 with
        | Zero -> ChurchFalse
        | Succ p2 -> isEven p2

This isn't as elegant as the previous implementation, but on the other hand, it's straightforward to translate to C#:

public static IChurchBoolean IsEven(this INaturalNumber n)
{
    return n.Match(
        zero: new ChurchTrue(),        // 0 is even, so true
        succ: p1 => p1.Match(          // Match previous
            zero: new ChurchFalse(),   // If 0 then successor was 1
            succ: p2 => p2.IsEven())); // Eval previous' previous
}

Like in the F# example, when n is a Zero object, it'll return the value associated with the zero case. Since zero is even, it returns a ChurchTrue object.

In all other cases, a Match on the predecessor p1 is required. If that nested match is zero, then we know that n must have been one, since the the predecessor turned out to be zero. In that case, then, return a ChurchFalse object, because one isn't even.

The nested Match considers the predecessor p1. In the succ case of the nested Match, then, we can consider p2; that is, the predecessor to the predecessor to n - in other words: n - 2. The function recursively calls itself with n - 2, and it'll keep doing so until it matches either the zero or the one case.

The implementation works:

> NaturalNumber.Two.IsEven()
ChurchTrue { }
> NaturalNumber.Three.IsEven()
ChurchFalse { }

IsEven is implemented from first principles. The only language features we need are lambda expressions and recursion, although in order to make these examples slightly more idiomatic, I've also used interfaces and classes.

Detecting odd numbers #

You could implement a corresponding IsOdd method similarly to IsEven, but it's easier to use the Boolean operators already in place from the previous article:

public static IChurchBoolean IsOdd(this INaturalNumber n)
{
    return new ChurchNot(n.IsEven());
}

IsOdd is simply the Boolean negation of IsEven. Like IsEven it also works correctly:

> NaturalNumber.Six.IsOdd().Match(trueCase: "Odd", falseCase: "Even")
"Even"
> NaturalNumber.Seven.IsOdd().Match(trueCase: "Odd", falseCase: "Even")
"Odd"

You can implement other operators (like multiplication) and predicates from the building blocks shown here, but I'm not going to cover that here (see the accompanying GitHub repository for more code). I hope that this article gave you a sense of how a programming language can be designed from the low-level building blocks defined by the lambda calculus.

Summary #

Giuseppe Peano described natural numbers as an initial number (zero) and successors to that number. Church formulated Peano numbers in the lambda calculus. Using Church encoding, you can translate this representation to various programming languages, including, as you've seen in this article, C#.

In the previous article, you saw how to model Boolean values as a set of functions with two arguments. In this article, you saw how to model natural numbers with another set of functions that take two arguments. In the next article, you'll see another data type modelled as a set of functions with two arguments. It looks like a patterns is starting to appear.

Next: Church-encoded Maybe.


Church-encoded Boolean values

Thursday, 24 May 2018 04:49:00 UTC

Boolean values, and logical branching, don't have to be built into programming languages. An introduction for object-oriented programmers.

This article is part of a series of articles about Church encoding.

Years ago, the so-called Anti-IF Campaign made the rounds on various social media (back then, IIRC, mostly known as 'the blogosphere'). The purpose of the campaign was never to eradicate every single use of if statements or expressions in source code, but rather to educate people about alternatives to the Arrow anti-pattern.

One easy way to deal with arrow code is to Replace Nested Conditionals with Guard Clauses, but that's not always possible. Another way is to encapsulate some if blocks in helper methods. Yet another way would be to use polymorphic dispatch, but how does that even work? Don't you, deep down, need at least a few if keywords here and there?

It turns out that the answer, surprisingly, is no.

Untyped Boolean functions #

if/then/else expressions are based on Boolean values (true and false): if some Boolean value is true, then something happens; otherwise, something else happens. Most programming languages, including C, C++, Java, C#, and JavaScript, have a ternary operator, which in C# looks like this:

isEven ? "Probably not a prime." : "Could be a prime.";

You can think of an expression like that as a function that takes a Boolean value and two potential return values: one for the true case, and one for the false case.

In lambda calculus, the only primitive building blocks are functions. There's no built-in Boolean values, but you can define them with functions. Boolean values are functions that take two arguments. By conventions, the first argument (the one to the left) represents the true case, whereas the second argument (to the right) signifies the false case - just like the ternary operator. In the lambda calculus, functions are curried, but we know from uncurry isomorphisms that we can also represent a two-argument function as a function that takes a two-tuple (a pair) as a single argument. Furthermore, we know from function isomorphisms that we can represent a function as an instance method. Therefore, we can declare a Boolean value in C# to be an object that implements this interface:

public interface IChurchBoolean
{
    object Match(object trueCase, object falseCase);
}

You'll notice that I've chosen to call the method Match, for reasons that should hopefully become clear as we go along.

The intent with such a Church-encoded Boolean is that any object that represents true should return the left argument (trueCase), whereas an object that represents false should return the right argument (falseCase).

In other words, true is an interface implementation:

public class ChurchTrue : IChurchBoolean
{
    public object Match(object trueCase, object falseCase)
    {
        return trueCase;
    }
}

Notice that this implementation always returns trueCase while ignoring falseCase. No explicit if statement is required.

Likewise, false is implemented the same way:

public class ChurchFalse : IChurchBoolean
{
    public object Match(object trueCase, object falseCase)
    {
        return falseCase;
    }
}

So far, this doesn't offer much capability, but it does already give you the ability to choose between two values, as this little C# Interactive session demonstrates:

> var b = new ChurchTrue();
> b.Match("foo", "bar")
"foo"
> var b = new ChurchFalse();
> b.Match("foo", "bar")
"bar"

When 'the Boolean value' is a ChurchTrue instance, then the left argument is returned; otherwise, when b is a ChurchFalse object, the return value is the right-hand value - just like the ternary operator.

Boolean And #

You can now define the standard Boolean operators and, or, and not. Starting with and:

public class ChurchAnd : IChurchBoolean
{
    private readonly IChurchBoolean x;
    private readonly IChurchBoolean y;
 
    public ChurchAnd(IChurchBoolean x, IChurchBoolean y)
    {
        this.x = x;
        this.y = y;
    }
 
    public object Match(object trueCase, object falseCase)
    {
        return x.Match(y.Match(trueCase, falseCase), falseCase);
    }
}

The ChurchAnd class is an implementation of IChurchBoolean that composes two other IChurchBoolean values, x and y. You can use it like this:

var b = new ChurchAnd(new ChurchTrue(), new ChurchFalse());

In this case, b represents false, because it'll always return the right-hand argument when Match is invoked.

Notice that the implementation of ChurchAnd.Match first matches on x. Only if x itself is true can the expression passed as the first argument be returned; otherwise, falseCase will be returned. Thus, if x is true, the expression y.Match(trueCase, falseCase) will be returned, and only if that as well evaluates to true is the final result true. The trueCase value is only returned if y represents true, as well as x.

In the lambda calculus, Boolean and is defined like this:

and = λx.λy.λt.λf.x (y t f) f

The way to read this is that Boolean and is a function that takes four arguments:

  • x, a Boolean value
  • y, another Boolean value
  • t, the value to return if the expression is true; the trueCase argument in the above C# implementation.
  • f, the value to return if the expression is false; the falseCase argument in the above C# implementation.
Recall that in the lambda calculus, Boolean values are functions that take two arguments, so x and y are functions. and calls x with two arguments. Since Boolean and requires both x and y to be true, it passes f as the second argument to x, because if x represents false, it'll return its right-hand argument. Only if x represents true does it make sense to investigate the Boolean value of y, which is also a function that takes two arguments. Only if y also represents true will t be returned.

This is exactly the same implementation as the above C# code.

Wait a minute, though, didn't I write that Boolean values are functions that take two arguments? And isn't and a function that takes four arguments?

Yes, indeed. That's how currying works. You can view and as a function that takes four arguments, but you can also view it as a function that takes two arguments (x and y) and returns another function that takes two arguments. This becomes clearer with partial application. When translating to C#, the 'contract' (that a Boolean value is a function that takes two arguments) is modelled as the interface IChurchBoolean, while the 'extra arguments' x and y become class fields, injected via the class' constructor.

Boolean Or #

In the lambda calculus, Boolean or is defined like this:

or = λx.λy.λt.λf.x t (y t f)

Translated to C#, this becomes:

public class ChurchOr : IChurchBoolean
{
    private readonly IChurchBoolean x;
    private readonly IChurchBoolean y;
 
    public ChurchOr(IChurchBoolean x, IChurchBoolean y)
    {
        this.x = x;
        this.y = y;
    }
 
    public object Match(object trueCase, object falseCase)
    {
        return x.Match(trueCase, y.Match(trueCase, falseCase));
    }
}

You can see that this is another direct translation. Boolean or only requires (at least) one of the Boolean values to be true, so if x is true, you can immediately return trueCase. Otherwise, in the case where x is false, there's still a chance that the entire expression could be true, so you'll have to evaluate y as well. When y represents true, you can still return trueCase. Only when y is also false should you return falseCase.

You can use ChurchOr like this:

var b = new ChurchOr(new ChurchTrue(), new ChurchFalse());

Here, b is true because true or false is true.

Boolean Not #

Finally, you can also define Boolean negation. In lambda calculus it's:

not = λx.λt.λf.x f t

Notice how this simply swaps the arguments passed to x. In C#, this translates to:

public class ChurchNot : IChurchBoolean
{
    private readonly IChurchBoolean b;
 
    public ChurchNot(IChurchBoolean b)
    {
        this.b = b;
    }
 
    public object Match(object trueCase, object falseCase)
    {
        return b.Match(falseCase, trueCase);
    }
}

You can combine all the Boolean operators like this:

var b = new ChurchOr(new ChurchFalse(), new ChurchNot(new ChurchTrue()));

Here, b is false because false or (not true) is false.

Typed Boolean functions #

So far, the IChurchBoolean interface has been untyped, in the sense that it took object arguments and had an object return type. You can, however, easily make the interface strongly typed, using generics:

public interface IChurchBoolean
{
    T Match<T>(T trueCase, T falseCase);
}

This doesn't really change the rest of the code you've seen in this article. The method signatures chance, but the implementations remain as shown. You can see the change in this commit.

Semigroups and monoids #

The strongly typed signature accentuates that the Match method is a binary operation; it takes two values of the type T and returns a single T value. Is it a monoid, then?

It's not a single monoid, but rather a collection of semigroups, some of which are monoids as well. The implementation of ChurchTrue corresponds to the first semigroup, and ChurchFalse to the last semigroup. You can make this explict in Haskell:

import Data.Semigroup
 
churchTrue :: a -> a -> a
churchTrue t f = getFirst (First t <> First f)

If you compare this implementation of churchTrue to the Travis Whitaker's true function, his is much simpler. I'm not suggesting that using First is better; I'm only trying to illustrate the connection.

If you aren't familiar with how things are done in Haskell, <> is the 'generic semigroup binary operator'. What it does depends on the type of expressions surrounding it. By wrapping both t and f in First containers, the <> operator becomes the operator that always returns the first argument (i.e. First t). Since the result is a First value, you have to unwrap it again by applying getFirst.

Likewise, you can define false:

churchFalse :: a -> a -> a
churchFalse t f = getLast (Last t <> Last f)

This still uses the <> operator, but now with the Last container, which gives it all the behaviour of the last semigroup.

The any and all monoids are implemented as compositions of these two fundamental semigroups. In the C# code in this article, they're implemented by ChurchAnd and ChurchOr, although in neither case have I defined an explicit identity value. This is, however, possible, so let's continue with the Haskell code to see what that would look like. First, you can define the 'naked' operations:

churchAnd x y t f = x (y t f) f
 
churchOr x y t f = x t (y t f)

I have here omitted the type signatures on purpose, as I believe they might confuse rather than help. In both cases, the logic is the same as in the above ChurchAnd and ChurchOr classes, although, as you can see, Haskell code is much terser.

These two functions already work as desired, but we can easily turn both into their respective monoids. First, the all monoid:

newtype ChurchAll = ChurchAll { runAll :: forall a. a -> a -> a }
 
instance Semigroup ChurchAll where
    ChurchAll x <> ChurchAll y = ChurchAll (churchAnd x y)
 
instance Monoid ChurchAll where
    mempty = ChurchAll churchTrue
    mappend = (<>)

In order for this code to compile, you must enable the RankNTypes language extension, which I did by adding the {-# LANGUAGE RankNTypes #-} pragma to the top of my code file. The forall a declaration corresponds to the <T> type annotation on the C# Match method. You can think of this as that the type argument is scoped to the function instead of the type.

The Semigroup instance simply delegates its behaviour to churchAnd, and the Monoid instance returns churchTrue as the identity (mempty).

Similarly, you can implement the any monoid:

newtype ChurchAny = ChurchAny { runAny :: forall a. a -> a -> a }
 
instance Semigroup ChurchAny where
    ChurchAny x <> ChurchAny y = ChurchAny (churchOr x y)
 
instance Monoid ChurchAny where
    mempty = ChurchAny churchFalse
    mappend = (<>)

As is also the case with ChurchAll, the ChurchAny instance of Semigroup simply delegates to a 'naked' function (in this case churchOr), and the Monoid instance again delegates mappend to <> and returns churchFalse as the identity.

The following brief GHCi session demonstrates that it all works as intended:

λ> runAny (ChurchAny churchTrue <> ChurchAny churchFalse) "foo" "bar"
"foo"
λ> runAny (ChurchAny churchFalse <> ChurchAny churchFalse) "foo" "bar"
"bar"
λ> runAll (ChurchAll churchFalse <> ChurchAll churchTrue) "foo" "bar"
"bar"
λ> runAll (ChurchAll churchTrue <> ChurchAll churchTrue) "foo" "bar"
"foo"

Recall that a Church-encoded Boolean is a function that takes two values - in all the four above examples "foo" and "bar". When the expression represents true it returns the left-hand value ("foo"); otherwise, it returns the right-hand value ("bar").

In summary, the Church-encoded Boolean values true and false correspond to the first and last semigroups. You can compose the well-known monoids over Boolean values using these two basic building blocks.

Summary #

You'd normally think of Boolean values as language primitives. True and false are built into most languages, as well as common operators like and, or, and not. While this is convenient, it doesn't have to be like this. Even in languages that already have built-in support for Boolean values, like Haskell or C#, you can define Church-encoded Boolean values from first principles.

In the lambda calculus, a Boolean value is function that takes two arguments and returns the left-hand argument when true, and the right-hand argument when false.

At this point, it may seem like you can't do much with the IChurchBoolean API. How could you, for instance, determine whether an integer is even or odd?

This innocuous-looking question is harder to answer than you may think, so that's worthy of its own article.

Next: Church-encoded natural numbers.


Church encoding

Tuesday, 22 May 2018 06:28:00 UTC

Church encoding is a unified way to model data and functions. An introduction for object-oriented developers.

This article series is part of an even larger series of articles about the relationship between design patterns and category theory.

When asked why I like functional programming so much, I often emphasise the superior modelling ability that I get from algebraic data types. Particularly, languages like F# and Haskell have sum types in addition to the product types that most statically typed languages seem to have.

In short, a sum type gives you the ability to declare, as part of the type system, that a particular data type must be exactly one of a finite list of mutually exclusive options. This differs from common object-oriented sub-typing because class inheritance or interface implementation offers conceptually infinite extensibility. Sometimes, unconstrained extensibility is exactly what you need, but in other cases, the ability to define a closed set of cases can be an effective modelling tool. If you need an easy-to-read introduction to algebraic data types, I recommend Tomas Petricek's fine article Power of mathematics: Reasoning about functional types.

Interestingly, TypeScript has sum types, so they don't have to belong exclusively in the realm of functional programming. In this article series, you'll see an alternative way to represent sum types in C# using Church encoding.

Lambda calculus #

In the 1930s, several mathematicians were investigating the foundations of mathematics. One of them, Alonzo Church, developed lambda calculus as a universal model of computation. In a sense, you can think of lambda calculus as a sort of hypothetical programming language, although it was never designed to be a practical programming language. Even so, you can learn a lot from it.

In the untyped lambda calculus, the only primitive data type is a function. There are no primitive numbers, Boolean values, branching instructions, loops, or anything else you'd normally consider as parts of a programming language. Instead, there's only functions, written as lambda expressions:

λf.λx.f x

This looks opaque and mathematical, but most modern programmers should be familiar with lambda (λ) expressions. The above expression is an anonymous function that takes a single argument: f. The body of the function is the return value; here, another lambda expression: λx.f x. This lambda expression also takes a single argument: x.

In the untyped lambda calculus, everything is a function, so that includes f and x. The return value of the entire expression is f x, which means that the function f is applied to the value (in fact: function) x. The entire expression is therefore a higher-order function.

In C#, the corresponding lambda expression would be:

f => x => f(x)

This is a lambda expression that returns another lambda expression, which again returns the result of calling the function f with the value x.

In F#, it would be:

fun f -> fun x -> f x

and in Haskell, it would be:

\f -> \x -> f x

In both Haskell and F#, functions are already curried, so you can shorten that Haskell lambda expression to:

\f x -> f x

and the F# lambda expression to:

fun f x -> f x

This looks more like a function that takes two arguments, so alternatively, via uncurry isomorphisms, you can also write the C# representation like this:

(f, x) => f(x)

Those six lambda expressions, however, are statically typed, even though they're generic (or, as Haskellers would put it, parametric polymorphic). This means that they're not entirely equal to λf.λx.f x, but it should give you a sense of what a lambda expression is.

It turns out that using nothing but lambda expressions, one can express any computation; lambda calculus is Turing-complete.

Church encoding #

Since languages like C#, F#, Haskell, and others, include lambda expressions, you can reproduce as much of the lambda calculus as you'd like. In this article series, I'll mainly use it to show you how to represent sum types in C#. Later, you'll see how it relates to design patterns.

These articles give you examples in C#. For Haskell examples, I found Travis Whitaker's article Scrap Your Constructors: Church Encoding Algebraic Types useful.

All C# code for these articles is available on GitHub.

Summary #

You can use lambda expressions to define all sorts of data types and computations. Because lambda calculus is a universal model of computation, you can learn about fundamental representations of computation. Particularly, lambda calculus offers a model of logical branching, which again teaches us how to model sum types.

Next: Church-encoded Boolean values.


Comments

Hey Mark, Just watched your Humane Code series so far on cleancoders.com. Really enjoying it. Looking forward to the next episode with much anticipation!

James
2018-05-24 12:42 UTC

Composite as a monoid - a business rules example

Thursday, 17 May 2018 06:45:00 UTC

Composites are monoids. An example in C#, F#, and Haskell.

Towards the end of the first decade of the third millennium, I'd been writing object-oriented code for about ten years, and I'd started to notice some patterns in my code. I'd read Design Patterns 6-7 years earlier, but I noticed that I tended to use only a small subset of the patterns from the book - particularly Composite, Decorator, Chain of Responsibility, and a few others.

In particular, I noticed that modelling seemed to be easier, and the code better structured, when I could apply the Composite design pattern. It was also clear, however, that I couldn't always use the Composite pattern, so I started to speculate on what could be the distinguishing factors. In 2010, I made a first attempt at identifying when a Composite is possible, and when it isn't. Unfortunately, while it was a fine attempt (which I'll return to later), it didn't lead anywhere. Ultimately, I gave up on the subject and moved on to other things.

A revelation #

One of my interests in the next decade became functional programming. One day in late 2016 I came across this Code Review question by Scott Nimrod. It was an solution to the Business Rules kata, which, briefly told, is about implementing changing business rules in a sustainable manner.

In my answer to the question, I gave an outline (repeated below) of how I would address the problem in F#. As a comment to my answer, Scott wrote:

"Feels like the Decorator Pattern..."

I responded,

"Not really; it's the Composite pattern..."

A few days later, as I was doing something else, it suddenly dawned on me that not only was a few lines of F# code equivalent to the Composite design pattern, but those lines of code were also manifestations of fundamental abstractions from category theory. Originally, I thought Composite was a combination of applicative functors and monoids, but as I investigated, I discovered that Composites are simply monoids.

This article shows a concrete example of that discovery, starting with my original F# code, subsequently translating it to C# to demonstrate that it's a Composite, and concluding with a translation to Haskell in order to demonstrate that it all fits with the formalisation of Monoid there.

Original F# solution outline #

The kata is about modelling volatile business rules in a sustainable manner. Particularly, you must implement various business rules associated with payments for products and services. Making a rough outline of a model, I started by introducing some types in F#:

type Membership = Basic | Gold
 
type Good =
| PhysicalProduct of string
| Book of string
| Video of string
| Membership of Membership
| Upgrade
 
type Command =
| Slip of string * (Good list)
| Activate of Membership
| Upgrade
| PayAgent

This basically states that there's a closed hierarchy of goods, and a closed hierarchy of business commands, as well as a Membership enumeration. A good can be a physical product with a name, a book with a name, a membership or upgrade, and so on. A command can be a packing slip, a membership activation, and so on.

Since I was only interested in a rough outline of a solution, I only sketched four business rules, all implemented as functions. The first creates a packing slip for certain goods:

// Good -> Command list
let slipForShipping = function
| PhysicalProduct name -> [Slip ("Shipping", [PhysicalProduct name])]
| Book name            -> [Slip ("Shipping", [Book name])]
| Video name           -> [Slip ("Shipping", [Video name])]
| _                    -> []

This function takes a Good value as input and returns a list of Command values as output. If the Good is a PhysicalProduct, Book, or Video, it returns a packing slip command; otherwise, it returns an empty list of commands.

The next business rule is a similar function:

// Good -> Command list
let slipForRoyalty = function
| Book name -> [Slip ("Royalty", [Book name])]
| _         -> []

This business rule generates a royalty slip for any Book, but does nothing for any other Good.

The third business rule activates a membership:

// Good -> Command list
let activate = function | Membership x -> [Activate x] | _ -> []

If the Good is a Membership, the activate function returns a list containing a single Activate command; otherwise, it returns an empty list.

Finally, the last rule upgrades a membership:

// Good -> Command list
let upgrade = function | Good.Upgrade -> [Upgrade] | _ -> []

Similar to the previous functions, this one looks at the type of Good, and returns an Upgrade command when the input is an Upgrade good, and an empty list otherwise.

Notice that all four functions share the same type: Good -> Command list. I designed them like that on purpose, because this enables you to compose a list of business rules to a function that looks like a single rule:

// ('a -> 'b list) list -> 'a -> 'b list
let handle rules good = List.collect (fun r -> r good) rules

This handle function takes a list of business rules (rules) and returns a new function with the type Good -> Command list (or, actually, a function with the type 'a -> 'b list - once again I've fallen into the trap of using too descriptive names). Notice that this is the same type as the individual rules.

You can now compose the four specific business rules:

// Good -> Command list
let handleAll = handle [slipForShipping; slipForRoyalty; activate; upgrade]

This function also has the type Good -> Command list although it's a composition of four rules.

You can use it like this F# Interactive example:

> handleAll (Book "The Annotated Turing");;
val it : Command list =
  [Slip ("Shipping",[Book "The Annotated Turing"]);
   Slip ("Royalty",[Book "The Annotated Turing"])]

(Yes, I like The Annotated Turing - read my review on Goodreads.)

Notice that while each of the business rules produces only zero or one Command values, in this example handleAll returns two Command values.

This design, where a composition looks like the things it composes, sounds familiar.

Business rules in C# #

You can translate the above F# model to an object-oriented model in C#. Translating discriminated unions like Good and Command to C# always involves compromises. In order to keep the example as simple as possible, I decided to translate each of those to a marker interface, although I loathe that 'pattern':

public interface IGood { }

While the interface doesn't afford any behaviour, various classes can still implement it, like, for example, Book:

public class Book : IGood
{
    public Book(string name)
    {
        Name = name;
    }
 
    public string Name { get; }
}

Other IGood 'implementations' looks similar, and there's a comparable class hierarchy for ICommand, which is another marker interface.

The above F# code used a shared function type of Good -> Command list as a polymorphic type for a business rule. You can translate that to a C# interface:

public interface IRule
{
    IReadOnlyCollection<ICommand> Handle(IGood good);
}

The above slipForShipping function becomes a class that implements the IRule interface:

public class SlipForShippingRule : IRule
{
    public IReadOnlyCollection<ICommand> Handle(IGood good)
    {
        if (good is PhysicalProduct ||
            good is Book ||
            good is Video)
            return new[] { new SlipCommand("Shipping", good) };
 
        return new ICommand[0];
    }
}

Instead of pattern matching on a discriminated union, the Handle method examines the subtype of good and only returns a SlipCommand if the good is either a PhysicalProduct, a Book, or a Video.

The other implementations are similar, so I'm not going to show all of them, but here's one more:

public class ActivateRule : IRule
{
    public IReadOnlyCollection<ICommand> Handle(IGood good)
    {
        var m = good as MembershipGood;
        if (m != null)
            return new[] { new ActivateCommand(m.Membership) };
 
        return new ICommand[0];
    }
}

Since 'all' members of IRule return collections, which form monoids over concatenation, the interface itself gives rise to a monoid. This means that you can create a Composite:

public class CompositeRule : IRule
{
    private readonly IRule[] rules;
 
    public CompositeRule(params IRule[] rules)
    {
        this.rules = rules;
    }
 
    public IReadOnlyCollection<ICommand> Handle(IGood good)
    {
        var commands = new List<ICommand>();
        foreach (var rule in rules)
            commands.AddRange(rule.Handle(good));
        return commands;
    }
}

Notice how the implementation of Handle follows the template for monoid accumulation. It starts with the identity, which, for the collection concatenation monoid is the empty collection. It then loops through all the composed rules and updates the accumulator commands in each iteration. Here, I used AddRange, which mutates commands instead of returning a new value, but the result is the same. Finally, the method returns the accumulator.

You can now compose all the business rules and use the composition as though it was a single object:

var rule =
    new CompositeRule(
        new SlipForShippingRule(),
        new SlipForRoyaltyRule(),
        new ActivateRule(),
        new UpgradeRule());
 
var book = new Book("The Annotated Turing");
var commands = rule.Handle(book);

When the method returns, commands contains two SlipCommand objects - a packing slip, and a royalty slip.

Business rules in Haskell #

You can also port the F# code to Haskell, which is usually easy as long as the F# is written in a 'functional style'. Since Haskell has an explicit notion of monoids, you'll be able to see how the two above solutions are monoidal.

The data types are easy to translate to Haskell - you only have to adjust the syntax a bit:

data Membership = Basic | Gold deriving (ShowEqEnumBounded)
 
data Good =
    PhysicalProduct String
  | Book String
  | Video String
  | Membership Membership
  | UpgradeGood
  deriving (ShowEq)
 
data Command =
    Slip String [Good]
  | Activate Membership
  | Upgrade
  | PayAgent
  deriving (ShowEq)

The business rule functions are also easy to translate:

slipForShipping :: Good -> [Command]
slipForShipping pp@(PhysicalProduct _) = [Slip "Shipping" [pp]]
slipForShipping             b@(Book _) = [Slip "Shipping"  [b]]
slipForShipping            v@(Video _) = [Slip "Shipping"  [v]]
slipForShipping                     _  = []
 
slipForRoyalty :: Good -> [Command]
slipForRoyalty b@(Book _) = [Slip "Royalty" [b]]
slipForRoyalty         _  = []
 
activate :: Good -> [Command]
activate (Membership m) = [Activate m]
activate             _  = []
 
upgrade :: Good -> [Command]
upgrade (UpgradeGood) = [Upgrade]
upgrade            _  = []

Notice that all four business rules share the same type: Good -> [Command]. This is conceptually the same type as in the F# code; instead of writing Command list, which is the F# syntax, the Haskell syntax for a list of Command values is [Command].

All those functions are monoids because their return types form a monoid, so in Haskell, you can compose them without further ado:

handleAll :: Good -> [Command]
handleAll = mconcat [slipForShipping, slipForRoyalty, activate, upgrade]

mconcat is a built-in function that aggregates any list of monoidal values to a single value:

mconcat :: Monoid a => [a] -> a

Since all four functions are monoids, this just works out of the box. A Composite is just a monoid. Here's an example of using handleAll from GHCi:

*BusinessRules> handleAll $ Book "The Annotated Turing"
[Slip "Shipping" [Book "The Annotated Turing"],Slip "Royalty" [Book "The Annotated Turing"]]

The result is as you'd come to expect.

Notice that not only don't you have to write a CompositeRule class, you don't even have to write a handle helper function. Haskell already understands monoids, so composition happens automatically.

If you prefer, you could even skip the handle function too:

*BusinessRules> mconcat [slipForShipping, slipForRoyalty, activate, upgrade] $ Book "Blindsight"
[Slip "Shipping" [Book "Blindsight"],Slip "Royalty" [Book "Blindsight"]]

(Yes, you should also read Blindsight.)

It's not that composition as such is built into Haskell, but rather that the language is designed around a powerful ability to model abstractions, and one of the built-in abstractions just happens to be monoids. You could argue, however, that many of Haskell's fundamental abstractions are built from category theory, and one of the fundamental characteristics of a category is how morphisms compose.

Summary #

Composite are monoids. This article shows an example, starting with a solution in F#. You can translate the F# code to object-oriented C# and model the composition of business rules as a Composite. You can also translate the F# code 'the other way', to the strictly functional language Haskell, and thereby demonstrate that the solution is based on a monoid.

This article is a repost of a guest post on the NDC blog, reproduced here with kind permission.


Project Arbitraries with view patterns

Monday, 14 May 2018 08:07:00 UTC

Write expressive property-based test with QuickCheck and view patterns.

Recently, I was writing some QuickCheck-based tests of some business logic, and since the business logic in question involved a custom domain type called Reservation, I had to write an Arbitrary instance for it. Being a dutiful Haskell programmer, I wrapped it in a newtype in order to prevent warnings about orphaned instances:

newtype ArbReservation = ArbReservation { getReservation :: Reservation } deriving (ShowEq)

instance Arbitrary ArbReservation where
  arbitrary = do
    (d, e, n, Positive q, b) <- arbitrary
    return $ ArbReservation $ Reservation d e n q b

This is all fine as long as you just need one Reservation in a test, because in that case, you can simply pattern-match it out of ArbReservation:

testProperty "tryAccept reservation in the past" $ \
  (Positive capacity) (ArbReservation reservation)
  ->
  let stub (IsReservationInFuture _ next) = next False
      stub (ReadReservations _ next) = next []
      stub (Create _ next) = next 0

      actual = iter stub $ runMaybeT $ tryAccept capacity reservation
      
  in  isNothing actual

Here, reservation is a Reservation value because it was pattern-matched out of ArbReservation reservation. That's just like capacity is an Int, because it was pattern-matched out of Positive capacity.

Incidentally, in the spirit of the previous article, I'm here using in-lined properties implemented as lambda expressions. The lambda expressions use non-idiomatic formatting in order to make the tests more readable (and to prevent horizontal scrolling), but the gist of the matter is that the entire expression has the type Positive Int -> ArbReservation -> Bool. This is a Testable property because all the input types have Arbitrary instances.

Discommodity creeps in #

That's fine for that test case, but for the next, I needed not only a single Reservation value, but also a list of Reservation values. Again, with QuickCheck, you can't write a property with a type like Positive Int -> [Reservation] -> ArbReservation -> Bool, because there's no Arbitrary instance for [Reservation]. Instead, you'll need a property with the type Positive Int -> [ArbReservation] -> ArbReservation -> Bool.

One way to do that is to write the property like this:

testProperty "tryAccept reservation when capacity is insufficient" $ \
  (Positive i)
  reservations
  (ArbReservation reservation)
  ->
  let stub (IsReservationInFuture _ next) = next True
      stub (ReadReservations _ next) = next $ getReservation <$> reservations
      stub (Create _ next) = next 0
      reservedSeats = sum $ reservationQuantity <$> getReservation <$> reservations
      capacity = reservedSeats + reservationQuantity reservation - i

      actual = iter stub $ runMaybeT $ tryAccept capacity reservation

  in  isNothing actual

Here, reservations has type type [ArbReservation], so every time the test needs to operate on the values, it first has to pull the Reservation values out of it using getReservation <$> reservations. That seems unnecessarily verbose and repetitive, so it'd be nice if a better option was available.

View pattern #

Had I been writing F# code, I'd immediately be reaching for an active pattern, but this is Haskell. If there's one thing, though, I've learned about Haskell so far, it's that, if F# can do something, there's a very good chance Haskell can do it too - only, it may be called something else.

With a vague sense that I'd seen something similar in some Haskell code somewhere, I went looking, and about fifteen minutes later I'd found what I was looking for: a little language extension called view patterns. Just add the language extension to the top of the file where you want to use it:

{-# LANGUAGE ViewPatterns #-}

You can now change the property to pattern-match reservations out of a function call, so to speak:

testProperty "tryAccept reservation when capacity is insufficient" $ \
  (Positive i)
  (fmap getReservation -> reservations)
  (ArbReservation reservation)
  ->
  let stub (IsReservationInFuture _ next) = next True
      stub (ReadReservations _ next) = next reservations
      stub (Create _ next) = next 0
      reservedSeats = sum $ reservationQuantity <$> reservations
      capacity = reservedSeats + reservationQuantity reservation - i

      actual = iter stub $ runMaybeT $ tryAccept capacity reservation

  in  isNothing actual

The function getReservation has the type ArbReservation -> Reservation, so fmap getReservation is a partially applied function with the type [ArbReservation] -> [Reservation]. In order to be able to call the overall lambda expression, the caller must supply an [ArbReservation] value to the view pattern, which means that the type of that argument must be [ArbReservation]. The view pattern then immediately unpacks the result of the function and gives you reservations, which is the return value of calling fmap getReservation with the input value(s). Thus, reservations has the type [Reservation].

The type of the entire property is now Positive Int -> [ArbReservation] -> ArbReservation -> Bool.

This removes some noise from the body of the property, so I find that this is a useful trick in this particular situation.

Summary #

You can use the view patterns GHC language extension when you need to write a function that takes an argument of a particular type, but you never care about the original input, but instead immediately wish to project it to a different value.

I haven't had much use for it before, but it seems to be useful in the context of QuickCheck properties.


Comments

I've seen folks wrap up the view pattern in a pattern synonym:


pattern ArbReservations :: [Reservation] -> [ArbReservation]
pattern ArbReservations rs <- (coerce -> rs) where ArbReservations rs = coerce rs

foo :: [ArbReservation] -> IO ()
foo (ArbReservations rs) = traverse print rs
			

(coerce is usually more efficient than fmap.)

OTOH I don't think orphan instances of Arbitrary are very harmful. It's unlikely that they'll get accidentally imported or overlap, because Arbitrary is purely used for testing. So in this specific case I'd probably just stick with an orphan instance and turn off the warning for that file.

2018-05-26 10:55 UTC

Benjamin, thank you for the pattern synonyms tip; I'll have to try that next time.

Regarding orphaned instances, your point is something I've been considering myself, but I'm still at the point of my Haskell journey where I'm trying to understand the subtleties of the ecosystem, so I wasn't sure whether or not it'd be a good idea to allow orphaned Arbitrary instances.

When you suggest turning off the warning for a file, do you mean adding an {-# OPTIONS_GHC -fno-warn-orphans #-} pragma, or did you have some other method in mind?

2018-05-27 7:54 UTC

Yep I meant OPTIONS_GHC.

Orphan instances are problematic because of the possibility that they'll be imported unintentionally or overlap with another orphan instance. If you import two modules which both define orphan instances for the same type then there's no way for GHC to know which one you meant when you attempt to use them. Since instances aren't named you can't even specify it manually, and the compiler can't check for this scenario ahead of time because of separate compilation. (Non-orphans are guaranteed unique by the fact that you can't import the parent type/class without importing the instance.)

In the case of Arbitrary these problems typically don't apply because the class is intended to be used for testing. Arbitrary instances are usually internal to your test project and not exported, so the potential for damage is small.

2018-05-27 14:08 UTC

Benjamin, thank you for elaborating. That all makes sense to me.

2018-05-27 16:06 UTC

Inlined HUnit test lists

Monday, 07 May 2018 12:41:00 UTC

An alternative way to organise tests lists with HUnit.

In the previous article you saw how to write parametrised test with HUnit. While the tests themselves were elegant and readable (in my opinion), the composition of test lists left something to be desired. This article offers a different way to organise test lists.

Duplication #

The main problem is one of duplication. Consider the main function for the test library, as defined in the previous article:

main = defaultMain $ hUnitTestToTests $ TestList [
  "adjustToBusinessHours returns correct result" ~: adjustToBusinessHoursReturnsCorrectResult,
  "adjustToDutchBankDay returns correct result" ~: adjustToDutchBankDayReturnsCorrectResult,
  "Composed adjust returns correct result" ~: composedAdjustReturnsCorrectResult ]

It annoys me that I have a function with a (somewhat) descriptive name, like adjustToBusinessHoursReturnsCorrectResult, but then I also have to give the test a label - in this case "adjustToBusinessHours returns correct result". Not only is this duplication, but it also adds an extra maintenance overhead, because if I decide to rename the test, should I also rename the label?

Why do you even need the label? When you run the test, that label is printed during the test run, so that you can see what happens:

$ stack test --color never --ta "--plain"
ZonedTimeAdjustment-0.1.0.0: test (suite: ZonedTimeAdjustment-test, args: --plain)

:adjustToDutchBankDay returns correct result:
  : [OK]
  : [OK]
  : [OK]
  : [OK]
  : [OK]
  : [OK]
  : [OK]
  : [OK]
  : [OK]
  : [OK]
  : [OK]
  : [OK]
:adjustToBusinessHours returns correct result:
  : [OK]
  : [OK]
  : [OK]
:Composed adjust returns correct result:
  : [OK]
  : [OK]
  : [OK]
  : [OK]
  : [OK]

         Test Cases   Total
 Passed  20           20
 Failed  0            0
 Total   20           20

I considered it redundant to give each test case in the parametrised tests their own labels, but I could have done that too, if I'd wanted to.

What happens if you remove the labels?

main = defaultMain $ hUnitTestToTests $ TestList $
      adjustToBusinessHoursReturnsCorrectResult
  ++  adjustToDutchBankDayReturnsCorrectResult
  ++  composedAdjustReturnsCorrectResult

That compiles, but produces output like this:

$ stack test --color never --ta "--plain"
ZonedTimeAdjustment-0.1.0.0: test (suite: ZonedTimeAdjustment-test, args: --plain)

: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]
: [OK]

         Test Cases   Total
 Passed  20           20
 Failed  0            0
 Total   20           20

If you don't care about the labels, then that's a fine solution. On the other hand, if you do care about the labels, then a different approach is warranted.

Inlined test lists #

Looking at an expression like "Composed adjust returns correct result" ~: composedAdjustReturnsCorrectResult, I find "Composed adjust returns correct result" more readable than composedAdjustReturnsCorrectResult, so if I want to reduce duplication, I want to go after a solution that names a test with a label, instead of a solution that names a test with a function name.

What is composedAdjustReturnsCorrectResult? It's just the name of a pure function (because its type is [Test]). Since it's referentially transparent, it means that in the test list in main, I can replace the function with its body! I can do this with all three functions, although, in order to keep things simplified, I'm only going to show you two of them:

main :: IO ()
main = defaultMain $ hUnitTestToTests $ TestList [
  "adjustToBusinessHours returns correct result" ~: do
    (dt, expected) <-
      [
        (zt (2017102) (659,  40, zt (2017102) (9,  0,  00),
        (zt (2017102) (942410, zt (2017102) (942410),
        (zt (2017102) (191320, zt (2017103) (9,  0,  00)
      ]
    let actual = adjustToBusinessHours dt
    return $ ZT expected ~=? ZT actual
 
  ,
  "Composed adjust returns correct result" ~: do
    (dt, expected) <-
      [
        (zt (2017131) ( 74555)   2 , zt (2017228) ( 7,  0,  00),
        (zt (20172,  6) (10,  3,  2)   1 , zt (20173,  6) ( 9,  3,  20),
        (zt (20172,  9) ( 420,  0)   0 , zt (20173,  9) ( 9,  0,  00),
        (zt (2017212) (16,  211)   0 , zt (2017310) (16,  2110),
        (zt (2017314) (134829) (-1), zt (2017413) (1448290)
      ]
    let adjustments =
          reverse [adjustToNextMonth, adjustToBusinessHours, adjustToDutchBankDay, adjustToUtc]
    let adjust = appEndo $ mconcat $ Endo <$> adjustments
 
    let actual = adjust dt
 
    return $ ZT expected ~=? ZT actual
  ]

In order to keep the code listing to a reasonable length, I didn't include the third test "adjustToDutchBankDay returns correct result", but it works in exactly the same way.

This is a list with two values. You can see that the values are separated by a ,, just like list elements normally are. What's unusual, however, is that each element in the list is defined with a multi-line do block.

In C# and F#, I'm used to being able to just write new test functions, and they're automatically picked up by convention and executed by the test runner. I wouldn't be at all surprised if there was a mechanism using Template Haskell that enables something similar, but I find that there's something appealing about treating tests as first-class values all the way.

By inlining the tests, I can retain my F# and C# workflow. Just add a new test within the list, and it's automatically picked up by the main function. Not only that, but it's no longer possible to write a test that compiles, but is never executed by the test runner because it has the wrong type. This occasionally happens to me in F#, but with the technique outlined here, if I accidentally give the test the wrong type, it's not going to compile.

Conclusion #

Since HUnit tests are first-class values, you can define them inlined in test lists. For larger code bases, I'd assume that you'd want to spread your unit tests across multiple modules. In that case, I suppose that you could have each test module export a [Test] value. In the test library's main function, you'd need to manually concatenate all the exported test lists together, so a small maintenance burden remains. When you add a new test module, you'd have to add its exported tests to main.

I wouldn't be surprised, however, if a clever reader could point out to me how to avoid that as well.


Page 3 of 44

"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!