Start Concurrent: A Gentle Introduction to Concurrent Programming

If a math teacher writes the expression 1 + 7 × 8 - 6 × (4 + 5) ÷ 3 on the blackboard and asks a group of 10-year-old children to solve it, different children might give different answers. The difficulty lies not in the operations themselves but in the order of operations. Modern graphing calculators and many computer programs can, of course, evaluate such expressions correctly, but how do they do it? You intuitively grasp order of operations (left to right, multiplication and division take higher precedence than addition and subtraction, and so on), but encoding that intuition into a computer program requires effort.

One way a computer scientist might approach this problem is to turn the mathematical expression from one that’s difficult to evaluate into one that’s easy. The normal style of writing mathematical expressions is called infix notation, because the operators are written in between the operands they’re used on. An easier notation for automatic evaluation is called postfix notation, because an operator is placed after the operands it works on. The following table gives a few examples of expressions written in both infix and postfix notation.

Although infix notation is probably more familiar to you, postfix notation has the benefit of exactly specifying the order of operations without using any precedence rules and without needing parentheses to clarify. To understand how to compute an expression in postfix notation, we rely on the idea of a stack, which we first introduced in Chapter 9 and examine in greater depth here.

Recall that a stack has three operations: push, pop, and top. It works like a stack of physical objects. The push operation places an object on the top, the pop operation removes an item from the top, and the top operation tells you what’s at the top of the stack.

Using a stack, postfix evaluation rules are easy: Scan the expression from left to right, if you see an operand (a number, in our case), put it on the stack. If you see an operator, pop the last two operands off the stack and use the operator on them. Then, push the result back on the stack. When you run out of input, the value at the top of the stack is your answer.

For example, with 1 9 2 * +, all three operands are pushed onto the stack. Then, the * is read, and so 2 and 9 are popped off the stack and multiplied. The result 18 is pushed back on the stack. Then, the + is read, and 18 and 1 are popped off the stack and summed, resulting in 19, which is pushed back on the stack as the final answer.

Our problem, however, is not to evaluate an expression in postfix notation but to convert an expression in infix notation to postfix notation. Again, the concept of a stack is useful. To do the conversion, we initialize a stack and scan through the input in infix notation. As we scan through the input, we do one of four things depending on which of the four possible inputs we see.

Precedence comes from order of operations: * and / have high precedence and ` and `-` have low precedence. When you encounter it on the stack, treat `(` as if it has even lower precedence than ` and -. A right parenthesis should never appear on the stack.

Following this algorithm, we’re able to write a program that converts infix notation to postfix notation. We further restrict our problem to the case when the only operands are positive integers in the range [0, 9]. Since each is a single character, parsing the input is much easier. The same ideas for postfix conversion hold no matter how the input is formatted, but parsing arbitrarily formatted numbers is a difficult problem in its own right. This restriction also makes spaces unnecessary.

To solve the infix conversion problem, we need to create a stack data structure whose elements are terms from an infix expression, where a term is an operator, operand, or a parenthesis. We created a stack to solve the nesting expression problem in Section 9.1, but we explore stacks in this chapter as one of many different kinds of dynamic data structure.

By now you’ve seen several ways to organize data in your programs. For example, you’ve used arrays to store a sequence of values and class definitions to store (and operate on) collections of related values in objects. These data structures have the property that they’re static in size: Once allocated, they do not grow as the program runs. If you allocate an array to store 100 integers, you’ll get an error if you try to store 101 integers into it.

In this chapter, we examine dynamic data structures: As more data is read or processed, these data structures grow and shrink in memory to store what is needed. The stack used to solve the nesting expressions problem from Chapter 9 was not actually a dynamic data structure since it was defined with a fixed maximum size. In this chapter, we implement a true stack as well as many other kinds of dynamic data structures.

We’ve seen two examples so far of dynamic data structures: dynamic arrays and linked lists. A great deal of complexity can go on inside these data structures, but code that uses these data structures doesn’t need to be aware of the details of the internal implementation. Ideally, user programs could use any data structure that provides the required set of operations.

Our dynamic array and linked list classes were simple examples of abstract data types (ADT). We can design many data structures that hide the details of their implementation inside a class. The user of each class is aware of the operations (public methods) that can be performed on objects of the class but not of the intricacies used to implement those operations. Defining an ADT without regard to an implementation keeps users of the ADT from becoming dependent on details of any particular implementation. It gives maximum freedom to the programmer to choose (and change) the implementation as appropriate for the overall system design.

We generalize a data structure by observing which operations are applied to it. Then, we create an abstraction that formalizes these observations. The idea is to cleanly separate the use and behavior of the data structure from the way in which it’s implemented.

Interfaces are the obvious tool for defining the behavior of a class in Java without specifying its implementation. When defining an ADT in Java, its set of operations becomes the set of methods specified by the interface. Then, any class that implements the ADT must implement the corresponding interface.

In subsequent sections we look at two fundamental abstract data types, stacks and queues, and sample classes that implement them.

Most of the dynamic data structures we’ve seen in this chapter store values of type String. We’ve explored dynamic arrays of String values, linked lists of String objects, queues of String objects, and stacks of String objects. In Example 18.1, we created the stack class TermStack to hold Term objects, but TermStack is identical to the existing LinkedListStack class with the substitution of Term for String.

What if you wanted to store values of some other type in these data structures? What if you wanted a stack of int values or a queue of Thread objects? You might think that you need to create a distinct but similar implementation of each ADT for each type, as we do in Example 18.1.

One possible solution is to take advantage of the fact that a variable of type Object can hold a reference to a value of any reference type, since all classes are subtypes of Object. If we create data structures using Object as the underlying type, we can store values of any type in the data structure. For example, Program 18.16 is an implementation of a stack ADT with an underlying data type of Object.

A stack of Object references could be an example of a heterogeneous data structure since it’s possible to push objects of different types onto the same stack. While there are situations in which this technique is useful, in most cases a homogeneous data structure (where all values are of the same type) is all that’s needed. Homogeneous data structures allow type checking to occur at compile time, thus helping to avoid run-time errors.

Using a stack of Object references is generally more cumbersome, since you must cast values returned from pop() or top() to the appropriate data type.

Casting the returning value from a heterogeneous data structure essentially forces type checking to move from compile time to run time. Instead of having the Java compiler verify the type correctness of operations, we force the Java virtual machine to do the check.

Here we give our solution to the infix conversion problem from the beginning of the chapter. As in Example 18.1, we use a stack of Term objects to solve the problem. However, we expand the Term class to hold both operands and operators. We only add methods and fields to the earlier definition, taking nothing away. In this way, we should be able to use the Term class for both infix to postfix conversion and postfix calculation.

Here we’ve augmented the earlier Term class by adding two more fields, a char called operator to hold an operator and a boolean called isOperator to keep track of whether or not our Term object holds an operator or an operand.

We now have two constructors. The first one takes an int value and stores it into value, setting isOperator to false to indicate that the Term object must be an operand. The second constructor takes a char value and stores it into operator, setting isOperator to true to indicate that the Term object must be an operator (such as +, -,*, or /).

These three accessors give back the operand value, the operator character, and whether or not the object is an operator, respectively. This solution is not necessarily the most elegant from an OOP perspective. The code that uses a Term object needs to choose the getOperator() method or the getValue() method depending on whether the Term is an operator. This design opens up the possibility that some code will call the wrong accessor method and get a useless default value.

The most complicated addition to the Term class is the greaterOrEqual() method, which takes in another Term object. This method compares the operator of the Term object being called with the one that’s being passed in as a parameter. Because this method is in the Term class, it can access the private variables of the term parameter. This method returns true if the operator of the called object has a greater or equal precedence compared to the operator of the parameter object. The meat of the method is the switch statement that establishes the high precedence of * and /, the medium precedence of + and -, and the low precedence of anything else, namely the left parenthesis (.

With this updated Term class, we can create Term objects that hold either an operator or an operand and allow the precedence of operators to be compared. We use exactly the same TermStack class from Example 18.1 for our stack. All that remains is the client code that parses the input.

The output from this program could be used as the input to the postfix evaluator program from Example 18.1. A more complex program that did both the conversion and the calculation might want to store everything in a queue of Term objects instead of producing String output and then recreating Term objects.

The implementations of stacks and queues in the previous sections are not thread-safe. If multiple threads use a stack or queue object simultaneously, the head or tail pointers can become inconsistent or be updated incorrectly, potentially causing the stack or queue to lose elements. As you’ve seen, multiple threads operating on the same data can produce unexpected results.

Program 18.21 is a simple multi-threaded program to test (and break!) the thread safety of the queue implementation in Program 18.15.

Without appropriate synchronization, the program may not correctly link all values into the queue nor remove them at the end. A typical error-prone output run is shown here.

How does this implementation fail? Consider the situation in which two threads are attempting to put a value in the queue simultaneously by calling the enqueue() method in Program 18.15. Suppose the first thread tests the queue and finds it empty (isEmpty() returns true) but is then interrupted. If a second thread gets control, it will also see that the queue’s empty, set the head and tail variables to the new Node object temp, and return. The first thread will eventually wake up, still thinking that the queue is empty, and also set the head and tail variables to its own new Node temp. But these assignments overwrite the assignments just done by the previous thread! The initial node that was in the queue is now lost. Note that there are other sequences of execution that can cause similar race conditions.

This problem can be fixed by ensuring that once one thread starts examining and modifying queue variables, no other thread can access the same variables until the first one is finished. As shown in Chapter 14, this mutual exclusion can be achieved by using the synchronized keyword on methods that need to have exclusive access to object variables. In this queue implementation, we need to synchronize access by threads that are using either the enqueue() or dequeue() methods, since both methods access and manipulate variables in the object. Although it’s not called in this program, the front() method should also be synchronized so that a null head is not accessed accidentally. The isEmpty() method doesn’t need to be synchronized since the only methods that call it that can do any harm are already synchronized. Outside code that calls isEmpty() might get the wrong value if another thread modifies the contents of the queue, but there’s no guarantee that other threads won’t modify the state of the queue at any point after the isEmpty() method is called anyway.

With both enqueue() and dequeue() methods synchronized as in Program 18.22, a typical output generated by the program is shown below.

As we mentioned in Section 9.6, some libraries are thread safe and some are not. The Java Collections Framework (JCF) is a very useful library, but it’s also a library that requires you to manage your own thread safety if it matters for your program.

The JCF defines the Collection interface and the Map interface. The Collection interface, which any collection of objects should implement, has subinterfaces Set, List, and Queue which define the basic operations in Java that are needed to implement a set, list, or queue of items. The Map interface gives the basic operations for a dictionary, a collection of key-value pairs, one implementation of which is the HashMap from Example 18.4.

As we mentioned in Chapter 10, an interface can’t mark a method with the synchronized keyword. Consequently, the JCF makes no guarantee about the thread safety of a container based on which interface it implements. The programmer must read the documentation carefully in order to know if a container is thread safe and react accordingly.

Conceptual Problems

Programming Practice

Experiments