Pointers

For any type t, the type t* is the type of pointers to values of type t. A value of this type is either the address of a location in memory which stores a value of type t, or a special value NULL. The memory holding values of type t must be explicitly allocated using the expression alloc(t) which returns an address of a memory holding a value of type t, initialized to the default value of type t. Pointers are therefore very similar to arrays, except that they always refer to just a single value instead of a whole array of values.

We dereference a pointer of type t* to obtain a value of type t using the expression *e. This operation requires that e not evaluate to NULL; any attempt to dereference NULL will cause the program to abort and issues an error message. Similarly, we can write to the location where the value is stored by using *p on the left-hand side of an assignment, where p is a pointer. For example:

% coin 
Coin 0.2.6 "Penny" (r2087, Fri May 27 12:10:21 EDT 2011)
Type `#help' for help or `#quit' to exit.
--> int* p = alloc(int);
p is 0xEFE14FF0 (int*)
--> *p;    
0 (int)
--> *p = 3;
*p is 3 (int)
--> *p;
3 (int)
--> 

Trying to dereference the null pointer is analogous to an attempt to access an array out of bounds. Your pre- and post-conditions, loop invariants, and assertions should always imply that e cannot have value NULL. NULL is also the default value of type t*, so it can arise implicitly. Let's so what it looks like to incorrectly attempt to dereference the null pointer in coin.

--> int* q;  
--> q = NULL;
q is NULL (pointer of unknown type)
--> *q = 3;
Error: null pointer was accessed
Last position: <stdio>:1.1-1.7
--> *q;
Error: null pointer was accessed
Last position: <stdio>:1.1-1.3
--> 

We first declare new variable q which is a pointer to an integer, then we initialize it to NULL instead of allocating space. Then we cannot store an integer at the memory location denoted by q because it is NULL and not a proper address. We can also not read from the location for the same reason. But we can allocate and assign the resulting address to q:

--> q = alloc(int);
q is 0xF50DDFF0 (int*)
--> *q = 4;
*q is 4 (int)
--> *q+1;
5 (int)
--> 

Pointers are usually used in conjunction with structs to implement data structures such as linked lists or binary trees; by themselves they are not particularly common. We therefore put off further examples to the section on structs.

## Aliasing

Like arrays, pointers can be aliased in that there are two pointers to the same memory location. The writing to one, will change the other. This can lead to inscrutable bugs, so it is very important to understand this.

--> int* p = alloc(int);
p is 0xF88ADFF0 (int*)
--> int* q;
--> q = p;
q is 0xF88ADFF0 (int*)
--> *q = 17;
*q is 17 (int)
--> *p;
17 (int)
--> q = alloc(int);
q is 0xF88ADFD0 (int*)
--> *q;
0 (int)
--> *q = 23;
*q is 23 (int)
--> *p;
17 (int)
--> *q = *p;
*q is 17 (int)
--> 

In particular, notice the difference between q = p which makes q and alias of p (in the the third input), and *q = *p which copies the contents of p to q (in the last input).