Mindshift: Part 6 Republished on Feb 1st, 2018 Previous Blog Next Blog Boolean Values and Pairs In the previous blog, we saw how to perform basic arithmetic using nothing more than abstract quantity functions. The previous blog showed how by starting from the abstract quantity function for ZERO and then repeatedly applying a 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: A pair of values? 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 decides whether to give back the first or second value:
// An abstract function that stores a PAIR of values (val1 & val2), together with some function (fn) that // decides whether the first or second value should be returned PAIR = val1 => val2 => fn => fn(val1)(val2)
This PAIR function is structured in such a way that pass it only the values of the pair, and leave the function parameter undefined until such time as you want to retrieve a value. This means that your PAIR function will remain a partial function until such time as you pass it a function that can decide which of the two values shoudl be returned. 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 CAR and CDR (LISP uses these instruction names...) 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).
// The HEAD function arbitrarily returns the first item in a pair HEAD = val1 => val2 => val1
// The TAIL function arbitrarily returns the second item in a pair TAIL = val1 => val2 => val2
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 partial function in which we will store the names of two colours. We can then extract the first or second items by passing the colour pair partial function either HEAD or TAIL as a parameter. In doing so, we will extract either the first or second item of the PAIR.
colours = PAIR("sky_blue_pink")("cherry_green")
colours(HEAD)
colours(TAIL)
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 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 an imperative language (E.G. JavaScript). Using this as our starting point, we can work our way towards an abstract function definition.
colour = "sky_blue_pink"
// Start with an imperative example { if (colour === "sky_blue_pink") { return "Pigs fly" } else { return "Elephants jump" } }
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:
{ // Hide the condition inside a predicate function var is_sbp = colour => colour === "sky_blue_pink" if (is_sbp("sky_blue_pink")) return "Pigs fly" else return "Elephants jump" }
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 evaluated if the predicate is true, and the second if the predicate is false (see footnote 2).
{ // Hide the condition inside a predicate function var is_sbp = colour => colour === "sky_blue_pink" // Use the JavaScript ternary operator return is_sbp("sky_blue_pink") ? "Pigs fly" : "Elephants jump" }
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 hard coding the predicate to each of its two possible return values.
// If the predicate evaluates to true true ? "Pigs fly" : "Elephants jump"
// If the predicate evaluates to false false ? "Pigs fly" : "Elephants jump"
So the behaviour here is really simple: when the predicate evaluates to true, the first expression is evaluated, and when the predicate evaluates to false, the second expression is evaluated. But hang on a minute, haven’t we just looked at some coding that does exactly the same thing to a pair of values? Yes! The coding that evaluates a predicate and then decides which of two expressions to evaluate 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 Instead of returning the JavaScript primitives true and false, our predicate function is_sbp will now return the abstract functions HEAD and TAIL The two possible responses ("Pigs fly" and "Elephants jump") are now stored in a PAIR partial function
{ // Rewrite the is_sbp predicate function to return HEAD and TAIL var is_sbp = colour => (colour === "sky_blue_pink") ? HEAD : TAIL // Store the responses to the colour test as a PAIR var colourResponses = PAIR("Pigs fly")("Elephants jump") return colourResponses(is_sbp("sky_blue_pink")) }
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.
// Rename the HEAD and TAIL functions to TRUE and FALSE and give the // parameters some user-friendly names. So // var HEAD = val1 => val2 => val1; // var TAIL = val1 => val2 => val2; // becomes: TRUE = true_part => false_part => true_part
FALSE = true_part => false_part => false_part
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.
{ // Rewrite the is_sbp predicate function to return HEAD and TAIL var is_sbp = colour => (colour === "sky_blue_pink") ? TRUE : FALSE // Store the responses to the colour test as a PAIR var colourResponses = PAIR("Pigs fly")("Elephants jump") return colourResponses(is_sbp("sky_blue_pink")) }
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: 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 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.
{ // The colour test function returns TRUE or FALSE var is_sbp = colour => (colour === "sky_blue_pink") ? TRUE : FALSE // Store the responses to the colour test as a PAIR var colourResponses = PAIR("Pigs fly")("Elephants jump") // Modify HEAD and TAIL to receive a PAIR var HEAD = pair => pair(TRUE) var TAIL = pair => pair(FALSE) // Now HEAD and TAIL can be used in a more intuitive manner return HEAD(colourResponses) }
Chris W Footnotes 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. 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 evaluation languages 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 the JavaScript runtime 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.