What are the fundamental rules of pointers?

A lot of questions I see in the C tag on StackOverflow are from beginners who have never been taught the fundamental rules of pointers. (I note that these rules apply to C# as well, though it is rare to use raw pointers in C#.) A lot of introductions to pointers get caught up on the implementation details of what pointers are for a particular compiler targeting a particular architecture, so I want to be a bit more abstract than that. So, without further ado, here are the fundamentals:

  • Computers store data, called values. Integers are one kind of data.
  • A value may be stored in a storage location by using the assignment operator.
  • People who like jargon will use lvalue to mean a storage location and rvalue to mean the value stored there. Use those terms if you like, but I find that this jargon is unnecessary. The “l” and “r” are chosen because an lvalue goes on the left side of an assignment operator and an rvalue goes on the right side.
  • A local variable is associated with a storage location. When you say …
    int x; 
    x = 123; 
    

    … then there is a storage location associated with x, and the value 123 is stored in that location.

  • A C programmer may associate a type with a storage location. In the example above, int is associated with the location of x.
  • There are certain program code positions in which the compiler deduces that a value is required, such as the right side of an assignment or an argument to a function call. If an expression which denotes a storage location is given at such a position then the value produced is the value stored in the storage location. For example…
    int x;
    int y;
    x = 123;
    y = x; 
    

    x denotes a storage location; the last line means “take the value that is in the storage location associated with x and copy it to storage location associated with y. Note that it does not mean “y is to be associated with the same storage location as x“.

  • A pointer is a value.
  • Let me reiterate that last point. A pointer is a value; a pointer is not a storage location. Rather, a pointer can refer to a storage location.
  • A C programmer may also associated a points-to type with a pointer. For example, a “pointer to int“. Such a type is denoted by int*
  • The unary prefix operator & takes as its operand an expression which denotes a storage location of type T, and produces as its value a
    pointer to T. The value of the resulting pointer is called the address of the storage location, and the pointer refers to that storage location.
  • Let me say that again, because this is fundamental: There are two ways to produce a value from a storage location of type T. You can obtain the value of type T which is stored in the storage location, or you can use the address-of operator to obtain a pointer value associated with the storage location.
  • The unary prefix operator * takes as its operand an expression whose value is a pointer to T, and produces a storage location of type T.
  • Let me say that again, because this is fundamental: if you have a pointer, its value is an address. Applying the * operator to an address gives you the storage location assocated with the address. This operation is called dereferencing the pointer. You can use that storage location just as you would use any other storage location; in particular, you can store things to it, and you can obtain the value stored in it.
  • I’ll say it again. The value of a pointer is an address. An address refers to a storage location. Dereferencing turns a reference to a storage location into a storage location; hence “dereferencing”.
  • The contents of an uninitialized storage location are implementation-defined, and it is undefined what happens when you use such a value.
  • “Undefined” means anything can legally happen. Working normally is “anything”. Crashing is “anything”. The program is under no obligation whatsoever to have any particular behaviour.
  • In particular, the value stored in an uninitialized storage location of pointer type is an address that need not be associated with any particular valid storage location; it is implementation-defined what happens if you dereference such a value.

A commenter points out that it’s not entirely clear from this description of the rules why we’d use pointers at all. Pointers allow you to transform a storage location into a value that can then be manipulated programmatically and then turned back into a storage location.

Those are the fundamental rules. There are more rules about arrays, pointer arithmetic, casting one pointer type to another, and so on, but the rules above are the truly fundamental ones regarding pointers. Now we can look at an example:

int x;
int y;
int *px;
x = 123;
px = &x;
y = *px;
*px = 456;

Walk through it. We have three local variables: x, y and px. Each is associated with a different storage location. Each starts with an implementation-determined value. We begin by storing the value 123 in the storage location associated with x. Then we use the address-of operator on x. What does that produce? Well, x denotes a storage location of type int, so the result must be a pointer value of type pointer to int that is equal to address of x. We store that value in the storage location associated with px, which is of type pointer to int.

So far so good. x and px have values. The value stored in x is 123 and the value stored in px is address of x.

Now we assign to the storage location associated with y. We need a value to store. What is the value of the right-hand side? Well, px is a pointer to int, so *px must be a storage location of type int. We are using a storage location in a context where we expect a value and there is no & operator, so this must mean to fetch the value associated with the storage location. What storage location is it? px has value address of x so *px is the storage location x. We fetch its value – 123 – and assign that value to y.

Finally, we use *px as the left side of an assignment, so we must be looking for a storage location. Since the * operator turns a pointer into a storage location, we’ve got one. What location? The location associated with x. So we store 456 into x.

What now are the values stored in each of our variables? x is 456, y is 123 and px is still “address of x

Summing up:

  • Storage locations hold values.
  • storage = value stores the value in the storage location.
  • Using a storage location in a context where a value is expected produces the stored value.
  • Pointers are values.
  • The & operator takes a storage location and produces a pointer value.
  • The * operator takes a pointer and produces a storage location.
About these ads

43 thoughts on “What are the fundamental rules of pointers?

  1. On a similar note, what exactly is a variable?
    Is ‘x’ a variable that is bound to a storage location?
    Is ‘x’ a symbol that is bound to a variable, which is another name for a storage location?
    Is ‘x’ a symbol that is bound to a variable, which is in turn bound to an entirely distinct storage location?
    Is there any practical difference?

    • For my money, there isn’t a practical difference from the point of view of someone writing ordinary code.

      From the point of view of the person writing the compiler, I imagine the third would be closest to the way they think. ‘x’ is a symbol that you keep in the symbol table, which when you look it up would describe the fact that it is a local variable and has a value stored at some memory address.

      Disclaimer: I haven’t myself implemented a general-purpose programming language in a commercial context.

    • The variable name ‘x’ is an identifier, i.e. a name, for a storage location but the actual storage location can depend on a context, or, to put it the other way round, there can be more than one storage location for every variable name. If you call a function recursively there will be one storage location for every local variable in every stack frame, i.e. the context is the stack frame (which is a implementation but I am not sure how to put it best in an implementation independent way. Maybe you can just say the function invocation is the context.) If you execute the function on several threads there will be different storage locations, too, because you have again different method invocations. If the variable is not local variable but a field of a class then there will be different storage locations for each instance, i.e. the context is the instance respectively the value of this. Thread local variables will again have different storage locations per thread. So ‘x’ is just a name that identifies a storage location depending on the current context and what the current context is depends on the kind of variable.

    • Personally I’ve always looked at it form a mathematical perspective. A variable is any data, be it a location or the value stored, which can change. The opposite of a variable being a constant which doesn’t change once it’s value has been set.

      Demonstrating what I mean by this:

      “int x” is variable in both it’s location and value. It’s location however is typically invariable within the context it’s used in.

      “const int x” is so invariable that most compilers just replace every use of it with the value.

      “int* x” has both variable location and variable value.

      “const int* x” has a variable location but an invariable value.

      “int* const x” has invariable location but a variable value. This one is a bit muddy though since the location it’s pointing to can be changed thus causing the value read to be different.

      “const int* const x” has both invariable location and value, may as well be a “const int” or “const int[]” depending on whether x is an array or not.

      It all gets blown out of the water when the memory manager is a modern type that does routine cleanups to keep memory space contiguous. Even though the address space is for all intents and purposes contiguous within our program’s context, accessing across program boundaries can be a real PITA with modern memory managers.

  2. A variable is an object declaration. Disclaimer: this is my definition. The C standard does not, in fact, define what a variable is (which was slightly surprising to me, but it’s true). It talks exclusively in terms of declarations, identifiers and objects; the term “variable” is used with implicit meaning. So if you want to have it *exactly*, well, according to the standard, a variable is nothing — there’s only objects, storage, identifiers and declarations.

    In “int x;”, ‘x’ is an identifier comprised of a single character (namely ‘x’), and “int x;” is a declaration of an object of type “int” that the identifier “x” refers to (but only within the scope of the declaration). That object, in turn, is associated with storage (or if you prefer, it *is* storage); ‘x’ is just a name for it. Informally, an object declaration is called a variable, and the identifier in such a declaration is the variable name.

    If you don’t want to go crazy, stick with what the standard uses for terminology — “symbol” isn’t part of that, nor is “binding”. The way the standard applies terms has been carefully chosen to give meaningful results when applied to the semantics of C (not coincidentally :-)), which needs tricky rules to explain how things like “extern int c;” work (and when they don’t and invoke undefined behavior).

    • I’m not sure I’m aware of what the standard terms are, I was just using the terms I learned in a programming languages course I took. Although I think I should have used “identifier” instead of “symbol”.
      Then again I’m not trying to restrict my question to C; it seemed like a concept that applies to any language, which might be especially relevant when there are pointers floating around.

      • Yes and no.

        Pointers are present in multiple languages — variables even more so. But if you ask “what *exactly* is a variable”, the easiest way to answer that is in the context of a specific language. Otherwise, you’re asking a much more general question about what makes a variable a variable in every language that has them, and that’s a bit more involved. For example, pure functional language don’t have variables in the strictest sense of the word, but let-bindings are often called variables regardless, since they fulfill roughly the same purpose. But in this case, talking about storage locations makes no sense — a let-binding is just a name for an expression. The runtime might allocate storage for it, but that’s outside the language.

        This is why I chose to answer your question in the specific context of C, since languages derived from C are likely to treat their notion of variables the same way (even if they don’t use the same terms). Eric took the same approach to pointers. To be fair, though, I haven’t even checked what the C# standard says about variables.

        • I think concepts apply pretty well across languages, even if that application is “Language L doesn’t have/use/distinguish feature X”. That is, I think the idea of a “variable” can and should be consistent across programming languages; If Lisp and Haskell don’t have variables, then they don’t have variables. If they do, they should be called variables for the same reason C has things called variables.

  3. Now Eric, any introductory discussion of pointers must be accompanied by a picture of Cthulhu wreaking havoc. It’s in the rules.

  4. Long live C# and VB6 refuses to die. Thank you for &pointing* me to safety. Now I can get some line of business code into the wide blue yonder. Disclaimer: I like C it just hurts my head and as Eric often says, if it hurts then don’t do that!

  5. “The “l” and “r” are chosen because an lvalue goes on the left side of an assignment operator and an rvalue goes on the right side.”
    Correct me if I’m wrong, but aren’t both a and b in “a = b” lvalues?

    I find the two concepts useful for understanding C++ (particularly with all those new-fangled additions such as rvalue references for move semantics, et al), but the nomenclature is really confusing imo.

    • An lvalue can go on either side, but an rvalue can only go on the right. Damn straight it’s confusing, which is why C/C++ compilers helpfully talks about “non-lvalues” instead of rvalues. That makes it so much clearer. ;)

      They wouldn’t have it any other way.

    • The explanation (or, Eric’s explanation) is right there, few points down the road:
      “There are certain program code positions in which the compiler deduces that a value is required, such as the right side of an assignment or an argument to a function call. If an expression which denotes a storage location is given at such a position then the value produced is the value stored in the storage location. For example…”

      In that context, when a storage location is positioned to the right of the assignment (or, when it is used as rvalue) – that the value stored in the storage location is returned as rvalue.

  6. Little errata (or, misunderstanding by me). You wrote: “A C programmer may also associated a points-to type with a *pointer*. [...]”

    This reads (to me) as nonsense.
    I think that that should have been “A C programmer may also associated a points-to type with a *storage location*. [...]”
    as in “A C programmer may associate a type with a storage location. [...]”

    Otherwise – I think I’ll use this if I’ll even need to explain to someone what pointers are, and how to use them.

  7. Lovely post; however I think your cameo use of the terms “lvalue” and “rvalue” may have caused more confusion than it solved — maybe you should put a dash through them.

    Although l stands for left and r stands for right, and value stands for value, at this point that is irrelevant: lvalues and rvalues can appear in many locations, and are in-general not values but expressions.

  8. Pingback: Dew Drop – May 13, 2014 (#1775) | Morning Dew

  9. I like to say that a pointer “identifies” a storage location, and a reference “identifies” an object. Such terminology avoids confusion when using languages that have pass-by-reference semantics.

    What do you see as the possibility for future language features and conventions to clarify whether an identifier is being used to refer to a variable, or to refer to the thing identified by a reference stored therein? IMHO, one of the biggest mistakes in Java and .NET wasn’t actually with the language itself, but rather with the decision not to use Apps Hungarian notation or any other means to distinguish the semantic types of the `Char[]` held by a `StringBuffer` [unsharable reference to object that can change] and the one held by `String` [sharable reference to object that must not change once the object holding it has been exposed to the outside world]. The runtime environment considers the two “types” equivalent, but using a variable of one semantic type as though it were the other is a recipe for disaster. Given that no convention has emerged for making such a distinction, do you have any recommendations how it might best be made?

    • The char[] in a String could be marked as final or readonly, which indicates that it will never be reassigned after its initial value. It would also be helpful to decorate the type with something saying the contents of the array are not going to change, too.

      I wouldn’t mind having a Java-like language with C++’s const feature, but neither set of language designers chose that.

      • Not C++’s const. Const correctness in C++ is nigh non-existent and leads to tons of duplicated code.

        Transitive const correctness on the other hand (I’m thinking of D) would be great to have. Also the distinction between immutable (= object cannot be modified through *any* reference) and const (= object cannot be modified through *this* reference) is most welcome.

        immutable vs. const would also come into play for your example: The char[] in String would be immutable, while the array in StringBuffer would just be const.

      • The `char[]` within `String` happens to be `readonly`, but that says nothing about whether the contents stored within the array might change. The `char[]` within `StringBuilder` is not `readonly`, since methods like `Append` may need to replace it with a reference to a larger array (abandoning the old one). That is, to be sure, a slight difference in the type of the fields, but one that says nothing about whether the array identified by the field can or cannot legitimately be modified, and whether references to that array may legitimately be allowed to escape control of the owner.

        Incidentally, it’s interesting that discussion of immutability focuses on the operations that can’t be done with an immutable object, rather than the more fundamental requirement, which is that code which acquires a reference to an immutable object is entitled to use that reference to encapsulate the state the object had when the reference was acquired; any action that would violate that entitlement is illegitimate. The purpose of immutability isn’t to prevent the owner of a variable from changing the encapsulated state, but rather to ensure that nobody *other* than the owner of a variable would be able to change its encapsulated state. Unfortunately, with class types, the only way to ensure that the state encapsulated by a variable won’t get changed by anyone other than the variable’s owner is to forbid changes by absolutely anyone, *including* the variable’s owner.

  10. The funny thing is, when you think about it, variable’s name is sorta pointer to:it refers to storage location, and we have auto-derefencing for variable names: on the right side of the assignment it denotes not the storage location, but the value in it. On the left side of the assignment it denots the storage location itself.

    • Upon reading this, I immediately tried to imagine a computer where the only form of memory address was a string name.

      Not sure that’s a winner.

      • However, “late bound” languages like JavaScript could easily have an interpreter that works that way. And what is a computer, if not a machine language interpreter?

  11. I’m not a novice programmer, but I’m definitely a C novice, and my knowledge of pointers is limited to a couple C++ lectures I attended many years ago. I was excited that you wrote this up, because I feel like pointers are a topic I should really “get”. I have to admit, though, that after a couple reads through, I was still a little foggy on some of the details:

    1. Why would I ever want to use pointers? (From a quick Google search, one answer seems to be that when programming in C, pointers are the only way (?) to refer to the same space in memory from multiple locations.)

    2. What does `int *px` actually mean? You say, “We have three local variables: x, y and px”, but you don’t really explain why the px is prefixed by an asterisk. Should I interpret `int *px` as “declare a storage location that holds an address such that if I dereference that address, I get an int”?

    3. What would be an example usage of int*, which you describe as a “pointer to int”? Before I saw `int *px` in your example, I was expecting the syntax to be `int* px`.

    • 1. Many reasons. I’m more familiar with C++, so I’ll answer from there.

      If you pass a subclass as the parent (e.g. passing a Dog to a function that takes Animal), and the parameter takes in a non-pointer (Animal instead of Animal*), then the Dog object will be sliced, and passed as an Animal. So you lose polymorphism. This happens because non-pointers are like value types in C#, and stored locally (such as on the stack). The Dog might be 8 bytes in size, whereas the Animal might be only 4 bytes. If you copied over the whole 8 bytes, you’d trash other memory. This is one reason why C# doesn’t allow extending value types, to avoid this slicing problem.

      If a function mutates the object, then any changes are lost if not passed as a pointer. This is the same as in C# where value types aren’t changed from a function call, whereas reference types are.

      If you have a type A that contains a type B, and type B contains an A (a circular reference), then they must be declared as pointers. If they weren’t, then you’d need an infinite amount of memory because A would contain a B would contain an A would contain a B…

      Non-pointers must be initialized with a value locally. So
      Dog d = Dog();
      is valid, while
      Dog d;
      is a compiler error.

      Pointers may defer initialization (and should be assigned NULL).
      Dog *d = NULL;
      //other code
      d = new Dog();

      Iterators over collections return a pointer, so you can mutate the object inside the collection. Also, since you can do arithmetic on pointers, to get the next item, it’s just i++.

      Also, pointers are copied faster, since they are smaller than objects. So passing a pointer copies just the address, but passing an object copies the whole object. But don’t make optimization decisions based on this.

      If you understand the difference between reference types and value types in C#, you mostly understand pointers. Though C++ has references, which work like pointers, but you can’t do arithmetic on them. And references don’t need to be dereferenced (no need to use ‘*’ on them).

      2. Yes. `int *px` means “declare a storage location that holds an address such that if I dereference that address, I get an int”.

      3. The ‘*’ is just used to denote that it is a pointer. White space is ignored by the compiler.
      int* px;
      int * px;
      int *px;
      are all treated the same. Most people use `int *px`, though my personal preference is `int* px`. Eric’s example above is how you use pointers with ints. And shows you everything you can do with them.

      • @treed, thanks very much! That definitely clears things up (especially the the part about white space not mattering in terms of where you put the asterisk).

      • There’s a very good reason to never, never, never use int* x instead of int *x. Simple example:
        int* x, y; // what type does y have?

        If you thought y is int*, sorry to disappoint you – that’s not how that declaration syntax works. You end up with x being an int* and y being simply int.

        One of those mistakes that Java and C# luckily learned from (not pointers but array declarations).

        • > int* x, y; // what type does y have?

          Agreed. I think it’s an important distinction to understand when you’re working with pointers. Given the three options when declaring a pointer:

          int* x; // suggests that x is a variable of type “int pointer”

          int *x; // suggests that x is a variable of type “pointer to an int”

          int * x; // can’t we all just be friends? (no, of course not, and I bet you indent by 1 tab + 2 spaces)

          I believe the second options is more correct as well as more readable and less prone to mistakes (and re-reading Eric’s post I’m happy to see he appears to concur :) )

          • I encountered a coding convention like that once. I think it was Netscape Java code or something. It still gives me nightmares.

          • It’s all about conventions.
            The conventions which I use, solves this problem by not allowing more than one variable declaration per line, so it allows you to interpret ‘int*’ as a type of its own.

            Now of course my convention is always superior, and all the other conventions are just plain stupid ;)

          • I’d just like to go back in time and fix the screwup in the language definition to actually interpret int* x,y; intuitively. I’d say that’d be even easier to parse so hey win-win!

            @Joshua: You must be kidding.. please tell me you’re kidding :/

          • @voo

            I swear, no kidding, I saw this. I might be misremembering what company wrote it, but it was in Java, it was an open-source project from a recognisable commercial name, and the indentation was consistently applied throughout the code base.

            Indentation was: two spaces, one tab, one tab and two spaces, two tabs, etc etc. Since my team’s convention was tabs indent by two spaces, there were plenty of places where increasing a level of indentation actually shifted text to the left.

    • treed’s answer is very comprehensive, but if I can inject some snark:


      1. Why would I ever want to use pointers? (From a quick Google search, one answer seems to be that when programming in C, pointers are the only way (?) to refer to the same space in memory from multiple locations.)

      You left out the phrase “in the name of all that is holy” in your question. You already know the answer: when the language gives you no alternative.


      3. Before I saw `int *px` in your example, I was expecting the syntax to be `int* px`.

      C type declarations offer a long and arduous journey that you are clearly just starting on. I’ll get popcorn.

      It’s sort of like Winston coming to appreciate Big Brother in 1984 – on the day it seems natural and right to you, you are truly a C programmer and ready for death.

  12. I was with you for the first paragraph of straight-int based examples.

    But then the explanations in the second highlight why people have problems. It wasn’t clearly explained.

    You referred to int* something, and then *something later, but didn’t explain it, or whether there was a difference between int* something or int *something – you just started *something-ing.

    Then, there’s talk of & and a type T, but I’d have expected to see something like an example at that point. It remained unclear.

    • As you can see from the above comments, whether it’s int* something or int *something is a bit subtle.

      Like the comments above, I try to think in terms of int *something. *something is an int, when you declare it and when you use it.

      int i = 6;
      int *pi = &i; // *pi is an int.
      int j = *pi / 2; // I can use *pi as an int in an expression. j gets the value 3.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s