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 valuey, another Boolean valuet, the value to return if the expression is true; thetrueCaseargument in the above C# implementation.f, the value to return if the expression is false; thefalseCaseargument 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.
