Mindshift: Part 5

Using Quantity Functions to Perform Basic Arithmetic

In Part 4 of my Mindshift series of blogs, 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 an incomplete set of parameters. 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 other value will not be known until runtime.

In the previous blog we saw how the partial functions increment and decrement can be created by passing only one parameter to the adder function.

Let’s extend this idea to the multiplication operation. When we talk about doubling a number, or tripling it, or quadrupling it, 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 multiplication operation.

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 transformation function “add one” 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.

Well, yes this works; but couldn’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. Such a function behaves like a regular quantity function in that it requires both a transform function and a start value as parameters, but it also requires the previous quantity function as a parameter.

Notice the code passed into the last occurrence of the transform function. This is simply the definition of a quantity function where the name of the quantity function is now the parameter qtyFn.

We then simply apply the transform function to whatever result is returned by the quantity function – thus generating a function that represents the current quantity function's successor.

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.

If you then happen to pass NINE the transformation function incr and a starting value of 0, then you will get back the counting number 9. But this is only one of many possible uses of a quantity function.

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.

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.

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.)

As yet however, we have no starting value.

Since we are performing repeated addition, we can use zero as the starting point:

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:

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.

Summary

So the objective of this blog has been to demonstrate the broad usefulness of function abstraction using the following sequence of steps:

  1. An abstract quantity function represents a specific type of computation - that computation being the iterative transformation of a starting value some number of times.
  2. 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.
  3. To start the counting process, we define a function ZERO that takes a starting value and applies a transformation function to it zero times.
  4. 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.
  5. The addition of two numbers a and b is then defined in terms of finding the b’th successor of a.
  6. Multiplication of two numbers a and b is then defined in terms of adding a to itself, b times.
  7. 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


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