Debugging

How To Avoid Debugging

  • First Defense: Make Bugs Impossible
  • Second Defense: Localize Bugs
  • Assertions
  • What to Assert
  • What Not to Assert
  • Incremental Development
  • Modularity & Encapsulation

Objectives

The topic of this chapter is debugging – or rather, how to avoid debugging entirely, or keep it easy when you have to do it.

First Defense: Make Bugs Impossible

The best defense against bugs is to make them impossible by design.

One way that we’ve already talked about is [static checking]2. Static checking eliminates many bugs by catching them at compile time.

There are also some simple examples of dynamic checking. For example, Java makes array overflow bugs impossible by catching them dynamically. If you try to use an index outside the bounds of an array or a List, then Java automatically produces an error. Older languages like C and C++ silently allow the bad access, which leads to bugs and security vulnerabilities.

Immutability (immunity from change) is another design principle that prevents bugs. An immutable type is a type whose values can never change once they have been created.

String is an immutable type. There are no methods that you can call on a String that will change the sequence of characters that it represents. Strings can be passed around and shared without fear that they will be modified by other code.

Java also gives us immutable references: variables declared with the keyword final, which can be assigned once but never reassigned. It’s good practice to use final for declaring the parameters of a method and as many local variables as possible. Like the type of the variable, these declarations are important documentation, useful to the reader of the code and statically checked by the compiler.

Consider this example:

1 final char[] vowels = new char[] { 'a', 'e', 'i', 'o', 'u' };

The vowels variable is declared final, but is it really unchanging? Which of the following statements will be illegal (caught statically by the compiler), and which will be allowed?

1 vowels = new char[] { 'x', 'y', 'z' };
2 vowels[0] = 'z';

Be careful about what final means! It only makes the reference immutable, not necessarily the object that the reference points to.

Second Defense: Localize Bugs

If we can’t prevent bugs, we can try to localize them to a small part of the program, so that we don’t have to look too hard to find the cause of a bug. When localized to a single method or small module, bugs may be found simply by studying the program text.

We already talked about fail fast: the earlier a problem is observed (the closer to its cause), the easier it is to fix.

Let’s begin with a simple example:

1 /**
2  * @param x  requires x >= 0
3  * @return approximation to square root of x
4  */
5 public double sqrt(double x) { ... }

Now suppose somebody calls sqrt with a negative argument. What’s the best behavior for sqrt? Since the caller has failed to satisfy the requirement that x should be nonnegative, sqrt is no longer bound by the terms of its contract, so it is technically free to do whatever it wants: return an arbitrary value, or enter an infinite loop, or melt down the CPU. Since the bad call indicates a bug in the caller, however, the most useful behavior would point out the bug as early as possible. We do this by inserting a runtime assertion that tests the precondition. Here is one way we might write the assertion:

1 /**
2  * @param x  requires x >= 0
3  * @return approximation to square root of x
4  */
5 public double sqrt(double x) {
6     if (! (x >= 0)) throw new AssertionError();
7     ...
8 }

When the precondition is not satisfied, this code terminates the program by throwing an AssertionError exception. The effects of the caller’s bug are prevented from propagating.

Checking preconditions is an example of defensive programming. Real programs are rarely bug-free. Defensive programming offers a way to mitigate the effects of bugs even if you don’t know where they are.

Assertions

It is common practice to define a procedure for these kinds of defensive checks, usually called assert:

1 assert (x >= 0);

This approach abstracts away from what exactly happens when the assertion fails. The failed assert might exit; it might record an event in a log file; it might email a report to a maintainer.

Assertions have the added benefit of documenting an assumption about the state of the program at that point. To somebody reading your code, assert(x>=0) says “at this point, it should always be true that x >= 0.” Unlike a comment, however, an assertion is executable code that enforces the assumption at runtime.

In Java, runtime assertions are a built-in feature of the language. The simplest form of the assert statement takes a boolean expression, exactly as shown above, and throws AssertionError if the boolean expression evaluates to false:

1 assert x >= 0;

An assert statement may also include a description expression, which is usually a string, but may also be a primitive type or a reference to an object. The description is printed in an error message when the assertion fails, so it can be used to provide additional details to the programmer about the cause of the failure. The description follows the asserted expression, separated by a colon. For example:

1 assert (x >= 0) : "x is " + x;

If x == -1, then this assertion fails with the error message

x is -1

along with a stack trace that tells you where the assert statement was found in your code and the sequence of calls that brought the program to that point. This information is often enough to get started in finding the bug.

A serious problem with Java assertions is that assertions are off by default.

If you just run your program as usual, none of your assertions will be checked! Java’s designers did this because checking assertions can sometimes be costly to performance. For most applications, however, assertions are not expensive compared to the rest of the code, and the benefit they provide in bug-checking is worth that small cost in performance.

So you have to enable assertions explicity by passing -ea (which stands for enable assertions) to the Java virtual machine. In Eclipse, you enable assertions by going to Run → Run Configurations → Arguments, and putting -ea in the VM arguments box. It’s best, in fact, to enable them by default by going to Preferences → Java → Installed JREs → Edit → Default VM Arguments.

It’s always a good idea to have assertions turned on when you’re running JUnit tests. You can ensure that assertions are enabled using the following test case:

1 @Test(expected=AssertionError.class)
2 public void testAssertionsEnabled() {
3     assert false;
4 }

If assertions are turned on as desired, then assert false throws an AssertionError. The annotation (expected=AssertionError.class) on the test expects and requires this error to be thrown, so the test passes. If assertions are turned off, however, then the body of the test will do nothing, failing to throw the expected exception, and JUnit will mark the test as failing.

Note that the Java assert statement is a different mechanism from the JUnit methods assertTrue(), assertEquals(), etc. They all assert a predicate about your code, but are designed for use in different contexts. The assert statement should be used in implementation code, for defensive checks inside the implementation. JUnit assert...() methods should be used in JUnit tests, to check the result of a test. The assert statements don’t run without -ea, but the JUnit assert...() methods always run.

What to Assert

Here are some things you should assert:

Method argument requirements, like we saw for sqrt.

Method return value requirements. This kind of assertion is sometimes called a self check. For example, the sqrt method might square its result to check whether it is reasonably close to x:

1 public double sqrt(double x) {
2     assert x >= 0;
3     double r;
4     ... // compute result r
5     assert Math.abs(r*r - x) < .0001;
6     return r;
7 }

Covering all cases. If a conditional statement or switch does not cover all the possible cases, it is good practice to use an assertion to block the illegal cases:

1 switch (vowel) {
2   case 'a':
3   case 'e':
4   case 'i':
5   case 'o':
6   case 'u': return "A";
7   default: Assert.fail();
8 }

The assertion in the default clause has the effect of asserting that vowel must be one of the five vowel letters.

When should you write runtime assertions? As you write the code, not after the fact. When you’re writing the code, you have the invariants in mind. If you postpone writing assertions, you’re less likely to do it, and you’re liable to omit some important invariants.

What Not to Assert

Runtime assertions are not free. They can clutter the code, so they must be used judiciously. Avoid trivial assertions, just as you would avoid uninformative comments. For example: java // don't do this: x = y + 1; assert x == y+1; This assertion doesn’t find bugs in your code. It finds bugs in the compiler or Java virtual machine, which are components that you should trust until you have good reason to doubt them. If an assertion is obvious from its local context, leave it out.

Never use assertions to test conditions that are external to your program, such as the existence of files, the availability of the network, or the correctness of input given by the user. Assertions test the internal state of your program to ensure that it is within the bounds of its specification. When an assertion fails, it indicates that the program has run off the rails in some sense, into a state in which it was not designed to function properly. Assertion failures therefore indicate bugs. External failures are not bugs, and there is no change you can make to your program in advance that will prevent them from happening. External failures should be handled using exceptions instead.

Many assertion mechanisms are designed so that assertions are executed only during testing and debugging, and turned off when the program is released to users. Java’s assert statement behaves this way. The advantage of this approach is that you can write very expensive assertions that would otherwise seriously degrade the performance of your program. For example, a procedure that searches an array using binary search has a requirement that the array be sorted. Asserting this requirement requires scanning through the entire array, however, turning an operation that should run in logarithmic time into one that takes linear time. You should be willing (eager!) to pay this cost during testing, since it makes debugging much easier, but not after the program is released to users.

However, disabling assertions in release has a serious disadvantage. With assertions disabled, a program has far less error checking when it needs it most. Novice programmers are usually much more concerned about the performance impact of assertions than they should be. Most assertions are cheap, so they should not be disabled in the official release.

Since assertions may be disabled, the correctness of your program should never depend on whether or not the assertion expressions are executed. In particular, asserted expressions should not have side-effects. For example, if you want to assert that an element removed from a list was actually found in the list, don’t write it like this: java // don't do this: assert list.remove(x);

If assertions are disabled, the entire expression is skipped, and x is never removed from the list. Write it like this instead: java boolean found = list.remove(x); assert found; For CPEN 221, you are required to have assertions turned on, all the time. Make sure you did this in Eclipse. If you don’t have assertions turned on, you will be sad, and the course staff won’t have much sympathy.

Incremental Development

A great way to localize bugs to a tiny part of the program is incremental development. Build only a bit of your program at a time, and test that bit thoroughly before you move on. That way, when you discover a bug, it’s more likely to be in the part that you just wrote, rather than anywhere in a huge pile of code.

Our class on testing talked about two techniques that help with this:

  • Unit testing: when you test a module in isolation, you can be confident that any bug you find is in that unit – or maybe in the test cases themselves.
  • Regression testing: when you’re adding a new feature to a big system, run the regression test suite as often as possible. If a test fails, the bug is probably in the code you just changed.

Modularity & Encapsulation

You can also localize bugs by better software design.

Modularity. Modularity means dividing up a system into components, or modules, each of which can be designed, implemented, tested, reasoned about, and reused separately from the rest of the system. The opposite of a modular system is a monolithic system – big and with all of its pieces tangled up and dependent on each other.

A program consisting of a single, very long main() function is monolithic – harder to understand, and harder to isolate bugs in. By contrast, a program broken up into small functions and classes is more modular.

Encapsulation. Encapsulation means building walls around a module (a hard shell or capsule) so that the module is responsible for its own internal behavior, and bugs in other parts of the system can’t damage its integrity.

One kind of encapsulation is access control, using public and private to control the visibility and accessibility of your variables and methods. A public variable or method can be accessed by any code (assuming the class containing that variable or method is also public). A private variable or method can only be accessed by code in the same class. Keeping things private as much as possible, especially for variables, provides encapsulation, since it limits the code that could inadvertently cause bugs.

Another kind of encapsulation comes from variable scope. The scope of a variable is the portion of the program text over which that variable is defined, in the sense that expressions and statements can refer to the variable. A method parameter’s scope is the body of the method. A local variable’s scope extends from its declaration to the next closing curly brace. Keeping variable scopes as small as possible makes it much easier to reason about where a bug might be in the program. For example, suppose you have a loop like this:

1 for (i = 0; i < 100; ++i) {
2     ...
3     doSomeThings();
4     ...
5 }

…and you’ve discovered that this loop keeps running forever – i never reaches 100. Somewhere, somebody is changing i. But where? If i is declared as a global variable like this:

1 public static int i;
2 ...
3 for (i = 0; i < 100; ++i) {
4     ...
5     doSomeThings();
6     ...
7 }

…then its scope is the entire program. It might be changed anywhere in your program: by doSomeThings(), by some other method that doSomeThings() calls, by a concurrent thread running some completely different code. But if i is instead declared as a local variable with a narrow scope, like this:

1 for (int i = 0; i < 100; ++i) {
2     ...
3     doSomeThings();
4     ...
5 }

… then the only place where i can be changed is within the for statement – in fact, only in the … parts that we’ve omitted. You don’t even have to consider doSomeThings(), because doSomeThings() doesn’t have access to this local variable.

Minimizing the scope of variables is a powerful practice for bug localization. Here are a few rules that are good for Java:

  • Always declare a loop variable in the for-loop initializer. So rather than declaring it before the loop:
1 int i;
2 for (i = 0; i < 100; ++i) {

which makes the scope of the variable the entire rest of the outer curly-brace block containing this code, you should do this:

1 for (int i = 0; i < 100; ++i) {

which makes the scope of i limited just to the for loop.

  • Declare a variable only when you first need it, and in the innermost curly-brace block that you can. Variable scopes in Java are curly-brace blocks, so put your variable declaration in the innermost one that contains all the expressions that need to use the variable. Don’t declare all your variables at the start of the function – it makes their scopes unnecessarily large. But note that in languages without static type declarations, like Python and Javascript, the scope of a variable is normally the entire function anyway, so you can’t restrict the scope of a variable with curly braces, alas.
  • Avoid global variables. Very bad idea, especially as programs get large. Global variables are often used as a shortcut to provide a parameter to several parts of your program. It’s better to just pass the parameter into the code that needs it, rather than putting it in global space where it can inadvertently reassigned.

Summary

In this reading, we looked at some ways to minimize the cost of debugging:

  • avoid debugging
    • make bugs impossible with techniques like static typing, automatic dynamic checking, and immutable types and references
  • keep bugs confined
    • failing fast with assertions keeps a bug’s effects from spreading
    • incremental development and unit testing confine bugs to your recent code
    • scope minimization reduces the amount of the program you have to search

Thinking about our three main measures of code quality:

  • Safe from bugs. We’re trying to prevent them and get rid of them.
  • Easy to understand. Techniques like static typing, final declarations, and assertions are additional documentation of the assumptions in your code. Variable scope minimization makes it easier for a reader to understand how the variable is used, because there’s less code to look at.
  • Ready for change. Assertions and static typing document the assumptions in an automatically-checkable way, so that when a future programmer changes the code, accidental violations of those assumptions are detected.

Test Yourself

How to Debug

Instance Diagrams

It will be useful for us to draw pictures of what’s happening at runtime, in order to understand subtle questions. Instance diagrams represent the internal state of an object or even a program at runtime – its stack (methods in progress and their local variables) and its heap (objects that currently exist).

Why should we use instance diagrams?

  • To talk to each other through pictures (in class and in team meetings)
  • To illustrate concepts like primitive types vs. object types, immutable values vs. immutable references, pointer aliasing, stack vs. heap, abstractions vs. concrete representations.
  • To help explain your design for your team project (with each other and with your TA)
  • To pave the way for richer design notations in subsequent courses.

Although the diagrams in this course use examples from Java, the notation can be applied to any modern programming language, e.g., Python, Javascript, C++, Ruby.

Primitive values

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Debugging/primitives.png” alt=”primitive values in an instance diagram” width=”300”></img>

Primitive values are represented by bare constants. The incoming arrow is a reference to the value from a variable or an object field.

Object values

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Debugging/objects.png” alt=”object values in an instance diagram” width=”400”></img>

An object value is a circle labeled by its type. When we want to show more detail, we write field names inside it, with arrows pointing out to their values. For still more detail, the fields can include their declared types. Some people prefer to write x:int instead of int x, but both are fine.

Mutating Values vs. Reassigning Variables

Instance diagrams give us a way to visualize the distinction between changing a variable and changing a value. When you assign to a variable or a field, you’re changing where the variable’s arrow points. You can point it to a different value.

When you assign to the contents of a mutable value – such as an array or list – you’re changing references inside that value.

Immutability (immunity from change) is a major design principle in this course. Immutable types are types whose values can never change once they have been created.

Java also gives us immutable references: variables that are assigned once and never reassigned.To make a reference immutable, declare it with the keyword final:

1 final int n = 5;

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Debugging/final-reference.png” alt=”final reference is a double arrow” width=”200”></img>

If the Java compiler isn’t convinced that your final variable will only be assigned once at runtime, then it will produce a compiler error. So final gives you static checking for immutable references.

In an instance diagram, an immutable reference (final) is denoted by a double arrow. Here’s an object whose id never changes (it can’t be reassigned to a different number), but whose age can change.

Immutable Objects vs. Mutable Objects

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Debugging/reassignment.png” alt=”reassigning a variable” width=”200”></img>

String is immutable: once created, a String object always has the same value. To add something to the end of a String, you have to create a new String object: java String s = "a"; s = s.concat("b"); /// s+="b" and s=s+"b" mean the same thing as this call

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Debugging/integer.png” alt=”Integer is immutable” width=”200”></img>

Immutable objects (intended by their designer to always represent the same value) are denoted by a double border. For example, here’s an Integer object, the result of new Integer(7). By design, this Integer object can never change value during its lifetime. There is no method of Integer that will change it to a different integer value.

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Debugging/mutation.png” alt=”mutating an object” width=”200”></img>

By contrast, StringBuilder (another built-in Java class) is a mutable object that represents a string of characters. It has methods that change the value of the object, rather than just returning new values: java StringBuilder sb = new StringBuilder("a"); sb.append("b");

StringBuilder has other methods as well, for deleting parts of the string, inserting in the middle, or changing individual characters.

So what? In both cases, you end up with s and sb referring to the string of characters “abcdef”. The difference between mutability and immutability doesn’t matter much when there’s only one reference to the object. But there are big differences in how they behave when there are other references to the object. For example, when another variable t points to the same String object as s, and another variable tb points to the same StringBuilder as sb, then the differences between the immutable and mutable objects become more evident:

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Debugging/string-vs-stringbuilder.png” alt=”different behavior of String and StringBuilder” width=”500”></img>

1 String t = s;
2 t = t + "c";
3 
4 StringBuilder tb = sb;
5 tb.append("c");

Why do we need the mutable StringBuilder in programming? A common use for it is to concatenate a large number of strings together, like this:

1 String s = "";
2 for (int i = 0; i < n; ++i) {
3     s = s + n;
4 }

Using immutable Strings, this makes a lot of temporary copies – the first number of the string (“0”) is actually copied n times in the course of building up the final string, the second number is copied n-1 times, and so on. It actually costs O(n^2) time just to do all that copying, even though we only concatenated n elements.

StringBuilder is designed to minimize this copying. It uses a simple but clever internal data structure to avoid doing any copying at all until the very end, when you ask for the final String with a toString() call:

1 StringBuilder sb = new StringBuilder();
2 for (int i = 0; i < n; ++i) {
3   sb.append(String.valueOf(n));
4 }
5 String s = sb.toString();

Getting good performance is one reason why we use mutable objects. Another is convenient sharing: two parts of your program can communicate more conveniently by sharing a common mutable data structure.

But the convenience of mutable data comes with big risks. Mutability makes it harder to understand what your program is doing, and much harder to enforce contracts.

Arrays and Lists

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Debugging/arrays-and-lists.png” alt=”Arrays and Lists” width=”500”></img>

Like other object values, arrays and lists are labeled with their type. In lieu of field names, we label the outgoing arrows with indexes 0, 1, 2, … When the sequence of elements is obvious, we may omit the index labels.

Both the array and List objects are mutable, as indicated by the single-line border and the single-line arrows that can be reassigned.

Debug Systematically

Sometimes you have no choice but to debug, however – particularly when the bug is found only when you plug the whole system together, or reported by a user after the system is deployed, in which case it may be hard to localize it to a particular module. For those situations, we can suggest a systematic strategy for more effective debugging.

Reproduce the Bug

Start by finding a small, repeatable test case that produces the failure. If the bug was found by regression testing, then you’re in luck; you already have a failing test case in your test suite. If the bug was reported by a user, it may take some effort to reproduce the bug. For graphical user interfaces and multithreaded programs, a bug may be hard to reproduce consistently if it depends on timing of events or thread execution.

Nevertheless, any effort you put into making the test case small and repeatable will pay off, because you’ll have to run it over and over while you search for the bug and develop a fix for it. Furthermore, after you’ve successfully fixed the bug, you’ll want to add the test case to your regression test suite, so that the bug never crops up again. Once you have a test case for the bug, making this test work becomes your goal.

Understand the Location and Cause of the Bug

To localize the bug and its cause, you can use the scientific method:

  1. Study the data. Look at the test input that causes the bug, and the incorrect results, failed assertions, and stack traces that result from it.
  2. Hypothesize.
    • Propose a hypothesis, consistent with all the data, about where the bug might be, or where it cannot be.
    • It’s good to make this hypothesis general at first. Here’s an example. You’re developing a web browser, and a user has found that displaying a certain web page causes the wrong text to appear on the screen. You might hypothesize that the bug is not in the networking code that fetches the page from the server, but in one of the modules that parses the web page or displays it.
  3. Experiment. Devise an experiment that tests your hypothesis. The experiment might be a different test case. In our web browser example, you might test your hypothesis by downloading the page to disk and loading it from a disk file instead of over the network. Another experiment inserts probes in the running program – print statements, assertions, or debugger breakpoints. It’s tempting to try to insert fixes to the hypothesized bug, instead of mere probes. This is almost always the wrong thing to do, because your fixes may just mask the true bug. For example, if you’re getting an ArrayOutOfBoundsException, try to understand what’s going on first. Don’t just add code to avoid the exception without fixing the real problem.
  4. Repeat. Add the data you collected from your experiment to what you knew before, and make a fresh hypothesis.

Bug localization by binary search.

Debugging is a search process, and you can sometimes use binary search to speed up the process.

For example, in a web browser, the web page might flow through four modules before being displayed on the screen.

To do a binary search, you would divide this workflow in half, guessing that the bug is found somewhere in the first two modules, and insert probes (like breakpoints, print statements, or assertions) after the second module to check its results.

From the results of that experiment, you would further divide in half.

Prioritize your hypotheses.

When making your hypothesis, you may want to keep in mind that different parts of the system have different likelihoods of failure.

For example, old, well-tested code is probably more trustworthy than recently-added code.

Java library code is probably more trustworthy than yours.

The Java compiler and runtime, operating system platform, and hardware are increasingly more trustworthy, because they are more tried and tested.

You should trust these lower levels until you’ve found good reason not to.

Make sure your source code and object code are up to date.

Pull the latest version from the repository, and delete all your .class files and recompile everything (in Eclipse, this is done by <kbd>Project / Clean</kbd>).

Swap components.

If you have another implementation of a module that satisfies the same interface, and you suspect the module, you may try swapping in the alternative.

For example, if you suspected java.util.ArrayList, you could swap in java.util.LinkedList instead. If you suspect the binarySearch() method, then substitute a simpler linearSearch() instead. If you suspect the Java runtime, run with a different version of Java. If you suspect the operating system, run your program on a different OS. If you suspect the hardware, run on a different machine.

You can waste a lot of time swapping unfailing components, however, so don’t do this unless you have good reason to suspect a component.

Get help.

It often helps to explain your problem to someone else, even if the person you’re talking to has no idea what you’re talking about. Teaching assistants and fellow students usually do know what you’re talking about, so they’re even better.

Sleep on it.

If you’re too tired, you won’t be an effective debugger. Trade latency for efficiency.

Fix the Bug

Once you’ve found the bug and understand its cause, the third step is to devise a fix for it. Avoid the temptation to slap a patch on it and move on. Ask yourself whether the bug was a coding error, like a misspelled variable or interchanged method parameters, or a design error, like an underspecified or insufficient interface. Design errors may suggest that you step back and revisit your design, or at the very least consider all the other clients of the failing interface to see if they suffer from the bug too.

Think also whether the bug has any relatives. If I just found a divide-by-zero error here, did I do that anywhere else in the code? Try to make the code safe from future bugs like this. Also consider what effects your fix will have. Will it break any other code?

Finally, after you have applied your fix, add the bug’s test case to your regression test suite, and run all the tests to assure yourself that (a) the bug is fixed, and (b) no new bugs have been introduced.

Summary

In this reading, we looked at instance diagrams to understand the difference between assignment and mutation. In instance diagrams, + objects are represented by circles with a type and fields inside them + immutable objects have a double border + a variable or field reference is represented by an arrow + an immutable reference is an double arrow

Debug systematically + reproduce the bug as a test case, and put it in your regression suite + find the bug using the scientific method + fix the bug thoughtfully, not slapdash

Mutability and Immutability

</p>

Risks of Mutation

Recall from our discussion of instance diagrams that some objects are immutable: once created, they always represent the same value. Other objects are mutable: they have methods that change the value of the object.

String is an example of an immutable type. A String object always represents the same string. StringBuilder is an example of a mutable type. It has methods to delete parts of the string, insert or replace characters, etc.

Mutable types seem much more powerful than immutable types. If you were shopping in the Datatype Supermarket, and you had to choose between a boring immutable String and a super-powerful-do-anything mutable StringBuilder, why on earth would you choose the immutable one? StringBuilder should be able to do everything that String can do, plus set() and append() and everything else.

The answer is that immutable types are safer from bugs, easier to understand, and more ready for change. Here are two examples that illustrate why.

Risky example #1: passing mutable values

Let’s start with a simple method that sums the integers in a list:

1 /** @return the sum of the numbers in the list */
2 public static int sum(List<Integer> list) {
3     int sum = 0;
4     for (int x : list)
5         sum += x;
6     return sum;
7 }

Suppose we also need a method that sums the absolute values. Following good DRY practice (Don’t Repeat Yourself), the implementer writes a method that uses sum():

1 /** @return the sum of the absolute values of the numbers in the list */
2 public static int sumAbsolute(List<Integer> list) {
3     // let's reuse sum(), because DRY, so first we take absolute values
4     for (int i = 0; i < list.size(); ++i)
5         list.set(i, Math.abs(list.get(i)));
6     return sum(list);
7 }

Notice that this method does its job by mutating the list directly. It seemed sensible to the implementer, because it’s more efficient to reuse the existing list. If the list is millions of items long, then you’re saving the time and memory of generating a new million-item list of absolute values. So the implementer has two very good reasons for this design: DRY, and performance. But the resulting behavior will be very surprising to anybody who uses it!

For example:

1 // meanwhile, somewhere else in the code...
2 public static void main(String[] args) {
3     // ...
4     List<Integer> myData = Arrays.asList(-5, -3, -2);
5     System.out.println(sumAbsolute(myData));
6     System.out.println(sum(myData));
7 }

What will this code print? Will it be 10 followed by -10? Or something else?

Let’s think about the key points here:

  • Safe from bugs? In this example, it’s easy to blame the implementer of sumAbsolute() for going beyond what its spec allowed. But really, passing mutable objects around is a latent bug. It’s just waiting for some programmer to inadvertently mutate that list, often with very good intentions like reuse or performance, but resulting in a bug that may be very hard to track down.
  • Easy to understand? When reading main(), what would you assume about sum() and sumAbsolute()? Is it clearly visible to the reader that myData gets changed by one of them?

Risky example #2: returning mutable values

We just saw an example where passing a mutable object to a function caused problems. What about returning a mutable object?

Let’s consider Date, one of the built-in Java classes. Date happens to be a mutable type. Suppose we write a method that determines the first day of spring:

1 /** @return the first day of spring this year */
2 public static Date startOfSpring() {
3     return askGroundhog();
4 }

Here we’re using the well-known Groundhog algorithm for calculating when spring starts (Harold Ramis, Bill Murray, et al. Groundhog Day, 1993).

Clients start using this method, for example to plan their big parties: java // somewhere else in the code... public static void partyPlanning() { Date partyDate = startOfSpring(); // ... }

All the code works and people are happy. Now, independently, two things happen. First, the implementer of startOfSpring() realizes that the groundhog is starting to get annoyed from being constantly asked when spring will start. So the code is rewritten to ask the groundhog at most once, and then cache the groundhog’s answer for future calls:

1 /** @return the first day of spring this year */
2 public static Date startOfSpring() {
3     if (groundhogAnswer == null) groundhogAnswer = askGroundhog();
4     return groundhogAnswer;
5 }
6 private static Date groundhogAnswer = null;

(Aside: note the use of a private static variable for the cached answer. Would you consider this a global variable, or not?)

Second, one of the clients of startOfSpring() decides that the actual first day of spring is too cold for the party, so the party will be exactly a month later instead:

1 // somewhere else in the code...
2 public static void partyPlanning() {
3     // let's have a party one month after spring starts!
4     Date partyDate = startOfSpring();
5     partyDate.setMonth(partyDate.getMonth() + 1);
6     // ... uh-oh. what just happened?
7 }

Aside: the code above also has a latent bug in the way it adds a month. Why? What does it implicitly assume about when spring starts?

What happens when these two decisions interact? Even worse, think about who will first discover this bug — will it be startOfSpring()? Will it be partyPlanning()? Or will it be some completely innocent third piece of code that also calls startOfSpring()?

Key points:

  • Safe from bugs? Again we had a latent bug that reared its ugly head.
  • Ready for change? Obviously the mutation of the date object is a change, but that’s not the kind of change we’re talking about when we say “ready for change.” Instead, the question is whether the code of the program can be easily changed without rewriting a lot of it or introducing bugs. Here we had two apparently independent changes, by different programmers, that interacted to produce a bad bug.

In both of these examples — the List<Integer> and the Date — the problems would have been completely avoided if the list and the date had been immutable types. The bugs would have been impossible by design.

In fact, you should never use Date! Use one of the classes from package java.time: LocalDateTime, Instant, etc. All guarantee in their specifications that they are immutable.

This example also illustrates why using mutable objects can actually be bad for performance. The simplest solution to this bug, which avoids changing any of the specifications or method signatures, is for startOfSpring() to always return a copy of the groundhog’s answer:

1 return new Date(groundhogAnswer.getTime());

This pattern is defensive copying, and we’ll see much more of it when we talk about abstract data types. The defensive copy means partyPlanning() can freely stomp all over the returned date without affecting startOfSpring()’s cached date. But defensive copying forces startOfSpring() to do extra work and use extra space for every client — even if 99% of the clients never mutate the date it returns. We may end up with lots of copies of the first day of spring throughout memory. If we used an immutable type instead, then different parts of the program could safely share the same values in memory, so less copying and less memory space is required.

Immutability can be more efficient than mutability, because immutable types never need to be defensively copied.

Aliasing is what makes mutable types risky

Actually, using mutable objects is just fine if you are using them entirely locally within a method, and with only one reference to the object. What led to the problem in the two examples we just looked at was having multiple references, also called aliases, for the same mutable object.

Walking through the examples with a instance diagram will make this clear, but here’s the outline:

  • In the List example, the same list is pointed to by both list (in sum and sumAbsolute) and myData (in main). One programmer (sumAbsolute’s) thinks it’s ok to modify the list; another programmer (main’s) wants the list to stay the same. Because of the aliases, main’s programmer loses.
  • In the Date example, there are two variable names that point to the Date object, groundhogAnswer and partyDate. These aliases are in completely different parts of the code, under the control of different programmers who may have no idea what the other is doing.

Draw instance diagrams on paper first, but your real goal should be to develop the instance diagram in your head, so you can visualize what’s happening in the code.

Specifications for mutating methods

At this point it should be clear that when a method performs mutation, it is crucial to include that mutation in the method’s spec, using [the structure we discussed in the previous reading][specs for mutating methods].

(Now we’ve seen that even when a particular method doesn’t mutate an object, that object’s mutability can still be a source of bugs.)

Here’s an example of a mutating method:

1 static void sort(List<String> lst)
2 // requires: nothing
3 // effects: puts lst in sorted order, i.e. lst[i] <= lst[j] for all 0 <= i < j <\
4  lst.size()

And an example of a method that does not mutate its argument:

1 static List<String> toLowerCase(List<String> lst)
2 // requires: nothing
3 // effects:  returns a new list t where t[i] = lst[i].toLowerCase()

If the effects do not describe mutation, in CPEN 221, we assume mutation of the inputs is implicitly disallowed.

Iterating over arrays and lists

The next mutable object we’re going to look at is an iterator — an object that steps through a collection of elements and returns the elements one by one.

Iterators are used under the covers in Java when you’re using a for loop to step through a List or array.

This code:

1 List<String> lst = ...;
2 for (String str : lst) {
3     System.out.println(str);
4 }

is rewritten by the compiler into something like this:

1 List<String> lst = ...;
2 Iterator iter = lst.iterator();
3 while (lst.hasNext()) {
4 	String str = iter.next();
5 	System.out.println(str);
6 }

An iterator has two methods:

  • next() returns the next element in the collection
  • hasNext() tests whether the iterator has reached the end of the collection.

Note that the next() method is a mutator method, not only returning an element but also advancing the iterator so that the subsequent call to next() will return a different element.

You can also look at the Java API definition of Iterator.

MyIterator

To better understand how an iterator works, here’s a simple implementation of an iterator for ArrayList<String>:

 1 /**
 2  * A MyIterator is a mutable object that iterates over
 3  * the elements of an ArrayList<String>, from first to last.
 4  * This is just an example to show how an iterator works.
 5  * In practice, you should use the ArrayList's own iterator
 6  * object, returned by its iterator() method.
 7  */
 8 public class MyIterator {
 9     
10     private final ArrayList<String> list;
11     private int index;
12     // list[index] is the next element that will be returned
13     // by next()
14     // index == list.size() means no more elements to return
15     
16     /**
17      * Make an iterator.
18      * @param list list to iterate over
19      */
20     public MyIterator(ArrayList<String> list) {
21         this.list = list;
22         this.index = 0;
23     }
24     
25     /**
26      * Test whether the iterator has more elements to return.
27      * @return true if next() will return another element,
28      *         false if all elements have been returned
29      */
30     public boolean hasNext() {
31         return index < list.size();
32     }
33     
34     /**
35      * Get the next element of the list.
36      * Requires: hasNext() returns true.
37      * Modifies: this iterator to advance it to the element 
38      *           following the returned element.
39      * @return next element of the list
40      */
41     public String next() {
42         final String str = list.get(index);
43         ++index;
44         return str;
45     }
46 }

MyIterator makes use of a few Java language features that are different from the classes we’ve been writing up to this point. Make sure you read the Java Tutorial sections required for this reading so that you understand them:

Instance variables, also called fields in Java. Instance variables differ from method parameters and local variables; the instance variables are stored in the object instance and persist for longer than a method call. What are the instance variables of MyIterator?

A constructor, which makes a new object instance and initializes its instance variables. Where is the constructor of MyIterator?

The static keyword is missing from MyIterator’s methods, which means they are instance methods that must be called on an instance of the object, e.g. iter.next().

The this keyword is used at one point to refer to the instance object, in particular to refer to an instance variable (this.list). This was done to disambiguate two different variables named list (an instance variable and a constructor parameter). Most of MyIterator’s code refers to instance variables without an explicit this, but this is just a convenient shorthand that Java supports — e.g., index actually means this.index.

private is used for the object’s internal state and internal helper methods, while public indicates methods and constructors that are intended for clients of the class (access control).

final is used to indicate which parts of the object’s internal state can change and which can’t. index is allowed to change (next() updates it as it steps through the list), but list cannot (the iterator has to keep pointing at the same list for its entire life — if you want to iterate through another list, you’re expected to create another iterator object).

Here’s a instance diagram showing a typical state for a MyIterator object in action: <img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Mutability/iterator.png” width=”400”></img>

Note that we drew the arrow from list with a double line, to indicate that it’s final. That means the arrow can’t change once it’s drawn. But the ArrayList object it points to is mutable — elements can be changed within it — and declaring list as final has no effect on that.

Why do iterators exist? There are many kinds of collection data structures (linked lists, maps, hash tables) with different kinds of internal representations. The iterator concept allows a single uniform way to access them all, so that client code is simpler and the collection implementation can change without changing the client code that iterates over it. Most modern languages (including Python, C#, and Ruby) use the notion of an iterator. It’s an effective design pattern (a well-tested solution to a common design problem).

We’ll see many other design patterns as we move through the course.

Mutation undermines an iterator

Let’s try using our iterator for a simple job. Suppose we have a list of UBC courses represented as strings, like ["CPEN 221", "CPEN 211", "CPEN 281", "MATH 253"]. We want a method dropCPENCourses that will delete the CPEN courses from the list, leaving the other courses behind.

Following good practices, we first write the spec: java /** * Drop all subjects that are from CPEN. * Modifies subjects list by removing subjects that start with CPEN. * * @param courseList list of UBC courses registered for */ public static void dropCPENCourses(ArrayList<String> courseList)

Note that dropCPENCourses has a frame condition (the modifies clause) in its contract, warning the client that its list argument will be mutated.

Next, following test-first programming, we devise a testing strategy that partitions the input space, and choose test cases to cover that partition:

 1     // Testing strategy:
 2     //   subjects.size: 0, 1, n
 3     //   contents: no CPEN course, one CPEN course, all CPEN courses
 4     //   position: CPEN course at start, CPEN course in middle, CPEN course at e\
 5 nd
 6 
 7     // Test cases:
 8     //   [] => []
 9     //   [“MATH 253”] => [“MATH 253”]
10     //   [“ENGL 112”, “MATH 253”, “ECON 102”] => [“ENGL 112”, “MATH 253”, “ECON \
11 102”]
12     //   [“PHIL 120”, “CPEN 221”, “MATH 256”] => [“PHIL 120”, “MATH 256”]
13     //   [“CPEN 221”, “CPEN 211”, “CPEN 281”] => []

Finally, we implement it:

1 public static void dropCPENCourses(ArrayList<String> courseList) {
2     MyIterator iter = new MyIterator(courseList);
3     while (iter.hasNext()) {
4         String course = iter.next();
5         if (course.startsWith("CPEN)) {
6             courseList.remove(subject);
7         }
8     }
9 }

Now we run our test cases, and they work! … almost. The last test case fails:

1     // dropCPENCourses([“CPEN 221”, “CPEN 211”, “CPEN 281”])
2     //   expected [], actual [“CPEN 211”]

We got the wrong answer: dropCPENCourses left a course behind in the list! Why? Trace through what happens. It will help to use a instance diagram showing the MyIterator object and the ArrayList object and update it while you work through the code.

Note that this isn’t just a bug in our MyIterator. The built-in iterator in ArrayList suffers from the same problem, and so does the for loop that’s syntactic sugar for it. The problem just has a different symptom. If you used this code instead:

1 for (String course : courseList) {
2     if (course.startsWith(“CPEN”)) {
3         courseList.remove(subject);
4     }
5 }

then you’ll get a ConcurrentModificationException. The built-in iterator detects that you’re changing the list under its feet, and cries foul. (How do you think it does that?)

How can you fix this problem? One way is to use the remove() method of Iterator, so that the iterator adjusts its index appropriately:

1 Iterator iter = courseList.iterator();
2 while (iter.hasNext()) {
3     String course = iter.next();
4     if (course.startsWith(“EECE”)) {
5         iter.remove(course);
6     }
7 }

This is actually more efficient as well, it turns out, because iter.remove() already knows where the element it should remove is, while courseList.remove() had to search for it again.

But this doesn’t fix the whole problem. What if there are other Iterators currently active over the same list? They won’t all be informed!

Mutation and contracts

Mutable objects can make simple contracts very complex

This is a fundamental issue with mutable data structures. Multiple references to the same mutable object (also called aliases for the object) may mean that multiple places in your program — possibly widely separated — are relying on that object to remain consistent.

To put it in terms of specifications, contracts can’t be enforced in just one place anymore, e.g. between the client of a class and the implementer of a class. Contracts involving mutable objects now depend on the good behavior of everyone who has a reference to the mutable object.

As a symptom of this non-local contract phenomenon, consider the Java collections classes, which are normally documented with very clear contracts on the client and implementer of a class. Try to find where it documents the crucial requirement on the client that we’ve just discovered - that you can’t modify a collection while you’re iterating over it. Who takes responsibility for it?

Can you find it?

The need to reason about global properties like this make it much harder to understand, and be confident in the correctness of, programs with mutable data structures. We still have to do it — for performance and convenience — but we pay a big cost in bug safety for doing so.

Mutable objects reduce changeability

Mutable objects make the contracts between clients and implementers more complicated, and reduce the freedom of the client and implementer to change. In other words, using objects that are allowed to change makes the code harder to change.

Here’s an example to illustrate the point.

The crux of our example will be the specification for this method, which looks up a username in UBC’s database and returns the user’s 9-digit identifier:

1 /**
2  * @param username username of person to look up
3  * @return the 9-digit UBC identifier for username.
4  * @throws NoSuchUserException if nobody with username is in UBC’s database
5  */
6 public static char[] getUBCId(String username) throws NoSuchUserException {     \
7    
8     // ... look up username in UBC’s database and return the 9-digit ID
9 }

A reasonable specification. Now suppose we have a client using this method to print out a user’s identifier:

1 char[] id = getUBCId("bitdiddle");
2 System.out.println(id);

Now both the client and the implementor separately decide to make a change. The client is worried about the user’s privacy, and decides to obscure the first 5 digits of the id:

1 char[] id = getUBCId("bitdiddle");
2 for (int i = 0; i < 5; ++i) {
3     id[i] = '*';
4 }
5 System.out.println(id);

The implementer is worried about the speed and load on the database, so the implementer introduces a cache that remembers usernames that have been looked up:

 1 private static Map<String, char[]> cache = new HashMap<String, char[]>();
 2 
 3 public static char[] getUBCId(String username) throws NoSuchUserException {     \
 4    
 5     // see if it's in the cache already
 6     if (cache.containsKey(username)) {
 7         return cache.get(username);
 8     }
 9     
10     // ... look up username in UBC’s database ...
11     
12     // store it in the cache for future lookups
13     cache.put(username, id);
14     return id;
15 }

These two changes have created a subtle bug. When the client looks up "bitdiddle" and gets back a char array, now both the client and the implementer’s cache are pointing to the same char array. The array is aliased. That means that the client’s obscuring code is actually overwriting the identifier in the cache, so future calls to getUBCId("bitdiddle") will not return the full 9-digit number, like “928432033”, but instead the obscured version “*****2033”.

Sharing a mutable object complicates a contract. If this contract failure went to software engineering court, it would be contentious. Who’s to blame here? Was the client obliged not to modify the object it got back? Was the implementer obliged not to hold on to the object that it returned?

Here’s one way we could have clarified the spec:

1 public static char[] getUBCId(String username) throws NoSuchUserException 
2   // requires: nothing
3   // effects: returns an array containing the 9-digit UBC identifier of username\
4 , or throws NoSuchUserException if nobody with username is in UBC’s database. Ca\
5 ller may never modify the returned array.

This is a bad way to do it. The problem with this approach is that it means the contract has to be in force for the entire rest of the program. It’s a lifetime contract! The other contracts we wrote were much narrower in scope; you could think about the precondition just before the call was made, and the postcondition just after, and you didn’t have to reason about what would happen for the rest of time.

Here’s a spec with a similar problem:

1 public static char[] getUBCId(String username) throws NoSuchUserException 
2   // requires: nothing
3   // effects: returns a new array containing the 9-digit UBC identifier of usern\
4 ame, or throws NoSuchUserException if nobody with username is in UBC's database.

This doesn’t entirely fix the problem either. This spec at least says that the array has to be fresh. But does it keep the implementer from holding an alias to that new array? Does it keep the implementer from changing that array or reusing it in the future for something else?

Here’s a much better spec:

1 public static String getUBCId(String username) throws NoSuchUserException 
2   // requires: nothing
3   // effects: returns the 9-digit UBC identifier of username, or throws NoSuchUs\
4 erException if nobody with username is in UBC's database.

The immutable String return value provides a guarantee that the client and the implementer will never step on each other the way they could with char arrays. It doesn’t depend on a programmer reading the spec comment carefully. String is immutable. Not only that, but this approach (unlike the previous one) gives the implementer the freedom to introduce a cache — a performance improvement.

Useful immutable types

Since immutable types avoid so many pitfalls, let’s enumerate some commonly-used immutable types in the Java API:

  • The primitive types and primitive wrappers are all immutable. If you need to compute with large numbers, BigInteger and BigDecimal are immutable.
  • Don’t use mutable Dates, use the appropriate immutable type from java.time based on the granularity of timekeeping you need.
  • The usual implementations of Java’s collections types — List, Set, Map — are all mutable: ArrayList, HashMap, etc. The Collections utility class has methods for obtaining unmodifiable views of these mutable collections:
    • Collections.unmodifiableList
    • Collections.unmodifiableSet
    • Collections.unmodifiableMap

    You can think of the unmodifiable view as a wrapper around the underlying list/set/map. A client who has a reference to the wrapper and tries to perform mutations — add, remove, put, etc. — will trigger an UnsupportedOperationException.

    Before we pass a mutable collection to another part of our program, we can wrap it in an unmodifiable wrapper. We should be careful at that point to lose our reference to the mutable collection, lest we accidentally mutate it. Just as a mutable object behind a final reference can be mutated, the mutable collection inside an unmodifiable wrapper can still be modified, defeating the wrapper.

  • Collections also provides methods for obtaining immutable empty collections: Collections.emptyList, etc. Nothing’s worse than discovering your definitely very empty list is suddenly definitely not empty.

Summary

In this reading, we saw that mutability is useful for performance and convenience, but it also creates risks of bugs by requiring the code that uses the objects to be well-behaved on a global level, greatly complicating the reasoning and testing we have to do to be confident in its correctness.

Make sure you understand the difference between an immutable object (like a String) and an immutable reference (like a final variable). Instance diagrams can help with this understanding.

Objects are values, represented by circles in a instance diagram, and an immutable one has a double border indicating that it never changes its value. A reference is a pointer to an object, represented by an arrow in the instance diagram, and an immutable reference is an arrow with a double line, indicating that the arrow can’t be moved to point to a different object.

The key design principle here is immutability: using immutable objects and immutable references as much as possible.

Let’s review how immutability helps with the main goals of the course: + Safe from bugs. Immutable objects aren’t susceptible to bugs caused by aliasing. Immutable references always point to the same object. + Easy to understand. Because an immutable object or reference always means the same thing, it’s simpler for a reader of the code to reason about — they don’t have to trace through all the code to find all the places where the object or reference might be changed, because it can’t be changed. + Ready for change. If an object or reference can’t be changed at runtime, then code that depends on that object or reference won’t have to be revised when the program changes.

Test Yourself

Up next

How To Avoid Debugging