Mindshift: Part 16

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

The function 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 transform function. 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 ONE or TWO etc?
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 ONE, TWO, and 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?

Yes.

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:

  1. If you supply them with other abstract quantity functions, they will generate the structure of some other computation
  2. 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.

For instance:

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?

Exactly!

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 TRUE or 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 and IS_POS. (These functions could just as easily be called something like SIGN).

In keeping with our naming convention, function is_pos in lowercase letters will return a native JavaScript data type, and 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 TRUE and FALSE functions.

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 NUMBER to 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 and 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 yes, no and 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 ZERO_MAGNITUDE.

So whilst this is rather arbitrary, it will serve as a workable representation of ZERO.

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 SUCCessor and PREDecessor functions.

Boo hoo!

So in the next blog, we'll look at how the SUCCessor and PREDecessor functions need to change in order to handle signed integers instead of unsigned integers.

Chris W


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