Forever Functional: D.I.Y. Booleans?

Could you program if you didn’t have booleans? What about lacking and, or, and other operators? Would you be able to cope without if or while statements? Functional Programming is very powerful, and in this article, we’ll see how we can make our own booleans in a fully functional way.

What do we use boolean values for? The answer is simple: to pick one thing or another. For instance, in an if statement, you do one thing or another depending on the value. If we can only work with functions, we will represent a boolean value by a function; no other option!

The boolean function that represents “true”, given two values, returns the first. Similarly, the boolean function that represents “false”, given two values, will return the second. We can write:

const TRUE  = (trueValue, falseValue) => trueValue;
const FALSE = (trueValue, falseValue) => falseValue;

Can we do something with these? Let’s start with something simple, to get used to these values gradually. We can write a toString() function to transform the boolean value into a string.

const toString = boolValue => boolValue("T", "F");

console.log(toString(TRUE));   // "T"
console.log(toString(FALSE));  // "F"

In our implementation, boolean expressions will always be evaluated as TRUE or FALSE.

Writing our boolean operators

OK, we now have the most basic values, TRUE and FALSE. But, if we had no booleans, we would not have any boolean operators either! So, what can we do? Let’s start with the simplest one.

The “not” operator

The first operator we’ll work out is the equivalent of JavaScript’s !: given a boolean value x, we want to write something corresponding to !x.

const NOT = (X) => X(FALSE, TRUE);

How does this work? Keep in mind that a boolean value is now a function that receives two values and returns the first if the boolean value represents “true” or the second if it represents “false”. Here, we pass FALSE and TRUE as values, so if the boolean value represents “true”, FALSE will be returned, and if the value represents FALSE, TRUE will be the result. We can test this quickly:

console.log(toString(NOT(TRUE)));  // "F"
console.log(toString(NOT(FALSE))); // "T"

Study this carefully, and make sure you understand how this works because the following operators are a bit more involved but require the same kind of thinking.

The “or” operator

Let’s create a version of the “OR” (||) operator, so given two boolean values, X and Y, we can write something equivalent to X||Y. First, we must remember how the operation works.

Checking the table above, we can say that:

• if X is TRUE, the result is TRUE, no matter what Y is.
• if X is FALSE, the result matches the value of Y.

We can transform this into code:

const OR = (X, Y) => X(TRUE, Y);

Let’s work this out, which is more involved! Suppose X represents TRUE. In that case, it will return the first argument it’s given (in this case, TRUE), so when X is TRUE, OR(X, Y) is also TRUE. On the other hand, if X is FALSE, it will return the second argument it’s given (here, Y), so in that case, OR(X, Y) will equal Y. Everything is according to our analysis of the table above.

The “and” operator

Let’s move on to the “AND” (&&) operator, so given x and y we can calculate x && y. The truth table for it is as follows.

In summary:

• if X is FALSE, the result is FALSE no matter what Y is.
• if X is TRUE, the result matches the value of Y.

This is transformed directly into code:

const AND = (X, Y) => X(Y, FALSE);

This analysis is very similar to what we did for OR. Without going into much detail, if X is TRUE, it will return the first argument it’s given (so, Y), and if X is FALSE, the AND will be FALSE; again, the working of this function matches our analysis.

Operators for circuit building

We’re on a roll! Let’s go for some other operators. In electronic circuit design, NOR and NAND logic gates are frequently used. (Why? This has to do with the concept of “universal operators”, but we won’t go into that here. NAND is also known as the “Sheffer stroke”, X↑Y, and NOR as the “Webb Operator”, X↓Y.)

The definitions are simple:

• X NOR Y is just the negation of X OR Y, so !(X || Y), equivalent to !X&&!Y.
• Similarly, X NAND Y is the negation of X AND Y, so !(X && Y) or, equivalently, !X||!Y.

const NOR  = (X, Y) => NOT(OR(X, Y));
const NAND = (X, Y) => NOT(AND(X, Y));

We won’t go into details; after all, the code fully matches the definitions we gave above, and it’s easy to verify they work correctly.

Other operators

So far, we’ve been able to transform several JavaScript operators into our functional style. What about some other operators that are less commonly used? The three we will see are:

• X XOR Y, exclusive OR (but not the bitwise ^ operator). This is written as X⊕Y or X⊻Y in boolean algebra.
• X EQU Y, equivalence, usually written as X↔Y or X≡Y
• X IMP Y, implication, written as X⊃Y or X⇒Y

The following table resumes the trio.

We can note:

• The results of X XOR Y and X EQU Y are always opposite.
• X XOR Y is equivalent to X !== Y or, equivalently, (X && !Y) || (!X && Y)… uglier!
• X EQU Y is equivalent to X === Y or (X && Y) || (!X && !Y)
• X IMP Y is always true unless X is TRUE and Y is FALSE, so !X || Y. (Check it out!)

const XOR = (X, Y) => X(NOT(Y), Y); 
const EQU = (X, Y) => X(Y, NOT(Y)); 
const IMP = (X, Y) => X(Y, TRUE); 

Can you see how these work? Going directly to the definitions is best. For instance, let’s see XOR: if X is TRUE, then the result will be NOT(Y), and if X is FALSE, the result will be Y, as we saw earlier. (I’ll leave the other two expressions to you.) The match between the boolean algebraic definitions and the actual JavaScript code gives us a lot of confidence in the validity of the results.

Writing conditional statements

We now have functional equivalents to boolean values, but what about using them? After all, the standard if and while JavaScript statements are not designed to work with our invented values. We will have to show that we can write our alternative implementations of both statements so we will be able to code anything we want to.

Writing our if statements

Now, what would an if look like? It would be a function (naturally! we only have functions!) with three parameters:

• booleanFn, a function that returns a boolean value
• thenFn, a function to be executed if the boolean value means “true”
• elseFn, a function to be executed if the boolean value means “false”

(Why are we providing functions? We don’t want anything to be evaluated unless it’s necessary. For example, if the boolean value is evaluated as TRUE, we will then evaluate thenFn() and ignore elseFn(); we will only evaluate what we really need.)

We would then write:

const ifThenElse = (booleanFn, thenFn, elseFn) =>
  booleanFn()(thenFn, elseFn)();

For example, let’s write a statement that will print out “AM” or “PM” depending on the time of the day. Let’s assume an isMorning() function that returns a TRUE boolean value in the morning and a FALSE one in the afternoon.

const printAM = () => console.log("It's AM");
const printPM = () => console.log("It's PM");

ifThenElse(isMorning, printAM, printPM);  // AM or PM as it may be

The isMorning() function would be written as follows. Keep in mind this is a very simple example; in reality, the evaluation could be much longer and more complex:

const isMorning = () =>
  new Date().getHours() < 12 ? TRUE : FALSE;

Why are we writing this using the ternary operator? The reason is that in a purely functional language, any test would return either TRUE or FALSE, our functions, but in JavaScript (which, after all, does have booleans!) we have to do the conversion ourselves.

Writing a while loop

We’re almost done; we managed to write basic TRUE and FALSE values, implemented several boolean operators, and also have an if alternative; we only need a while equivalent for looping, and we’ll have all the tools we could ever need.

This will be a tad trickier than the if code. In Functional Programming, instead of loops, we use recursion. The functional way of doing a while loop would be the following.

const whileLoop = (booleanFn, loopFn) =>
  booleanFn()(
    () => {
      loopFn();
      whileLoop(booleanFn, loopFn);
    },
    () => {}
  )();

Let’s start by describing the parameters of the whileLoop() function.

• booleanFn is, as in the if implementation, a function that will return a boolean value
• loopFn is a function that will be executed in every pass of the loop, as long as the evaluated boolean value is TRUE.

How does this work? If booleanFn() evaluates to TRUE, the first argument to the function will be evaluated — it will execute loopFn() and recursively call itself again. On the other hand, when booleanFn() evaluates to FALSE, a “no operation” function will be executed, and the loop will end; good!

Let’s finish with a short example showing a countdown loop.

let number = 5;
const checkPositive = () => MakeBool(number > 0);
const loopFn = () => console.log(number--);
whileLoop(checkPositive, loopFn); // 5 4 3 2 1 in that order

Can you follow how this works? The part that’s usually harder to understand is the usage of recursion to do the looping; after you wrap your head around that, the rest follows quickly.

Conclusion

We started this article by wondering what we would do if we had to code without having boolean values and operators, and also lacking basic flow statements like if and while. By applying Functional Programming ideas, first, we were able to produce our own TRUE and FALSE equivalents. We then added several operators to be able to build complex expressions, and we finally produced functional versions for if and while statements.

Initially, it seemed like we were getting into an impossible situation, but we solved all the issues. Of course, working with JavaScript, you wouldn’t do this — why would you? After all, booleans are an integral part of the language, so there’s no need to do all this rigmarole to get what you already have!

The true objective of the article was to help you widen your horizon and realize that Functional Programming goes even further than just letting you use functions in some ways; it allows you to elegantly express many concepts and operations, all with the same basic tools: impressive!

I cannot say it better: as it reads in an article by Alex Beal,

“In the end, this might strike you as nothing more than a useless programming trick. In a sense that’s right. I’d never use this in my own code. What makes this technique so valuable is that it actually fits into the broader context of lambda calculus […] In the language of lambda calculus, you’re given only a very basic set of tools. […] Incredibly, it turns out that that’s all you need.”

References

If you want to learn more about the techniques we used here, you should read about Church Encoding and Scott Encoding; for boolean values, both representations are the same.

In the mood for some questions?

If you want to experiment a bit more, try your hand with these questions.

1. Show that these OR versions are equivalent to the one we wrote.

const OR1  = (left, right) => left(left, right);
const OR2  = (left, right) => right(right, left);

2. Do the same for these alternatives to our AND.

const AND1 = (left, right) => left(right, left);
const AND2 = (left, right) => right(left, right);

3. Show that if X is a boolean value, X(Y,Z) is equivalent to (X && Y) || (!X && Z).

4. Using the previous result, prove that our NOT, OR, AND, etc., definitions are correct.

5. Show that our implementations of AND and OR also apply JavaScript’s “short circuit” evaluation rules.

6. Do the alternative versions for AND and OR from questions 1 and 2 also apply short circuit evaluation like JavaScript?

Understand every bug

Uncover frustrations, understand bugs and fix slowdowns like never before with OpenReplay — the open-source session replay tool for developers. Self-host it in minutes, and have complete control over your customer data. Check our GitHub repo and join the thousands of developers in our community.