Sunday, November 06, 2005

The void paradox and pointers

With our present view of universe, it is reasonable to theorize the existence of smallest form of particle, say quark. We cannot visualize infinite divisibility of matter. However, the theory of smallest particle implies separation, and therefore the existence of void. In other words, there are gaps in existence.

The problem with gaps is that they can grow to a point where no two particles are close enough to interact in any way. This is feasible even for an infinite supply of particles. Whatever the gaps may be, their lack is blackness, or dark energy.

Turning our attention to history, we notice that the concept of void has been instrumental in our scientific evolution. The Persian mathematician Kharazmi, (spelled Alkharazmi in Arabic) wrote the first book called Algebra. We increased our vocabulary with a few words from that book, including algebra and algorithm. Algorithm is just his name again as pronounced by Europeans. In this book he introduced our positional (decimal) number system by including the symbol 0 for nothing (zero).

Perhaps I should avoid the well-know history of mathematics after Cantor introduced the notion of Set. Suffice it to say that the entire mathematics is constructed from the empty set alone, that is the set that is itself void.

Notice how the symbol 0 allows us to differentiate between 11 and 101. Now compare that to “fun()” and “void fun(void)”. Anymore we recognize the former as a call, only. Basically, void is the type of object that cannot be constructed. In other words, the domain and range of the function “fun” are empty sets.

The notion of void pointer is quite different from the use of void in function prototypes. Let us first review our understanding of pointers. The first book of algebra also introduced the notions of equation and unknown. Khayyam extended these notions in two directions. He introduced quadratic and cubic equations, and followed that by solving a number of interesting systems of equations.

The notion of unknown has been the starting point for a variety of concepts in mathematics, generally known as “variable”. We only need one of these variations for our discussion.

In a statement like “Let n be an integer”, the n is a variable in the sense that it can be any one of the elements in the set of integers. We may rephrase this as follows “Let (the values of) n range over the set of integers”. With this in mind, let us turn to pointers.

Let p be a pointer to type integer. From this we understand that p can point to objects of type integer. That is, p ranges over a set of objects of type integer. This statement should make it clear that the abstract notion of pointer is equivalent to the notion of variable in mathematics.

So, why do we refer to a loop-counter as a variable? There are two reasons for this. First, a loop-counter is usually a familiar mathematical symbol like X. Second, in early imperative languages a symbol was a placeholder for a set of literals of a given type, not an object. This form of thinking is a reflection of mathematical mentality imposed on programming. That mentality would have confined programming to Formula Translation.

Note that equivalent and identical mean different things. The notion of pointer is equivalent, but not identical to the mathematical concept of variable.

A void pointer is a variable of second degree. It can become a pointer to any specific type, which is itself a variable that ranges over a set of objects of that type. As we know from logic, a language of second degree admits statements that cannot be derived. Equivalently, this eliminates any hope for correctness proof of programs involving void pointers.

I have a feeling that some people will never give up hope. In fact, Khayyam conjectured that cubic equations are unsolvable. About nine centuries later we were able to prove that it is actually fourth-degree equations that are unsolvable, thanks to Abel.

Labels: , , , ,