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

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
{

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
{

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
{

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.

### Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

#### Published

Thursday, 24 May 2018 04:49:00 UTC

#### Tags

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