Incremental Java
Associativity

Associativity

Suppose you had an expression like 12 - 6 - 6. What value would it evaluate to?

Subtraction, unlike addition or multiplication, is not associative. Associativity says that @ is associative if and only if (a @ b) @ c = a @ (b @ c), where @ is a binary operator.

Because subtraction isn't associative, there are two answers, depending on which subtraction you do first. If you evaluate the left subtraction first, as in: (12 - 6) - 6, the answer is 0.

If you start with the right subtraction: 12 - (6 - 6), the answer is 12.

Which one does Java pick? It picks the left subtraction first. We'll see why.

Left Associativity

If you have an expression with several operators, how does Java know which operator to use first?

We can constrain this problem further. Suppose all the operators are the same, such as the subtraction operator. How does it decide which subtraction it must perform?

The answer depends on the associativity of the operator. Some operators are left associative. Others are right associative.

To understand associativity, we're going to play a game. Here are the rules.

We add a pair of parentheses for each occurrence of an operator. If there are 5 operators, we add 5 parentheses.
Each time we add a pair, we eliminate one of the operators. We say the operator has been covered.
We can only cover one uncovered operator at a time.
The parentheses must surround the operator, plus a left operand and a right operand. Each operands must be either: a literal, a variable, or a parenthesized (covered) expression, using the rules we've established.

The rules sound a little complicated, but it'll be much clearer with an example.

Consider the expression: a -₁ b -₂ c -₃ d -₄ e.

We have four subtraction operators (they look funny because I've written subscripts on them---for now, ignore the subscripts). We must pick one to parenthesize. Left associativity says to pick the leftmost operator that isn't covered (i.e., not surrounded by parentheses).

I've subscripted the subtraction operators so we can identify them. For example, -₁ refers to the leftmost subtraction operator, while -₄ refers to the rightmost subtraction operator.

The rule is add a pair of parentheses at a time, eliminating one subtraction operator at a time.

Step 1

(a -₁ b) -₂ c -₃ d -₄ e.

The first pair of parentheses goes around a - b. In this example, a is the left operand, while b is the right operand. A subtraction operator, which is binary, requires two operands.

We can't make the parentheses surround anything larger. For example:

(a -₁ b -₂ c) -₃ d -₄ e. WRONG!

The above parenthesization is "wrong". Java permits it, but the rules of the game only allow one uncovered subtraction operator to be covered at a time.

Step 2

Again, we pick the leftmost uncovered subtraction operator. This is -₂. Recall that we've already covered -₁.

((a -₁ b) -₂ c) -₃ d -₄ e.

The left operand for -₂ is (a - b) which is a covered expression, and the right operand is c.

Step 3

We pick the leftmost uncovered subtraction operator. This is -₃. Recall that we've already covered -₁ and -₂.

(((a -₁ b) -₂ c) -₃ d) -₄ e.

The left operand for -₂ is ((a - b) - c) which is a covered expression, and the right operand is d.

Step 4

We pick the leftmost uncovered subtraction operator. This is -₄. The other subtraction operators are all covered.

((((a -₁ b) -₂ c) -₃ d) -₄ e).

The left operand for -₂ is (((a - b) - c) - d) which is a covered expression, and the right operand is e.

Summary

We don't really have to go all 4 steps since this last step is obvious, but if we play by the rules of the game, we need to do it.

When Java evaluates an expression where all the operators have the same precedence (a concept we'll explain in the next lesson), it uses the associativity of the operator to determine which subexpression to evaluate first.

Left associativity says to pick the leftmost uncovered operator (and its operands) to add parentheses to.

Order of Evaluation

In order, Java evaluates a - b (call the result t1), then t1 - c (call the result t2), then t2 - d (call the result t3), and finally t2 - e.

In reality, temporary values are used internally by Java to keep track of the computation. As the programmer, you don't have to worry about it. Java handles this for you.

Right Associativity

Almost all arithmetic operators are left associative. This includes addition, multiplication, subtraction, and division.

Even so, it's good to know what right associativity is.

Here's the rule: if all operators have the same precedence and are right associative, then pick the rightmost uncovered operator to parenthesize.

For example, suppose Java had a $ operator (it doesn't, but pretend that it does), and you wanted to parenthesize a $ b $ c $ d $ e using right associativity.

What would the answer be?

It's (a $ (b $ (c $ (d $ e))))

You Can Always Use Parentheses

Programmers use associativity so they don't have to fully parenthesize expressions. However, sometimes you must add parentheses to get Java to do what you want.

For example, suppose you want to have Java evaluate x - y - z, but you want y - z to be evaluted first. Without parentheses, this wouldn't happen. You must add parentheses as in x - (y - z) to get it to evaluate y - z first.

When in doubt, add parentheses.

Incremental Java Associativity

Associativity

Left Associativity