Mindshift: Part 8

Using Minimal Functions To Build Predicates And Boolean Operators

In the last exciting episode of the Mindshift blog, we looked at how subtraction can be performed when our counting system only allows us to count upwards from zero.

Now we need to expand our range of predicate functions to perform various equality or equivalence tests, and from these, then build up a wider range of functional tools.

There’s Nothing There, Or Is There?

It would be pretty handy if we could determine whether a quantity function is ZERO or not. To put that in fancier language, how can we tell whether or not a quantity function has zero magnitude?

Lets remind ourselves of the basic definition of ZERO and ONE (ignoring the use of the SUCC function)

// ZERO and ONE
var ZERO = transform => start_value => start_value;
var ONE  = transform => start_value => transform(start_value);

Notice how the transform function is used inside the ZERO function – it isn’t. It’s completely ignored; all that happens inside ZERO is that the second parameter (start_value) is returned unmodified.

Aside

Let’s hold the definition of ZERO up against the definition of another function we’ve seen already – FALSE.
// ZERO and FALSE
var ZERO  = transform => start_value => start_value;
var FALSE = true_part => false_part  => false_part;
Ok, the parameter names are different, but the functionality is identical! Both ZERO and FALSE brainlessly return their second parameter unmodified.
This now provides us with a (possibly unexpected) way to demonstrate that it is far more than simply computing convention to evaluate Boolean false to zero – they are in fact functionally indistinguishable.

The only circumstance under which a quantity function will ignore its transformation function is when its magnitude is zero, and any non-zero quantity function will always apply its transform function some number of times to the start value.

Therefore, we can get a quantity function to reveal its magnitude by passing it a transformation function that, if called, will always return FALSE. We can pass a starting value of TRUE knowing that this will be returned only when the quantity function has a magnitude of zero.

// Define an IS_ZERO function
var IS_ZERO = qtyFn => qtyFn(dont_care => FALSE)(TRUE);

// A function to reify the Boolean functions TRUE and FALSE
var to_boolean = fn => fn(true)(false);

IS_ZERO(ZERO);             // -> Boolean function TRUE
to_boolean(IS_ZERO(ZERO)); // -> JavaScript primitive 'true'

IS_ZERO(ONE);             // -> Boolean function FALSE
to_boolean(IS_ZERO(ONE)); // -> JavaScript primitive 'false'

So now that we can determine whether a quantity function has a magnitude of zero, we can now define the “less than or equal to” predicate.

Less Is More (Than a Negative Number)

You might recall from the previous blog that our counting system cannot handle negative numbers. This means that we will get odd results such as 5 - 8 = 0 instead of the expected -3.

Apart from limiting all our calculations to give positive answers, this is in fact a useful feature that allows us to check whether one number is greater than another number.

All we need to do is subtract one number from the other, then pass the result to our new IS_ZERO function. And there you have it, a definition for the “less than or equal to” predicate.

// Define an IS_ZERO function
var IS_ZERO = qtyFn => qtyFn(dont_care => FALSE)(TRUE);

// A function to reify the Boolean functions TRUE and FALSE
var to_boolean = fn => fn(true)(false);

// Define an IS_LTE function
var IS_LTE = val1 => val2 => IS_ZERO(SUBTRACT(val1)(val2));

IS_LTE(TWO)(FIVE);                // -> TRUE, 2 is <= to 5
to_boolean(IS_LTE(TWO)(FIVE));    // -> JavaScript primitive 'true'

IS_LTE(SEVEN)(THREE);             // -> FALSE, 7 is not <= to 3
to_boolean(IS_LTE(SEVEN)(THREE)); // -> JavaScript primitive 'false'

Boolean Operators

Using the Boolean values of TRUE and FALSE, the normal Boolean operators of NOT, AND, OR and XOR can be defined.

// Define Boolean the values TRUE and FALSE
var TRUE  = true_part => false_value => true_part;
var FALSE = true_part => false_part => false_part;

// Define the Boolean Operators
var AND = bool1 => bool2 => bool1(bool2)(FALSE);
var OR  = bool1 => bool2 => bool1(TRUE)(bool2);
var NOT = bool  => bool(FALSE)(TRUE);
var XOR = bool1 => bool2 => bool1(NOT(bool2))(bool2);

AND(FALSE)(FALSE);   // -> FALSE
AND(TRUE)(FALSE);    // -> FALSE
AND(FALSE)(TRUE);    // -> FALSE
AND(TRUE)(TRUE);     // -> TRUE

OR(FALSE)(FALSE);    // -> FALSE
OR(TRUE)(FALSE);     // -> TRUE
OR(FALSE)(TRUE);     // -> TRUE
OR(TRUE)(TRUE);      // -> TRUE

NOT(FALSE);          // -> TRUE
NOT(TRUE);           // -> FALSE

XOR(FALSE)(FALSE);   // -> FALSE
XOR(TRUE)(FALSE);    // -> TRUE
XOR(FALSE)(TRUE);    // -> TRUE
XOR(TRUE)(TRUE);     // -> FALSE

Now that we have a “not” and a “less than or equal” operator, it is quite straight forward to adapt this to create a “less than” operator.

// Define an IS_LT function
var IS_LT = val1 => val2 => NOT(IS_LTE(val2)(val1));

Now that we have these tools available to us, we can start to look at arithmetic operations such as division and modulus. What makes these operations harder to implement is not only that they need to perform a SUBTRACT operation an unknown number of times, they must also be defined recursively.

I know I’ve been cheating slightly by assigning names such as TRUE, ZERO and MULTIPLY to our function definitions, but this is to account for our severely limited human ability to interpret long expressions. Really, names such as ZERO and MULTIPLY behave as macros that are substituted at runtime for the functions they represent.

Here, we also run up against another problem. Any recursively defined function must be able to make reference to itself; but if we create a DIV function that refers to itself directly by name, then we have broken our rule that functions may not directly refer to themselves by name.

At first, you might think this arbitrary restriction requires us to perform some pointless mental gymnastics simply to overcome our own self-imposed hurdles. Whilst this might be true from one particular perspective, from the wider perspective of wanting understanding the nature of computation, overcoming this hurdle leads us to an understanding of one of the most important constructs in functional programming – the Y-combinator.

Chris W

Advertisements

One thought on “Mindshift: Part 8

Comments are closed.