A Deeper Look at Expressions in C
Evaluation Semantics

A lot of C code consists of expressions. Expressions are everywhere, really. For example, consider an assignment

i = 7 + j;

The sum on the right-hand side (7 + j) is an expression. That is clear. The expression is defined by the addition operator (+) and its two operands, and the value of the expression is the value of j plus 7. All of this is pretty obvious. However, j could be considered an expression, and even 7, and i. And the assignment as a whole is also an expression.

In fact, an assignment expression is defined by the assignment operator (=) and its two operands (or arguments): a left-hand-side expression that determines the object whose value will be assigned, and a right-hand-side expression that determines the value that will be assigned to the left-hand-side object. And the whole assignment is itself an expression whose value (or “result”) is the value being assigned, meaning the result of the right-hand-side expression.

We now take a closer look at expressions in order to better understand the semantics of the evaluation of expressions, which is a fundamental part of the semantics of the language.

Objects, L-values, and R-values

An object is a region of storage, in memory. An object can therefore store a value, which can be read and written. Examples are a variable of a basic type such as this one:

int i;

This defines an int object corresponding to variable i. Notice that object i may have static storage or automatic storage, which affects its lifetime. However, for the purpose of this discussion, we are not concerned about the storage class and therefore the lifetime of i. All that matters at this point is that the object exists.

An l-value is an expression referring to an object. An obvious example of an l-value expression is an identifier. For example, the left-hand side of the assignment below is the expression i, which is an l-value expression, since it refers to an object (i).

i = 7;

Single variables aren’t the only l-value expressions. Here is a slightly more complex example:

char s[100];

s[i] = 'a';

Here the expression s[i] is an l-value. That is, it is an expression that refers to an object. And here’s another one, just a bit more complicated—but you got the idea, right?

struct S {
    int x;
    char s[10];
};

struct S * fun2(int);

(fun2(i + 2) + 5)->s[i] = '?';

The left-hand side of the last expression statement (above) refers an object: a particular char object in the s array of a struct S object located in some sequence of struct S objects, specifically 5 struct S objects down from one whose address is returned by the invocation of the fun2 function, which in fact returns pointers to struct S objects. Bottom line, it’s an l-value expression.

That’s no coincidence. It must be an l-value. The left-hand side of an assignment must be an l-value. An assignment stores a value into an object. The right-hand side of the assignment determines the value, and the left-hand side determines the object. In fact, that’s what the name comes from: an l-value is what you want on the left-hand side of the assignment. This concept might be grasped intuitively by considering the following two expression statements:

char s[100];

/* CORRECT: s[i + 1] is an l-value, that's the object being assigned. */
s[i + 1] = 'a'; 
/* INCORRECT:  What object are we assigning? Makes no sense. */
s[i] + 1 = 'a';

Did you try compiling this example? What does the compiler say?

So, an l-value is what you need whenever you need to refer to an object. Like on the left-hand side of an assignment. However, the right-hand side of an assignment may also denote a value that does not correspond to an object. The most obvious example is a literal value:

i = 7;

But many other expressions evaluate to a value without a corresponding object. These are called r-values. Here’s another example:

i = (fun2(i + 2) + 5)->s[i] * i;

So, both l-values and r-values are expressions, but the main difference is that an l-value refers to an object, while an r-value refers to a value without a corresponding object. Of course, an object also has a value, so an l-value expression can be used in both cases, when you need an object or when you just need a value. This is

Another thing you can do with an l-value that you can not do with an r-value is to apply the address-of operator (&). Makes sense: the address-of operator takes that address of an object, so it must apply to objects.

/* CORRECT: the & operator applies to l-values */
int * p = &i;
char * c = &((fun2(i + 2) + 5)->s[i]);
/* INCORRECT: these are not l-values */
int * p_bad = &(i + 2);
char * c_bad = &(i > 0 ? 'x' : 'y');

Okay, but what is this all about? Why should one care about distinguishing l-value from r-value expressions? The reason is that these are fundamental concepts to understand the semantics of expressions in general. These concepts are particularly important to understand C++, where operators can be defined by the programmer, and where functions can return l-values (references).

Each operator in the C language has specific requirements for its operands. As we have seen, the assignment operator (=) requires that its first operator (left-hand side) is an l-value; the address-of operator (&), which is a unary operator, requires that its operand be an l-value, and the same is true for the prefix and postfix increment and decrement operators (++, --); instead, the addition operator (binary +) only requires that its operands be r-values.

Furthermore, the result of an expression consisting of a particular operator may be an l-value or an r-value. For example, the return of the addition operator (binary +) is an r-value, while the array-index operator [] returns an l-value expression. For example A[3] is an l-value.

Pop quiz 1: does the dereference operator (*) take an l-value or an r-value?

Pop quiz 2: does the dereference operator (*) return an l-value or an r-value?

Pop quiz 3: does the assignment operator (=) return an l-value or an r-value?

Pop quiz 4: does the prefix increment (++) return an l-value or an r-value?

Pop quiz 5: does the postfix increment (++) return an l-value or an r-value?

Operator Precedence and Associativity

See http://en.cppreference.com/w/c/language/operator_precedence

Operator precedence determines the semantics—that is, the exact interpretation—of an expression. For example:

int i = 5;
int j = 10;

i = i + j * 2;

printf("i = %d\n", i);

Here the result is 25, not 30, since the multiplication operator (*) has a higher precedence than the addition operator (+). Of course, you can use parenthesized expressions to force a certain evaluation precedence. So, the output of the code below is 30, not 25:

int i = 5;
int j = 10;

i = (i + j) * 2;

printf("i = %d\n", i);

When operators have the same precedence, the semantics is defined by the associativity. For example, the + and - operators, when used as binary operators representing subtraction and addition, have the same precedence, and are left-associative:

int i = 10;
int j = 2;
i = i - j + 4;

So the above expression is equivalent to the following:

i = ((i - j) + 4); /* == 12 */

as opposed to this:

i = (i - (j + 4)); /* == 6 */

Other operators associate from right to left. For example:

int i = 3;
int j = 5;

i = j = 7;
printf("i = %d, j = %d\n", i, j);

where the assignment expression is equivalent to this:

i = (j = 7);

Pop quiz 1: what happens here? And why?

int i = 3;
int j = 5;

(i = j) = 7;
printf("i = %d, j = %d\n", i, j);

Pop quiz 2: what happens here? And why?

int i = 3;
int j = 5;

i = -j--;

printf("i = %d, j = %d\n", i, j);

Pop quiz 3: what happens here? And why?

int i = 3;
int j = 5;

i = ---j;

printf("i = %d, j = %d\n", i, j);

Evaluation Order

The semantics of an expression, as determined by the precedence and associativity of operators, dictates how an expression is to be parsed. In other words, we can interpret an expression as a tree, where the nodes are operators and the edges connect each operator to the submextressions that make up its operands. In this view, the precedence and associativity of operators defines the shape of the tree. The lower-precedence operators will be at the top of the tree, while the higher-precedence operators will be at the bottom of the trees (closer to the leaves).

Another way to look at the associativity rules and therefore the parse tree of an expression is to consider it as a data flow diagram, where every sub-expression is a source of data, and data flows from sub-expressions into and out of operators to other operators up to determine the value of the highest-level expression. For example, in this interpretation of the expression i = j + k * 10, data flows from k and literal value 10 into the * operator; then the result of the * operator flows into + operator together with the data from j; then the result of the + operator goes into the = operator (right-hand side) together with i (left-hand side).

This is all very nice. It’s a good way to look at the semantics of expressions. In fact, you should take a piece of paper and practice drawing the parse and data-flow tree for many expressions. But this is not what this section is about. Here we talk about the order of evaluation of the operands and (subexpressions). And that has little to do with the parse and data-flow tree. The same is true of the side-effects of the various operators. These include the “side-effect” of incrementing a variable with ++ or of assigning one with =. Those are also not determined by precedence or associativity rules. We need to learn new rules for that.

To illustrate the question of the evaluation order, consider the following code:

i = f() + g() - h();

What is the order of invocation of the three functions?

Does the order change in the following expression? And if so, how?

i = f() + g() * h();

And what about this case:

A[f()] = B[g()] = C[h()];

What is the order of invocation of the three functions?

The answer is, unspecified! The order is in fact unspecified in the previous examples as well.

Notice that the evaluation of an expression (or subexpression) might include the computations of values, as well as the initiation of side-effects.

Sequencing and Sequence Points

The C and C++ languages do not mandate a precise evaluation order for all expressions. (Other languages such as Java do that.) This means that in C and C++ the evaluation order of expressions is sometimes unspecified. For example, the order in which the arguments of a function call are evaluated is unspecified. One reason for this design choice is to give maximum flexibility to the compiler to perform aggressive code optimization. On the other hand, this means that the programmer must make sure that the code is correct in all allowable evaluation orders. And of course the programmer can explicitly determine any evaluation order. Also, in some cases the order of evaluation is fully specified and therefore unambiguous.

Let’s learn how all of this is done. We start by defining the fundamental notion of execution order. We consider the order between any two elementary evaluations \(A\) and \(B\). An elementary evaluation might represent the use of the value of an object, the computation of a value by the application of operator, the side-effect of the application of an operator on scalar value, such as the assignment or the increment of an int value, or the invocation of a function.

In some cases, an evaluation \(A\) is sequenced before another evaluation \(B\). In other cases, it’s the opposite. And yet in other cases, it is neither, that is, neither \(A\) is squenced before \(B\) nor \(B\) is sequenced before \(A\). In this latter case, we also say that \(A\) and \(B\) are unsequenced relative to each other.

Here is an example:

A[i] = A[i+1] * A[i+2];

Here the evaluations of the two operands of the multiplication operator are unsequenced. This means that the expressions A[i+1] and A[i+2] may be evaluated in any order. In fact, the same is true for the subexpressions that make up the array indexes. In fact, even the evaluation of the two operands of the assignment operator are unsequenced. This means that the determination of the destination object (l-value A[i]) and the determination of the value to be assigned (r-value A[i+1]*A[i+2]) are unsequenced. However, those two evaluations are sequenced before the side effect of storing the value of the right operand (r-value) into the object of the left operand (l-value). This is confusing. I know. So, just go back and read this paragraph once again from the beginnig. Trust me: do it!

Here is another, related example:

i = f(i) + g(i);

Here the evaluations of the left- and right-hand sides of the assignment, i (l-value) and f(i) + g(i), respectively, are unsequenced. However, all of them are sequenced before the side effect of the assignment. This means that the value of i used in evaluating f(i) and g(i) is the initial value of i, which is later replaced by the value of the expression f(i) + g(i).

Furthermore, as in the previous case for multiplication, the evaluation of the operands of the addition operator are unsequenced. So, neither f(i) is sequenced before g(i), nor g(i) is sequenced before f(i). However, in this case, both evaluations include the invocation of a function, f(i) and g(i) respectively, and since the executions of functions do not overlap, f(i) is sequenced either before or after g(i), but we do not know which. In this case we say that the two evaluations (function executions) are indeterminately sequenced.

Here is yet another example:

if (i > 0 || f(i) == 1 || g(i) == 2) {
    /* ... */
}

Here the evaluation is completely specified. In fact, the evaluation of i > 0 is sequenced before the evaluation of f(i) == 1, which is sequenced before g(i) == 2. Furthermore, since the evaluation of logical operators always uses a short-cut semantics, f(i) == 1 is evaluated only if i > 0 evaluates to false, and g(i) == 2 is evaluated only if f(i) == 1 also evaluates to false.

So, what determines the sequencing of evaluations? Many language contstructs do that. Some operators induce some sequencing. We have seen that an assignment (= operator) introduces a sequencing between, on the one hand the computations of its two operands, and on the other hand the side effect of assignment. But the assignment does not induce a complete sequencing between any other evaluations. In particular, if the computations of the operands of the assignment have side-effects, those are unsequenced relative to all other computations in the assignment expression and also relative to the side-effect of the assignment.

Other language constructs introduce complete sequencing between their sub-expressions or even more generally. These points in the program (flow) are what we call sequence points. Everything before a sequence point is sequenced before anything after that sequence point.

The most straightforward example of a sequence point is the end of a full expression statement. Syntactically, that is indicated by a semicolon (;):

i = g(j) + h(j);
j = f(i);

Here g(j) and h(j) are sequenced before f(i), although g(j) and h(j) are unsequenced. Also, the assignment to i in the first expression statement is sequenced before the evaluation of f(i) in the second expression statement.

There is also a sequence point between the evaluation of function parameters (as well as the function designator) and the actual call. So, for example

j = f(g(j) + h(j));

here the evaluation of the parameter to function f is sequenced before the actual call of f, so the invocations of g and h are both sequenced before the invocation of f. However, the invocations of g and h are indeterminately sequenced.

Other syntactic structures introduce sequence points. The details are intuitive in most cases.

So, what happens when two evaluations are unsequenced? There are good and bad cases. Good cases are perfectly fine expressions (indeed most non-trivial expressions) in which unsequenced expressions do not interfere with each other, and the semantics of the program is unambiguous anyway.

Bad cases are those in which unsequenced expressions have interrelated side-effects, which leads to ambiguities in the interpretation of the evaluation. For example:

j = i++ - i--;

What is the value of j? And what is the value of i?

And again:

int i = 0;
j = A[++i] + B[++i];

What’s the semantics here? Is it j == A[1] + B[2]? or perhaps j == A[2] + B[1]? Or j == A[1] + B[1]?

The answer is, in all these cases the behavior is undefined. And it should be at least intuitively clear, because they are all ambiguous cases. However, notice that there are other, perhaps more subtle cases in which the behavior is also undefined. For example:

int i = 0;
int j = 1;
i = ++i;
A[j] = j++;

These two (latter) statements might look innoquous. In the first assignment, you might think that object i gets its own increment, which changes the value of i from 0 to 1. There does not seem to be any other possible interpretation. Similarly, the following assignment statement seems to assign A[1] = 1 and then increment j. However, both these statements invoke undefined behavior.

Why?

This is the precise wording in the definition of the C language:

If a side effect on a scalar object is unsequenced relative to either a different side effect on the same scalar object or a value computation using the value of the same scalar object, the behavior is undefined. If there are multiple allowable orderings of the subexpressions of an expression, the behavior is undefined if such an unsequenced side effect occurs in any of the orderings.

So, the key point is that a side effect on an object should never be unsequenced relative to another side effect on the same object, or relative to a use of the value of the same object. In the two examples above, that’s exactly what we have. In i = ++i there are two side-effects on the same object i, one from the increment operator and one from the assignment. And those side-effects are unsequenced. But okay, you might think that i = ++i is a silly if not perverse statement that no sane programmer would write. I concede that point of view. However, the second statement is not so absurd. Say you want to fill an array with the bumbers between 0 and 9. A sane programmer—although perhaps an inexperienced one—might well write j = 0; while (j < 10) A[j] = j++; thinking that there is no ambiguity. However, the side-effect on j for the increment, and the use of the same object j in the evaluation of the left-hand side expression, are unsequenced.

Are you still not convinced that this type of undefined behavior is really a problem? Fair enough. Test yourself with the follwing quizzes.

Pop quiz: do the following two statements invoke undefined behavior? Why?

A[i] = i;
i = i + 1;