The boolean lets us separate how to make a decision (which we define in function1), from how to handle a decision (which we define in function2). We can always eliminate this data by bringing those two things together, e.g.
// Inline function1 into function2
void function3(...) {
FOO
BAR
if (true) {
BAZ
} else {
QUUX
}
}
// Simplify the if/then/else
void function4(...) {
FOO
BAR
BAZ
}
Of course, it's very useful to keep things separate and to pass data around (modularity, readability, etc.). My point is that the computer/language doesn't care about these things, so we can use refactorings like this to 'distill the essence' of what data 'really is' (from this one perspective, at least).
So what can we do with a boolean?
- We can discard it. Such code can always be refactored to eliminate the boolean (it's dead code).
- Pass it to some other code. We can always refactor this to remove such intermediate steps, e.g. above we inlined 'function1' to avoid passing the boolean around.
- Construct them. We do this by using the "constructors" 'true' or 'false', AKA the "introduction forms".
- Branch on them using if/then/else. This is also called "destructing", where if/then/else is a "destructor" or "elimination form".
- Simplify 'if(true) ...' and 'if(false) ...'. Here we are 'destructing a constructor', which can always be replaced by the relevant branch.
If we apply these refactorings over and over we can eventually simplify-away every boolean value in a program. There are a couple of things to keep in mind:
- Some languages have special-case boolean operations like '!foo'. Those are equivalent to functions containing branches, which can be refactored as above, e.g.
boolean not(boolean x) {
if (x) {
return false;
} else {
return true;
}
}
boolean and(boolean x, boolean y) {
if (x) {
return y;
} else {
return false;
}
}
boolean or(boolean x, boolean y) {
if (x) {
return true;
} else {
return y;
}
}
- To fully eliminate data, we need to include any 'external' code, e.g. 'inlining' external libraries, system calls, third-party APIs, etc. For simplicity I'll just assume we're using a single program in a single language, but the principle still holds in general.
Note that inlining intermediate steps and removing unused parameters have nothing to do with booleans themselves; they apply to all forms of data. Hence the 'essence' of booleans is the simplification of 'if(true)...' and if(false)...'.
We can do this with booleans since they are a "sum type", i.e. there are a few distinct forms of boolean (namely "true" and "false"). This is similar to the article's "Shape" type, which has a "Circle" form and a "Rectangle" form.
OOP languages don't tend to support sum types directly; instead we can 'fake it' using subtypes. Here's an example, where I've implemented the simplification behaviour using subtype polymorphism:
abstract class Boolean {
T ifThenElse(T t, T e);
}
class True extends Boolean {
T ifThenElse(T t, T e) {
return t;
}
}
class False extends Boolean {
T ifThenElse(T t, T e) {
return e;
}
}
There's a slight wrinkle here, since calling 'ifThenElse(foo, bar)' will execute both 'foo' and 'bar'; we'll just get one of them returned back to us. If this is a problem, we can wrap our branches in zero-argument functions, pass those to 'ifThenElse', and call whichever function gets returned. Note that this is actually how Smalltalk implements boolean branching! https://rosettacode.org/wiki/Conditional_structures#Smalltal...
Hopefully I've demonstrated that the three classed defined above are a complete implementation of booleans: we have the constructors ('new True()' and 'new False()'), the destructor 'ifThenElse(thenBranch, elseBranch)', and we don't need anything else. To drive this point home, here's how we can define boolean algebra, translated from the above:
// not(x)
x.ifThenElse(new False(), new True())
// and(x, y)
x.ifThenElse(y, new False())
// or(x, y)
x.ifThenElse(new True(), y)
This implementation of Boolean is a rather simple form of "visitor pattern": the implementation of the "ifThenElse algorithm" is spread out amongst different implementations of the method, where each subclass knows how to handle its own case, and we just dispatch on whatever Boolean object we happen to have.
The point of Church Encoding is that we don't actually need these classes and polymorphism at all: rather than wrapping up these methods into classes, defining a class hierarchy, constructing instances of these subclasses, invoking methods on those instances, dynamically dispatching on the vtables, etc.; we can just pass the functions around directly!
Switching to JS, since it has first-class functions, here's my first example again:
If we want to avoid executing both BAZ and QUUX, we could wrap them up in functions like 'function1(...)(() => BAZ, () => QUUX)()'. We could also rename these functions to simply 'true' and 'false', since they're completely equivalent to those values (although that would be a syntax error in JS).
So now we've seen that (a) booleans can be completely implemented using if/then/else (b) the behaviour of if/then/else can be implemented using subclass polymorphism (c) subclass polymorphism can be emulated by passing around first-class functions. Note that we could have skipped all the OOP stuff and gone straight to functions, but I thought it might help some people, and it's also interesting in its own right.
This also extends to sum types with any number of distinct forms (which we now know are "constructors"). The rule is simple: a type with N constructors can be represented as a function which takes N arguments, and returns one of them. For example, we could represent Colour, with Red/Green/Blue like this:
const red = (r, g, b) => r;
const green = (r, g, b) => g;
const blue = (r, g, b) => b;
function printColour(c) {
console.log(c("Received red", "Given green", "Bestowed with blue"));
}
There are two other sorts of data to consider:
"Product types" contain multiple sub-values, e.g. 'Coordinate(x, y, z)'. For these, the rule is that we call the corresponding argument as a function, passing it the sub-values as arguments. For example:
const mkCoord = (x, y, z) => f => f(x, y, z);
function showCoord(c) {
c((x, y, z) => console.log(
"x: " + x.toString + " y:" + y.toString + " z: " + z.toString
));
}
const origin = mkCoord(0, 0, 0);
showCoord(origin);
Note that I'm using raw JS numbers and strings for simplicity; we can implement these using Church Encoding (e.g. using 64 booleans to emulate a double-precision float), but it would be tedious for this example.
We can combine sums and products, i.e. each constructor can contain sub-values. This is what the "Shape" example from the article does. We just need to combine the two rules: take N arguments (once for each constructor), and call the appropriate argument with the sub-values. For example:
const circle = (x, y, r) => (ifCirc, ifRect) => ifCirc(x, y, z)
const rectangle = (x, y, w, h) => (ifCirc, ifRect) => ifRect(x, y, w, h)
const unitCircle = circle(0, 0, 1);
const unitSquare = rectangle(0, 0, 1, 1);
function drawShape(s) {
s(
(x, y, r) => console.log("Circle of radius " + r.toString),
(x, y, w, h) => console.log("Rect of area " (w * h).toString)
);
}
The final possibility is recursive data, where the sub-values can be of the same type we're defining. The article uses a binary tree as an example, but a list is easier. In OOP:
abstract class List<T> {
U reduce(U init, Function<U, Pair<U, T>> f);
}
class Nil<T> extends List<T> {
U reduce(U init, Function<U, Pair<U, T>> f) {
return init;
}
}
class Cons<T> extends List<T> {
private T head;
private List<T> tail;
public Cons(T head, List<T> tail) {
this.head = head;
this.tail = tail;
}
U reduce(U init, Function<U, Pair<U, T>> f) {
return this.tail.reduce(
f(new Pair<U, T>(init, this.head)),
f
);
}
}
With first-class functions (this might be slightly off; it's been a while!):
So the trick to recursive data is that whenever we need to pass a sub-value to one of our N given functions, if that sub-value is of our recursive type (like the 'tail' of a list is another list) then we first call that sub-value with the same N functions we've been given. That way, the structure 'reduces' down to a single result.
So what can we do with a boolean?
- We can discard it. Such code can always be refactored to eliminate the boolean (it's dead code).
- Pass it to some other code. We can always refactor this to remove such intermediate steps, e.g. above we inlined 'function1' to avoid passing the boolean around.
- Construct them. We do this by using the "constructors" 'true' or 'false', AKA the "introduction forms".
- Branch on them using if/then/else. This is also called "destructing", where if/then/else is a "destructor" or "elimination form".
- Simplify 'if(true) ...' and 'if(false) ...'. Here we are 'destructing a constructor', which can always be replaced by the relevant branch.
If we apply these refactorings over and over we can eventually simplify-away every boolean value in a program. There are a couple of things to keep in mind:
- Some languages have special-case boolean operations like '!foo'. Those are equivalent to functions containing branches, which can be refactored as above, e.g.
Note that inlining intermediate steps and removing unused parameters have nothing to do with booleans themselves; they apply to all forms of data. Hence the 'essence' of booleans is the simplification of 'if(true)...' and if(false)...'.We can do this with booleans since they are a "sum type", i.e. there are a few distinct forms of boolean (namely "true" and "false"). This is similar to the article's "Shape" type, which has a "Circle" form and a "Rectangle" form.
OOP languages don't tend to support sum types directly; instead we can 'fake it' using subtypes. Here's an example, where I've implemented the simplification behaviour using subtype polymorphism:
There's a slight wrinkle here, since calling 'ifThenElse(foo, bar)' will execute both 'foo' and 'bar'; we'll just get one of them returned back to us. If this is a problem, we can wrap our branches in zero-argument functions, pass those to 'ifThenElse', and call whichever function gets returned. Note that this is actually how Smalltalk implements boolean branching! https://rosettacode.org/wiki/Conditional_structures#Smalltal...Hopefully I've demonstrated that the three classed defined above are a complete implementation of booleans: we have the constructors ('new True()' and 'new False()'), the destructor 'ifThenElse(thenBranch, elseBranch)', and we don't need anything else. To drive this point home, here's how we can define boolean algebra, translated from the above:
This implementation of Boolean is a rather simple form of "visitor pattern": the implementation of the "ifThenElse algorithm" is spread out amongst different implementations of the method, where each subclass knows how to handle its own case, and we just dispatch on whatever Boolean object we happen to have.The point of Church Encoding is that we don't actually need these classes and polymorphism at all: rather than wrapping up these methods into classes, defining a class hierarchy, constructing instances of these subclasses, invoking methods on those instances, dynamically dispatching on the vtables, etc.; we can just pass the functions around directly!
Switching to JS, since it has first-class functions, here's my first example again:
If we want to avoid executing both BAZ and QUUX, we could wrap them up in functions like 'function1(...)(() => BAZ, () => QUUX)()'. We could also rename these functions to simply 'true' and 'false', since they're completely equivalent to those values (although that would be a syntax error in JS).So now we've seen that (a) booleans can be completely implemented using if/then/else (b) the behaviour of if/then/else can be implemented using subclass polymorphism (c) subclass polymorphism can be emulated by passing around first-class functions. Note that we could have skipped all the OOP stuff and gone straight to functions, but I thought it might help some people, and it's also interesting in its own right.
This also extends to sum types with any number of distinct forms (which we now know are "constructors"). The rule is simple: a type with N constructors can be represented as a function which takes N arguments, and returns one of them. For example, we could represent Colour, with Red/Green/Blue like this:
There are two other sorts of data to consider:"Product types" contain multiple sub-values, e.g. 'Coordinate(x, y, z)'. For these, the rule is that we call the corresponding argument as a function, passing it the sub-values as arguments. For example:
Note that I'm using raw JS numbers and strings for simplicity; we can implement these using Church Encoding (e.g. using 64 booleans to emulate a double-precision float), but it would be tedious for this example.We can combine sums and products, i.e. each constructor can contain sub-values. This is what the "Shape" example from the article does. We just need to combine the two rules: take N arguments (once for each constructor), and call the appropriate argument with the sub-values. For example:
The final possibility is recursive data, where the sub-values can be of the same type we're defining. The article uses a binary tree as an example, but a list is easier. In OOP: With first-class functions (this might be slightly off; it's been a while!): So the trick to recursive data is that whenever we need to pass a sub-value to one of our N given functions, if that sub-value is of our recursive type (like the 'tail' of a list is another list) then we first call that sub-value with the same N functions we've been given. That way, the structure 'reduces' down to a single result.