Preparing For Negative Numbers
So far in this blog series, our ability to count has been restricted to handling only positive integers. It goes without saying that our computational abilities are somewhat cramped by this restriction - so its time to look at extending our counting system to include negative integers.
In order to perform this extension, we must first have a clear understanding about how our current counting system works.
Recap - Understanding How We've Been Counting So Far
Our method of representing the counting numbers is based on defining the computations needed to derive those numbers by starting at zero.
The name I have been using for the functions that perform these computations is Abstract Quantity Functions. These are partial functions that apply some transformation function (supplied later) to a starting value (also supplied later) some predetermined number of times.
These functions are Abstract in the sense that they do not represent any specific value (such as the counting numbers); but instead, they represent the structure of the computation needed to derive a value.
And they are Quantity Functions in the sense that the quantity of times the transformation function is applied to the starting value is hard-coded with the function.
Hence, these abstract quantity functions can be applied to many different situations - not simply the generation of the counting numbers.
This is a key point to understand because we have been working with functions that separate the structure of a computation, from the specific details of performing some instance of that computation.
This is abstraction - functional style.
Starting From Nothing
ZERO describes a computation in which some transformation function is applied zero times to the starting value.
Similarly, the function
ONE describes a computation in which the transformation function is applied once to the starting value.
We could continue in this same vein and define a function
TWO as follows:
But as you can imagine, having to write functions in which you hard-code the required number of nested calls to
transform will rapidly become totally impractical.
However, using our definition of the computation for
ZERO, we can create a function that calculates the
SUCCessor of the previous quantity function.
The beauty of the
SUCCessor approach is that we do not need to hard-code some predetermined number of nested calls to the
SUCC does that for us.
Hence we can create any number quantity functions simply by generating the
Successor of the previous one. Hence:
But look closely at what is happening here:
Q: How many parameters does the
SUCCessor function require?
A: Three: A quantity function, a transform function and a start value
Q: How many parameters are we passing the
SUCCessor function at the time we generate
A: Only one: The preceding quantity function
Hmmm, so how is this working?
The point is that
SUCC generates a partial function in which the preceding quantity function is known, but the transformation function and the starting value are not yet known.
Therefore, the functions
THREE etc. represent only the structure of the computations in which some (as yet undefined) transformation function will be applied to some (as yet undefined) starting value.
Are These Functions Abstract Or Real?
What makes these quantity functions so versatile is that because they represent only the structure of a computation, they can be used in one of two ways:
- If you supply them with other abstract quantity functions, they will generate the structure of some other computation
- If you supply them with reification functions, they will generate some concrete value such as an integer or a string
It all depends on what you want to do.
When working with abstract functions such as these, ask yourself the following questions:
Q1: Do I want to build a function that represents the structure of some computation?
A1: Yes? Then I can build the structure of this computation using other abstract functions as parameters.
Q2: Or do I want to build a function that reifies an abstract function?
A2: Yes? Then I should pass the abstract function both a suitable transformation function and a suitable starting value. The generated result will then be a native data type.
How Big Is A Quantity Function?
Often it is useful to know exactly how many times a quantity function will apply its transformation function to the starting value.
The simplest way to discover this is to pass the quantity function a starting value of integer
0 and a transformation function that increments that value once for each invocation.
But isn't that how we generate the counting numbers?
But since we're looking at the counting numbers through the lens of abstract quantity functions, it would be more helpful for us to think of the reified counting number as a side-effect, or consequence of the quantity function's magnitude.
So now we can create simple a function called
magnitude that takes an abstract quantity function as its only parameter, and returns that function's magnitude. In other words, it returns an integer showing how many times the transformation function is called.
So How Would We Represent A Negative Number?
Since we already have a perfectly good (albeit abstract) mechanism for representing the counting integers, all we lack is the ability to store a plus or minus sign along with that quantity.
So, if we have a quick rummage around in our existing toolbox of functions, we'll find we already have the parts needed to build a solution.
We can represent the plus or minus sign with a Boolean
FALSE, and then we can create a
PAIR from an abstract Boolean and an abstract quantity function.
In other words, we can use the
PAIR function to join together a
sign and a
magnitude, thus forming a signed integer.
So positive and negative numbers can be created like this:
So now we can find out whether a number is positive or negative by creating two functions,
IS_POS. (These functions could just as easily be called something like
In keeping with our naming convention, function
IS_POS in uppercase letters will return an abstract Boolean function.
We will also need to create a
to_boolean function to reify our abstract
If we can test the sign that easily, we can also easily test for the
NUMBER's magnitude. Here we could apply our
magnitude function to the quantity function returned by passing the
TAIL. However, it would be better if we were a little more rigorous about our terminology.
The value of a number without its sign is more correctly referred to as its absolute value; so we'll create some functions called
ABS as per our naming convention.
Teeny Weeny Problem... Zero
So we now have a means for representing signed integers as abstract functions. In addition to this, we also have a means for testing the sign and obtaining the absolute value of such a signed integer.
But what about zero?
Strictly speaking, zero is neither positive nor negative. It sits at the centre of the number line and joins the positive and negative halves together - without being a member of either half!
In our little scheme of representing signed integers, we have represented the sign as a binary value; but strictly speaking, we should use a ternary value storing
n/a. However, since no such thing exists down in abstract function land, we must content ourselves with the arbitrary (and mathematically wrong) decision to give zero a positive sign value.
So if we create
ZERO, we will need to form a
PAIR from the abstract Boolean function
TRUE and some representation of zero.
But we can't use the previous definition of
ZERO because that's what we're redefining here. What we need is a representation of the absolute value zero, rather than the signed value.
For this, we will therefore rename our old, unsigned definition of
ZERO to be
So whilst this is rather arbitrary, it will serve as a workable representation of
However, we should now realise the consequences of what we've just done. By changing the definition of
ZERO from unsigned to signed, we've just broken or
So in the next blog, we'll look at how the
PREDecessor functions need to change in order to handle signed integers instead of unsigned integers.
All source code from the Mindshift blog series can be found on GitHub