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
decrement can be created by passing only one parameter to the
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
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
b can be seen as calculating the
b’th successor of
Since addition is commutative, it makes no difference whether we calculate the
a’th successor of
b’th successor of
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
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
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
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
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 (
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
b is defined as finding the
b’th successor of
a, then the multiplication of
b can be defined as repeatedly finding the
b'th successor of zero,
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
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
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
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.
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
ZEROthat 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
SUCCthat, 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
bis then defined in terms of finding the
b’th successor of
- Multiplication of two numbers a and b is then defined in terms of adding
- Finally, raising
ato the power of
bis defined in terms of multiplying
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
b together amounts to finding the
b’th successor of
a, so subtracting
a requires finding the
b’th predecessor of
However, it turns out that before we can define a
PREDecessor function, we must first define the Boolean
FALSE functions – and we haven’t got on to Boolean functions yet...
This will be the subject of the next blog.
All source code from the Mindshift blog series can be found on GitHub