Close
Register
Close Window

F17 OpenDSA entire modules

Chapter 5 Pointers

Show Source |    | About   «  5.1. Pointers Chapter Introduction   ::   Contents   ::   5.3. Local Memory  »

5.2. Basic References

5.2.1. Pointers and References

5.2.1.1. What is a Pointer?

There's a lot of nice, tidy code you can write without knowing about pointers. But once you learn to use the power of pointers, you can never go back. There are too many things that can only be done with pointers. But with increased power comes increased responsibility. Pointers allow new and more ugly types of bugs, and pointer bugs can crash in random ways which makes them more difficult to debug. Nonetheless, even with their problems, pointers are an irresistibly powerful programming construct.

Pointers solve two common software problems. First, pointers allow different sections of code to share information easily. You can get the same effect by copying information back and forth, but pointers solve the problem better. Second, pointers enable complex linked data structures like linked lists and binary trees.

5.2.1.2. What is a Reference?

Java actually uses a restricted version of the pointer concept, which is called a reference. While they mean roughly the same thing, the term "pointer" tends to be used in discussions that are not specific to any particular language or implementation. The word "pointers" connotes the common C/C++ implementation of pointers as addresses or locations in memory. Programmers have more limited access with a reference. This limits what they can do, but the Java philosophy is that this is more than made up for by a greater chance of the code working correctly. Essentially, Java programmers may only assign to a reference and compare two references for equality. Other uses of a reference are done implicitly with no control from the programmer. These restrictions reduce the chance for bugs.

5.2.1.3. Data Types in Java

Simple int and float variables operate pretty intuitively. An int variable is like a box that can store a single int value such as 42. Visually, a simple variable can be viewed as a box with its current value shown inside.

A reference variable works a little differently. It does not store a simple value directly. Instead, a reference variable stores a reference to some object. The object that the reference refers to is sometimes known as its pointee. In the next figure, the reference variable (called empRef) is shown as a box that contains the beginning of a directed line, which leads to its pointee (an Employee object, shown as the box storing two fields: the string value "John" and the integer value "1000"). So empRef is the reference and the Employee object is its pointee. What is stored inside of empRef? Its value is not an Employee object. Its value is only a reference to an Employee object. (By the way, there is no commonly used word for the concept of a pointee—pointee is just the word that we used in these explanations.)

Going back to simple things like int and float variables that just store a value in a box: In Java, these are referred to as primitive data types. In Java, Objects and Arrays are non-primitive data types, and they are always accessed by references. Java automatically uses references behind the scenes for such complex types, and there is no reference-specific syntax (like there is in C/C++). You just need to realize that assignment operations like a = b will automatically be implemented with references if a and b are arrays or objects, which is different from the behavior that you get if a and b are primitive objects like int. Assignments and parameters with arrays and objects are intrinsically shallow or shared—, which is discussed in the Shallow vs. Deep Copying section below.

5.2.2. Referencing and Dereferencing

Dereferencing means to follow a reference to get the value of its pointee. Dereferencing empRef in the figure above gives back its pointee, the Employee object. So, "dereference" just means to access the value of the pointee. Visually, the result of a dereference is the object pointed to by the arrow. The key restriction is that the reference must have a pointee to access. A lot of bugs in reference code involve violating that one restriction. A reference must be assigned a pointee before dereference operations will work.

The constant null is a special reference value that encodes the idea of "points to nothing". It turns out to be convenient to have a well-defined reference value to represent the idea that a reference does not have a pointee. It is a runtime error to try to get the pointee of a null reference. In drawings, the value null is often drawn as X's or as a diagonal line between the corners of the reference variable's box.

5.2.3. The Employee Class

We are going to use the Employee object for a lot of our examples, so let's make a formal introduction now. Meet the Employee class.

/**
 * Employee is a class used in this tutorial to explain various pointer concepts
 */
class Employee {
  String name;
  int salary;

  /**
   * class constructor to initialize name and salary fields
   * @param name: employee name
   * @param salary: employee salary
   */
  public Employee(String name, int salary)
  {
    this.name = name;
    this.salary = salary;
  }

  /**
   * getter method for the name field
   * @return the value of name field
   */
  public String getName()
  {
    return name;
  }

  /**
   * setter method for the name field
   * @param newName the value to be assigned to name field
   */
  public void setName(String newName)
  {
    name = newName;
  }

  /**
   * getter method for the salary field
   * @return the value of salary field
   */
  public int getSalary()
  {
    return salary;
  }

  /**
   * setter method for the salary field
   * @param newSalary the value to be assigned to salary field
   */
  public void setSalary(int newSalary)
  {
    salary = newSalary;
  }
}

5.2.4. Reference Assignments

An assignment (=) of one reference to another makes them point to the same pointee. It's a simple rule for a potentially complex situation, so it is worth repeating: assigning one reference to another makes them point to the same thing. The example below adds a second reference, named second, assigned with the statement:

second = empRef;

The result is that second points to the same pointee as empRef. In the drawing, this means that the second and empRef boxes both contain arrows pointing to the Employee object. Assignment between references does not change or even touch the pointees. It just changes which pointee a reference refers to.

After the assignment, testing for (second == empRef) would return true.

The assignment operation also works with the null value. An assignment operation with a null reference copies the null value from one reference to another.

Memory drawings are key to thinking about reference code. When you are looking at code, think about how it will use memory at run time, then make a quick drawing to work out your ideas. This tutorial uses a lot of drawings to show how references work. You should too.

5.2.4.1. Sharing

Two references which both refer to a single pointee are said to be "sharing". That two or more entities can cooperatively share a single memory structure is a key advantage of references. References second and empRef in the above example both share the same object, so either can modify the object's value. Reference manipulation is just technique—sharing is often the real goal. Later we will see how sharing can be used to provide efficient communication between parts of a program.

5.2.5. Shallow and Deep Copying

An important use of sharing is to enable communication between two functions. One function passes a reference to the object of interest to another function. Both functions can access the object of interest, but the object of interest itself is not copied. This communication is called shallow copy since, instead of making and sending a (large) copy of the object of interest, a (small) reference is sent and the object of interest is shared. The recipient needs to understand that they have a shallow copy, so that they know not to change or delete it accidentally, since it is shared. The alternative—where a complete copy is made and sent—is known as a deep copy. Deep copies are simpler in a way, since each function can change their copy without interfering with the other copy. But deep copies run slower because of all the copying. And if the second function was meant to modify the copy for every user of the object, then deep copy won't let this happen. The drawing below shows shallow and deep copying between two functions, A() and B(). In the shallow case, the smiley face is shared by passing a reference between the two. In the deep case, the smiley face is copied, and each function gets their own.

Here is an example of the difference between shallow and deep copying:

    Employee firstEmployee = new Employee("Sam");
    Employee theSameEmployee = firstEmployee; // Shallow copy
    theSameEmployee.setName("John");
    System.out.println(theSameEmployee.getName()); // Print John
    Employee secondEmployee = new Employee("Patrice");
    Employee deepCopyEmployee = new Employee();
    // Deep copying the secondEmployee's values
    deepCopyEmployee.setName(secondEmployee.getName());
    // Now we have two different Employees with the name Patrice.
    // Any change in one object will not affect the other
    deepCopyEmployee.setName("John");
    System.out.println(secondEmployee.getName()); // this will print Patrice

5.2.6. Bad References

When a reference is first allocated, it does not have a pointee. The reference is uninitialized or simply "bad". Dereferencing a bad reference is a serious runtime error. The dereference operation will crash or halt immediately. Each reference must be assigned a pointee before it can support dereference operations. Before that, the reference is bad and must not be used. In our memory drawings, the bad reference value is shown with an XXX value.

Bad references are common. In fact, every reference starts out with a bad value. Correct code overwrites the bad value with a correct reference to a pointee, and thereafter the reference works fine. There is nothing automatic that gives a reference a valid pointee. You just have to program carefully. Fortunately, the Java compiler will usually spot when a reference variable has not been initialized, and generate an error (meaning that you cannot even complete compiling and run the program).

On the other hand, that does not stop you from assigning the variable to something that will lead to a serious problem later. If your code is crashing, a bad reference should be your first suspicion. In Java, the run-time system checks each time that a reference variable is dereferenced to see if it is null. So code can still exhibit reference bugs, but the kind that dereferences a null value will at least halt politely on the offending line. A runtime error called NullPointerException will occur and the program will stop. As a result, it is much easier to locate and fix reference bugs in Java. Such run-time checks are also a reason why Java tends to run at least a little slower than a language like C or C++.

One way to think about reference code is that it operates at two levels—reference level and pointee level. The trick is that both levels need to be initialized and connected for things to work. (1) The reference must be allocated, (2) The pointee must be allocated, and (3) the reference must be assigned to point to the pointee. It's rare to forget step (1). But forget (2) or (3), and the whole thing will blow up at the first dereference. For example, a popular mistake is declare a string variable, but then never assign it an actual string before tyring to print or otherwise use it. Remember to account for both levels. Making a memory drawing during your design can help to make sure that it's right.

Code with the most common sort of reference bug will look correct, but without the middle step where the references are assigned pointees. The bad code will compile fine, but at run-time, each dereference with a bad reference will raise NullPointerException and the program will crash. It is up to you to ensure that each reference is assigned a pointee before it is used. Here is a simple example of bad code, and a drawing of how memory is likely to react.

        Employee badPointer; // Allocate the reference ...
        // badPointer = new Employee("Sam", 1000); ... but forget the pointee
        System.out.println(badPointer.getName());  // This line causes a NullPointerException

5.2.6.1. Why Are Bad Reference Bugs So Common?

There must be a reason why Java cares so much about dereferencing null pointers, that its always watching out for it. Why? Because it happens in a lot of programs.

Why is it so often the case that programmers will allocate a reference, but forget to set it to refer to a pointee? The rules for references do not seem that complex, yet every programmer makes this error repeatedly. Why? One explanation is that we are trained by the tools that we use. Simple variables don't require any extra setup. You can allocate a simple variable, such as int, and use it immediately. All that int, char or boolean variable code that you have written has trained you, quite reasonably, that a variable may be used once it is declared. Unfortunately, references look like simple variables. But they require the extra initialization before use. It's unfortunate, in a way, that references happen look like other variables, since it makes it easy to forget that the rules for their use are very different. Oh well. Try to remember to assign your references to refer to pointees. But don't be surprised when you forget, and your program breaks.

5.2.7. Syntax

The above basic features of references, pointees, dereferencing, and assigning are the only concepts you need to build reference code. However, in order to talk about reference code, we need to use a known syntax which is about as interesting as... a syntax. We will use the Java language syntax which has the advantage that it has influenced the syntaxes of several languages.

5.2.7.1. Declaring a Reference Variable

A reference to a non-primitive data type (that is, a reference to any object) is defined by declaring a variable of that object's type. In other words, reference variables are declared just like any other variable. The declaration gives the type and identifier of the new variable, and reserves memory to hold its value. But—and here is the most important thing—declaring the reference variable does not assign a pointee for the reference. The reference starts out with a "bad" value until you assign it to something.

    Employee empPtr1; // Declare a reference to an Employee
    // This allocates space for the reference, but not the pointee.
    // The reference starts out as "null"

5.2.7.2. Assigning a pointee to a reference

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.2.7.3. Dereference the reference

Anytime a reference variable appears anywhere other than the left side of an assignment statement, it is dereferenced. This is really no different than how a primitive variable like an int is used. Consider the following code:

int a = 5;
int b = a;

In this case, the value of a in the second line is just 5. In exactly the same way, in this code:

Employee empPtr = johnRef;

the value of johnRef is simply the location of the object that it is referencing. This is why empPtr ends up pointing to that same object. Of course, whenever you dereference any reference variable, it had better have a pointee. Otherwise, you get a runtime error of type NullPointerException.

5.2.7.4. Example Reference Code

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.2.8. Reference Rules Summary

No matter how complex a reference structure gets, the list of rules remains short.

  • A reference variable stores a reference to its pointee. The pointee, in turn, stores something useful.
  • The dereference operation on a reference accesses its pointee. A reference may only be dereferenced after it has been assigned to refer to a pointee. Most reference bugs involve violating this one rule.
  • Allocating a reference does not automatically assign it to refer to a pointee. Assigning the reference to refer to a specific pointee is a separate operation. This is easy to forget.
  • Assignment between two references makes them refer to the same pointee, which allows object sharing.

5.2.8.1. Java References vs Pointers

Java references have two main features that distinguishes them from the less restrictive pointers in a language like C or C++.

  1. Fewer bugs. Because the language implements the reference manipulation accurately and automatically, the most common reference bug are no longer possible. Yay! Also, the Java runtime system checks each reference value every time it is used, so dereferencing a null reference is caught immediately on the line where it occurs. This is in contrast to a language like C++, where dereferencing a value of null might not make the program crash until later. This can make a programmer much more productive to know exactly where the problem occurred.
  2. Slower. Because the language takes responsibility for implementing so much reference machinery at runtime, and does so much extra runtime checking, Java code runs slower than other languages like C and C++. But the appeal of increased programmer efficiency and fewer bugs makes the slowness worthwhile for many applications.

5.2.8.2. How Are References Implemented In The Machine?

How are references implemented? The short explanation is that every area of memory in the machine has a numeric address like 1000 or 20452. You can think of memory as a big array, and each position in memory has an index which is its memory address. A reference to an area of memory is really just an integer which is storing the address of that area of memory.

In the picture above, we assume that Java decides to place the new Employee object starting at memory location 2000. So the reference variable just stores a value of 2000. If we looked closely at the computer's memory then we could see exactly how the Employee object is layed out in the bytes in memory (beginning at 2000). But we don't show it in this picture because the internal details for how the Employee object is implemented are more complicated than we need to care about right now. (But you should go ahead and look this up if you really want to know. You will learn a lot.)

A dereference operation looks at the address of the reference variable, and goes to that position in memory to retrieve the pointee stored there. An assignment of one reference variable to another just copies the numeric memory location. This is exactly like what happens when making an assignment between two int variables: The value is simply copied from one to the other. The value of null is always a special value that Java will never use as the location of any legal pointee. A bad reference is really just a reference which contains a null value. Java's runtime environment is constantly watching for a dereference of a reference variable with a null value, so it can catch it right away if that happens.

   «  5.1. Pointers Chapter Introduction   ::   Contents   ::   5.3. Local Memory  »

nsf

© Copyright 2016 by OpenDSA Project Contributors and distributed under an MIT license. Last updated on Sep 26, 2017. Created using Sphinx 1.2.
Close Window