Tarnished Pixels

As we learned earlier, computers fundamentally operate on vast collections of bits, which are organized into groups of eight (bytes). Bytes are, in turn, organized into massive blocks, in which each byte is identified by the number corresponding to its position in the block. The first byte is number zero, the second is number one, and so on.

Memory Addresses

The reason we number the bytes in sequence (starting with zero), is that this is a convenient scheme when interacting with the hardware. The first byte is zero bytes over from the start of the block (after all, it's on the start of the block), so we number it zero. The second byte is one byte over from the start, so we number it one. The numbers tell us where the byte is located, which is why we call them addresses.

That bears repeating: a byte's address is a number (more precisely, an integer) giving its position in the system's memory.

Null

The address zero has special meaning to software. While there technically is a byte zero in hardware, programs don't typically use that address. It's reserved in almost all software environments as a special value whose meaning is typically something along the lines of "no address assigned for this value" or "no value to take the address of".

(Note: there are programming environments where zero is a valid address, and null has some other value, but these are rare, and you're unlikely to have to deal with one as a beginning programmer.)

There are many other "special" addresses in a typical computing system, but only software that interfaces directly with hardware components typically needs to worry about them, so enough said about that for now.

Keeping Track

Now, this is the point where things become obnoxious.

Computers encode everything as bits, including memory addresses (which are encoded using that machine's standard encoding for integers - typically plain binary). And we, as programmers, have a lot of data to store.

Every quantity our application needs to track has to go into memory somewhere. So we need to assign each of those pieces of information an address. And sometimes we don't know what that information will be, specifically, or how much we'll have, so we need to have other information that tracks that information (about our information), with addresses assigned for storing that. And sometimes we're tracking information about information about information about... well, I'm sure you get the point.

Furthermore, our programs are, themselves, information. Processors have a set of commands they'll accept (called instructions), and these are themselves stored as sequences of bits. In memory. At some address. And because computers only understand bits, instructions which access memory only accept numeric addresses, so we not only need to keep track of what goes where, but we need to make sure that we get that location exactly correct each time when entering our instructions.

And as we add instructions, other instructions shift around, and anything that referred to their addresses has to be updated to compensate. (And sometimes instructions come out to different sizes depending on the specific address they're programmed to access, so updating our references might require another round of updating references...)

Oh, and of course our data can shift around if we go back later and try to give some more space to some chunk of it, creating the same sort of cascading address-update workload that changing instructions can create.

And I'm simplifying things, here. There are all sorts of other restrictions on what can go into which memory, and how things need to be grouped, and these vary from one type of processor to the next. If you were to actually try to create a real-world program (i.e. one that actually does something useful) by writing machine instructions directly you'd actually have a much harder time of things than I've described.

And that is why compilers were created.

Variables

People typically think of compilers as being about code - about instructions. But compilers are just as much about keeping track of the tens of thousands of different bits of information (even in simple programs - remember, there's a lot of data just keeping track of all the other data) that we use to get work done. Laying out data in memory is an enormous task, but it's fortunately relatively simple and easily automated. So while compilers turn textual program instructions into machine instructions, they also turn logical groupings of data (described in the same program text as the instructions) into the many relevant addresses within a given program.

At the heart of the compiler's data-tracking duties, are variables.

These aren't variables in the mathematical sense. Variables in a program are simply storage locations. The thing is, we typically don't care where a bit of data is actually stored. One address is, to us, as good as another. What we care about is that we have some space reserved somewhere for some purpose, and that we can refer to it in a meaningful way that doesn't break every time the memory layout changes even slightly.

Variables fundamentally consist of three things:

• They have a name, which we humans can easily remember, and which doesn't need to be changed in every place it's referenced (or in fact anywhere) whenever we make some unrelated change that shuffles things around in memory.
• They have a type, which tells the compiler how much data we need to store (particularly, how many bytes to reserve for that data). The type also informs the compiler of any special restrictions that the hardware might have about storing this particular bit of data. (For instance, many processors require 2-byte data to be at an even address, 4-byte data to be at an address which is a multiple of four, and so on. This is called alignment.)
• They have a lifetime. Memory can, after all, be reused when we're done with it. By creating our variables in different ways, we indicate to the compiler when it will become safe for it to reuse the address that it assigns to that variable for some other data.

In C (which many languages mimic), variables are declared (created) as follows:

//create a type "char" (1-byte) variable called "a"
//and a type "int" (4-byte) variable called "b"
//and have both stick around for the program's duration
char a;
int b;
 
{
    //create a type "int" variable "c"
    //this variable is only going to stick around
    //while the program is running code inside
    //this pair of curly braces - its memory will
    //be reused for other data afterwards
    int c;
}

A Little More on Types

Before I go on, a reminder: computers themselves have no concept of particular groups if bits or bytes having "types". It doesn't know if you're working with a group of on/off values, a binary integer or a memory address any more than a piece of paper can distinguish between the Os and zeroes on the page. It's up to the reader to distinguish letters from numbers, and it's up to the programmer to keep track of what it is that any given bit of data represents.

Programming environments help take some of that burden by assigning each value in the program a type. In statically-typed languages (like C), not only the values, but also the variables have types. Now, these types are still a lot more abstract than what you might think of as the type of a given bit of data. In C, for instance, text is represented as a sequence of numbers, each corresponding to a letter. So you still have to keep track of what's what, but the compiler will at least do some of that work for you.

There is another class of languages, the dynamically-typed languages, where a variable's type changes depending on what value you last put into it. These languages don't really reflect the way that a processor works at a lower level, so we won't discuss them until later.

Variables Are Addresses

Variables are, fundamentally, addresses. Whenever you create a variable, you're telling your compiler "I've got some data to store, go pick an address for it to be stored at". And when you use a variable thereafter, you're essentially instructing the compiler to look that address up and paste it verbatim into the instructions it's creating.

This also means that it's (in some languages, many "higher-level" languages forbid these sorts of operations) possible for us to actually get the address itself as a number, and manipulate it as such. This is typically done through the "address of" operator (In C, that's "&"):

int c;
 
//store the number zero at the memory address
//assigned to the variable "c"
c = 0;
//this reads best right-to-left
//get the actual address number assigned to "c"
//adjust it so it's the size of an "int"
//and then store it at the address assigned to "c"
c = (int)&c;

This can be a tricky concept to deal with at first. But here's how it works. If you're working with the name of the variable directly, then you're working with the contents of the memory at its address. If you apply the address-of operator, then you're working with its address directly. And since the contents of the memory and the address of the memory are to separate entities, we can do silly things like storing one inside the other.

Pointers

In the code sample above, we had to take an extra step to convert the address (a number) into a regular integer type. That's because address-numbers are usually given their own special type in programming language. That type is called the pointer (think of a pointer as a sign "pointing out" a particular memory address).

Now, "pointer" isn't really a type. It's a family of types. Variables are addresses, and their type information is thus associated not with the variable's name, but with its address. So it only makes sense that the type information also be associated with any pointers to that variable. So pointers are declared with their own special syntax:

int c;
int* pc = &c;

In the above example, pc's type is int* or "pointer-to-int". And when we take the address of c we get a value whose type is "pointer-to-int" (because we're getting the address of a variable which is an int). That's why this time we can store the pointer value directly into the pointer variable without converting its type.

Dereferencing Pointers

Now pointers would be pretty useless if all you could do was make them and assign them to variables. That's why there's one more aspect to pointers: dereferencing. That just means "using the pointer to get at the value it points at".

Take the following example:

int c;
c = 0;
int* pc = &c;
*pc = 1; //write a 1 into the memory pointed to by pc

Now let's take that example and follow through what a compiler's going to do with it in terms of memory:

• There's a variable c. The compiler will pick a memory location to store its value and produce that number wherever you mention the variable's name. For the purposes of this example, let's say that the compiler picks address 50 for c.
• There's a pointer pc. pc is also a variable, so the compiler will set aside another little chunk of memory to store that value. Again, for illustration, let's say that this variable goes at address 54.

In terms of instructions, here's what's going to happen:

• For the first line, the compiler will issue an instruction to write a zero value into the memory at c's location. This is its location as a number. Since c happens to be at address 50, the compiler will write the literal value 50 into the write instruction's target-address parameter.
• The second line is basically the same thing. Only instead of writing into location 50, it's writing into the location assigned to pc, 54. So the instruction would read, "write these bits (which happen to be the binary bit pattern for the number 50) into the memory at address 54".
• The last line is the most complicated. That will likely end up being a pair of instructions. The first will be "read a pointer-sized block of data from location 54". The second will be "treat the value you just read as a memory address (remember, just a number) and write these bits (binary for 1) into that memory location".

Complex Types

Now we're typically dealing with data that's more complex than individual integers, and this more-complex data needs to be laid out in memory as well. Programming languages give us tools to help with that.

Structs

The simplest of these types is just a grouping of related variables into one. In C (and many of its related languages), this is called a struct. A struct is a type which we ourselves define, and it goes something like this:

//if you're not familiar with C, ignore "typedef" the repeated name,
//that's just its silly syntax being silly
typedef struct Point
{
    int x;
    int y;
} Point;
 
Point pt;
 
pt.x = 4;
pt.y = 7;
 
Point* ppt = &pt;
 
ppt->x = 6;
ppt->y = 90;
 
//C's '->' operator is just a dereference operator
//and a dot operator combined into one
//and it gets the order of operations
//right so you don't need the parentheses
 
//so ppt->x is shorthand for (*ppt).x

This code does a few things. First, it defines Point as a structure type containing two integer variables, x and y. This tells the compiler that everywhere it sees you make a Point variable, it needs to reserve enough space for two side-by-side integers.

Next, we declare a variable pt of type Point. Now, let's say int is a 4-byte type. That means that 8 bytes are going to be reserved for pt. Let's say that those eight bytes happen to begin at address 1200. We've also got a pointer-to-Point, ppt. Let's say pointers are 4-byte values and that the compiler put ppt at location 1208. (Eight bytes over from pt, because those eight bytes following pt are reserved for it.)

Next up, we have a pair of simple variable assignments. These are no different from our earlier assignment to c. The instructions read something like the following:

• Take this 4 byte long bit pattern (binary for 4) and store it at location 1200.
• Take this 4 byte long bit pattern (binary for 7) and store it at location 1204.

Make sense? The x variable is declared first in the struct, so it goes at the beginning (pt's address plus zero). y is declared next, so it goes right after, putting it at pt's address plus four.

The next instruction is also trivial:

• Take this 4 byte long bit pattern (binary for 1200 - the address of pt) and store it at location 1208 (ppt).

What follows is a simple extension of the previous example:

• Load the 4-byte value stored at 1208.
• The previously loaded value is an address, write these bits (binary for 6) to the memory it points to.
• Add four to the address we loaded in the step before last.
• The newly computed value is an address, write these bits (binary for 90) to the memory it points to.

Pointers and Arrays

Arrays are the other complex type. An array is basically a sequence of elements all of the same type, all laid out one beside the other. Arrays are also secretly pointers. Well, sort of. It's complicated, is a simple sort of way.

int a[4];

That's a simple array declaration. Similarly to the other variable declarations, it tells the compiler, "set aside 16 bytes (4 4-byte ints) and associate the address you pick for them with the name 'a'". Let's say that a ends up at address 800.

Direct assignments are also very simple.

a[0] = 3;
a[2] = 12;

Those lines mean, respectively:

• Take these bits (binary for 3) and store them at location 800.
• Take these bits (binary for 12) and store them at location 808.

But arrays can also behave like pointers. This happens if we don't type a number directly into the square brackets.

int x = 1;
a[x] = 50;

That makes the compiler create these instructions (assume that x has been given address 40):

• Write these bits (binary 1) to location 40.
• Read the value from location 40. (This seems stupid, and real compilers aren't actually this dumb - go with it for the sake of illustration.)
• Multiply the value we just read by 4 (the size of an int).
• Add 800 (the start of our array) to value we just computed.
• The last computed value is an address. Store these bits (binary 50) to the memory it points to.

The only difference from the standard pointer arithmetic is the multiplication by the size of the array element. And this is because the index into the array we're passing is, like an address, an offset from the array's start (zero is the first element, and so on), only it's an offset in terms of individual elements rather than bytes, so therefore the multiply. The ubiquity of these operations is why indexing in most programming environments is done from zero - it skips having to subtract one in order to account for the first element's offset from the start of the array being zero bytes.

And, of course, arrays and structs can be arbitrarily combined, allowing structs to contain arrays and arrays to be of struct types. Once you nest one inside the other a few levels deep, you'll be very thankful you're not computing all the sizes, addresses, and offsets manually.

Wait! You Said Arrays are Pointers! What's up with that?

Given that the operations required when dereferencing pointers and when accessing arrays are so similar, in C the two are nearly synonyms. And so both are valid candidates for pointer arithmetic, which is another way that compilers make dealing with memory more convenient.

The thing is that you very often want to compute the address of the byte immediately following a variable, because you very often know that there's another variable of that type there (for instance, the first variable is the middle element of an array). Similarly, you might want to go an element-size backwards. And it's often convenient not just to compute that address, but to dereference it all in one go. (Well, in code. In processor instructions it's still more than one step, but the compiler gets to worry about that.)

This is why C and a good number of its relatives have pointer arithmetic. What this means is that any time you add or subtract an integer to a pointer, that integer will first be multiplied by the size of the type that pointer is a pointer to:

//given:
int a[50];
int* p = &a[20];
 
//these are equivalent expressions
p + 1
&a[21]
a + 21
 
//as are these
&a[18]
p - 2
 
//and combined with dereferencing:
a[20]
p[0]
*p
 
//likewise these refer to the same memory
a[21]
p[1]
*(p + 1)

And when arrays and structs meet, the compiler creates instructions that compute each level of offsets in turn:

Point pts[20];
pts[6].y = 4;
 
int i = 2;
pts[i].y = 3;

If pts ends up at location 100, the first assignment writes to address 152. That's 100 for the start of the array, 48 (6 * 8) for the 6th element in an array of 8-byte elements, and another 4 for the offset of the y variable within that element.

The next bit is the same, only instead of the compiler directly computing the address, it'll multiply the value in i by 8 (element offset in the array), add it to 100 (array's starting address), and then add 4 again for the offset of the y field. (Again, compilers are smart, most likely they'd just add 104 in one step rather than two. And if they could prove, by analyzing the program, that i will have a particular value at that point then the compiler would create a direct write to the final address.)

In Summary

There's nothing magical about variables or pointers. Variables are just blocks of memory that the compiler's assigned to specific addresses. Their names are just a convenient way to refer to that address (a number) without losing our sanity, or having to correct every reference to that data any time we do something that forces it to move to a new address.

Pointers are a means that many programming languages provide for working directly with the memory addresses themselves. They have their own type, in order to make it hard to mix them up with numbers that aren't meant to point to data, and also in order to tell the compiler that it should use special rules (allowing dereferencing and pointer arithmetic) to make working with the pointed-to data more convenient.

The whole point of the two is to spare programmers the massive headache that organizing data into the billions of bytes in a modern computer's RAM would be. They're often daunting to new programmers, but they're much, much better than what we'd face if we had to work directly in the terms that a computer "understands", where everything is just bits and there are no clues as to which bits are for what.

Compilers keep track of some of the data that they need in order to carry out their business by keeping track of types, which can also help programmers deal with some of the load of remembering what any given varible is supposed to represent.