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

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