Forever Functional: D.I.Y. Booleans?
Published: 2024-03-11 16:55:08

by [Federico kereki](https://blog.openreplay.com/authors/federico-kereki)


<blockquote><em>
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.
</em></blockquote>


<div style="background-color:#efefef; border-radius:8px; padding:10px; display:block;">
<hr/>
<h3><em>Session Replay for Developers</em></h3> 
<p><em>Uncover frustrations, understand bugs and fix slowdowns like never before with <strong><a href="https://github.com/openreplay/openreplay" target="_blank">OpenReplay</a></strong> — an open-source session replay suite for developers. It can be <strong>self-hosted</strong> in minutes, giving you complete control over your customer data.</em></p>
<img alt="OpenReplay" style="margin-top:5px; margin-bottom:5px;" width="768" height="400" src="https://raw.githubusercontent.com/openreplay/openreplay/main/static/openreplay-git-hero.svg" class="astro-UXNKDZ4E" loading="lazy" decoding="async">
<p><em>Happy debugging! <a href="https://openreplay.com" target="_blank">Try using OpenReplay today.</a></em><p>
<hr/>
</div>


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:

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

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

```javascript
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:

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

| X        | Y        | X OR Y   |
|:--------:|:--------:|:--------:|
| FALSE    | FALSE    | FALSE    |
| FALSE    | TRUE     | TRUE     |
| TRUE     | FALSE    | TRUE     |
| TRUE     | TRUE     | TRUE     |

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:

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

| X        | Y        | X AND Y  |
|:--------:|:--------:|:--------:|
| FALSE    | FALSE    | FALSE    |
| FALSE    | TRUE     | FALSE    |
| TRUE     | FALSE    | FALSE    |
| TRUE     | TRUE     | TRUE     |

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:

```javascript
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"](https://www.allaboutcircuits.com/textbook/digital/chpt-3/gate-universality/), but we won't go into that here. `NAND` is also known as the ["Sheffer stroke"](https://en.wikipedia.org/wiki/Sheffer_stroke), `X↑Y`, and `NOR` as the ["Webb Operator"](https://en.wikipedia.org/wiki/Logical_NOR), `X↓Y`.)

| X        | Y        | X NOR Y  | X NAND Y |
|:--------:|:--------:|:--------:|:--------:|
| FALSE    | FALSE    | TRUE     | TRUE     |
| FALSE    | TRUE     | FALSE    | TRUE     |
| TRUE     | FALSE    | FALSE    | TRUE     |
| TRUE     | TRUE     | FALSE    | FALSE    |

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

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

| X        | Y        | X XOR Y  | X EQU Y  | X IMP Y  |
|:--------:|:--------:|:--------:|:--------:|:--------:|
| FALSE    | FALSE    | FALSE    | TRUE     | TRUE     |
| FALSE    | TRUE     | TRUE     | FALSE    | TRUE     |
| TRUE     | FALSE    | TRUE     | FALSE    | FALSE    |
| TRUE     | TRUE     | FALSE    | TRUE     | TRUE     |

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!)


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


<CTA_Middle_Programming />



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

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

```javascript
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:

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

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

```javascript
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](http://www.usrsb.in/Building-Data-Structures-from-Functions.html),

> *"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](https://en.wikipedia.org/wiki/Church_encoding) and [Scott Encoding](https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_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.

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

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

```javascript
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"](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Logical_AND#short-circuit_evaluation) evaluation rules.

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