Mindshift Blog: Part 5 Republished on Feb 1st, 2018 Previous Blog Next Blog In Part 4, we examined how quantity functions can be used to generate, among other things, the counting numbers; but in doing so, we needed to make use of partial functions. Now we are going to look at an example of function abstraction by seeing how arithmetic can be performed using only these functions; but before we do that, it would be good to have a quick review of how partial functions work because this concept will become a powerful tool in your functional programming arsenal. A Quick Recap of Partial Functions In simple terms, a partial function is a function that has received an incomplete set of parameter values. In other words, at the time a partial function is created, we know some, but not all of the values required to perform the operation – hence the identifier “partial“. This is actually a very powerful programming concept because we can use partial functions to perform operations where, for instance, one value is known at design time, but the remaining values will not be known until runtime. We have seen how the partial functions increment and decrement can be created by passing only one parameter to the generic adder function. Let’s extend this idea to the multiplication operation. When we talk about doubling, tripling, or quadrupling a number, we are really talking about special cases of the multiply operation in which one of the operands is known to be 2, or 3, or 4. So the functions that double, triple or quadruple a number can be defined as incomplete definitions of a general multiplication operation.
// Create a adder function adder = value1 => value2 => value2 + value1
// Using the adder function, create an incr function incr = adder(1)
// Create a multiplier function multiplier = p => q => q * p
The multiplier function can now be used to create partial functions that double, triple and quadruple their subsequent operand
double = multiplier(2) // -> double = q => q * 2
triple = multiplier(3) // -> triple = q => q * 3
quadruple = multiplier(4) // -> quadruple = q => q * 4
double(21)
triple(9)
quadruple(18)
From now on, partial functions will form the fundamental building blocks of almost everything that we will build. Improving Our Ability To Count In the previous blog, we saw that numerical quantities such as the counting numbers can be generated by repeatedly applying the “add one” transformation function to a starting value of zero. That’s fine, but it won’t take long before we end up with some pretty large function definitions. Using the above definition, we can see that even the definition of a small number such as 15 becomes pretty awkward.
// Now this is getting silly (but then, this is JavaScript) FIFTEEN = transform => start_value => transform( transform( transform( transform( transform( transform( transform( transform( transform( transform( transform( transform( transform( transform( transform(start_value)))))))))))))))
FIFTEEN(incr)(0)
Well, yes this works - but its a pretty dumb way of doing things. Can’t we make life a little easier for ourselves? Yes, we certainly can. Instead of hard-coding the required number of nested calls to the transform function, we can abstract this operation and create a successor function. The successor function behaves like a regular quantity function in that it requires both a transform function and a start value as parameters, but in addition, it also requires the previous quantity function as a parameter.
ZERO = transform => start_value => start_value
SUCC = qtyFn => transform => start_value => transform(qtyFn(transform)(start_value))
This code requires some explanation. Notice what value is being passed to transform function. This is simply the definition of a quantity function where the name of the quantity function is now the parameter qtyFn. So all we are doing is taking the generic code for a quantity function (the qtyFn(transform)(start_value) part) and applying the transform to again. This then generates a function that represents the current quantity function's successor. So now we can use our SUCCessor function to generate the same quantity functions as before.
ONE = SUCC(ZERO)
TWO = SUCC(ONE)
THREE = SUCC(TWO)
FOUR = SUCC(THREE)
FIVE = SUCC(FOUR)
SIX = SUCC(FIVE)
SEVEN = SUCC(SIX)
EIGHT = SUCC(SEVEN)
NINE = SUCC(EIGHT)
TEN = SUCC(NINE)
So the function ONE is created by finding the successor of ZERO. Likewise, the function SEVEN is the successor of SIX, which is the successor of FIVE, which is the successor of...yeah, you get the picture. It’s very important to keep in mind what the SUCC function actually does. It does nothing more than generate another quantity function – and a quantity function is merely the abstract representation of the application of some transformation function to some starting value. The point here is that when you ask for the successor of EIGHT, you do not get back a function that represents the counting number 9; instead you get back a quantity function that will apply a given transformation function to some starting value nine times. In order to get back the counting number 9, you must pass NINE the specific transformation function incr and a specific starting value of 0. Only then will get back 9. As you can see, generating the counting numbers is only one of many possible uses of a quantity function.
Depending on the task you wish to perform, our quantity functions can be passed any suitable transformation function and starting value
// Incrememt 0 seven times SEVEN(incr)(0)
// Double 1 seven times SEVEN(double)(1)
// Triple 1 seven times SEVEN(triple)(1)
But I’m jumping ahead of myself here… Making it Real So how do we turn a function that represents the abstract concept of four-ness or twentythree-ness into a real counting number? As it turns out, in English there is a special verb that means specifically “To make an abstract idea or concept real or concrete”. That verb is “To Reify“. So, we are going to need some functions that reify our abstract quantity functions. For the sake of simplicity, we will create two functions that return an integer and a string respectively. For this, we'll first need some helper functions, then we can create a to_integer and to_string function.
// Concatenate any character to a string str_concatenate = char => acc => acc.concat(char)
// Add a plus character to a string asPlusChar = str_concatenate('+')
// Reify an abstract quantity function as an integer to_integer = qtyFn => qtyFn(incr)(0)
// Reify an abstract quantity function as a string to_string = qtyFn => qtyFn(asPlusChar)('')
to_integer(SEVEN)
to_integer(SUCC(TWO))
to_string(FIVE)
to_string(SUCC(EIGHT))
Now Its Starting To Add Up Think about what happens when you add two number together. Let’s say we want to add together the numbers 2 and 3. What we are effectively doing here is asking the following question: What quantity is the second successor of three? Or more generally, the addition of any two numbers a and b can be seen as calculating the b’th successor of a. Since addition is commutative, it makes no difference whether we calculate the a’th successor of b or the b’th successor of a. We already have a function that can determine the successor of any other quantity function, so we can start to piece together the internal structure of an ADD function. It will need to receive two quantity functions as parameters, then internally use the SUCC function as the transformation function, and one of the quantity function parameters as the starting value. Now we can define an ADD function. Here we apply the SUCC function to qtyFn2, as many times as are determined by the magnitude of qtyFn1.
ADD = qtyFn1 => qtyFn2 => qtyFn1(SUCC)(qtyFn2)
to_integer(ADD(TWO)(THREE))
to_integer(ADD(NINE)(EIGHT))
So can you now see that a quantity function can be passed any transformation function you like? Abstraction – Functional Style Notice how our ADD function does not work. At no time in this implementation do we require the use of real numbers. We are working entirely with abstract quantity functions. So its really important to understand exactly what an abstract quantity function represents. An abstract quantity function represents the structure of a computation,not the value created by performing that computation So the abstract quantity functions THREE or FOUR or FIVE represent the computation of three-ness or four-ness or five-ness. Exactly what values these functions output at runtime is entirely down to what parameters they are passed. So for instance, if we pass the abstract quantity function THREE the transformation function incr and a starting value of 0, then it will apply incr to 0 three times, resulting in the counting number 3. Equally well, we can pass THREE the transformation function decr and a starting value of 5, then it will apply decr to 5 three times, resulting in the counting number 2. OK, that's clear enough. But the step you must now take is to understand that an abstract quantity function can operate just as easily on other abstract quantity functions. So now we can say for example, that if we use the abstract quantity function representing "three-ness" (THREE) to apply the ADD function to the abstract quantity function representing "four-ness" (FOUR), we will get back the abstract quantity function representing seven-ness (SEVEN). Its only when we plug in the specific transformation function incr and the start value of 0 that we actually generate a tangible counting number. This is abstraction - functional style. It is first where we create an abstract representation of a computation, and second, where we discover that we can manipulate these abstract computations just as easily as manipulating the tangible values these computations represent. In fact, this is the whole of focus of a branch of mathematics called the Lambda Calculus - but now I'm really jumping ahead of myself... The bottom line here is that understanding function abstraction is a foundational concept in functional programming. Here, we will use it as the foundation upon which to build all the basic arithmetic operators. Multiplying Our Success Now that we have a function that can perform abstract addition, it is a small step to create a function that performs multiplication. If the addition of a and b is defined as finding the b’th successor of a, then the multiplication of a and b can be defined as repeatedly finding the b'th successor of zero, a times. Let’s build up a MULTIPLY function by combining the functions we already have such that they give us the required answer. First, create a partial function from ADD and one of the quantity functions. This will act as our transformation function for the other quantity function. (Since multiplication is commutative, it doesn’t matter which quantity function is passed to ADD to form the partial function.) Create a partial function using ADD and one of the parameters. In this example, we will multiply THREE by FOUR, so our partial function will look like this:
// Our transformation function ADD(THREE)
// ADD(THREE) is now applied FOUR times to...? FOUR(ADD(THREE))
As yet however, we have no starting value. Since we are performing repeated addition, we can use zero as the starting point:
// Add THREE to ZERO, FOUR times FOUR(ADD(THREE))(ZERO)
to_integer(FOUR(ADD(THREE))(ZERO))
All that now remains is to generalise this into a MULTIPLY function. Remove the instances of THREE and FOUR and replace them with parameters representing quantity functions:
MULTIPLY = qtyFn1 => qtyFn2 => qtyFn1(ADD(qtyFn2))(ZERO)
// Three times four to_integer(MULTIPLY(THREE)(FOUR))
// And just to prove that multiplication is commutative to_integer(MULTIPLY(FOUR)(THREE))
Now We’re Getting Powerful In the same way that multiplication is repeated addition, so raising one number to the power of another number is repeated multiplication. When we derived the MULTIPLY function, we first created a transformation function from ADD and one of the quantity functions, and then started the whole “repeated addition” process from ZERO. In order to create a function that performs exponentiation, we will follow exactly the same pattern, but instead of deriving the transformation function from ADD, we will use MULTIPLY. Also, since we’re performing repeated multiplication instead of addition, we must start from ONE rather than ZERO (because zero times anything is still zero...) One important difference here is that exponentiation is not a commutative operation – 3 to the power of 4 is not the same as 4 to the power of 3. Therefore, it is important to state that the first parameter is always raised to the power of the second parameter.
// Create a POWER function POWER = qtyFn1 => qtyFn2 => qtyFn2(MULTIPLY(qtyFn1))(ONE)
// Three raised to the power of four to_integer(POWER(THREE)(FOUR))
// Exponentiation is not commutative to_integer(POWER(FOUR)(THREE))
Summary So the objective of this blog has been to demonstrate the broad usefulness of function abstraction using the following sequence of steps: An abstract quantity function represents a specific type of computation - that computation being the iterative transformation of a starting value some number of times. The counting numbers are a set quantities related to each other by the repeated application of the transformation “add one” to the starting value of zero. To start the counting process, we define a function ZERO that takes a starting value and applies a transformation function to it zero times. In order to be able to count, we define a successor function SUCC that, given both a quantity function and a transformation function, will apply the transformation function to the quantity function. The return value is another quantity function. The addition of two numbers a and b is then defined in terms of finding the b’th successor of a. Multiplication of two numbers a and b is then defined in terms of adding a to itself, b times. Finally, raising a to the power of b is defined in terms of multiplying a by itself, b times. PS, Why No Subtraction? You might have noticed that we have not yet covered the topic of subtraction. This is because given our definition of the counting numbers and the way the SUCCessor function works, its actually quite tricky to count backwards... Tricky, but not impossible. In the same way that adding two numbers a and b together amounts to finding the b’th successor of a, so subtracting b from a requires finding the b’th predecessor of a. However, it turns out that before we can define a PREDecessor function, we must first define the Boolean TRUE and FALSE functions – and we haven’t got on to Boolean functions yet... This will be the subject of the next blog. Chris W
lib = { // ******************************************************************** // Generic operations // ******************************************************************** var adder = val1 => val2 => val2 + val1; // The increment and decrement functions can now be created var incr = adder(1); var decr = adder(-1); return { incr : adder(1), decr : adder(-1) } }