# Church-encoded Boolean values by Mark Seemann

*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.

`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.