Mindshift: Part 6

Boolean Values and Pairs

If you’ve been following my series of Mindshift blogs, then I trust that I have been able to communicate how we can perform basic arithmetic using nothing more than abstract quantity functions.

The previous blog showed how by starting from an abstract quantity function for ZERO and then applying a SUCC successor function, we can perform a variety of simple arithmetic operations.

However, we were only able to implement those arithmetic operations that make use of repeated addition. Consequently, we were limited to performing addition, multiplication and exponentiation. There was no mention of how subtraction could be performed.

So let’s fill in this gap in our capability; but in order to do so, we must first understand two apparently unrelated topics. How can we use abstract functions to represent:

  1. A pair of values
  2. A predicate

Pear, Pare, Pair…

So first of all, we need a way of representing a pair of values. (Why this is so will become clearer in the later blogs).

To create a PAIR, we will create a function that takes three parameters. The first two parameters represent the two values from which the pair is formed, and the third parameter is a function that performs some operation on the values in the pair: for instance, giving back either the first or second value:

This abstract function is structured such that you start by passing it only two of the three required parameters.

Remember the discussion about partial functions? A partial function is a function that knows how to perform only part of an operation. In this case, we have built a partial function that knows the value of two parameters (the values forming our pair), but has no idea which function those two parameters should be passed to.

The trick to getting either the first or second value out of the pair is to pass the PAIR partial function a function that returns either the first or second parameter.

So now we need to define a pair of functions that will extract either the first or last item from the pair. Here we could choose from quite a few different name pairs: we could call these functions:

  • FIRST and LAST, or
  • FIRST and SECOND, or
  • LEFT and RIGHT, or
  • HEAD and TAIL, or
  • CHARLIE and BILL (uh, no…forget that last suggestion).

Here, I’ll use the names HEAD and TAIL because these will be more generally useful for topics that are coming in the future (such as lists).

As you can see, the HEAD and TAIL functions are pretty dumb. They both take two parameters (val1 and val2) and without performing any “processing”, brainlessly return either the first or second parameter.

Let’s create an example of a PAIR in which we will store the names of two colours. We can then extract the first and second items by passing the colour partial function either HEAD or TAIL as a parameter. In doing so, we will extract either the first or second item of the PAIR.

Whilst it might be a little strange to have to write colours(HEAD) instead of HEAD(colours), at least we have a mechanism for extracting the first and second values from the pair. At the end of this blog, we’ll correct this slightly non-intuitive usage of HEAD and TAIL.

Now for predicates…

Predicates

In technical terminology, any function that evaluates to either true or false is said to be a “predicate”.

Restating that in non-technical terminology, a predicate is the “is” operator. So for instance, the statement “Chris is typing” is a predicate because it is either true or false.

In computer programming, predicates are used to create a two-way branches in program logic. So the question is this “How can we create a predicate using only a minimal function?”.

Let’s take a typical condition as implemented in a familiar imperative language such as JavaScript. Using this as our starting point, we can work our way towards an abstract function definition.

OK, that’s simple enough…

Now let's start to abstract this coding. The first thing to replace is the specific details of the condition. The details of how the test is performed can be hidden away inside a predicate function:

Fine, that’s not too demanding. But let’s really start to strip things back to the bare minimum.

Strictly speaking, the if and else keywords are simply syntactic markers that indicate firstly the presence of a two-way branch in the program logic, and secondly what statements each branch should contain.

In the minimal world of abstract functions, we can certainly live without the else keyword, and possibly even the if keyword (see footnote 1).

JavaScript offers us an if/then/else construct that does not require the use of either the if or else keywords. This is called the ternary operator and it is structured as follows:

<predicate> ? <true_expression> : <false_expression>;  

A predicate is immediately followed by two expressions: the first to be returned if the predicate evaluates to true, and the second if the predicate evaluates to false (see footnote 2).

Since we know that the function is_sbp is a predicate (meaning it can only return true or false), we can examine both paths the logic could take by replacing the predicate with its two possible return values.

So the behaviour here is really simple: when the predicate evaluates to true, the first expression is returned, and when the predicate evaluates to false, the second expression is returned.

But hang on a minute, haven’t we just looked at some coding that does exactly the same thing to a pair of values?

The coding that evaluates a predicate and then decides what value to return uses exactly the same logic as the coding to extract the first or second item from a PAIR.

So let’s make two changes to the is_sbp predicate function

  1. Instead of returning the JavaScript primitives true and false, our predicate function is_sbp will now return the abstract functions HEAD and TAIL
  2. The two possible responses (pigs.fly and elephants.jump) are now stored in a PAIR partial function

So Where Are All the Booleans?

From the coding above, we can see that extracting the first item from a list is functionally identical to when the predicate of the ternary operator evaluates to true. Similarly, extracting the second item from a list is functionally identical to when the predicate of the ternary operator evaluates to false.

If fact, we could argue that when applied to a PAIR function, the HEAD and TAIL functions are nothing more than synonyms for TRUE and FALSE. So if we rename HEAD and TAIL to TRUE and FALSE, the coding behaves exactly the same way.

In the following code, we’ll also rename the parameters passed to TRUE and FALSE in order to make their usage clearer; but other than changing some names, the functionality is identical.

So where the function is_sbp previously returned HEAD and TAIL, we’ll change it so that it now returns the abstract functions TRUE or FALSE. But other than fiddling around with the function names, the functionality remains completely unchanged.

If you’ve followed the reasoning so far, then I trust you should see that when represented as abstract functions, TRUE and FALSE are simply the HEAD and TAIL functions in disguise.

Summary

The key learning points from this blogs are:

  1. The PAIR abstract function is a vital building block for creating more complex data structures – that we’ll look at in the next few blogs
  2. When represented as abstract functions, the Boolean values of TRUE and FALSE are functionally indistinguishable from the HEAD and TAIL functions

Oh, and by the way…

Now that we have the TRUE and FALSE functions, we will use those as the primary means for extracting the first or second item from a PAIR.

We are now free to rewrite the HEAD and TAIL functions to make their usage more intuitive.

Chris W


All source code from the Mindshift blog series can be found on GitHub


Footnotes

  1. If you find yourself perplexed or confused by the idea that a programming language does not require the if keyword, then you should consider learning Erlang.

    The if keyword does exist in Erlang, but its really just syntactic sugar and if you use Erlang correctly, will hardly need to use it. This is because conditions in Erlang are typically implemented implicitly by means of function signatures, rather than explicitly by means of a keyword.

  2. A word of caution about implementing the concepts of functional programming in a language that performs strict evaluation (such as JavaScript or Ruby).

    When creating an if/then/else construct using JavaScript arrow functions, you must ensure that only one branch of the condition is evaluated.

The problem with strict languages such as JavaScript is that they always evaluate expressions as soon as they are encountered. So when writing a condition using these abstract functions, you must avoid creating the nonsensical situation in which JavaScript tries to evaluate both the true and false branches of a condition!

This is particularly important when implementing recursion. See the difference between the Y-Combinator and the Z-Combinator.