The entire Mindshift blog series has moved to langram.org/mindshift-series.
Click here to read Mindshift: Part 11 on langram.org
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.
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
ONE (ignoring the use of the
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.
|Let’s hold the definition of
|Ok, the parameter names are different, but the functionality is identical! Both
|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.
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.
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
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.
Using the Boolean values of
FALSE, the normal Boolean operators of
XOR can be defined.
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.
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
MULTIPLY to our function definitions, but this is to account for our severely limited human ability to interpret long expressions. Really, names such as
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.
PAIR of values, and secondly how extracting the first or second item from such a
PAIR yields a definition of the Boolean values of
So now that we have these definitions under our belt, we can look at how subtraction is implemented.
In the same way that the addition of a and b is defined as the b’th successor of a, so subtracting b from a amounts to nothing more than finding the b’th predecessor of a.
So the task for this blog is to develop a predecessor function1 and then from that, develop a
First however, we must understand the constraints of our current counting system.
This does restrict the functionality of our
SUBTRACT function, but that’s not an issue here for two reasons:
So given that our implementation cannot actually count backwards, we will have to think of the predecessor of a number in a different way.
The way we do can this is to think of numbers as pairs such as
(n-1,n). Then, to derive the predecessor of a number, we start counting up from zero – but always keeping track of the numbers as pairs. This means that when we’ve finished counting up to
n (the second number in our pair), the required predecessor will be the first number of the pair.
In the previous blog, we saw how the
PAIR function operates, so now we need to apply that function to our situation.
What we need now is a function that creates not just the successor of a single quantity function, but creates the successors of a
PAIR of quantity functions. So what we need here is a
Here, we will implement the “shift and increment” principle. A new pair of numbers is constructed as follows:
Now let’s use this function to create the next two successor pairs to
PAIR(ZERO)(ZERO) – which we expect to be
Lastly, to find the predecessor of any particular number
n, we need to invoke the
n times on the
PAIR(ZERO)(ZERO), and the required predecessor will then be the first number of the resulting pair.
Do you remember how a quantity function works? A quantity function applies the transformation function to the starting value as many times as is represented by that quantity function.
Q: What’s our transformation function going to be?
Q: What’s our starting value going to be?
A: We will define our starting point for counting to be
This means that the predecessor of any particular quantity function can be obtained by a two-step process: first, pass
PAIR(ZERO)(ZERO) to the quantity function as the transformation function and starting value, and second, extract the first value from the resulting pair.
Phew! That was a lot of hard work just to create a predecessor function, but finally we’re in a position to define a
Since subtraction is non-commutative, we must stipulate that
SUBTRACT always takes the second quantity away from the first; but apart from that, we’re using exactly the same principle as has been used before. In other words, to subtract b from a, apply the
PRED function b times starting from a.
Now that we have the ability to perform any subtraction whose answer is greater than or equal to zero2, we can start to look at other arithmetic operations such as modulus and division; but, as always, there’s a catch – in fact there are two catches caused by the fact that both the modulus and division operators are implemented using repeated subtraction:
SUBTRACToperation until the divisor becomes bigger than the remainder – yet, we have no functions such as
IS_LTE(is less than or equal to).
SUBTRACTfunction will need to be called, it must called recursively.
Teeny weeny problem… Our ground rules state that all functions must be anonymous. Therefore, how can the function
SUBTRACT call itself without referring to it by name?
This is where something called the Y-Combinator comes in; but more of that later.
1) The definition of the predecessor function shown in this blog is not the only way this functionality could be implemented, but it is the simplest to understand. The following definition of the predecessor function is also widely used:
var PRED = n => f => x => n(g => h => h(g(f)))(y => x)(y => y);
Whilst this definition is equally valid, it is much harder to understand because it involves the use of nested wrapper functions – so we won’t look at this implementation here.
2) It might seem ridiculous to you that we have created a
SUBTRACT function that yields zero when asked what
5 - 8 is. But this is not so wacky as it might seem. For more information on this type of operation, look up Monus – but be warned – you’ll be venturing into the lands of Abstract Algebra and Group Theory. Here be dragons.