Pointer

From PEGWiki
Revision as of 19:43, 1 August 2012 by Brian (Talk | contribs) (Java, C#, Python, Ruby, etc.)

Jump to: navigation, search

This article is intended to provide an introduction to and critical analysis of the concept of a pointer. Despite the samples of code shown below for various languages, it is not intended to provide a reference on how to use pointers in specific languages.

A pointer is an object that contains information about the address of another object in memory (called the referent or the pointee) and which may be used to access that object. Accessing an object using a pointer to it rather than by referring to the object itself is known as indirection; using a pointer is said to add a level of indirection. When we use a particular pointer to access its referent, we say that we are dereferencing the pointer.

Definition

The usage of the term pointer among programmers does not quite mirror the general definition given above. Whether or not certain objects can be considered pointers is subject to dispute. We consider a few examples:

C

In C, a pointer is a first class object. A pointer may be used in any place where it is appropriate. Pointers may be assigned to each passed to functions, and returned from functions. They may be converted to other values, they may be printed on the screen, and they may be read from and written to files. To every C data type T there corresponds a pointer type T*, and this is true even of pointers themselves; a pointer may point to another pointer. The programming community is in consensus that these objects are considered true pointers.

The standard does not prescribe the nature of a pointer; however, C is, by design, close to the machine and efficient with computing time and memory, and, therefore, in essentially all implementations of C, a pointer is a raw memory address, that is, one that contains no more and no less information than is required in order to unambiguously specify the address of an object in primary storage (RAM/ROM) or virtual memory in a form that the CPU can use directly. Today, the vast majority of computing devices in existence operate in flat memory addressing; here, a pointer is simply an unsigned integer from 0 to N-1 (where N is the total size of available memory in bytes). The pointer that compares equal to the integer 0 is called the null pointer and is taken to mean a pointer that does not point to anything.

Pascal and its descendants have pointers that are similar to C pointers, but more limited (in that they cannot be operands to arithmetic operators, nor can they be read and written like numeric and character types).

Examples

int x = 123;
int* p = &x;
*p = 456;
printf("%d\n", x); /* This prints "456" */

Note that x is an integer and p is a pointer to integer. In line 2, p is made to point to x. Beyond this point, *p and x are semantically indistinguishable; using the asterisk operator on p is said to dereference the pointer, providing access to the referent. This remains the case until either x or p goes out of scope, or p is reassigned to point somewhere else.

#include <stdio.h>
void foo(int z)
{
    z = 456;
}
void bar(int* p)
{
    *p = 456;
}
int main(int argc, char** argv)
{
    int x = 123;
    foo(x);
    printf("%d\n", x); /* This prints "123" */
    bar(&x);
    printf("%d\n", x); /* This prints "456" */
    return 0;
}

This example shows how pointers may be used to pass by reference. If an integer variable is passed into a function, then a copy of the variable is made; any changes made to the parameter within the function will leave the variable in the caller unaffected. However, passing a pointer to x rather than x itself merely copies the address information of x, which, within the body of f, may still be used to refer to x itself.

Function pointers

Pointers to functions are also allowed. Unlike pointers to data types, these point to code, not data.

#include <stdio.h>
void f(int x)
{
    printf("%d\n", x);
}
int main()
{
    void (*p)(int) = &f;
    (*p)(123); // prints "123" 
    return 0;
}

The type void (*)(int) is a pointer to function of int returning void. When p is declared, it is made to point to the function f. Then, *p will refer to f. A function pointer is also a fully first-class data type. Pointers to function pointers are allowed, as are pointers to functions taking or returning function pointers; however, the syntax quickly becomes confusing.

(Note that for function pointers the use of & and * are optional; the syntax void (*p)(int) = f; is correct, as is p(123);)

C++

References

C++ inherits the "true" pointers found in C, but also has a type known as reference. The reference type corresponding to the type T is known as T&. Here is an example to parallel the above:

int x = 123;
int& r = x;
r = 456;
std::cout << x << std::endl; // This prints "456"

Here, the object r is a reference to x. It differs from a pointer to x in that it is implicitly dereferenced at all future usage; r is semantically indistinguishable from x after line 2. Furthermore, r can never be reassigned so that it refers to any variable other than x. Effectively, r is an alias for x.

It is worth noting that the similarity to the corresponding C code using pointers demonstrates that references really are pointers that simply hide the fact that they have any independent existence as raw memory addresses.

References are not by any means first class objects in C++. References to references, arrays of references, and pointers to references are not allowed.

When a reference type is on a function's parameter list, pass by reference occurs. The reference parameter will be initialized when the function call is made, but, once within the body of the function, it will be semantically indistinguishable from the object from which it was initialized, and will go out of scope when the function returns. Changes made to the reference parameter will change the actual argument passed in. Thus:

#include <iostream>
void bar(int& z)
{
    z = 456;
}
int main(int argc, char** argv)
{
    int x = 123;
    bar(x);
    std::cout << x << std::endl; // This prints "456"
    return 0;
}

On the other hand, if a variable of reference type is passed into a function, the effect will be the same as if the referent itself were passed into the function.

References may be returned from functions, too. For example, the function std::vector::operator[] returns a reference to the vector's value_type. This is done so that we may write a statement such as V[x] = y (where V is a map). Because the value returned is from the vector's internal memory, this assignment statement will change the contents of the vector. If operator[] returned simply value_type, rather than value_type&, then the return value would be a temporary copy of the value inside the vector, and it would not be an lvalue, so this assignment statement would not be valid, and, even if it were, it would have no hope of modifying the contents of the vector as desired.

C++ references are not referred to as pointers, because this would lead to confusion with the actual pointer type T*. The question of whether, in general, these objects should be considered pointers is more tricky. Yes, they contain address information about their referents, and yes, they may be used to access their referents in memory, but the fact that r and x are semantically indistinguishable after the initialization of r makes it logically dissatisfying to call r a pointer but not x. However, as everyone agrees on the statement, "C++ has pointers", this issue is not often discussed.

Pointers to member

C++ also has pointers to data member. The following example illustrates their usage:

#include <iostream>
struct A
{
    int x;
};
int main()
{
    A a; a.x = 123;
    int A::*p = &A::x;
    a.*p = 456;
    std::cout << a.x << std::endl; // this prints "456"
    return 0;
}

The type int A::* is a pointer to int member of A. It is used to point to some int field of the class (or struct) A (and not to an instance thereof). In line 9, we initialize this pointer so that it points to the member A::x. However, this pointer does not actually refer to anything by itself; it only refers to a field within A. In order to use this pointer, we must instantiate it by actually providing an instance of the struct A. The value a.*p points to a.x, since p refers to the field x of some A.

In some implementations of C++, the pointer p in this example actually contains the offset of the member A::x from the beginning of the corresponding instance of A in memory. In the example above, the numerical value of p is probably actually zero, since x is the first field of A. However, this is not a null pointer. In fact, it is not a fully qualified pointer at all. It may only be used in conjunction with an object of type A. Arguably, since it does not contain enough information to refer to any specific value in memory, it should not be considered a true pointer at all. Yet, in C++ terminology, it is still a type of pointer, whereas the reference type discussed in the previous section is not!

There are also pointers to member functions:

#include <iostream>
struct A
{
    int x;
    virtual void f()
    {
        x = 123;
    }
};
struct B : A
{
    void f()
    {
        x = 456;
    }
};
int main(int argc, char** argv)
{
    A a;
    B b;
    void (A::*p)() = &A::f;
    (a.*p)();
    (b.*p)();
    std::cout << a.x << std::endl; // this prints "123"
    std::cout << b.x << std::endl; // this prints "456"
    return 0;
}

These are more subtle than pointers to data members. The type void (A::*)() is a pointer to member function of A taking no arguments and returning void. However, just as a pointer to data member is not a complete pointer capable of referring to a specific memory location, a pointer to member function does not completely specify the address of the function it points to, because of the possibility of inheritance. In this example, because of polymorphism, the object b, which is of type B, is also a valid object of type A. The pointer p is required to be able to invoke the function f on any object of type A. And yet a.*p and b.*p are different functions (that is, functions at different memory addresses), because B::f overrides A::f! This means p cannot store a simple address. Instead, p probably points to the offset of the entry for f from the beginning of A's virtual method table; instantiating and invoking f then requires a lookup and a translation.

Iterators

As C++ supports operator overloading, it is possible to define a type of object that behaves like a pointer syntactically, but doesn't have type T*. For example:

#include <set>
#include <iostream>
int main(int argc, char** argv)
{
    std::set<int> S;
    S.insert(123);
    std::set<int>::iterator I = S.find(123);
    std::cout << *I << std::endl; // this prints "123"
    return 0;
}

In this code, the object I is called an iterator. The std::set<>::find function returns an iterator, which is like a pointer to one of the set's elements. After this initialization of I, the expression *I may be used to dereference the iterator. As it points to the element of value 123 found within the set, *I equals 123.

An iterator must, at the very least, define operator*, so that it may be dereferenced using the same syntax as an ordinary pointer.

It is arguable whether an iterator can be considered a pointer. Iterators do provide access to their referents, but they are not required to contain their referents' memory addresses; they just need to store enough information to unambiguously determine their referents' addresses. Iterators are usually implemented as classes containing a private pointer member to their referents, but this is not a requirement. On the other hand, C pointers are also not required to contain raw memory addresses, even though they usually do; this suggests that iterators ought to be considered pointers just as much as "true" C pointers. The fact that iterators in C++ are generally considered more general objects than pointers, however, suggests that the term pointer should perhaps be best understood in the context of individual languages.

Java, C#, Python, Ruby, etc.

There is some controversy over the question of whether Java has pointers. Here is an example to illustrate the source of this confusion:

class Foo {
        int bar;
        Foo(int x) {
                bar = x;
        }
        int getBar() {
                return bar;
        }
        void setBar(int x) {
                bar = x;
        }
}
 
public class Example {
        public static void main(String[] args) {
                Foo f = new Foo(123);
                Foo g = f;
                g.setBar(456);
                System.out.println(f.getBar()); // This prints "456"
        }
}

It is clear from this example that f and g are not value instances of the class Foo; if they were, then the statement g = f; would create a copy of f. Instead, f and g are like pointers with an anonymous referent constructed by the new invocation, so that after f is assigned to g, the two pointers will have the same referent. On the other hand, in semantics, f and g are more like C++ references; it would not make sense to use & and * operators because these Java pointers do not exist independently of their referents; only one or the other is exposed in the language proper. (Primitive types such as int cannot be referred to with pointers, and they cannot be passed by reference.)

When an object is passed into a function, it is as though a pointer to the object's data were passed into a C function. Hence, if a function takes a parameter Foo f, then assigning to f inside the function will simply rebind the name, and leave the original argument untouched; but any modification to f's members will be reflected in the original argument, as it entails the dereferencing of this pointer.

One can also argue about whether Java passes parameters by value or by reference. If we insist that Java passes all parameters by value, then we must accept that f and g have pointer nature, because if f is passed into a function, and the parameter that receives it is reassigned via the assignment operator, then f is unchanged, but if a method is called on the parameter that mutates a data member of Foo, then those changes will be reflected in f, which is just what we would expect if a C++ pointer were passed (and the method called with the -> operator). However, the lack of independent existence of pointers and their referents is taken by some to imply that Java cannot really said to possess pointers. Thus, there is considerable controversy over the question of whether Java has pointers.

The names f and g, at any rate, probably do not refer to fixed memory addresses; this stands in contrast to C, where pointers probably do refer to fixed memory addresses (but this is not required by the standard). This is because Java's automatic memory management is allowed to move values around in memory, and "pointers" must therefore be defined in a way that allows them to follow this movement.

Disk (and other) pointers

File systems that organize data on disks also use pointers to keep track of where on the disk files are located; however, these are typically specialized data structures handled by an operating system kernel, and do not appear in application programs or in mainstream programming languages. These disk pointers are usually referred to as such to distinguish them from pointers into primary storage and virtual memory, which are simply called pointers.

The term memory can, in general, refer not only to primary storage, disks, and virtual memory, but also to CPU registers, cache, and other machines (as in a network cluster). Nevertheless, the term pointer is very rarely used to describe objects that address these other forms of memory. For example, an IP address is not referred to as a pointer.