Introduction to Java

An Introduction to Java

Objectives of CPEN 221

The central goal of CPEN 221 (Principles of Software Construction) is to enable reasoning about the correctness of programs and to highlight concepts that can be applied across programming languages.

We will use Java as the language for our discussions and to reason about the correctness of Java programs we will need to know about the language and some Java internals.

Objectives for this Reading

• Develop a basic understanding of Java as a programming language
• Understand aspects of memory management in Java

What is Java?

Java is a programming language that was developed in the 1990s by James Gosling and others at Sun Microsystems. After Sun was acquired by Oracle, the programming language is maintained principally by Oracle (although others are involved in standardizing features).

These days there are a few different and related Java environments and specifications such as Java Standard Edition (Java SE), Java Mobile Edition (Java ME) and Java Enterprise Edition (Java EE). The language itself has been revised many times since its initial development, with the most recent version being Java 8.

Java Programs and the JVM

Java programs are compiled using the Java compiler into a format that is known as Java bytecode. Java programs typically have a .java extension. This is the source code that programmers/software developers write, which is intended to be human-readable. After compilation, the compiler generates .class files that contain Java bytecode.

Java bytecode is intended to be portable: this means that one can compile a Java program on any computing device that has a Java compiler but it is possible to execute the .class file on any computing device that can run the Java Virtual Machine.

The Java Virtual Machine (JVM) has been ported to a variety of hardware+OS platforms. It is the existence of the JVM that allows a Java compiler to produce the .class file without any knowledge of the target runtime environment. So a .class file that you produce on your machine can be sent to a friend who can run it as long as she has a system capable of running a JVM. (The same cannot be said for a compiled C program. You cannot ship a binary to a friend and expect it to run unless the friend’s system is identical to the system the program was compiled for.)

The process of executing a Java program, starting with the source code, can be visualized as follows (assuming that we are compiling the Java program in Xyz.java):

1 java=>inputoutput: Xyz.java
2 class=>inputoutput: Xyz.class
3 compile=>operation: Compilation (javac, platform-independent)
4 jvm=>operation: JVM (java, platform-dependent)
5 exec=>subroutine: Program Execution on Target Platform
6 
7 java->compile->class
8 class->jvm->exec

This is in contrast to a language like C (see flow below). With C, the C compiler takes source code and produces an executable that will run on a specific target platform. It is not (easily) possible to run an executable program that a C compiler produces on a platform other than the intended target platform.

1 c-source=>inputoutput: Xyz.c
2 c-binary=>inputoutput: [Executable] Xyz.exe | Xyz (Unix/Linux)
3 c-compiler=>operation: Compile (gcc|Visual C|etc., platform-dependent)
4 exec=>subroutine: Program Execution on Target Platform
5 
6 c-source->c-compiler->c-binary->exec

In the case of Java, the JVM interprets the bytecode and produces (assembly/machine) instructions that can be executed by the target platform. The JVM is a runtime environment, and it provides additional features (garbage collection is one of them) that enable the Java language to be “safer” to use than C. (We will discuss safety at length later.)

Integrated Development Environments (IDEs) like Eclipse hide the multi-stage process that is required to run a program described in a .java file.

Hello World! in Java

To begin an exploration of the Java language, let us start with a simple program: one that prints Hello World!.

Let us assume that this program is in the file HelloWorld.java. The source code would then look something like this:

 1 /**
 2 * @author Sathish Gopalakrishnan
 3 */
 4 
 5 public class HelloWorld {
 6 	/**
 7 	* The main method simply prints "Hello World!"
 8 	* We are not using any program arguments.
 9 	* @param args not used (ignored)
10 	*/
11 	public static void main(String[] args) {
12 		System.out.println("Hello World!");
13 	}
14 }

Let us understand the different elements of this simple program.

The first few sentences simply indicate who the author of the program.

1 /**
2 * @author Sathish Gopalakrishnan
3 */

The above lines constitute a special type of comment, namely a javadoc comment. javadoc is a tool that is part of the Java Development Kit that automatically generates program documentation using comments that are in the /** ... */ blocks.

Java is an object-oriented programming language, and objects in Java are instances of classes. All code in Java is part of some class. To print “Hello World!”, we use have created a class named HelloWorld. This class is being defined by the code block that starts with the sentence public class HelloWorld.

public is a keyword in Java that one will become more familiar with soon. It suffices for now to mention that any class that is marked public should be in a separate .java file and that the file must be named after the class. The public class HelloWorld must be in HelloWorld.java.

We then have the following javadoc block:

1 	/**
2 	* The main method simply prints "Hello World!"
3 	* We are not using any program arguments.
4 	* @param args not used (ignored)
5 	*/

This block states what the purpose of the method that follows it is. It also states that the parameter args is not going to be used in the method.

The only method (or function, but we will use the term method) in the class HelloWorld is main(). This method has also been tagged public; additionally it has also been declared static. It does not return any data and hence its return type is void.

All Java programs that are intended to be executed should have exactly one method main() that takes an array of Strings as its argument and is public, static and has return type void. In our simple Java example, we are dealing with only one class and one file. In the general case, we will work with many classes and many files, so only one class may contain a method with the following signature: public static void main(String[] args).

The method main() in our example has only one action statement: System.out.println("Hello World!");

This is the statement that prints “Hello World!” to the standard output device. The . (dot) operator is used in Java to access “stuff” within an object (or a class – in some circumstances).

When we write System.out.println("Hello World!");, what we are stating is that the Java runtime environment (the JVM) should execute the method println() that belongs to the object out, and that out itself belongs to the object/class System.

For those familiar with C, the equivalent program might look like this:

1 #include <stdio.h>
2 
3 // print the string "Hello World!"
4 int main(int argc, char* argv[]) {
5 	printf("Hello World!\n");
6 }

The C program above appears more compact (fewer lines of code) than HelloWorld.java. Java can be a verbose language at times. Python is even more compact because we only need to write the following:

1 print "Hello World!"

Of Classes and Objects

In the previous example, we looked at a trivial Java program that did not use objects in any significant way. We will now delve a bit into the need for objects and how to use them (at an introductory level) in Java.

Classes and objects are Java’s approach to creating user-defined data types. (Other languages may also permit the creation of user-defined types, but without the use of objects.)

Java, like C, supports primitive types such as int, float, double and char. (This is not an exhaustive list.) int is the data type that represents the set of integer values that can be represented on a computing platform and some of the standard arithmetic operations (such as addition, subtraction, multiplication, division) are defined on the ints.

Let us suppose we wanted to step up the level of abstraction and deal with a set of circles. (This is a rather common situation if you were developing a graphics package or a video game.) To represent a circle, we may need to specify its centre (x, y coordinates) and its radius (r). If we wanted to work with 50 circles then we could, possibly, use an array of x values, an array of y values and an array of r values with the convention that x[i], y[i], r[i] represent circle i. Such an approach may work but it may also be difficult to keep track of all the arrays and indices. We may want to have a datatype called Circle that encapsulates the center coordinates as well as the radius, and has some well-defined operations that are relevant to a circle (find the area of the circle, find the circumference of the circle). Such a datatype can be created in Java through its classes and objects.

We can declare a public class called Circle as follows (naturally in the file Circle.java):

 1 public class Circle {
 2 	public double x, y; // these represent the center coordinates
 3 	public double r; // this represents the radius of the circle
 4 
 5 	/**
 6 	* This is the default constructor for the class Circle. It does not do anything\
 7  specific.
 8 	*/
 9 	public Circle() { }
10 
11 	/**
12 	 * This method returns the area of the circle.
13 	 */
14 	public double getArea() {
15 		return Math.PI * r * r;
16 	}
17 	
18 	/**
19 	 * This method returns the circumference of the circle.
20 	 */
21 	public double getCircumference() {
22 		return 2 * Math.PI * r;
23 	}
24 }

Now, if we wanted to compute the area of a particular circle, we could write a method to do so. To illustrate some points, we will write this method in a file called UseCircles.java, that we will place in the same directory as Circle.java.

 1 public class UseCircles {
 2 	
 3 	/**
 4 	* This main( ) method computes the areas of a circle 
 5 	* and prints the area out to standard output.
 6 	*/
 7 	
 8 	public static void main( String[] args ) {
 9 		// Let us declare a circle
10 		Circle c;
11 
12 		// we can also declare other variables here
13 		double radius = 22;
14 		
15 		// Let us now create a circle
16 		c = new Circle();
17 
18 		// We could have also done this in one step:
19 		// Circle c = new Circle();
20 
21 		// Let us set the centre of the circle
22 		c.x = 10;
23 		c.y = 20;
24 		
25 		// Let us set the radius of the circle
26 		c.r = radius;
27 
28 		// Let us now print the area of the circle
29 		System.out.println(c.getArea());
30 	}
31 }

In the Circle example, x, y and r that are within the class Circle are called instance variables and the methods getArea() and getCircumference() are called instance methods.

The code in the class Circle merely helps us declare what a Circle is. It is only when we create a new circle by using the keyword new that an object (or instance of class Circle) is created.

Once we have created an object and associated it with c, we can access elements (both variables and methods) that are part of the object with the . (dot) operator.

The new keyword is used to create objects, and it is the JVM that creates objects at runtime by invoking a method called a constructor. Our class Circle has a default constructor that does nothing:

1 public Circle() { }

We can have constructors do more work, and even take arguments/parameters but we have kept the constructor simple in this example.

Does the statement

1 Circle c;

not create an object? Why do we need to use the keyword new?

To understand some of these details we will now discuss how memory is managed in Java. For now, it is worth mentioning that c is not an object – it is a reference to an object.

The examples and discussion here are intended to provide some basis for further study of Java and are not intended to replace a more comprehensive Java book. The goal of this note is to lay some groundwork for reasoning about Java programs and I have deliberately omitted many details.

The JVM and Memory Areas

Let us consider the situation when we want to run the main() method in UseCircles.class file after compilation. To run the method, we would start the JVM and pass it the .class file and the JVM will then execute main() in the .class file.

The JVM, when it starts running, will be allocated some memory by the underlying operating system. (There have been efforts to build JVMs that run without an OS but that can be a topic for another discussion.) The JVM then divides the allocated memory into different areas. The ones that we will focus on now are the JVM stack and the JVM heap. (There are other areas for storing method code, run-time constants, etc.)

The JVM stores all primitive types (int, float, double, boolean, etc.) that are not instance variables of an objects on the stack. All objects are stored on the heap.

In our example with Circle and UseCircles, c is a primitive type variable that is only used in main() and is not an instance variable. Is c a primitive type? Indeed it is. In Java, c is a reference or pointer to an object, and pointers are primitive types. A pointer simply stores a memory address.

Let us use two tables to represent the stack and heap, respectively. We will see how the stack and the heap evolve after a sequence of statements. (The memory addresses used in this example are arbitrary and are used only for illustration.)

1. Circle c; radius = 22;

After the statement, space is allocated on the stack for c at address 10097. (The c in brackets is for readability. The JVM only tracks memory addresses.) The statement simply declares c to be a reference that is supposed to point to an object of type Circle. It is not pointing to a particular object and therefore the value at that memory address is set to NULL. On a 64-bit processor, a reference will use 64 bits or 8 bytes of memory.

The heap is not necessarily empty at this point in time but for this example we show it as empty to indicate that no relevant data is on the heap. We will only show the portion of the heap that is relevant in this example.

2. c = new Circle();

When this statement is executed, a new Circle object is created and space is allocated for it on the heap. Let us suppose that the address at which memory for the object starts is 516. This address is then assigned to c, which now points to the object on the heap.

The double type uses 8 bytes of space. For simplicity, we will assume that the only data associated with the object that was created are x, y and r, each of which is 8 bytes long.

3. c.x = 10; c.y = 20; c.r = radius;

When these statements are executed, the appropriate locations on the heap are updated.

Java and Pointers

Sometimes one is told that to use Java one does not need to understand pointers. This view is inaccurate and can lead to significant mistakes.

Java does rely on pointers because all objects are accessed using variables that point/refer to the objects. The difference between Java and, say, C or C++ is that one cannot manipulate the pointers directly (perform pointer arithmetic), which eliminates the possibility of certain types of errors at the cost of reduced low-level control.

The Program Stack

Why does the JVM place some data on the stack? Why is it called a stack? These notes will be updated to included this important topic that is relevant to all programming language implementations.

Static Checking, Testing and Code Reviews

Static Checking

Objectives for This Reading

This reading has two major topics:

• static typing
• the big three properties of good software

Hailstone Sequence

For an initial example, we’re going to consider the hailstone sequence, which is defined as follows. Starting with a number , the next number in the sequence is if is even, or if is odd. The sequence ends when it reaches 1. Here are some examples:

1 2, 1
2 3, 10, 5, 16, 8, 4, 2, 1
3 4, 2, 1
4 2n, 2n-1 , ... , 4, 2, 1
5 5, 16, 8, 4, 2, 1
6 7, 22, 11, 34, 17, 52, 6, 13, 40, ...? (where does this stop?)

Because of the odd-number rule, the sequence may bounce up and down before decreasing to 1. It’s conjectured that all hailstones eventually fall to the ground – i.e., the hailstone sequence reaches 1 for all starting – but that’s still an open question¹.

Computing Hailstones

Here’s some code for computing and printing the hailstone sequence for some starting n. We’ll write the code in Java and C for comparison:

Java

 1 int n = 3;
 2 while (n != 1) {
 3 	System.out.println(n);
 4     if (n % 2 == 0) {
 5         n = n / 2;
 6     } else {
 7         n = 3 * n + 1;
 8     }
 9 }
10 System.out.println(n);

C

 1 int n;
 2 n = 3;
 3 while (n != 1) {
 4     printf("%d", n);
 5     if (n % 2 == 0) {
 6         n = n / 2;
 7     }
 8     else {
 9         n = 3 * n + 1;
10     }
11 }
12 printf("%d", n);

It is worth noting that the basic semantics of expressions and statements in Java are very similar to C: while and if behave the same, for example.

Types

A type is a set of values, along with operations that can be performed on those values.

Java has several primitive types, among them:

• int (for integers like 5 and -200, but limited to the range ± 2^31, or roughly ± 2 billion)
• long (for larger integers up to ± 2^63)
• boolean (for true or false)
• double (for floating-point numbers, which represent a subset of the real numbers)
• char (for single characters like 'A' and '$')

Java also has object types, for example:

• String represents a sequence of characters, like a Python string.
• BigInteger represents an integer of arbitrary size, so it acts like a Python number.

By Java convention, primtive types are lowercase, while object types start with a capital letter.

Operations are functions that take inputs and produce outputs (and sometimes change the values themselves). The syntax for operations varies, but we still think of them as functions no matter how they’re written. Here are three different syntaxes for an operation in Python or Java:

• As an infix, prefix, or postfix operator. For example, a + b invokes the operation \+ : int × int → int.
• As a method of an object. For example, bigint1.add(bigint2) calls the operation add: BigInteger × BigInteger → BigInteger.
• As a function. For example, Math.sin(theta) calls the operation sin: double → double. Here, Math is not an object. It’s the class that contains the sin function.

Some operations are overloaded in the sense that the same operation name is used for different types. The arithmetic operators +, -, *, / are heavily overloaded for the numeric primitive types in Java. Methods can also be overloaded. Most programming languages have some degree of overloading.

Static Typing

Java is a statically-typed language. The types of all variables are known at compile time (before the program runs), and the compiler can therefore deduce the types of all expressions as well. If a and b are declared as ints, then the compiler concludes that a+b is also an int. The Eclipse environment does this while you’re writing the code, in fact, so you find out about many errors while you’re still typing.

In dynamically-typed languages like Python, this kind of checking is deferred until runtime (while the program is running).

Static typing is a particular kind of static checking, which means checking for bugs at compile time. Bugs are the bane of programming. Many of the ideas in this course are aimed at eliminating bugs from your code, and static checking is the first idea that we’ve seen for this.

Static typing prevents a large class of bugs from infecting your program: to be precise, bugs caused by applying an operation to the wrong types of arguments. If you write a broken line of code like:

1 "5" * "6"

that tries to multiply two strings, then static typing will catch this error while you’re still programming, rather than waiting until the line is reached during execution.

Static Checking, Dynamic Checking, No Checking

It’s useful to think about three kinds of automatic checking that a language can provide:

• Static checking: the bug is found automatically before the program even runs.
• Dynamic checking: the bug is found automatically when the code is executed.
• No checking: the language doesn’t help you find the error at all. You have to watch for it yourself, or end up with wrong answers.

Needless to say, catching a bug statically is better than catching it dynamically, and catching it dynamically is better than not catching it at all.

Here are some rules of thumb for what errors you can expect to be caught at each of these times.

Static checking can catch:

• syntax errors, like extra punctuation or spurious words. Even dynamically-typed languages like Python do this kind of static checking. If you have an indentation error in your Python program, you’ll find out before the program starts running.
• wrong names, like Math.sine(2). (The right name is sin.)
• wrong number of arguments, like Math.sin(30, 20).
• wrong argument types, like Math.sin("30").
• wrong return types, like return "30"; from a function that’s declared to return an int.

Dynamic checking can catch:

• illegal argument values. For example, the integer expression x/y is only erroneous when y is actually zero; otherwise it works. So in this expression, divide-by-zero is not a static error, but a dynamic error.
• unrepresentable return values, i.e., when the specific return value can’t be represented in the type.
• out-of-range indexes, e.g., using a negative or too-large index on a string.
• calling a method on a null object reference.

Static checking tends to be about types, errors that are independent of the specific value that a variable has. A type is a set of values. Static typing guarantees that a variable will have some value from that set, but we don’t know until runtime exactly which value it has. So if the error would be caused only by certain values, like divide-by-zero or index-out-of-range then the compiler won’t raise a static error about it.

Dynamic checking, by contrast, tends to be about errors caused by specific values.

Surprise: Primitive Types Are Not True Numbers

One trap in Java – and many other programming languages – is that its primitive numeric types have corner cases that do not behave like the integers and real numbers we’re used to. As a result, some errors that really should be dynamically checked are not checked at all. Here are the traps:

• Integer division. 5/2 does not return a fraction, it returns a truncated integer. So this is an example of where what we might have hoped would be a dynamic error (because a fraction isn’t representable as an integer) frequently produces the wrong answer instead.
• Integer overflow. The int and long types are actually finite sets of integers, with maximum and minimum values. What happens when you do a computation whose answer is too positive or too negative to fit in that finite range? The computation quietly overflows (wraps around), and returns an integer from somewhere in the legal range but not the right answer.
• Special values in float and doubles. The float and double types have several special values that aren’t real numbers: NaN (which stands for “Not a Number”), POSITIVE_INFINITY, and NEGATIVE_INFINITY. So operations that you’d expect to produce dynamic errors, like dividing by zero or taking the square root of a negative number, produce one of these special values instead. If you keep computing with it, you’ll end up with a bad final answer.

Arrays and Collections

Let’s change our hailstone computation so that it stores the sequence in a data structure, instead of just printing it out. Java has two kinds of list-like types that we could use: arrays and Lists.

Arrays are fixed-length sequences of another type T. For example, here’s how to declare an array variable and construct an array value to assign to it:

1   int[] a = new int[100];

The int[] array type includes all possible array values, but a particular array value, once created, can never change its length. Operations on array types include:

• indexing: a[2]
• assignment: a[2]=0
• length: a.length (note that this is different syntax from String.length() – a.length is not a method call, so you don’t put parentheses after it)

Here’s a crack at the hailstone code using an array. We start by constructing the array, and then use an index variable i to step through the array, storing values of the sequence as we generate them.

 1 int[] a = new int[100];
 2 int i = 0;
 3 int n = 3;
 4 while (n != 1) {
 5     a[i] = n;
 6     i++;
 7     if (n % 2 == 0) {
 8         n = n / 2;
 9     } else {
10         n = 3 * n + 1;
11     }
12 }
13 a[i] = n;
14 i++;

Something should immediately smell wrong in this approach. What’s that magic number 100? What would happen if we tried an n that turned out to have a very long hailstone sequence? It wouldn’t fit in a length-100 array. We have a bug. Would Java catch the bug statically, dynamically, or not at all? Incidentally, bugs like these – overflowing a fixed-length array, which are commonly used in less-safe languages like C and C++ that don’t do automatic runtime checking of array accesses – have been responsible for a large number of network security breaches and Internet worms.

Instead of a fixed-length array, let’s use the List type. Lists are variable-length sequences of another type T. Here’s how we can declare a List variable and make a list value:

1 List<Integer> list = new ArrayList<Integer>();

And here are some of its operations:

• indexing: list.get(2) – get the value at index 2 or the 3rd entry in the list; indices start at 0.
• assignment: list.set(2, 0) – set the value at index 2 to 0.
• length: list.size() – get the number of values in the list.

Note that List is an interface, a type that can’t be constructed directly with new, but that instead specifies the operations that a List must provide. We’ll talk about this notion in a future chapter on abstract data types. ArrayList is a class, a concrete type that provides implementations of those operations.

Note also that we wrote List<Integer> instead of List<int>. Unfortunately we can’t write List<int> in direct analog to int[]. Lists only know how to deal with object types, not primitive types. In Java, each of the primitive types (which are written in lowercase and often abbreviated, like int) has an equivalent object type (which is capitalized, and fully spelled out, like Integer). Java requires us to use these object type equivalents when we parameterize a type with angle brackets; as far as I know, the only reason for this requirement is to remind the programmer that the list actually contains objects, which use more memory than primitive values. But in other contexts, Java automatically converts between int and Integer, so we can write Integer i = 5 without any type error (this is sometimes referred to as auto-boxing, auto-unboxing). We should, however, be careful about the following piece of code:

1 int a = 1000;
2 Integer b = new Integer(1000);
3 if (a == b) {
4 	// do something
5 }

The reason for care here is that when performing comparisons the autoboxing/autounboxing approach does not work as well.

Now, back to the Hailstone Sequence. Here is the hailstone sequence code written using a List:

 1 List<Integer> list = new ArrayList<Integer>();
 2 int n = 3;
 3 while (n != 1) {
 4     list.add(n);
 5     if (n % 2 == 0) {
 6         n = n / 2;
 7     } else {
 8         n = 3 * n + 1;
 9     }
10 }
11 list.add(n);

Not only simpler but safer too, because the List` automatically enlarges itself to fit as many numbers as you add to it (until you run out of memory, of course).

Iterating

A for loop steps through the elements of an array or a list, though the syntax can look a little different. For example:

1 int max = 0;
2 for (int x : list) {
3     max = Math.max(x, max);
4 }

is the same as

1 int max = 0;
2 for (int i = 0; i < list.size(); i++) {
3 	max = Math.max(list.get(i), max);
4 }

You can iterate through arrays as well as lists. The same code would work if the list were replaced by an array.

Methods

In Java, statements generally have to be inside a method, and every method has to be in a class, so the simplest way to write our hailstone program looks like this:

 1 public class Hailstone {
 2     public static List<integer> hailstoneSequence(int n) {
 3       List<integer> list = new ArrayList<integer>();
 4       while (n != 1) {
 5           list.add(n);
 6           if (n % 2 == 0) {
 7               n = n / 2;
 8           } else {
 9               n = 3 * n + 1;
10           }
11       }
12       list.add(n);
13       return list;
14     }
15 }

Let’s explain a few of the new things here.

public means that any code, anywhere in your program, can refer to the class or method. Other access modifiers, like private, are used to get more safety in a program, and to guarantee immutability for immutable types. We’ll talk more about them later.

static means that the method doesn’t take a self parameter – which in Java is implicit anyway, you won’t ever see it as a method parameter. Static methods cannot be called on an object. Contrast that with the List add() method or the String length() method, for example, which require an object to come first. Instead, the right way to call a static method uses the class name instead of an object reference:

1 Hailstone.hailstoneSequence(83)

Take note also of the comment before the method, because it is very important. This comment is a specification of the method, describing the inputs and outputs of the operation. The specification should be concise and clear and precise. The comment provides information that is not already clear from the method types. It doesn’t say, for example, that n is an integer, because the int n declaration just below already says that. But it does say that n must be positive, which is not captured by the type declaration but is very important for the caller to know.

We’ll have a lot more to say about how to write good specifications, but you’ll have to start reading them and using them right away.

Mutating Values vs. Reassigning Variables

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

Change is a necessary evil. Good programmers avoid things that change, because they may change unexpectedly.

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. (At least not in a way that’s visible to the outside world – there are some subtleties there that we’ll talk more about in a future class about immutability.) Which of the types we’ve discussed so far are immutable, and which are mutable?

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;

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.

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.

To Ponder

There are two variables in our hailstoneSequence method: can we declare them final, or not?

1 public static List<integer> hailstoneSequence(final int n) {
2 	final List<integer> list = new ArrayList<integer>();

Documenting Assumptions

Writing the type of a variable down documents an assumption about it: e.g., this variable will always refer to an integer. Java actually checks this assumption at compile time, and guarantees that there’s no place in your program where you violated this assumption.

Declaring a variable final is also a form of documentation, a claim that the variable will never change after its initial assignment. Java checks that too, statically.

We documented another assumption that Java (unfortunately) doesn’t check automatically: that n must be positive.

Why do we need to write down our assumptions? Because programming is full of them, and if we don’t write them down, we won’t remember them, and other people who need to read or change our programs later won’t know them. They’ll have to guess.

Programs have to be written with two goals in mind:

• communicating with the computer. First persuading the compiler that your program is sensible – syntactically correct and type-correct. Then getting the logic right so that it gives the right results at runtime.
• communicating with other people. Making the program easy to understand, so that when somebody has to fix it, improve it, or adapt it in the future, they can do so.

Hacking vs. Engineering

We’ve all written some hacky code. Hacking is often marked by unbridled optimism:

• Bad: writing lots of code before testing any of it
• Bad: keeping all the details in your head, assuming you’ll remember them forever, instead of writing them down in your code
• Bad: assuming that bugs will be nonexistent or else easy to find and fix

But software engineering is not hacking. Engineers are pessimists:

• Good: write a little bit at a time, testing as you go. In a future class, we’ll talk about test-first programming.
• Good: document the assumptions that your code depends on
• Good: defend your code against stupidity – especially your own! Static checking helps with that.

The Goal of CPEN 221

Our primary goal in this course is learning how to produce software that is:

• Safe from bugs. Correctness (correct behaviour right now), and defensiveness (correct behavior in the future).
• Easy to understand. Has to communicate to future programmers who need to understand it and make changes in it (fixing bugs or adding new features). That future programmer might be you, months or years from now. You’ll be surprised how much you forget if you don’t write it down, and how much it helps your own future self to have a good design.
• Ready for change. Software always changes. Some designs make it easy to make changes; others require throwing away and rewriting a lot of code.

There are other important properties of software (like performance, usability, security), and they may trade off against these three. But these are the Big Three that we care about in CPEN 221, and that software developers generally put foremost in the practice of building software. It’s worth considering every language feature, every programming practice, every design pattern that we study in this course, and understanding how they relate to the Big Three.

Why we use Java in this course

Since you’ve all completed APSC 160 (or an equivalent course), we’re assuming that you’re comfortable with C. So why aren’t we using C in this course?

Safety is the first reason. Java has static checking (primarily type checking, but other kinds of static checks too, like that your code returns values from methods declared to do so). We’re studying software engineering in this course, and safety from bugs is a key tenet of that approach. Java dials safety up to 11, which makes it a good language for learning about good software engineering practices. It’s certainly possible to write safe code in dynamic languages like Python, but it’s easier to understand what you need to do if you learn how in a safe, statically-checked language.

Ubiquity is another reason. Java is widely used in research, education, and industry. Java runs on many platforms, not just Windows/Mac/Linux. Java can be used for web programming (both on the server and in the client), and native Android programming is done in Java. Although other programming languages are far better suited to teaching programming (Scheme and ML come to mind), regrettably these languages aren’t as widespread in the real world. Java on your resume will be recognized as a marketable skill. But don’t get us wrong: the real skills you’ll get from this course are not Java-specific, but carry over to any language that you might program in. The most important lessons from this course will survive language fads: safety, clarity, abstraction, engineering instincts.

In any case, a good programmer must be multilingual. Programming languages are tools, and you have to use the right tool for the job. You will certainly have to pick up other programming languages before you even finish your career (Javascript, C/C++, Scheme), so we’re getting started now by learning a second one.

As a result of its ubiquity, Java has a wide array of interesting and useful libraries (both its enormous built-in library, and other libraries out on the net), and excellent free tools for development (IDEs like Eclipse, editors, compilers, test frameworks, profilers, code coverage, style checkers). Even Python is still behind Java in the richness of its ecosystem.

There are some reasons to regret using Java. It’s wordy, which makes it hard to write examples on the board. It’s large, having accumulated many features over the years. It’s internally inconsistent (e.g. the final keyword means different things in different contexts, and the static keyword in Java has nothing to do with static checking). It’s weighted with the baggage of older languages like C/C++ (the primitive types and the switch statement are good examples).

But on the whole, Java is a reasonable choice of language right now to learn how to write code that is safe from bugs, easy to understand, and ready for change. And that’s our goal.

Summary

The main idea we introduced in this chapter is that of static checking. Here’s how this idea relates to the goals of the course:

• Safe from bugs. Static checking helps with safety by catching type errors and other bugs before runtime.
• Easy to understand. It helps with understanding, because types are explicitly stated in the code.
• Ready for change. Static checking makes it easier to change your code by identifying other places that need to change in tandem. For example, when you change the name or type of a variable, the compiler immediately displays errors at all the places where that variable is used, reminding you to update them as well.

Test Yourself

• Questions
• Answers

Testing and Code Review

Validation

Testing and code review are two examples of a more general process called validation. The purpose of validation is to uncover problems in a program and thereby increase your confidence in the program’s correctness.

Validation includes:

• Formal reasoning about a program, usually called verification. Verification constructs a formal proof that a program is correct. Verification is tedious to do by hand, and automated tool support for verification is still an active area of research. Nevertheless, small, crucial pieces of a program may be formally verified, such as the scheduler in an operating system or the bytecode interpreter in a virtual machine.
• Code review. Having somebody else carefully read your code (and reason informally about it) can be a good way to uncover bugs, much like having somebody else proofread an essay you have written.
• Testing. Running the program on carefully selected inputs and checking the results.

Even with the best validation, it’s very hard to achieve perfect quality in software. Here are some typical residual defect rates (bugs left over after the software has shipped) per kloc (one thousand lines of source code):

• 1 - 10 defects/kloc: Typical industry software.
• 0.1 - 1 defects/kloc: High-quality validation. The Java libraries might achieve this level of correctness.
• 0.01 - 0.1 defects/kloc: The very best, safety-critical validation. NASA and companies like Praxis can achieve this level.

This can be discouraging for large systems. For example, if you have shipped a million lines of typical industry source code (1 defect/kloc), it means you missed 1000 bugs!

Putting on Your Testing Hat

Testing requires having the right attitude. When you’re coding, your goal is to make the program work, but as a tester, you want to make it fail.

That’s a subtle but important difference. It is all too tempting to treat code you’ve just written as a precious thing, a fragile eggshell, and test it very lightly just to see it work.

Instead, you have to be brutal. A good tester wields a sledgehammer and beats the program everywhere it might be vulnerable, so that those vulnerabilities can be eliminated.

Test-first Programming

Test early and often. Don’t leave testing until the end, when you have a big pile of unvalidated code. Leaving testing until the end only makes debugging longer and more painful, because bugs may be anywhere in your code. It’s far more pleasant to test your code as you develop it.

In test-first-programming, you write tests before you even write any code. The development of a single function proceeds in this order:

1. Write a specification for the function.
2. Write tests that exercise the specification.
3. Write the actual code. Once your code passes the tests you wrote, you’re done.

The specification describes the input/output behaviour of the function. It gives the types of the parameters and any additional constraints on them (e.g. sqrt’s parameter must be nonnegative). It also gives the type of the return value and how the return value relates to the inputs. You’ve already seen and used specifications on your problem sets in this class. In code, the specification consists of the method signature and the comment above it that describes what it does. We’ll have much more to say about specifications soon enough.

Writing tests first is a good way to understand the specification. The specification can be buggy, too — incorrect, incomplete, ambiguous, missing corner cases. Trying to write tests can uncover these problems early, before you’ve wasted time writing an implementation of a buggy spec.

Why Software Testing is Hard

Here are some approaches that unfortunately don’t work well in the world of software.

Exhaustive testing is infeasible. The space of possible test cases is generally too big to cover exhaustively. Imagine exhaustively testing a 32-bit floating-point multiply operation, a*b. There are 2⁶⁴ test cases!

Haphazard testing (“just try it and see if it works”) is less likely to find bugs, unless the program is so buggy that an arbitrarily-chosen input is more likely to fail than to succeed.It also doesn’t increase our confidence in program correctness.

Random or statistical testing doesn’t work well for software. Other engineering disciplines can test small random samples (e.g. 1% of hard drives manufactured) and infer the defect rate for the whole production lot. Physical systems can use many tricks to speed up time, like opening a refrigerator 1000 times in 24 hours instead of 10 years. These tricks give known failure rates (e.g. mean lifetime of a hard drive), but they assume continuity or uniformity across the space of defects. This is true for physical artifacts.

But it’s not true for software. Software behaviour varies discontinuously and discretely across the space of possible inputs. The famous Pentium division bug affected approximately 1 in 9 billion divisions. Stack overflows, out of memory errors, and numeric overflow bugs tend to happen abruptly, and always in the same way.

Instead, test cases must be chosen carefully and systematically, and that’s what we’ll look at next.

Choosing Test Cases by Partitioning

Creating a good test suite is a challenging and interesting design problem. We want to pick a set of test cases that is small enough to run quickly, yet large enough to validate the program.

To do this, we divide the input space into subdomains, each consisting of a set of inputs. Taken together the subdomains completely cover the input space, so that every input lies in at least one subdomain. Then we choose one test case from each subdomain, and that’s our test suite.

The idea behind subdomains is to partition the input space into sets of similar inputs on which the program has similar behaviour. Then we use one representative of each set. This approach makes the best use of limited testing resources by choosing dissimilar test cases, and forcing the testing to explore parts of the input space that random testing might not reach.

Example: BigInteger.multiply()

Let’s look at an example. BigInteger is a class built into the Java library that can represent integers of any size, unlike the primitive types int and long that have only limited ranges. BigInteger has a method multiply that multiplies two BigInteger values together:

1 /**
2  * @param val  another BigIntger
3  * @return a BigInteger whose value is (this * val).
4  */
5 public BigInteger multiply(BigInteger val)

For example, here’s how it might be used:

1 BigInteger a = ...;
2 BigInteger b = ...;
3 BigInteger ab = a.multiply(b);

This example shows that even though only one parameter is explicitly shown in the method’s declaration, multiply is actually a function of two arguments: the object you’re calling the method on (a in the example above), and the parameter that you’re passing in the parentheses (b in this example). In Python, the object receiving the method call would be explicitly named as a parameter called self in the method declaration. In Java, you don’t mention the receiving object in the parameters, and it’s called this instead of self.

So we should think of multiply as a function taking two inputs, each of type BigInteger, and producing one output of type BigInteger:

multiply : BigInteger × BigInteger → BigInteger

So we have a two-dimensional input space, consisting of all the pairs of integers (a,b). Now let’s partition it. Thinking about how multiplication works, we might start with these partitions:

• a and b are both positive
• a and b are both negative
• a is positive, b is negative
• a is negative, b is positive

There are also some special cases for multiplication that we should check: 0, 1, and -1.

• a or b is 0, 1, or -1

Finally, as a suspicious tester trying to find bugs, we might suspect that the implementor of BigInteger might try to make it faster by using int or long internally when possible, and only fall back to an expensive general representation (like a list of digits) when the value is too big. So we should definitely also try integers that are very big, bigger than the biggest long.

• a or b is small
• a or b is bigger than Long.MAX_VALUE, the biggest possible primitive integer in Java, which is roughly 2⁶³.

Let’s bring all these observations together into a straightforward partition of the whole (a,b) space. We’ll choose a and b independently from:

• 0
• 1
• -1
• small positive integer
• small negative integer
• huge positive integer
• huge negative integer

So this will produce 7 × 7 = 49 partitions that completely cover the space of pairs of integers.

To produce the test suite, we would pick an arbitrary pair (a,b) from each square of the grid, for example:

• (a,b) = (-3, 25) to cover (small negative, small positive)
• (a,b) = (0, 30) to cover (0, small positive)
• (a,b) = (2¹⁰⁰, 1) to cover (large positive, 1)
• etc.

Example: max()

Let’s look at another example from the Java library: the integer max() function, found in the Math class.

1 /**
2  * @param a  an argument
3  * @param b  another argument
4  * @return the larger of a and b.
5  */
6 public static int max(int a, int b)

Mathematically, this method is a function of the following type:

max : int × int → int

From the specification, it makes sense to partition this function as:

• a < b
• a = b
• a > b

Our test suite might then be:

• (a, b) = (1, 2) to cover a < b
• (a, b) = (9, 9) to cover a = b
• (a, b) = (-5, -6) to cover a > b

Include Boundaries in the Partition

Bugs often occur at boundaries between subdomains. Some examples:

• 0 is a boundary between positive numbers and negative numbers
• the maximum and minimum values of numeric types, like int and double
• emptiness (the empty string, empty list, empty array) for collection types
• the first and last element of a collection

Why do bugs often happen at boundaries? One reason is that programmers often make off-by-one mistakes (like writing <= instead of <, or initializing a counter to 0 instead of 1). Another is that some boundaries may need to bee handled as special cases in the code. Another is that boundaries may be places of discontinuity in the code’s behaviour. When an int variable grows beyond its maximum positive value, for example, it abruptly becomes a negative number.

It’s important to include boundaries as subdomains in your partition, so that you’re choosing an input from the boundary.

Let’s redo max : int × int → int.

Partition into:

• relationship between a and b
  • a < b
  • a = b
  • a > b
• value of a
  • a = 0
  • a < 0
  • a > 0
  • a = minimum integer
  • a = maximum integer
• value of b
  • b = 0
  • b < 0
  • b > 0
  • b = minimum integer
  • b = maximum integer

Now let’s pick test values that cover all these classes:

• (1, 2) covers a < b, a > 0, b > 0
• (-1, -3) covers a > b, a < 0, b < 0
• (0, 0) covers a = b, a = 0, b = 0
• (Integer.MIN_VALUE, Integer.MAX_VALUE) covers a < b, a = minint, b = maxint
• (Integer.MAX_VALUE, Integer.MIN_VALUE) covers a > b, a = maxint, b = minint

Two Extremes

After partitioning the input space, we can choose how exhaustive we want the test suite to be:

• Full Cartesian product.
  Every legal combination of the partition dimensions is covered by one test case. This is what we did for the multiply example, and it gave us 7 × 7 = 49 test cases. For the max example that included boundaries, which has three dimensions with 3 parts, 5 parts, and 5 parts respectively, it would mean up to 3 × 5 × 5 = 75 test cases.
  In practice not all of these combinations are possible, however. For example, there’s no way to cover the combination a < b, a=0, b=0, because a can’t be simultaneously less than zero and equal to zero.
• Cover each part.
  Every part of each dimension is covered by at least one test case, but not necessarily every combination. With this approach, the test suite for max might be as small as max(3, 5, 5) = 5 if carefully chosen. That’s the approach we took above, which allowed us to choose 5 test cases.

Often we strike some compromise between these two extremes, influenced by whitebox testing and code coverage tools, which we look at next.

Blackbox and Whitebox Testing

Recall from above that the specification is the description of the function’s behaviour — the types of parameters, type of return value, and constraints and relationships between them.

Blackbox testing means choosing test cases only from the specification, not the implementation of the function. That’s what we’ve been doing in our examples so far. We partitioned and looked for boundaries in multiply, max, and intersect without looking at the actual code for these functions.

Whitebox testing (also called glass box testing) means choosing test cases with knowledge of how the function is actually implemented. For example, if the implementation selects different algorithms depending on the input, then you should partition according to those domains. If the implementation keeps an internal cache that remembers the answers to previous inputs, then you should test repeated inputs.

When doing whitebox testing, you must take care that your test cases don’t require specific implementation behaviour that isn’t specifically called for by the spec. For example, if the spec says “throws an exception if the input is poorly formatted”, then your test shouldn’t check specifically for a NullPointerException just because that’s what the current implementation does. The specification in this case allows any exception to be thrown, so your test case should likewise be general to preserve the implementor’s freedom. We’ll have much more to say about this in the class on specs.

Coverage

One way to judge a test suite is to ask how thoroughly it exercises the program. This notion is called coverage. Here are three common kinds of coverage:

• Statement coverage: is every statement run by some test case?
• Branch coverage: for every if or while statement in the program, are both the true or false direction taken by some test case?
• Path coverage: is every possible combination of branches — every path through the program — taken by some test case?

In industry, 100% statement coverage is common goal, but rarely achieved due to unreachable defensive code (like “should never get here” assertions). 100% branch coverage is highly desirable, and safety critical industry has even more arduous criteria (eg, “MCDC”, modified decision/condition coverage). Unfortunately 100% path coverage is infeasible, requiring exponential test suites to achieve.

A standard approach to testing is to add tests until the test suite achieves adequate statement coverage: so that every reachable statement in the program is executed by at least one test case. In practice, statement coverage is usually measured by a code coverage tool, which instruments your program to count the number of times each statement is run by your test suite. With such a tool, white box testing is easy; you just measure the coverage of your black box tests, and add more test cases until all important statements are logged as executed.

A good code coverage tool for Eclipse is EclEmma.

Automated Testing and Regression Testing

Nothing makes tests easier to run, and more likely to be run, than complete automation. A test driver should not be an interactive program that prompts you for inputs and prints out results for you to manually check. Instead, a test driver should invoke the module itself on fixed test cases and automatically check that the results are correct. The result of the test driver should be either “all tests OK” or “these tests failed: …” A good testing framework, like JUnit, helps you build automated test suites.

It’s very important to rerun your tests when you modify your code. This prevents your program from regressing — introducing other bugs when you fix new bugs or add new features. Running all your tests after every change is called regression testing.

Whenever you find and fix a bug, take the input that elicited the bug and add it to your test suite as a test case. This kind of test case is called a regression test. This helps to populate your test suite with good test cases. Remember that a test is good if it elicits a bug — and every regression test did in one version of your code! Saving regression tests also protects against reversions that reintroduce bug. The bug may be an easy error to make, since it happened once already.

This idea also leads to test-first debugging. When a bug arises, immediately write a test case for it that elicits it, and immediately add it to your test suite. Once you find and fix the bug, all your test cases will be passing, and you’ll be done with debugging and have a regression test for that bug.

Code Review

The second validation technique we’ll look at in today’s class is code review. Code review is careful, systematic study of source code by others (not the original author of the code). It’s analogous to proofreading an English paper.

Code review is widely practiced in open source projects like Apache and Mozilla. Code review is also widely practiced in industry. At Google, you can’t push any code until another engineer has signed off on it in a code review.

Style Standards

Most companies and large projects have coding style standards. These can get pretty detailed, even to the point of specifying: whitespace (how deep to indent) and where curly braces and parentheses should go. These kinds of questions often lead to holy wars since they end up being a matter of taste and style.

For Java, there’s a general style guide. Some of its advice gets very specific:

• The opening brace should be at the end of the line that begins the compound statement; the closing brace should begin a line and be indented to the beginning of the compound statement.

In CPEN 221, we have no official style guide of this sort. We’re not going to tell you where to put your curly braces. That’s a personal decision that each programmer should make. It’s important to be self-consistent, however, and it’s very important to follow the conventions of the project you’re working on. If you’re the guy who reformats every module you touch to match your personal style, your teammates will hate you, and rightly so. Be a team player.

But there are some rules that are quite sensible and target our big three properties, in a stronger way than placing curly braces. The rest of this reading talks about some of these rules, at least the ones that are relevant at this point in the course, where we’re mostly talking about writing basic Java. These are some things you should start to look for when you’re code reviewing other students, and when you’re looking at your own code for improvement. Don’t consider it an exhaustive list of code style guidelines, however. Over the course of the semester, we’ll talk about a lot more things — specifications, abstract data types with representation invariants, concurrency and thread safety — which will then become fodder for code review.

Smelly Example #1

Programmers often describe bad code as having a “bad smell” that needs to be removed. “Code hygiene” is another word for this. Let’s start with some smelly code.

 1 public static int dayOfYear(int month, int dayOfMonth, int year) {
 2     if (month == 2) {
 3         dayOfMonth += 31;
 4     } else if (month == 3) {
 5         dayOfMonth += 59;
 6     } else if (month == 4) {
 7         dayOfMonth += 90;
 8     } else if (month == 5) {
 9         dayOfMonth += 31 + 28 + 31 + 30;
10     } else if (month == 6) {
11         dayOfMonth += 31 + 28 + 31 + 30 + 31;
12     } else if (month == 7) {
13         dayOfMonth += 31 + 28 + 31 + 30 + 31 + 30;
14     } else if (month == 8) {
15         dayOfMonth += 31 + 28 + 31 + 30 + 31 + 30 + 31;
16     } else if (month == 9) {
17         dayOfMonth += 31 + 28 + 31 + 30 + 31 + 30 + 31 + 31;
18     } else if (month == 10) {
19         dayOfMonth += 31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30;
20     } else if (month == 11) {
21         dayOfMonth += 31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31;
22     } else if (month == 12) {
23         dayOfMonth += 31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + 31;
24     }
25     return dayOfMonth;
26 }

Don’t Repeat Yourself

Duplicated code is a risk to safety. If you have identical or very-similar code in two places, then the fundamental risk is that there’s a bug in both copies, and some maintainer fixes the bug in one place but not the other.

Avoid duplication like you’d avoid crossing the street without looking. Copy-and-paste is an enormously tempting programming tool, and you should feel a frisson of danger run down your spine every time you use it. The longer the block you’re copying, the riskier it is.

Don’t Repeat Yourself, or DRY for short, has become a programmer’s mantra.

The dayOfYear example is full of identical code. How would you DRY it out?

Comments Where Needed

A quick general word about commenting. Good software developers write comments in their code, and do it judiciously. Good comments should make the code easier to understand, safer from bugs (because important assumptions have been documented), and ready for change.

One kind of crucial comment is a specification, which appears above a method or above a class and documents the behaviour of the method or class. In Java, this is conventionally written as a Javadoc comment, meaning that it starts with /** and includes @-syntax, like @param and @return for methods. Here’s an example of a spec:

 1 /**
 2  * Compute the hailstone sequence.
 3  * See http://en.wikipedia.org/wiki/Collatz_conjecture#Statement_of_the_problem
 4  * @param n starting number of sequence; requires n > 0.
 5  * @return the hailstone sequence starting at n and ending with 1.
 6  * For example, hailstone(3)=[3,10,5,16,8,4,2,1].
 7  */
 8 public static List<Integer> hailstoneSequence(int n) {
 9 ...
10 }

Specifications document assumptions. We’ve already mentioned specs a few times, and there will be much more to say about them.

Another crucial comment is one that specifies the provenance or source of a piece of code that was copied or adapted from elsewhere. This is vitally important for practicing software developers.

Some comments are bad and unnecessary. Direct transliterations of code into English, for example, do nothing to improve understanding, because you should assume that your reader at least knows Java:

1 while (n != 1) { // test whether n is 1   (don't write comments like this!)
2    ++i; // increment i
3    l.add(n); // add n to l
4 }

But obscure code should get a comment:

1 sendMessage("as you wish"); // this basically says "I love you"

The dayOfYear code needs some comments — where would you put them? For example, where would document whether month runs from 0 to 11 or from 1 to 12?

Fail Fast

dayOfYear doesn’t fail fast — if you pass it the arguments in the wrong order, it will quietly return the wrong answer. In fact, the way dayOfYear is designed, it’s highly likely that a non-American will pass the arguments in the wrong order! It needs more checking — either static checking or dynamic checking.

Avoid Magic Numbers

There are really only two constants that computer scientists recognize as valid in and of themselves: 0, 1, and maybe 2. (Okay, three constants.)

Other constant numbers need to be explained. One way to explain them is with a comment, but a far better way is to declare the number as a constant with a good, explanatory name.

dayOfYear is full of magic numbers:

• the months 2, …, 12 would be far more readable as FEBRUARY, …, DECEMBER
• the days-of-months 30, 31, 28 would be more readable (and eliminate duplicate code) if they were in a data structure like an array, list or map, e.g. MONTH_LENGTH[month]
• the mysterious numbers 59 and 90 are particularly pernicious examples of magic numbers. Not only are they uncommented and undocumented, they are actually the result of a computation done by hand by the programmer. Don’t hardcode constants that you’ve computed by hand. Java is better at arithmetic than you are. Explicit computations like 31 + 28 make the provenance of these mysterious numbers much clearer. MONTH_LENGTH[JANUARY] + MONTH_LENGTH[FEBRUARY] would be clearer still.

One Purpose For Each Variable

In the dayOfYear example, the parameter dayOfMonth is reused to compute a very different value — the return value of the function, which is not the day of the month.

Don’t reuse parameters, and don’t reuse variables. Variables are not a scarce resource in programming. Mint them freely, give them good names, and just stop using them when you don’t need them. You will confuse your reader if a variable that used to mean one thing suddenly starts meaning something different a few lines down.

Not only is this an ease-of-understanding question, but it’s also a safety-from-bugs and ready-for-change question.

Method parameters, in particular, should generally be left unmodified. (This is important for being ready-for-change — in the future, some other part of the method may want to know what the original parameters of the method were, so you shouldn’t blow them away while you’re computing.) It’s a good idea to use final for method parameters, and as many other variables as you can. Final says that the variable should never be reassigned, and the Java compiler will check it statically. For example:

1 public static int dayOfYear(final int month, final int dayOfMonth, final int yea\
2 r) { ... }

Smelly Example #2

There was a latent bug in dayOfYear. It didn’t handle leap years at all. As part of fixing that, suppose we write a leap-year test method.

 1 public static boolean leap(int y) {
 2     String tmp = String.valueOf(y);
 3     if (tmp.charAt(2) == '1' || tmp.charAt(2) == '3' || tmp.charAt(2) == 5 || tm\
 4 p.charAt(2) == '7' || tmp.charAt(2) == '9') {
 5         if (tmp.charAt(3)=='2'||tmp.charAt(3)=='6') return true;
 6         else
 7             return false;
 8     }else{
 9         if (tmp.charAt(2) == '0' && tmp.charAt(3) == '0') {
10             return false;
11         }
12         if (tmp.charAt(3)=='0'||tmp.charAt(3)=='4'||tmp.charAt(3)=='8')return tr\
13 ue;
14     }
15     return false;
16 }

What are the bugs hidden in this code? And what style problems that we’ve already talked about?

Use Good Names

Good method and variable names are long and self-descriptive. Comments can often be avoided entirely by making the code itself more readable, with better names that describe the methods and variables.

For example, you can rewrite

1 int tmp = 86400;  // tmp is the number of seconds in a day (don't do this!)

into:

1 int secondsPerDay = 86400;

In general, variable names like tmp, temp and data are awful, symptoms of extreme programmer laziness. Every local variable is temporary, and every variable is data, so those names are generally meaningless. Better to use a longer, more descriptive name, so that your code reads clearly all by itself.

Follow the lexical naming conventions of the language. In Python, classes are typically Capitalized, variables are lowercase, and words_are_separated_by_underscores. In Java:

• methodsAreNamedWithCamelCaseLikeThis
• variablesAreAlsoCamelCase
• CONSTANTS_ARE_IN_ALL_CAPS_WITH_UNDERSCORES
• ClassesAreCapitalized
• packages.are.lowercase.and.separated.by.dots

The leap method has bad names: the method name itself, and the local variable name.

Smelly Example #3

Here’s a third example of smelly code.

 1 public static int LONG_WORD_LENGTH = 5;
 2 public static String longestWord;
 3 
 4 public static void countLongWords(List<String> words) {
 5    int n = 0;
 6    longestWord = "";
 7    for (String word: words) {
 8        if (word.length() > LONG_WORD_LENGTH) ++n;
 9        if (word.length() > longestWord.length()) longestWord = word;
10    }
11    System.out.println(n);
12 }

Don’t Use Global Variables

Let’s parse out global variable. A global variable means two things:

• a variable, a name whose meaning can be changed
• that is global, accessible and changeable from anywhere in the program.

The countLongWords function uses two global variables:

1 public static int LONG_WORD_LENGTH = 5;
2 public static String longestWord;

Why are global variables dangerous? Which of these could be made into a constant instead, and how would you do that?

In general, change global variables into parameters and return values, or into objects that you’re calling methods on.

Coherent Methods

countLongWords isn’t coherent — it does two different things, counting words and finding the longest word. Separating those two responsibilities into two different methods will make them simpler (easy to understand) and more useful in other contexts (ready for change).

Methods Should Return Results, not Print Them

countLongWords isn’t ready for change. It sends some of its result to the console, System.out. That means that if you want to use it in another context — where the number is needed for some other purpose, like computation rather than human eyes — it would have to be rewritten.

In general, only the highest-level parts of a program should interact with the human user or the console. Lower-level parts should take their input as parameters and return their output as results. (The sole exception here is debugging output, which can of course be printed to the console, but that shouldn’t be a part of your design, only a part of how you debug your design.)

Use Whitespace to Help the Reader

Use consistent indentation. The leap example is bad at this. The dayOfYear example is much better. In fact, dayOfYear nicely lines up all the numbers into columns, making them easy for a human reader to compare and check. That’s a great use of whitespace.

Put spaces within code lines to make them easy to read. The leap example has some lines that are packed together — put in some spaces.

Never use tab characters for indentation, only space characters. Note that we say characters. We’re not saying you should never press the Tab key, only that your editor should never put a tab character into your source file in response to your pressing the Tab key. The reason for this rule is that different tools treat tab characters differently — sometimes expanding them to 4 spaces, sometimes to 2 spaces, sometimes to 8. If you run “git diff” on the command line, or if you view your source code in a different editor, then the indentation may be completely screwed up. Just use spaces. Always set your programming editor to insert space characters when you press the Tab key.

Summary

By now, we’ve talked about three good techniques for reducing bugs:

• static checking
• testing
• code reviews

In testing, we saw these ideas:

• Test-first programming. Write tests before you write code.
• Partitioning and boundaries for choosing test cases systematically.
• White box testing and statement coverage for filling out a test suite.
• Automated regression testing to keep bugs from coming back.

In code review, we saw these principles:

• Don’t Repeat Yourself (DRY)
• Comments where needed
• Fail fast
• Avoid magic numbers
• One purpose for each variable
• Use good names
• No global variables
• Coherent methods
• Return results, don’t print them
• Use whitespace for readability

The topics of today’s reading connect to our three key properties of good software as follows:

• Safe from bugs. Testing is about finding bugs in your code, and test-first programming is about finding them as early as possible, immediately after you introduced them. Code review uses human reviewers to find bugs.
• Easy to understand. Code review is really the only way to find obscure or confusing code, because other people are reading it and trying to understand it.
• Ready for change. Readiness for change was considered by writing tests that only depend on behaviour in the spec. We also talked about automated regression testing, which helps keep bugs from coming back when changes are made to code. Code review also helps here, when it’s done by experienced software developers who can anticipate what might change and suggest ways to guard against it.

Test Yourself

• Questions
• Answers

Specifications

Need for Specifications

Why Specifications?

Many of the nastiest bugs in programs arise because of misunderstandings about behaviour at the interface between two pieces of code. Although every programmer has specifications in mind, not all programmers write them down. As a result, different programmers on a team have different specifications in mind. When the program fails, it’s hard to determine where the error is. Precise specifications in the code let you apportion blame (to code fragments, not people!), and can spare you the agony of puzzling over where a fix should go.

Specifications are good for the client of a method because they spare the task of reading code. If you’re not convinced that reading a spec is easier than reading code, take a look at some of the standard Java specs and compare them to the source code that implements them. ArrayList, for example, in the package java.util, has a very simple spec but its code is not at all simple.

Specifications are good for the implementer of a method because they give the freedom to change the implementation without telling clients. Specifications can make code faster, too. Sometimes a weak specification makes it possible to do a much more efficient implementation. In particular, a precondition may rule out certain states in which a method might have been invoked that would have incurred an expensive check that is no longer necessary.

The contract acts as a firewall between client and implementor. It shields the client from the details of the workings of the unit — you don’t need to read the source code of the procedure if you have its specification. And it shields the implementor from the details of the usage of the unit; he doesn’t have to ask every client how she plans to use the unit. This firewall results in decoupling, allowing the code of the unit and the code of a client to be changed independently, so long as the changes respect the specification — each obeying its obligation.

Can we eliminate the need for specifications by allowing everyone access to all source code?

Source code is complicated and provides more details than needed. Understanding or even reading every line of code is an excessive burden.

• Suppose you had to read the source code of Java libraries in order to use them!
• The same applies to developers of different parts of the libraries.

A client cares only about what the code does, not how it does it.

Source code is ambiguous even though it may appear unambiguous and concrete.

• Which details of code’s behavior are essential, and which are incidental?
• Code invariably gets rewritten.
• Client needs to know what they can rely on.
• What properties will be maintained over time?
• What properties might be changed by future optimization, improved algorithms, or just bug fixes?
• Implementer needs to know what features the client depends on, and which can be changed.

The Role of a Specification

With a specification, + the client (the user of a method or a class) agrees to rely only on information in the description/specification of the method or class for their part, and + the implementer promises to support everything in the specification, and outside of the specification has perfect liberty to make implementation decisions.

Specifications facilitate change by reducing the Medusa effect: it is the specifications that should be turned to stone rather than the implementation.

Sadly, much code that is written lacks clear specifications. Clients have to work out what a method/class does by using it and observing the results, and this leads to bugs because programs have unclear dependencies (that reduce simplicity and flexibility).

Behavioural equivalence

Consider these two methods. Are they the same or different?

 1 static int findA(int[] a, int val) {
 2     for (int i = 0; i < a.length; i++) {
 3         if (a[i] == val) return i;
 4     }
 5     return a.length;
 6 }
 7 
 8 static int findB(int[] a, int val) {
 9     for (int i = a.length -1 ; i >= 0; i--) {
10         if (a[i] == val) return i;
11     }
12     return -1;
13 }

Of course the code is different, so in that sense they are different. Our question is whether we could substitute one implementation for the other. Not only do these methods have different code, they actually have different behaviour:

• when val is missing, findA returns the length of a and findB returns -1;
• when val appears twice, findA returns the lower index and findB returns the higher.

But when val occurs at exactly one index of the array, the two methods behave the same. It may be that clients never rely on the behaviour in the other cases. So the notion of equivalence is in the eye of the beholder, that is, the client. In order to make it possible to substitute one implementation for another, and to know when this is acceptable, we need a specification that states exactly what the client depends on.

In this case, our specification might be: requires: val occurs in a effects: returns index i such that a[i] = val

The Structure of a Specification

A specification of a method consists of several clauses:

• a precondition, indicated by the keyword requires
• a postcondition, indicated by the keyword effects

The precondition is an obligation on the client (i.e., the caller of the method). It’s a condition over the state in which the method is invoked. If the precondition does not hold, the implementation of the method is free to do anything (including not terminating, throwing an exception, returning arbitrary results, making arbitrary modifications, etc.).

The postcondition is an obligation on the implementer of the method. If the precondition holds for the invoking state, the method is obliged to obey the postcondition, by returning appropriate values, throwing specified exceptions, modifying or not modifying objects, and so on.

The overall structure is a logical implication: if the precondition holds when the method is called, then the postcondition must hold when the method completes.

Specifications in Java

Some languages (notably Eiffel) incorporate preconditions and postconditions as a fundamental part of the language, as expressions that the runtime system (or even the compiler) can automatically check to enforce the contracts between clients and implementers.

Java does not go quite so far, but its static type declarations are effectively part of the precondition and postcondition of a method, a part that is automatically checked and enforced by the compiler. The rest of the contract — the parts that we can’t write as types — must be described in a comment preceding the method, and generally depends on human beings to check it and guarantee it.

Java has a convention for documentation comments, in which parameters are described by @param clauses and results are described by @return and @throws clauses. You should put the preconditions into @param where possible, and postconditions into @return and @throws.

A specification like this: static int find(int[] a, int val) requires: val occurs exactly once in a effects: returns index i such that a[i] = val … might be rendered in Java like this:

1 /**
2  * Find value in an array.
3  * @param a array to search; requires that val occurs exactly once in a
4  * @param val value to search for
5  * @return index i such that a[i] = val
6  */
7 static int find(int[] a, int val)

The Java API documentation is produced from Javadoc comments in the Java standard library source code. Documenting your specifications in Javadoc allows Eclipse to show you (and clients of your code) useful information, and allows you to produce HTML documentation in the same format as the Java API docs.

Null references

In Java, references to objects and arrays can also take on the special value null, which means that the reference doesn’t point to an object. Null values are an unfortunate hole in Java’s type system.

You can assign null to any non-primitive variable:

1 String s = null;
2 int a[] = null;

and the compiler happily accepts this code at compile time. But you’ll get errors at runtime because you can’t call any methods or use any fields with one of these references:

1 s.length()    // throws NullPointerException  
2 a.length      // throws NullPointerException

Note, in particular, that null is not the same as an empty string "" or an empty array. On an empty string or empty array, you can call methods and access fields. The length of an empty array or an empty string is 0. The length of a string variable that points to null throws a NullPointerException.

Null values are troublesome and unsafe, so much so that you’re well advised to remove them from your design vocabulary. For good Java programming — null values are implicitly disallowed as parameters and return values. So every method implicitly has a precondition on its object and array parameters that they be non-null. Every method that returns an object or an array implicitly has a postcondition that its return value is non-null. If a method allows null values for a parameter, it should explicitly state it, or if it might return a null value as a result, it should explicitly state it. But these are in general not good ideas.

Avoid null.

There are extensions to Java that allow you to forbid null directly in the type declaration, e.g.:

1 static boolean addAll(@NonNull List<T> list1, @NonNull List<T> list2)

where it can be checked automatically at compile time or runtime.

What a Specification May Talk About

A specification of a method can talk about the parameters and return value of the method, but it should never talk about local variables of the method or private fields of the method’s class. You should consider the implementation invisible to the reader of the spec.

In Java, the source code of the method is often unavailable to the reader of your spec, because the Javadoc tool extracts the spec comments from your code and renders them as HTML.

Testing and Specifications

In testing, we talk about black box tests that are chosen with only the specification in mind, and glass box tests that are chosen with knowledge of the actual implementation. But it’s important to note that even glass box tests must follow the specification. Your implementation may provide stronger guarantees than the specification calls for, or it may have specific behaviour where the specification is undefined. But your test cases should not count on that behaviour. Test cases must obey the contract, just like every other client.

For example, suppose you are testing this specification of find:

1 static int find(int[] a, int val)
2   requires: val occurs in a
3   effects:   returns index i such that a[i] = val

This spec has a strong precondition in the sense that val is required to be found; and it has a fairly weak postcondition in the sense that if val appears more than once in the array, this specification says nothing about which particular index of val is returned. Even if you implemented find so that it always returns the lowest index, your test case can’t assume that specific behaviour:

1 int[] array = new int[] { 7, 7, 7 };
2 assertEquals(0, find(array, 7));  // bad test case: violates the spec
3 assertEquals(7, array[find(array, 7)]);  // correct

Similarly, even if you implemented find so that it (sensibly) throws an exception when val isn’t found, instead of returning some arbitrary misleading index, your test case can’t assume that behaviour, because it can’t call find() in a way that violates the precondition.

So what does glass box testing mean, if it can’t go beyond the spec? It means you are trying to find new test cases that exercise different parts of the implementation, but still checking those test cases in an implementation-independent way.

Specifications for Mutating Methods

We will later discuss mutable vs. immutable objects, but here we will briefly mention the role of specification when dealing with mutability. Our specifications of find didn’t give us the opportunity to illustrate how to describe side-effects — changes to mutable data — in the postcondition.

Here’s a specification that describes a method that mutates an object:

1 static boolean addAll(List<T> list1, List<T> list2)
2   requires: list1 != list2
3   effects:   modifies list1 by adding the elements of list2 to the end of it, 
4   		     and returns true if list1 changed as a result of call

We’ve taken this, slightly simplified, from the Java List interface.

First, look at the postcondition. It gives two constraints: the first telling us how list1 is modified, and the second telling us how the return value is determined.

Second, look at the precondition. It tells us that the behaviour of the method if you attempt to add the elements of a list to itself is undefined. You can easily imagine why the implementor of the method would want to impose this constraint: it’s not likely to rule out any useful applications of the method, and it makes it easier to implement. The specification allows a simple implementation in which you take an element from list2 and add it to list1, then go on to the next element of list2 until you get to the end.

If list1 and list2 are the same list, this algorithm will not terminate — an outcome permitted by the specification.

Remember also our implicit precondition that list1 and list2 must be valid objects, rather than null. We’ll usually omit saying this because it’s virtually always required of object references.

Here is another 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()

Just as we’ve said that null is implicitly disallowed unless stated otherwise, we will also use the convention that mutation is disallowed unless stated otherwise. The spec of toLowerCase could explicitly state as an effect that “lst is not modified”, but in the absence of a postcondition describing mutation, we demand no mutation of the inputs.

Exceptions

Now that we’re writing specifications and thinking about how clients will use our methods, let’s discuss how to handle exceptional cases in a way that is safe from bugs and easy to understand.

A method’s signature — its name, parameter types, return type — is a core part of its specification, and the signature may also include exceptions that the method may trigger.

Exceptions for Signalling Bugs

You’ve probably already seen some exceptions in your Java programming so far, such as ArrayIndex­OutOfBounds­Exception (thrown when an array index foo[i] is outside the valid range for the array foo) or Null­Pointer­Exception (thrown when trying to call a method on a null object reference). These exceptions generally indicate bugs in your code, and the information displayed by Java when the exception is thrown can help you find and fix the bug.

ArrayIndex­OutOfBounds- and Null­Pointer­Exception are probably the most common exceptions of this sort. Other examples include:

• ArithmeticException, thrown for arithmetic errors like integer division by zero.
• NumberFormatException, thrown by methods like Integer.parseInt if you pass in a string that cannot be parsed into an integer.

Exceptions for Special Results

Exceptions are not just for signalling bugs. They can be used to improve the structure of code that involves procedures with special results.

An unfortunately common way to handle special results is to return special values. Lookup operations in the Java library are often designed like this: you get an index of -1 when expecting a positive integer, or a null reference when expecting an object. This approach is OK if used sparingly, but it has two problems. First, it’s tedious to check the return value. Second, it’s easy to forget to do it. (We’ll see that by using exceptions you can get help from the compiler in this.)

Also, it’s not always easy to find a ‘special value’. Suppose we have a BirthdayBook class with a lookup method. Here’s one possible method signature: java class BirthdayBook { LocalDate lookup(String name) { ... } }

(LocalDate is part of the Java API.)

What should the method do if the birthday book doesn’t have an entry for the person whose name is given? Well, we could return some special date that is not going to be used as a real date. Bad programmers have been doing this for decades; they would return 9/9/99, for example, since it was obvious that no program written in 1960 would still be running at the end of the century. (They were wrong, by the way.)

Here’s a better approach. The method throws an exception: java LocalDate lookup(String name) throws NotFoundException { ... if ( ...not found... ) throw new NotFoundException(); ... }

and the caller handles the exception with a catch clause. For example: java BirthdayBook birthdays = ... try { LocalDate birthdate = birthdays.lookup("Alyssa"); } catch (NotFoundException nfe) { ... }

Now there is no need for any special value, nor the checking associated with it.

Checked and Unchecked Exceptions

We’ve seen two different purposes for exceptions: special results and bug detection. As a general rule, you will want to use checked exceptions to signal special results and unchecked exceptions to signal bugs. In a later chapter, we will refine this a bit.

Some terminology: checked exceptions are called that because they are checked by the compiler:

• If a method might throw a checked exception, the possibility must be declared in its signature. Not­Found­Exception would be a checked exception, and that’s why the signature ends throws Not­Found­Exception.
• If a method calls another method that may throw a checked exception, it must either handle it, or declare the exception itself, since if it isn’t caught locally it will be propagated up to callers.

So if you call BirthdayBook’s lookup method and forget to handle the Not­Found­Exception, the compiler will reject your code. This is very useful, because it ensures that exceptions that are expected to occur will be handled.

Unchecked exceptions, in contrast, are used to signal bugs. These exceptions are not expected to be handled by the code except perhaps at the top level. We wouldn’t want every method up the call chain to have to declare that it (might) throw all the kinds of bug-related exceptions that can happen at lower call levels: index out of bounds, null pointers, illegal arguments, assertion failures, etc.

As a result, for an unchecked exception the compiler will not check for try-catch or a throws declaration. Java still allows you to write a throws clause for an unchecked exception as part of a method signature, but this has no effect, and is thus a bit funny, and we don’t recommend doing it.

All exceptions may have a message associated with them. If not provided in the constructor, the reference to the message string is null.

Throwable Hierarchy

To understand how Java decides whether an exception is checked or unchecked, let’s look at the class hierarchy for Java exceptions.

Throwable is the class of objects that can be thrown or caught. Throwable’s implementation records a stack trace at the point where the exception was thrown, along with an optional string describing the exception. Any object used in a throw or catch statement, or declared in the throws clause of a method, must be a subclass of Throwable.

Error is a subclass of Throwable that is reserved for errors produced by the Java runtime system, such as StackOverflow­Error and OutOfMemory­Error. For some reason Assertion­Error also extends Error, even though it indicates a bug in user code, not in the runtime. Errors should be considered unrecoverable, and are generally not caught.

Here’s how Java distinguishes between checked and unchecked exceptions:

• RuntimeException, Error, and their subclasses are unchecked exceptions. The compiler doesn’t require them to be declared in the throws clause of a method that throws them, and doesn’t require them to be caught or declared by a caller of such a method.
• All other throwables — Throwable, Exception, and all of their subclasses except for those of the RuntimeException and Error lineage — are checked exceptions. The compiler requires these exceptions to be caught or declared when it’s possible for them to be thrown.

When you define your own exceptions, you should either subclass RuntimeException (to make it an unchecked exception) or Exception (to make it checked). Programmers generally don’t subclass Error or Throwable, because these are reserved by Java itself.

Exception Design Considerations

The rule we have given — use checked exceptions for special results (i.e., anticipated situations), and unchecked exceptions to signal bugs (unexpected failures) — makes sense, but it isn’t the end of the story. The snag is that exceptions in Java aren’t as lightweight as they might be.

Aside from the performance penalty, exceptions in Java incur another (more serious) cost: they’re a pain to use, in both method design and method use. If you design a method to have its own (new) exception, you have to create a new class for the exception. If you call a method that can throw a checked exception, you have to wrap it in a try-catch statement (even if you know the exception will never be thrown). This latter stipulation creates a dilemma. Suppose, for example, you’re designing a queue abstraction. Should popping the queue throw a checked exception when the queue is empty? Suppose you want to support a style of programming in the client in which the queue is popped (in a loop say) until the exception is thrown. So you choose a checked exception. Now some client wants to use the method in a context in which, immediately prior to popping, the client tests whether the queue is empty and only pops if it isn’t. Maddeningly, that client will still need to wrap the call in a try-catch statement.

This suggests a more refined rule:

• You should use an unchecked exception only to signal an unexpected failure (i.e. a bug), or if you expect that clients will usually write code that ensures the exception will not happen, because there is a convenient and inexpensive way to avoid the exception;
• Otherwise you should use a checked exception.

Here are some examples of applying this rule to hypothetical methods:

• Queue.pop() throws an unchecked Empty­Queue­Exception when the queue is empty, because it’s reasonable to expect the caller to avoid this with a call like Queue.size() or Queue.isEmpty().
• Url.getWebPage() throws a checked IOException when it can’t retrieve the web page, because it’s not easy for the caller to prevent this.
• int integerSquareRoot(int x) throws a checked Not­Perfect­Square­Exception when x has no integral square root, because testing whether x is a perfect square is just as hard as finding the actual square root, so it’s not reasonable to expect the caller to prevent it.

The cost of using exceptions in Java is one reason that many Java API’s use the null reference as a special value. It’s not a terrible thing to do, so long as it’s done judiciously, and carefully specified.

Abuse of Exceptions

Here’s an example from Effective Java by Joshua Bloch (Item 57 in the 2nd edition). java try { int i = 0; while (true) a[i++].f(); } catch (ArrayIndexOutOfBoundsException e) { }

What does this code do? It is not at all obvious from inspection, and that’s reason enough not to use it. … The infinite loop terminates by throwing, catching, and ignoring an ArrayIndex­OutOfBounds­Exception when it attempts to access the first array element outside the bounds of the array.

It is supposed to be equivalent to: java for (int i = 0; i < a.length; i++) { a[i].f(); }

Or (using appropriate type T) to: java for (T x : a) { x.f(); }

The exception-based idiom, Bloch writes:

… is a misguided attempt to improve performance based on the faulty reasoning that, since the VM checks the bounds of array accesses, the normal loop termination test (i < a.length) is redundant and should be avoided.

However, because exceptions in Java are designed for use only under exceptional circumstances, few, if any, JVM implementations attempt to optimize their performance. On a typical machine, the exception-based idiom runs 70 times slower than the standard one when looping from 0 to 99.

Much worse than that, the exception-based idiom is not even guaranteed to work! Suppose the computation of f() in the body of the loop contains a bug that results in an out-of-bounds access to some unrelated array. What happens?

If a reasonable loop idiom were used, the bug would generate an uncaught exception, resulting in immediate thread termination with a full stack trace. If the misguided exception-based loop were used, the bug-related exception would be caught and misinterpreted as a normal loop termination.

Test Yourself

• Questions
• Answers

Designing Specifications

Now, we will look at different specs for similar behaviours, and talk about the tradeoffs between them.

We will look at three dimensions for comparing specs:

• How deterministic it is: Does the spec define only a single possible output for a given input, or allow the implementor to choose from a set of legal outputs?
• How declarative it is: Does the spec just characterize what the output should be, or does it explicitly say how to compute the output?
• How strong it is: Does the spec have a small set of legal implementations, or a large set?

Deterministic vs. Underdetermined specs

Recall the two example implementations of find we began with in the previous part:

 1 static int findA(int[] a, int val) {
 2     for (int i = 0; i < a.length; i++) {
 3         if (a[i] == val) return i;
 4     }
 5     return a.length;
 6 }
 7 
 8 static int findB(int[] a, int val) {
 9     for (int i = a.length -1 ; i >= 0; i--) {
10         if (a[i] == val) return i;
11     }
12     return -1;
13 }

Here is one possible specification of find:

1 static int find(int[] a, int val)
2   requires: val occurs exactly once in a
3   effects:  returns index i such that a[i] = val

This specification is deterministic: when presented with a state satisfying the precondition, the outcome is determined. Both findA and findB satisfy the specification, so if this is the specification on which the clients relied, the two implementations are equivalent and substitutable for one another. (Of course a procedure must have the name demanded by the specification; here we are using different names to allow us to talk about the two versions. To use either, you’d have to change its name to find.)

Here is a slightly different specification:

1 static int find(int[] a, int val)
2   requires: val occurs in a
3   effects:  returns index i such that a[i] = val

This specification is not deterministic. Such a specification is often said to be non-deterministic, but this is a bit misleading. Non-deterministic code is code that you expect to sometimes behave one way and sometimes another. This can happen, for example, with concurrency: the scheduler chooses to run threads in different orders depending on conditions outside the program.

But a ‘non-deterministic’ specification doesn’t call for such non-determinism in the code. The behaviour specified is not non-deterministic but under-determined. In this case, the specification doesn’t say which index is returned if val occurs more than once; it simply says that if you look up the entry at the index given by the returned value, you’ll find val.

This specification is again satisfied by both findA and findB, each ‘resolving’ the under-determinedness in its own way. A client of find can’t predict which index will be returned, but should not expect the behaviour to be truly non-deterministic. Of course, the specification is satisfied by a non-deterministic procedure too — for example, one that rather improbably tosses a coin to decide whether to start searching from the top or the bottom of the array. But in almost all cases we’ll encounter, non-determinism in specifications offers a choice that is made by the implementor at implementation time, and not at runtime.

So for this specification, too, the two versions of find are equivalent.

Finally, here’s a specification that distinguishes the two:

1 static int find(int[] a, int val)
2 // effects: returns largest index i such that
3 //          a[i] = val, or -1 if no such i

Declarative vs. operational specs

Generally speaking, there are two kinds of specifications:

• • Operational specifications give a series of steps that the method performs; pseudocode descriptions are operational.
• Declarative specifications don’t give details of intermediate steps. Instead, they just give properties of the final outcome, and how it’s related to the initial state.

Almost always, declarative specifications are preferable. They’re usually shorter, easier to understand, and most importantly, they don’t expose implementation details inadvertently that a client may rely on (and then find no longer hold when the implementation is changed). For example, if we want to allow either implementation of find, we would not want to say in the spec that the method “goes down the array until it finds val,” since aside from being rather vague, this spec suggests that the search proceeds from lower to higher indices and that the lowest will be returned, which perhaps the specifier did not intend.

One reason programmers sometimes lapse into operational specifications is because they’re using the spec comment to explain the implementation for a maintainer. Don’t. Do that using comments within the body of the method, not in the spec comment.

Stronger vs. Weaker Specifications

Suppose you want to substitute one method for another. How do you compare the specifications?

A specification A is stronger than or equal to a specification B if

• A’s precondition is weaker than or equal to B’s
• A’s postcondition is stronger than or equal to B’s, for the states that satisfy B’s precondition.

If this is the case, then an implementation that satisfies A can be used to satisfy B as well.

These two rules embody several ideas. They tell you that you can always weaken the precondition; placing fewer demands on a client will never upset them. And you can always strengthen the post-condition, which means making more promises.

For example, this spec for find:

1 static int find1(int[] a, int val)
2   requires: val occurs exactly once in a
3   effects:  returns index i such that a[i] = val

can be replaced in any context by:

1 static int findStronger2(int[] a, int val)
2   requires: val occurs at least once in a
3   effects:  returns index i such that a[i] = val

which has a weaker precondition.

This in turn can be replaced by:

1 static int findStronger3(int[] a, int val)
2   requires: val occurs at least once in a
3   effects:  returns lowest index i such that a[i] = val

which has a stronger postcondition.

What about this specification:

1 static int find4(int[] a, int val)
2   requires: nothing
3   effects:  returns index i such that a[i] = val,
4             or -1 if no such i

Diagramming Specifications

Imagine (very abstractly) the space of all possible Java methods.

Each point in this space represents a method implementation.

Here we’ll diagram findA and findB defined above.

A specification defines a region in the space of all possible implementations.

A given implementation either behaves according to the spec, satisfying the precondition-implies-postcondition contract (it is inside the region), or it does not (outside the region).

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Designing%20Specifications/fig1.png”></img>

Both findA and findB satisfy findStronger2, so they are inside the region defined by that spec.

We can imagine clients looking in on this space: the specification acts as a firewall. Implementors have the freedom to move around inside the spec, changing their code without fear of upsetting a client. Clients don’t know which implementation they will get. They must respect the spec, but also have the freedom to change how they’re using the implementation without fear that it will suddenly break.

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Designing%20Specifications/fig2.png”></img>

How will similar specifications relate to one another? Suppose we start with specification S1 and use it to create a new specification S2.

If S2 is stronger than S1, how will these specs appear in our diagram?

• Let’s start by strengthening the postcondition. If S2’s postcondition is now stronger than S1’s, S2 is the stronger specification.

Think about what strengthening the postcondition means for implementors: it means they have less freedom, the requirements on their output are stronger. Perhaps they previously satisfied findStronger2 by returning any index i, but now the spec demands the lowest index i. So there are now implementations inside findStronger2 but outside findStronger3.

Could there be implementations inside findStronger3 but outside findStronger2? No. All of those implementations satisfy a stronger postcondition than what findStronger2 demands.

• Think through what happens if we weaken the precondition, which will again make S2 a stronger specification. Implementations will have to handle new inputs that were previously excluded by the spec. If they behaved badly on those inputs before, we wouldn’t have noticed, but now their bad behaviour is exposed.

<img src=”https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/Designing%20Specifications/fig3.png”></img>

We see that when S2 is stronger than S1, it defines a smaller region in this diagram; a weaker specification defines a larger region.

In our figure, since findB iterates from the end of the array a, it does not satisfy findStronger3 and is outside that region.

A specification S2 that is neither stronger nor weaker than S1 might overlap (such that there exist implementations that satisfy only S1, only S2, and both S1 and S2) or might be disjoint.

Designing Good Specifications

What makes a good method? Designing a method means primarily writing a specification.

About the form of the specification: it should be succinct, clear, and well-structured, so that it’s easy to read.

The content of the specification, however, is harder to prescribe. There are no infallible rules, but there are some useful guidelines.

The specification should be coherent: it shouldn’t have lots of different cases. Long argument lists, deeply nested if-statements, and boolean flags are a sign of trouble.

Consider this specification: static int minFind(int[] a, int[] b, int val) effects: returns smallest index in arrays a and b at which val appears

Is this a well-designed procedure? Probably not: it’s incoherent, since it does two things (finding and minimizing) that are not really related. It would be better to use two separate procedures.

The results of a call should be informative. Consider the specification of a method that puts a value in a map:

1 static V put (Map<K,V> map, K key, V val)
2   requires: val may be null, 
3             and map may contain null values
4   effects:  inserts (key, val) into the mapping, 
5             overriding any existing mapping for key, 
6             and returns old value for key, unless none, 
7             in which case it returns null

Note that the precondition does not rule out null values so the map can store nulls. But the postcondition uses null as a special return value for a missing key. This means that if null is returned, you can’t tell whether the key was not bound previously, or whether it was in fact bound to null. This is not a very good design, because the return value is useless unless you know for sure that you didn’t insert nulls.

The specification should be strong enough. There’s no point throwing a checked exception for a bad argument but allowing arbitrary mutations, because a client won’t be able to determine what mutations have actually been made. Here’s a specification illustrating this flaw (and also written in an inappropriately operational style):

1 static void addAll(List<T> list1, List<T> list2)
2   effects: adds the elements of list2 to list1,
3            unless it encounters a null element,
4            at which point it throws a NullPointerException

The specification should also be weak enough. Consider this specification for a method that opens a file:

1 static File open(String filename)
2   effects: opens a file named filename

This is a bad specification. It lacks important details: is the file opened for reading or writing? Does it already exist or is it created? And it’s too strong, since there’s no way it can guarantee to open a file. The process in which it runs may lack permission to open a file, or there might be some problem with the file system beyond the control of the program. Instead, the specification should say something much weaker: that it attempts to open a file, and if it succeeds, the file has certain properties.

The specification should use abstract types where possible, giving more freedom to both the client and the implementor. In Java, this often means using an interface type, like Map or Reader, instead of specific implementation types like HashMap or FileReader.

Consider this specification:

1 static ArrayList<T> reverse(ArrayList<T> list)
2   effects: returns a new list 
3            which is the reversal of list, i.e., 
4            newList[i] == list[n-i-1] for all 0 <= i < n, 
5            where n = list.size()

This forces the client to pass in an ArrayList, and forces the implementor to return an ArrayList, even if there might be alternative List implementations that they would rather use. Since the behaviour of the specification doesn’t depend on anything specific about ArrayList, it would be better to write this spec in terms of the more abstract List<T>.

Precondition or Postcondition?

Another design issue is whether to use a precondition, and if so, whether the method code should attempt to make sure the precondition has been met before proceeding. In fact, the most common use of preconditions is to demand a property precisely because it would be hard or expensive for the method to check it.

As mentioned above, a non-trivial precondition inconveniences clients, because they have to ensure that they don’t call the method in a bad state (that violates the precondition); if they do, there is no predictable way to recover from the error. So users of methods don’t like preconditions. That’s why the Java API classes, for example, invariably specify (as a postcondition) that they throw unchecked exceptions when arguments are inappropriate. This approach makes it easier to find the bug or incorrect assumption in the caller code that led to passing bad arguments.

In general, it’s better to fail fast, as close as possible to the site of the bug, rather than let bad values propagate through a program far from their original cause.

Sometimes, it’s not feasible to check a condition without making a method unacceptably slow, and a precondition is often necessary in this case. If we wanted to implement the find() method using binary search, we would have to require that the array be sorted. Forcing the method to actually check that the array is sorted would defeat the entire purpose of the binary search: to obtain a result in logarithmic and not linear time.

The decision of whether to use a precondition is an engineering judgment. The key factors are the cost of the check (in writing and executing code), and the scope of the method. If it’s only called locally in a class, the precondition can be discharged by carefully checking all the sites that call the method. But if the method is public, and used by other developers, it would be less wise to use a precondition. Instead, like the Java API classes, you should throw an exception.

About access control

We have been using public for almost all of our methods, without really thinking about it. The decision to make a method public or private is actually a decision about the contract of the class.

<p style=”text-align: right; background: #eaeaea; padding: 15px;”> <strong>Additional Reading</strong><br /> <a href=”http://docs.oracle.com/javase/tutorial/java/package/index.html”>Packages</a> in the Java Tutorials.<br /> <a href=”http://docs.oracle.com/javase/tutorial/java/javaOO/accesscontrol.html”>Controlling Access</a> in the Java Tutorials. </p>

Public methods are freely accessible to other parts of the program. Making a method public advertises it as a service that your class is willing to provide. If you make all your methods public — including helper methods that are really meant only for local use within the class — then other parts of the program may come to depend on them, which will make it harder for you to change the internal implementation of the class in the future. Your code won’t be as ready for change.

Making internal helper methods public will also add clutter to the visible interface your class offers. Keeping internal things private makes your class’s public interface smaller and more coherent (meaning that it does one thing and does it well). Your code will be easier to understand.

We will see even stronger reasons to use private when we start to write classes with persistent internal state. Protecting this state will help keep the program safe from bugs.

About Static vs. Instance methods

<p style=”text-align: right; background: #eaeaea; padding: 15px;”> Read about the <a href=”http://www.codeguru.com/java/tij/tij0037.shtml#Heading79”><tt>static</tt> keyword on CodeGuru.</a> </p>

We have also been using static for almost all of our methods, again without much discussion. Static methods are not associated with any particular instance of a class, while instance methods (declared without the static keyword) must be called on a particular object.

Specifications for instance methods are written just the same way as specifications for static methods, but they will often refer to properties of the instance on which they were called.

For example, by now we’re very familiar with this specification:

1 static int find(int[] arr, int val)
2 // requires: val occurs in arr
3 // effects:  returns index i such that arr[i] = val

Instead of using an int[], what if we had a class IntArray designed for storing arrays of integers? The IntArray class might provide an instance method with the specification:

1 int find(int val)
2 // requires: val occurs in *this array*
3 // effects:  returns index i such that *the value at index i in this array* is v\
4 al

We will have much more to say about specifications for instance methods later.

Summary

A specification acts as a crucial firewall between implementor and client — both between people (or the same person at different times) and between code. Specifications make separate development possible: the client is free to write code that uses a module without seeing its source code, and the implementor is free to write the implementation code without knowing how it will be used.

Declarative specifications are the most useful in practice. Preconditions (which weaken the specification) make life harder for the client, but applied judiciously they are a vital tool in the software designer’s repertoire, allowing the implementor to make necessary assumptions.

As always, our goal is to design specifications that make our software:

• Safe from bugs. Without specifications, even the tiniest change to any part of our program could be the tipped domino that knocks the whole thing over. Well-structured, coherent specifications minimize misunderstandings and maximize our ability to write correct code with the help of static checking, careful reasoning, testing, and code review.
• Easy to understand. A well-written declarative specification means the client doesn’t have to read or understand the code. You’ve probably never read the code for, say, Python dict.update, and doing so isn’t nearly as useful to the Python programmer as reading the declarative spec.
• Ready for change. An appropriately weak specification gives freedom to the implementor, and an appropriately strong specification gives freedom to the client. We can even change the specs themselves, without having to revisit every place they’re used, as long as we’re only strengthening them: weakening preconditions and strengthening postconditions.

Test Yourself

• Questions
• Answers

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

• Questions

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?

• Iterator?
• List?
• Collection?

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

• Questions
• Answers

Abstract Data Types

Abstract Data Types

In this reading, we look at a powerful idea, abstract data types, which enable us to separate how we use a data structure in a program from the particular form of the data structure itself.

Abstract data types address a particularly dangerous problem: clients making assumptions about the type’s internal representation. We’ll see why this is dangerous and how it can be avoided. We’ll also discuss the classification of operations, and some principles of good design for abstract data types.

What Abstraction Means

Abstract data types are an instance of a general principle in software engineering, which goes by many names with slightly different shades of meaning. Here are some of the names that are used for this idea:

• Abstraction. Omitting or hiding low-level details with a simpler, higher-level idea.
• Modularity. Dividing 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.
• Encapsulation. 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.
• Information hiding. Hiding details of a module’s implementation from the rest of the system, so that those details can be changed later without changing the rest of the system.
• Separation of concerns. Making a feature (or “concern”) the responsibility of a single module, rather than spreading it across multiple modules.

As a software engineer, you should know these terms, because you will run into them frequently. The fundamental purpose of all of these ideas is to help achieve the three important properties that we care about: safety from bugs, ease of understanding, and readiness for change.

User-Defined Types

In the early days of computing, a programming language came with built-in types (such as integers, booleans, strings, etc.) and built-in procedures, e.g., for input and output. Users could define their own procedures: that’s how large programs were built.

A major advance in software development was the idea of abstract types: that one could design a programming language to allow user-defined types, too. This idea came out of the work of many researchers, notably Dahl (the inventor of the Simula language), Hoare (who developed many of the techniques we now use to reason about abstract types), Parnas (who coined the term information hiding and first articulated the idea of organizing program modules around the secrets they encapsulated), Liskov and Guttag, who did seminal work in the specification of abstract types, and in programming language support for them.

The key idea of data abstraction is that a type is characterized by the operations you can perform on it. A number is something you can add and multiply; a string is something you can concatenate and take substrings of; a boolean is something you can negate, and so on.

In a sense, users could already define their own types in early programming languages: you could create a record type date, for example, with integer fields for day, month, and year. But what made abstract types new and different was the focus on operations: the user of the type would not need to worry about how its values were actually stored, in the same way that a programmer can ignore how the compiler actually stores integers. All that matters is the operations.

In Java, as in many modern programming languages, the separation between built-in types and user-defined types is a bit blurry. The classes in java.lang, such as Integer and Boolean are built-in; whether you regard all the collections of java.util as built-in is less clear (and not very important anyway). Java complicates the issue by having primitive types that are not objects. The set of these types, such as int and boolean, cannot be extended by the user.

Classifying Types and Operations

Types, whether built-in or user-defined, can be classified as mutable or immutable.

The objects of a mutable type can be changed: that is, they provide operations which when executed cause the results of other operations on the same object to give different results. So Date is mutable, because you can call setMonth( ) and observe the change with the getMonth( ) operation. But String is immutable, because its operations create new String objects rather than changing existing ones. Sometimes a type will be provided in two forms, a mutable and an immutable form. StringBuilder, for example, is a mutable version of String (although the two are certainly not the same Java type, and are not interchangeable).

The operations of an abstract type can be classified as follows:

• Creators create new objects of the type. A creator may take an object as an argument, but not an object of the type being constructed.
• Producers create new objects from old objects of the type. The concat() method of String , for example, is a producer: it takes two strings and produces a new one representing their concatenation.
• Observers take objects of the abstract type and return objects of a different type. The size() method of List, for example, returns an int.
• Mutators change objects. The add() method of List, for example, mutates a list by adding an element to the end.

We can summarize these distinctions schematically like this (explanation to follow):

• creator: t^* → T
• producer: T⁺, t^* → T
• observer: T⁺, t^* → t
• mutator: T⁺, t^* → void|t|T

These show informally the shape of the signatures of operations in the various classes.

Each T is the abstract type itself; each t is some other type.

The + marker indicates that the type may occur one or more times in that part of the signature, and the * marker indicates that it occurs zero or more times.

For example, a producer may take two values of the abstract type, like String.concat() does.

The occurrences of t on the left may also be omitted, since some observers take no non-abstract arguments, and some take several.

Mutators are often signalled by a void return type. A method that returns void must be called for some kind of side-effect, since otherwise it doesn’t return anything. But not all mutators return void. For example, Set.add() returns a boolean that indicates whether the set was actually changed. In Java’s graphical user interface toolkit, Component.add() returns the object itself, so that multiple add() calls can be chained together.

Abstract Data Type Examples

Here are some examples of abstract data types, along with some of their operations, grouped by kind.

int is Java’s primitive integer type. int is immutable, so it has no mutators.

• creators: the numeric literals 0, 1, 2, …
• producers: arithmetic operators +, -, ,
• observers: comparison operators ==, !=, <, >
• mutators: none (it’s immutable)

List is Java’s list interface. List is mutable. List is also an interface, which means that other classes provide the actual implementation of the data type. These classes include ArrayList and LinkedList.

• creators: ArrayList and LinkedList constructors, Collections.singletonList
• producers: Collections.unmodifiableList
• observers: size(), get()
• mutators: add(), remove(), addAll(), Collections.sort()

String is Java’s string type. String is immutable.

• creators: String constructors
• producers: concat, substring, toUpperCase
• observers: length, charAt
• mutators: none (it’s immutable)

This classification gives some useful terminology, but it’s not perfect. In complicated data types, there may be an operation that is both a producer and a mutator, for example. Some people reserve the term producer only for operations that do no mutation.

Designing an Abstract Type

Designing an abstract type involves choosing good operations and determining how they should behave. Here are a few rules of thumb.

It’s better to have a few, simple operations that can be combined in powerful ways, rather than lots of complex operations.

Each operation should have a well-defined purpose, and should have a coherent behavior rather than a panoply of special cases. We probably shouldn’t add a sum operation to List, for example. It might help clients who work with lists of Integers, but what about lists of Strings? Or nested lists? All these special cases would make sum a hard operation to understand and use.

The set of operations should be adequate in the sense that there must be enough to do the kinds of computations clients are likely to want to do. A good test is to check that every property of an object of the type can be extracted. For example, if there were no get operation, we would not be able to find out what the elements of a list are. Basic information should not be inordinately difficult to obtain. For example, the size method is not strictly necessary for List, because we could apply get on increasing indices until we get a failure, but this is inefficient and inconvenient.

The type may be generic: a list or a set, or a graph, for example. Or it may be domain-specific: a street map, an employee database, a phone book, etc. But it should not mix generic and domain-specific features.

A Deck type intended to represent a sequence of playing cards shouldn’t have a generic add method that accepts arbitrary objects like ints or Strings. Conversely, it wouldn’t make sense to put a domain-specific method like dealCards into the generic type List.

Representation Independence

Critically, a good abstract data type should be representation independent. This means that the use of an abstract type is independent of its representation (the actual data structure or data fields used to implement it), so that changes in representation have no effect on code outside the abstract type itself.

For example, the operations offered by List are independent of whether the list is represented as a linked list or as an array.

You won’t be able to change the representation of an ADT at all unless its operations are fully specified with preconditions and postconditions, so that clients know what to depend on, and you know what you can safely change.

Example: Different Representations for Strings

Let’s look at a simple abstract data type to see what representation independence means and why it’s useful. The MyString type below has far fewer operations than the real Java String, and their specs are a little different, but it’s still illustrative. Here are the specs for the ADT:

 1 /** String represents an immutable sequence of characters. */
 2 public class MyString { 
 3 
 4     //////////////////// Example of a creator operation ///////////////
 5     /** @param b a boolean value
 6       * @return string representation of b, either "true" or "false" */
 7     public static MyString valueOf(boolean b) { ... }
 8     
 9     //////////////////// Examples of observer operations ///////////////
10     /** @return number of characters in this string */
11     public int length() { ... }
12     
13     /** @param i character position (requires 0 <= i < string length)
14       * @return character at position i
15       */
16     public char charAt(int i) { ... }
17 
18     //////////////////// Example of a producer operation ///////////////    
19     /** Get the substring between start (inclusive) and end (exclusive).
20      * @param start starting index
21      * @param end ending index.  Requires 0 <= start <= end <= string length.
22      * @return string consisting of charAt(start)...charAt(end-1)
23      */
24     public MyString substring (int start, int end) { ... }
25 }

These public operations and their specifications are the only information that a client of this data type is allowed to know.

Following the test-first programming paradigm, in fact, the first client we should create is a test suite that exercises these operations according to their specs.

At the moment, however, writing test cases that use assertEquals directly on MyString objects wouldn’t work, because we don’t have an equality operation defined on these MyStrings. We’ll talk about how to implement equality carefully in subsequent discussions. For now, the only operations we can perform with MyStrings are the ones we’ve defined above: valueOf, length, charAt, and substring. Our tests have to limit themselves to those operations. For example, here’s one test for the valueOf operation:

1 MyString s = MyString.valueOf(true);
2 assertEquals(4, s.length());
3 assertEquals('t', s.charAt(0));
4 assertEquals('r', s.charAt(1));
5 assertEquals('u', s.charAt(2));
6 assertEquals('e', s.charAt(3));

We’ll come back to the question of testing ADTs in a later section of this reading.

For now, let’s look at a simple representation for MyString: just an array of characters, exactly the length of the string (no extra room at the end). Here’s how that internal representation would be declared, as an instance variable within the class:

1 private char[] a;

With that choice of representation, the operations would be implemented in a straightforward way:

 1 public static MyString valueOf(boolean b) {
 2     MyString s = new MyString();
 3     s.a = b ? new char[] { 't', 'r', 'u', 'e' } 
 4             : new char[] { 'f', 'a', 'l', 's', 'e' };
 5     return s;
 6 }
 7 
 8 public int length() {
 9     return a.length;
10 }
11 
12 public char charAt(int i) {
13     return a[i];
14 }
15 
16 public MyString substring (int start, int end) {
17     MyString that = new MyString();
18     that.a = new char[end - start];
19     System.arraycopy(this.a, start, that.a, 0, end - start);
20     return that;
21 }

Question to ponder: Why don’t charAt( ) and substring() have to check whether their parameters are within the valid range? What do you think will happen if the client calls these implementations with illegal inputs?

One problem with this implementation is that it’s passing up an opportunity for performance improvement. Because this data type is immutable, the substring() operation doesn’t really have to copy characters out into a fresh array. It could just point to the original MyString’s character array and keep track of the start and end that the new substring object represents. The String implementation in some versions of Java do this.

To implement this optimization, we could change the internal representation of this class to:

1 private char[] a;
2 private int start;
3 private int end;

With this new representation, the operations are now implemented like this:

 1     public static MyString valueOf(boolean b) {
 2         MyString s = new MyString();
 3         s.a = b ? new char[] { 't', 'r', 'u', 'e' } 
 4                 : new char[] { 'f', 'a', 'l', 's', 'e' };
 5         s.start = 0;
 6         s.end = s.a.length;
 7         return s;
 8     }
 9     
10     public int length() {
11         return end - start;
12     }
13     
14     public char charAt(int i) {
15       return a[start + i];
16     }
17 
18     public MyString substring (int start, int end) {
19         MyString that = new MyString();
20         that.a = this.a;
21         that.start = this.start + start;
22         that.end = this.start + end;
23         return that;
24     }

Because MyString’s existing clients depend only on the specs of its public methods, not on its private fields, we can make this change without having to inspect and change all that client code. That’s the power of representation independence.

Interfaces

In the Java tutorial, read these pages:

• Defining an Interface
• Implementing an Interface
• Using an Interface as a Type

Java’s interface is a useful language mechanism for expressing an abstract data type. An interface in Java is a list of method signatures, but no method bodies. A class implements an interface if it declares the interface in its implements clause, and provides method bodies for all of the interface’s methods. So one way to define an abstract data type in Java is as an interface, with its implementation as a class implementing that interface.

One advantage of this approach is that the interface specifies the contract for the client and nothing more. The interface is all a client programmer needs to read to understand the ADT. The client can’t create inadvertent dependencies on the ADT’s rep, because instance variables can’t be put in an interface at all. The implementation is kept well and truly separated, in a different class altogether.

Another advantage is that multiple different representations of the abstract data type can co-exist in the same program, as different classes implementing the interface. When an abstract data type is represented just as a single class, without an interface, it’s harder to have multiple representations. We saw that in the MyString example above, which was a single class. We couldn’t have both representations for MyString in the same program.

Java’s static type checking allows the compiler to catch many mistakes in implementing an ADT’s contract. For instance, it is a compile-time error to omit one of the required methods, or to give it the wrong return type. Unfortunately, the compiler doesn’t check for us that the code adheres to the specs of those methods that are written in documentation comments.

Example: Set

Java’s collection classes provide a good example of the idea of separating interface and implementation. Let’s consider as an example one of the ADTs from the Java collections library, Set. Set is the ADT of finite sets of elements of some other type E. Here is a simplified version of the Set interface:

1 public interface Set<E> {
2   ...

We can match Java interfaces with our classification of ADT operations, starting with a creator:

1     // example of creator method
2     /** Make an empty set.
3      * @return a new set instance, initially empty
4      */
5     public static Set<E> make() { ... } 

Unfortunately, Java interfaces are not allowed to have constructors, but (as of Java 8) they are allowed to contain static methods. So we can implement creator operations as static methods. This design pattern, using a static method as a creator instead of a constructor, is called a factory method. The MyString.valueOf( ) method we saw earlier is also a factory method.

 1     // examples of observer methods
 2 
 3     /** Get size of the set.
 4      * @return the number of elements in this set. */
 5     public int size();
 6 
 7     /** Test for membership.
 8      * @param e an element
 9      * @return true iff this set contains e. */
10     public boolean contains(E e);

Next we have two observer methods. Notice how the specs are in terms of our abstract notion of a set; it would be malformed to mention the details of any particular implementation of sets with particular private fields. These specs should apply to any valid implementation of the set ADT.

 1     // examples of mutator methods
 2     
 3     /** Modifies this set by adding e to the set.
 4      * @param e element to add. */
 5     public void add(E e);
 6 
 7     /** Modifies this set by removing e, if found.
 8      * If e is not found in the set, has no effect.
 9      * @param e element to remove.*/
10     public void remove(E e);

The story for these three mutator methods is basically the same as for the observers. We still write specs at the level of our abstract model of sets.

In the Java tutorial, read these pages:

• Lesson: Interfaces
• The Set Interface
• The List Interface
• Set Implementations
• List Implementations

Why Interfaces?

Interfaces are used pervasively in real Java code. Not every class is associated with an interface, but there are a few good reasons to bring an interface into the picture.

• Documentation for both the compiler and for humans. Not only does an interface help the compiler catch ADT implementation bugs, but it is also much more useful for a human to read than the code for a concrete implementation. Such an implementation intersperses ADT-level types and specs with implementation details.
• Allowing performance trade-offs. Different implementations of the ADT can provide methods with very different performance characteristics. Different applications may work better with different choices, but we would like to code these applications in a way that is representation-independent. From a correctness standpoint, it should be possible to drop in any new implementation of a key ADT with simple, localized code changes.
• Flexibility in providing invariants. Different implementations of an ADT can provide different invariants.
• Optional methods. List from the Java standard library marks all mutator methods as optional. By building an implementation that does not support these methods, we can provide immutable lists. Some operations are hard to implement with good enough performance on immutable lists, so we want mutable implementations, too. Code that doesn’t call mutators can be written to work automatically with either kind of list.
• Methods with intentionally underdetermined specifications. An ADT for finite sets could leave unspecified the element order one gets when converting to a list. Some implementations might use slower method implementations that manage to keep the set representation in some sorted order, allowing quick conversion to a sorted list. Other implementations might make many methods faster by not bothering to support conversion to sorted lists.
• Multiple views of one class. A Java class may implement multiple methods. For instance, a user interface widget displaying a drop-down list is natural to view as both a widget and a list. The class for this widget could implement both interfaces. In other words, we don’t implement an ADT multiple times just because we are choosing different data structures; we may make multiple implementations because many different sorts of objects may also be seen as special cases of the ADT, among other useful perspectives.
• More and less trustworthy implementations. Another reason to implement an interface multiple times might be that it is easy to build a simple implementation that you believe is correct, while you can work harder to build a fancier version that is more likely to contain bugs. You can choose implementations for applications based on how bad it would be to get bitten by a bug.

Testing an Abstract Data Type

We build a test suite for an abstract data type by creating tests for each of its operations. These tests inevitably interact with each other, since the only way to test creators, producers, and mutators is by calling observers on the objects that result.

Here’s how we might partition the input spaces of the four operations in our MyString type:

 1 // testing strategy for each operation of MyString:
 2 //
 3 // valueOf():
 4 //    true, false
 5 // length(): 
 6 //    string len = 0, 1, n
 7 //    string = produced by valueOf(), produced by substring()
 8 // charAt(): 
 9 //    string len = 1, n
10 //    i = 0, middle, len-1
11 //    string = produced by valueOf(), produced by substring()
12 // substring():
13 //    string len = 0, 1, n
14 //    start = 0, middle, len
15 //    end = 0, middle, len
16 //    end-start = 0, n
17 //    string = produced by valueOf(), produced by substring()

Then a compact test suite that covers all these partitions might look like:

 1 @Test public void testValueOfTrue() {
 2     MyString s = MyString.valueOf(true);
 3     assertEquals(4, s.length());
 4     assertEquals('t', s.charAt(0));
 5     assertEquals('r', s.charAt(1));
 6     assertEquals('u', s.charAt(2));
 7     assertEquals('e', s.charAt(3));
 8 }
 9 
10 @Test public void testValueOfFalse() {
11     MyString s = MyString.valueOf(false);
12     assertEquals(5, s.length());
13     assertEquals('f', s.charAt(0));
14     assertEquals('a', s.charAt(1));
15     assertEquals('l', s.charAt(2));
16     assertEquals('s', s.charAt(3));
17     assertEquals('e', s.charAt(4));
18 }
19 
20 @Test public void testEndSubstring() {
21     MyString s = MyString.valueOf(true).substring(2, 4);
22     assertEquals(2, s.length());
23     assertEquals('u', s.charAt(0));
24     assertEquals('e', s.charAt(1));
25 }
26 
27 @Test public void testMiddleSubstring() {
28     MyString s = MyString.valueOf(false).substring(1, 2);
29     assertEquals(1, s.length());
30     assertEquals('a', s.charAt(0));
31 }
32 
33 @Test public void testSubstringIsWholeString() {
34     MyString s = MyString.valueOf(false).substring(0, 5);
35     assertEquals(5, s.length());
36     assertEquals('f', s.charAt(0));
37     assertEquals('a', s.charAt(1));
38     assertEquals('l', s.charAt(2));
39     assertEquals('s', s.charAt(3));
40     assertEquals('e', s.charAt(4));
41 }
42 
43 @Test public void testSubstringOfEmptySubstring() {
44     MyString s = MyString.valueOf(false).substring(1, 1).substring(0, 0);
45     assertEquals(0, s.length());
46 }

Notice that each test case typically calls a few operations that make or modify objects of the type (creators, producers, mutators) and some operations that inspect objects of the type (observers). As a result, each test case covers parts of several operations.

Invariants

Resuming our discussion of what makes a good abstract data type, the final, and perhaps most important, property of a good abstract data type is that it preserves its own invariants.

An invariant is a property of a program that is always true, for every possible runtime state of the program.

Immutability is one crucial invariant that we’ve already encountered: once created, an immutable object should always represent the same value, for its entire lifetime. Saying that the ADT preserves its own invariants means that the ADT is responsible for ensuring that its own invariants hold. It doesn’t depend on good behaviour from its clients.

When an ADT preserves its own invariants, reasoning about the code becomes much easier. If you can count on the fact that Strings never change, you can rule out that possibility when you’re debugging code that uses Strings – or when you’re trying to establish an invariant for another ADT that uses Strings. Contrast that with a string type that guarantees that it will be immutable only if its clients promise not to change it. Then you’d have to check all the places in the code where the string might be used.

Immutability

We’ll see many interesting invariants. Let’s focus on immutability for now. Here’s a specific example:

 1 /**
 2  * This immutable data type represents a tweet from Twitter.
 3  */
 4 public class Tweet {
 5 
 6     public String author;
 7     public String text;
 8     public Date timestamp;
 9 
10     /**
11      * Make a Tweet.
12      * @param author    Twitter user who wrote the tweet.
13      * @param text      text of the tweet
14      * @param timestamp date/time when the tweet was sent
15      */
16     public Tweet(String author, String text, Date timestamp) {
17         this.author = author;
18         this.text = text;
19         this.timestamp = timestamp;
20     }
21 }

How do we guarantee that these Tweet objects are immutable – that, once a tweet is created, its author, message, and date can never be changed?

The first threat to immutability comes from the fact that clients can — in fact must — directly access its fields. So nothing’s stopping us from writing code like this:

1 Tweet t = new Tweet("justinbieber", 
2                     "Thanks to all those beliebers out there inspiring me every \
3 day", 
4                     new Date());
5 t.author = "GSatInRealTime";

This is a trivial example of representation exposure, meaning that code outside the class can modify the representation directly. Rep exposure like this threatens not only invariants, but also representation independence. We can’t change the implementation of Tweet without affecting all the clients who are directly accessing those fields.

Fortunately, Java gives us language mechanisms to deal with this kind of rep exposure: ```java public class Tweet {

 1 private final String author;
 2 private final String text;
 3 private final Date timestamp;
 4 
 5 public Tweet(String author, String text, Date timestamp) {
 6     this.author = author;
 7     this.text = text;
 8     this.timestamp = timestamp;
 9 }
10 
11 /** @return Twitter user who wrote the tweet */
12 public String getAuthor() {
13     return author;
14 }
15 
16 /** @return text of the tweet */
17 public String getText() {
18     return text;
19 }
20 
21 /** @return date/time when the tweet was sent */
22 public Date getTimestamp() {
23     return timestamp;
24 }

} ```

The private and public keywords indicate which fields and methods are accessible only within the class and which can be accessed from outside the class. The final keyword also helps by guaranteeing that the fields of this immutable type won’t be reassigned after the object is constructed.

https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/ADTs/retweetLater.png alt=”retweetLater breaking Tweet’s immutability”

But that’s not the end of the story: the rep is still exposed! Consider this perfectly reasonable client code that uses Tweet:

1 /** @return a tweet that retweets t, one hour later*/
2 public static Tweet retweetLater(Tweet t) {
3     Date d = t.getTimestamp();
4     d.setHours(d.getHours()+1);
5     return new Tweet("GSatInRealTime", t.getText(), d);
6 }

retweetLater takes a tweet and should return another tweet with the same message (called a retweet) but sent an hour later. The retweetLater method might be part of a system that automatically echoes funny things that Twitter celebrities say.

What’s the problem here? The getTimestamp call returns a reference to the same date object referenced by tweet t. t.timestamp and d are aliases to the same mutable object. So when that date object is mutated by d.setHours(), this affects the date in t as well, as shown in the snapshot diagram.

Tweet’s immutability invariant has been broken. The problem is that Tweet leaked out a reference to a mutable object that its immutability depended on. We exposed the rep, in such a way that Tweet can no longer guarantee that its objects are immutable. Perfectly reasonable client code created a subtle bug.

We can patch this kind of rep exposure by using defensive copying: making a copy of a mutable object to avoid leaking out references to the rep. Here’s the code:

1 public Date getTimestamp() {
2     return new Date(Date.getTime());
3 }

Mutable types often have a copy constructor that allows you to make a new instance that duplicates the value of an existing instance. In this case, Date’s copy constructor uses the timestamp value, measured in seconds since January 1, 1970. As another example, StringBuilder’s copy constructor takes a String. Another way to copy a mutable object is clone(), which is supported by some types but not all. There are unfortunate problems with the way clone() works in Java. For more, see Josh Bloch, Effective Java, item 10.

https://dl.dropboxusercontent.com/u/567187/EECE%20210/Images/ADTs/tweetEveryHourToday.png alt=”tweetEveryHourToday breaking Tweet’s immutability”

So we’ve done some defensive copying in the return value of getTimestamp( ). But we’re not done yet! There’s still rep exposure. Consider this (again perfectly reasonable) client code:

 1 /** @return a list of 24 inspiring tweets, one per hour today */
 2 public static List<Tweet> tweetEveryHourToday () {
 3     List<Tweet> list = new ArrayList<Tweet>(); 
 4     Date date = new Date();
 5     for (int i=0; i < 24; i++) {
 6         date.setHours(i);
 7         list.add(new Tweet("GSatInRealTime", "keep it up! you can do it", date));
 8     } 
 9     return list;
10 }

This code intends to advance a single Date object through the 24 hours of a day, creating a tweet for every hour. But notice that the constructor of Tweet saves the reference that was passed in, so all 24 Tweet objects end up with the same time, as shown in this instance diagram.

Again, the immutability of Tweet has been violated. We can fix this problem too by using judicious defensive copying, this time in the constructor:

1 public Tweet(String author, String text, Date timestamp) {
2     this.author = author;
3     this.text = text;
4     this.timestamp = new Date(timestamp.getTime());
5 }

In general, you should carefully inspect the argument types and return types of all your ADT operations. If any of the types are mutable, make sure your implementation doesn’t return direct references to its representation. Doing that creates rep exposure.

You may object that this seems wasteful. Why make all these copies of dates? Why can’t we just solve this problem by a carefully written specification, like this?

1 /**
2  * Make a Tweet.
3  * @param author    Twitter user who wrote the tweet.
4  * @param text      text of the tweet
5  * @param timestamp date/time when the tweet was sent. Caller must never 
6  *                   mutate this Date object again!
7  */
8 public Tweet(String author, String text, Date timestamp) {

This approach is sometimes taken when there isn’t any other reasonable alternative – for example, when the mutable object is too large to copy efficiently. But the cost in your ability to reason about the program, and your ability to avoid bugs, is enormous. In the absence of compelling arguments to the contrary, it’s almost always worth it for an abstract data type to guarantee its own invariants, and preventing rep exposure is essential to that.

An even better solution is to prefer immutable types. If we had used an immutable date object, like java.time.ZonedDateTime, instead of the mutable java.util.Date, then we would have ended this section after talking about public and private. No further rep exposure would have been possible.

Immutable Wrappers Around Mutable Data Types

The Java collections classes offer an interesting compromise: immutable wrappers.

Collections.unmodifiableList() takes a (mutable) List and wraps it with an object that looks like a List, but whose mutators are disabled – set(), add(), remove() throw exceptions. So you can construct a list using mutators, then seal it up in an unmodifiable wrapper (and throw away your reference to the original mutable list), and get an immutable list.

The downside here is that you get immutability at runtime, but not at compile time. Java won’t warn you at compile time if you try to sort() this unmodifiable list. You’ll just get an exception at runtime. But that’s still better than nothing, so using unmodifiable lists, maps, and sets can be a very good way to reduce the risk of bugs.

How to Establish Invariants

An invariant is a property that is true for the entire program – which in the case of an invariant about an object, reduces to the entire lifetime of the object.

To make an invariant hold, we need to:

• make the invariant true in the initial state of the object; and
• ensure that all changes to the object keep the invariant true.

Translating this in terms of the types of ADT operations, this means:

• creators and producers must establish the invariant for new object instances; and
• mutators and observers must preserve the invariant.

The risk of rep exposure makes the situation more complicated. If the rep is exposed, then the object might be changed anywhere in the program, not just in the ADT’s operations, and we can’t guarantee that the invariant still holds after those arbitrary changes. So the full rule for proving invariants is:

Structural induction. If an invariant of an abstract data type is

1. established by creators and producers;
2. preserved by mutators, and observers; and
3. no representation exposure occurs,

then the invariant is true of all instances of the abstract data type.

Summary

• Abstract data types are characterized by their operations.
  • Operations can be classified into creators, producers, observers, and mutators.
  • An ADT’s specification is its set of operations and their specs.
  • A good ADT is simple, coherent, adequate, representation-independent, and preserves its own invariants.
• An invariant is a property that is always true of an ADT object instance, for the lifetime of the object.
  • Invariants must be established by creators and producers, and preserved by observers and mutators.
• Representation exposure threatens both representation independence and invariant preservation.
• Java interfaces help us formalize the idea of an abstract data type as a set of operations that must be supported by a type.

These ideas connect to our three key properties of good software as follows:

• Safe from bugs. A good ADT offers a well-defined contract for a data type, and preserves its own invariants, so that those invariants are less vulnerable to bugs in the ADT’s clients, and violations of the invariants can be more easily isolated within the implementation of the ADT itself.
• Easy to understand. A good ADT hides its implementation behind a set of simple operations, so that programmers using the ADT only need to understand the operations, not the details of the implementation.
• Ready for change. Representation independence allows the implementation of an abstract data type to change without requiring changes from its clients.

Rep Invariants and Abstraction Functions

In this reading, we study a more formal mathematical idea of what it means for a class to implement an ADT, via the notions of abstraction functions and rep invariants. These mathematical notions are eminently practical in software design. The abstraction function will give us a way to cleanly define the equality operation on an abstract data type, and the rep invariant will make it easier to catch bugs caused by a corrupted data structure.

Rep Invariant and Abstraction Function

We now take a deeper look at the theory underlying abstract data types. This theory is not only elegant and interesting in its own right; it also has immediate practical application to the design and implementation of abstract types. If you understand the theory deeply, you’ll be able to build better abstract types, and will be less likely to fall into subtle traps.

In thinking about an abstract type, it helps to consider the relationship between two spaces of values.

The space of representation values (or rep values for short) consists of the values of the actual implementation entities. In simple cases, an abstract type will be implemented as a single object, but more commonly a small network of objects is needed, so this value is actually often something rather complicated. For now, though, it will suffice to view it simply as a mathematical value.

The space of abstract values consists of the values that the type is designed to support. These are a figment of our imaginations. They’re platonic entities that don’t exist as described, but they are the way we want to view the elements of the abstract type, as clients of the type. For example, an abstract type for unbounded integers might have the mathematical integers as its abstract value space; the fact that it might be implemented as an array of primitive (bounded) integers, say, is not relevant to the user of the type.

Now of course the implementor of the abstract type must be interested in the representation values, since it is the implementor’s job to achieve the illusion of the abstract value space using the rep value space.

Suppose, for example, that we choose to use a string to represent a Set<Character> (a set of characters).

1 public class CharSet implements Set<Character> {
2     private String s;
3     ...
4 }

Then the rep space R contains Strings, and the abstract space A is mathematical sets of characters. We can show the two value spaces graphically, with an arc from a rep value to the abstract value it represents. There are several things to note about this picture:

• Every abstract value is mapped to by some rep value. The purpose of implementing the abstract type is to support operations on abstract values. Presumably, then, we will need to be able to create and manipulate all possible abstract values, and they must therefore be representable.
• Some abstract values are mapped to by more than one rep value. This happens because the representation is not a tight encoding. There’s more than one way to represent an unordered set of characters as a string.
• Not all rep values are mapped. For example, the string “abbc” is not mapped. In this case, we have decided that the string should not contain duplicates. This will allow us to terminate the remove() method when we hit the first instance of a particular character, since we know there can be at most one.

In practice, we can only illustrate a few elements of the two spaces and their relationships; the graph as a whole is infinite. So we describe it by giving two things:

1. An abstraction function that maps rep values to the abstract values they represent:

AF : R → A

The arcs in the diagram show the abstraction function. In the terminology of functions, the properties we discussed above can be expressed by saying that the function is surjective (also called onto), not necessarily bijective (also called one-to-one), and often partial.

2. A rep invariant that maps rep values to booleans:

RI : R → boolean

For a rep value r, RI(r) is true if and only if r is mapped by AF. In other words, RI tells us whether a given rep value is well-formed. Alternatively, you can think of RI as a set: it’s the subset of rep values on which AF is defined.

Both the rep invariant and the abstraction function should be documented in the code, right next to the declaration of the rep itself:

1 public class CharSet_NoRepeatsRep implements Set<Character> {
2     private String s;
3     // Rep invariant:
4     //    s contains no repeated characters
5     // Abstraction Function:
6     //   represents the set of characters found in s
7     ...
8 }

A common confusion about abstraction functions and rep invariants is that they are determined by the choice of rep and abstract value spaces, or even by the abstract value space alone. If this were the case, they would be of little use, since they would be saying something redundant that’s already available elsewhere.

The abstract value space alone doesn’t determine the AF or RI: there can be several representations for the same abstract type. A set of characters could equally be represented as a string, as above, or as a bit vector, with one bit for each possible character. Clearly we need two different abstraction functions to map these two different rep value spaces.

It is less obvious why the choice of both spaces does not determine AF and RI. The key point is that defining a type for the rep, and thus choosing the values for the space of rep values, does not determine which of the rep values will be deemed to be legal, and of those that are legal, how they will be interpreted. Rather than deciding, as we did above, that the strings have no duplicates, we could instead allow duplicates, but at the same time require that the characters be sorted, appearing in nondecreasing order. This would allow us to perform a binary search on the string and thus check membership in logarithmic rather than linear time. Same rep value space – different rep invariant:

1 public class CharSet_SortedRep implements Set<Character> {
2     private String s;
3     // Rep invariant:
4     //    s[0] < s[1] < ... < s[s.length()-1]
5     // Abstraction Function:
6     //   represents the set of characters found in s
7     ...
8 }

Even with the same type for the rep value space and the same rep invariant RI, we might still interpret the rep differently, with different abstraction functions AF. Suppose RI admits any string of characters. Then we could define AF, as above, to interpret the array’s elements as the elements of the set. But there’s no a priori reason to let the rep decide the interpretation. Perhaps we’ll interpret consecutive pairs of characters as subranges, so that the string “acgg” represents the set {a,b,c,g}.

 1 public class CharSet_SortedRangeRep implements Set<Character> {
 2     private String s;
 3     // Rep invariant:
 4     //    s.length is even
 5     //    s[0] <= s[1] <= ... <= s[s.length()-1]
 6     // Abstraction Function:
 7     //   represents the union of the ranges
 8     //   {s[i]...s[i+1]} for each adjacent pair of characters 
 9     //   in s
10     ...
11 }

The essential point is that designing an abstract type means not only choosing the two spaces – the abstract value space for the specification and the rep value space for the implementation – but also deciding what rep values to use and how to interpret them.

It’s critically important to write down these assumptions in your code, as we’ve done above, so that future programmers (and your future self) are aware of what the representation actually means. Why? What happens if different implementers disagree about the meaning of the rep?

Example: Rational Numbers

Here’s an example of an abstract data type for rational numbers. Look closely at its rep invariant and abstraction function.

 1 public class RatNum {
 2     private final int numer;
 3     private final int denom;
 4 
 5     // Rep invariant:
 6     //   denom > 0
 7     //   numer/denom is in reduced form
 8 
 9     // Abstraction Function:
10     //   represents the rational number numer / denom
11 
12     /** Make a new Ratnum == n. */
13     public RatNum(int n) {
14         numer = n;
15         denom = 1;
16         checkRep();
17     }
18 
19     /**
20      * Make a new RatNum == (n / d).
21      * @param n numerator
22      * @param d denominator
23      * @throws ArithmeticException if d == 0
24      */
25     public RatNum(int n, int d) throws ArithmeticException {
26         // reduce ratio to lowest terms
27         int g = gcd(n, d);
28         n = n / g;
29         d = d / g;
30 
31         // make denominator positive
32         if (d < 0) {
33             numer = -n;
34             denom = -d;
35         } else {
36             numer = n;
37             denom = d;
38         }
39         checkRep();
40     }
41 }

Here is a picture of the abstraction function and rep invariant for this code. The RI requires that numerator/denominator pairs be in reduced form (i.e., lowest terms), so pairs like (2,4) and (18,12) above should be drawn as outside the RI.

It would be completely reasonable to design another implementation of this same ADT with a more permissive RI. With such a change, some operations might become more expensive to perform, and others cheaper.

Checking the Rep Invariant

The rep invariant is not just a neat mathematical idea. If your implementation asserts the rep invariant at run time, then you can catch bugs early. Here’s a method for RatNum that tests its rep invariant:

1 // Check that the rep invariant is true
2 // *** Warning: this does nothing unless you turn on assertion checking
3 // by passing -enableassertions to Java
4 private void checkRep() {
5     assert denom > 0;
6     assert gcd(numer, denom) == 1;
7 }

You should certainly call checkRep() to assert the rep invariant at the end of every operation that creates or mutates the rep – in other words, creators, producers, and mutators. Look back at the RatNum code above, and you’ll see that it calls checkRep() at the end of both constructors.

Observer methods don’t normally need to call checkRep(), but it’s good defensive practice to do so anyway. Why? Calling checkRep() in every method, including observers, means you’ll be more likely to catch rep invariant violations caused by rep exposure.

Why is checkRep() private? Who should be responsible for checking and enforcing a rep invariant – clients, or the implementation itself?

No Null Values in the Rep

Recall from the reading on Specifications that null values are troublesome and unsafe, so much so that we try to remove them from our programming entirely.

We extend that prohibition to the reps of abstract data types. By default, in this course, the rep invariant implicitly includes x != null for every reference x in the rep that has object type (including references inside arrays or lists). So if your rep is:

1 class CharSet {
2     String s;
3 }

then its rep invariant automatically includes s != null.

By stating that references cannot be null in the rep invariant you are adding to safety. You will often work with others who may have not had this approach as a dictum.

When it’s time to implement that rep invariant in a checkRep() method, however, you still must implement the s != null check, and make sure that your checkRep() correctly fails when s is null. Often that check comes for free from Java, because checking other parts of your rep invariant will throw an exception if s is null. For example, if your checkRep() looks like this:

1 private void checkRep() {
2     assert s.length() % 2 == 0;
3     ...
4 }

then you don’t need assert s!= null, because the call to s.length() will fail just as effectively on a null reference. But if s is not otherwise checked by your rep invariant, then assert s != null explicitly.

Summary

The Abstraction Function maps a concrete representation to the abstract value it represents.

The Rep Invariant specifies legal values of the representation, and should be checked at runtime with checkRep().

For a slightly different – and compressed – view of RIs and AFs, consider the following summary.

We write specifications for methods because we wanted to state certain assumptions or describe some aspect of the method: + Preconditions, for example, indicate what are valid arguments and when one can call a method. We use preconditions because there are certain things that are impossible for a compiler to verify (there is only limited power in static analysis) and it would slow down our programs too much if we had to verify these conditions at runtime (e.g., make the JVM do a lot of checks). + Postconditions and effects tell us what we can expect after a method has finished, and this is important because not all changes in a language like Java involve what is returned by a method.

It is not always enough to reason about methods. When we define a datatype in Java we use the class abstraction that Java provides. We represent an abstract object (such as a git blob or a bicyclist in the Tour de France) using some other datatypes. The representations take the form of field declarations within the class.

Take the example of a line segment that may be represented by the two end points (x1, y1) and (x2, y2). We could easily declare a class called Segment with four floating point numbers x1, y1, x2, y2 as the internal fields (this is really a vector with 4 dimensions). We can then ask the question: Do all vectors in R⁴ represent valid line segments? We might then conclude that a line segment cannot be of length 0 which would then eliminate those representations where x1 == x2 and y1 == y2. This type of constraint is something that is not communicated by the following definition: java public class Segment { private double x1, x2, y1, y2; ... } The restriction we want is therefore encoded as a rep invariant. The abstract function, in turn, tells us that if we have four double values that satisfy this rep invariant then they represent a particular line segment. (In a different situation, four doubles might just as well represent latitude, longitude, altitude and temperature of a location on the planet!)

We could therefore think of specs, rep invariants and abstraction functions as encoding assumptions we make when we write software. Separating the assumptions into different categories makes it easier to understand and maintain software, and to automate certain aspects of software verification.

The topics of today’s reading connect to our three properties of good software as follows:

• Safe from bugs. Stating the rep invariant explicitly, and checking it at runtime with checkRep(), catches misunderstandings and bugs earlier, rather than continuing on with a corrupt data structure.
• Easy to understand. Rep invariants and abstraction functions explicate the meaning of a data type’s representation, and how it relates to its abstraction.
• Ready for change. Abstract data types separate the abstraction from the concrete representation, which makes it possible to change the representation without having to change client code.

Test Yourself

• Questions
• Answers

Interfaces

Interfaces

Java’s interface is a useful language mechanism for expressing an abstract data type. An interface in Java is a list of method signatures, but no method bodies. A class implements an interface if it declares the interface in its implements clause, and provides method bodies for all of the interface’s methods. So one way to define an abstract data type in Java is as an interface, with its implementation as a class implementing that interface.

One advantage of this approach is that the interface specifies the contract for the client and nothing more. The interface is all a client programmer needs to read to understand the ADT. The client can’t create inadvertent dependencies on the ADT’s rep, because instance variables can’t be put in an interface at all. The implementation is kept well and truly separated, in a different class altogether.

Another advantage is that multiple different representations of the abstract data type can co-exist in the same program, as different classes implementing the interface. When an abstract data type is represented just as a single class, without an interface, it’s harder to have multiple representations. In the [MyString example from Abstract Data Types][1], MyString was a single class. We explored two different representations for MyString, but we couldn’t have both representations for the ADT in the same program.

Java’s static type checking allows the compiler to catch many mistakes in implementing an ADT’s contract. For instance, it is a compile-time error to omit one of the required methods, or to give a method the wrong return type. Unfortunately, the compiler doesn’t check for us that the code adheres to the specs of those methods that are written in documentation comments.

Example: MyString

Let’s revisit [MyString][1]. Using an interface instead of a class for the ADT, we can support multiple implementations: ```java /** MyString represents an immutable sequence of characters. */ public interface MyString {

 1 /** @return number of characters in this string */
 2 public int length();
 3 
 4 /** @param i character position (requires 0 <= i < string length)
 5  *  @return character at position i */
 6 public char charAt(int i);
 7 
 8 /** Get the substring between start (inclusive) and end (exclusive).
 9  *  @param start starting index
10  *  @param end ending index.  Requires 0 <= start <= end <= string length.
11  *  @return string consisting of charAt(start)...charAt(end-1) */
12 public MyString substring(int start, int end);

} ```

We’ll skip the static valueOf method and come back to it in a minute. Instead, let’s go ahead using a different technique from our [toolbox of ADT concepts in Java][2]: constructors.

Here’s our first implementation: ```java public class SimpleMyString implements MyString { private char[] a; private SimpleMyString() {}

 1 /** Create a string representation of b, either "true" or "false".
 2  *  @param b a boolean value */
 3 public SimpleMyString(boolean b) {
 4 	a = b ? new char[] { 't', 'r', 'u', 'e' }
 5 		: new char[] { 'f', 'a', 'l', 's', 'e' };
 6 }
 7 
 8 @Override 
 9 public int length() { return a.length; }
10 
11 @Override 
12 public char charAt(int i) { return a[i]; }
13 
14 @Override 
15 public MyString substring(int start, int end) {
16 	SimpleMyString that = new SimpleMyString();
17 	that.a = new char[end - start];
18 	System.arraycopy(this.a, start, that.a, 0, end - start);
19 	return that;
20 }