From: scs@eskimo.com (Steve Summit)
Newsgroups: comp.lang.c
Subject: Re: Interesting question in C
Date: 5 Nov 1998 17:41:02 GMT
Lines: 257
Message-ID: <71snve\$3cg\$1@eskinews.eskimo.com>
References: <01be08ba\$4b7439c0\$ec19ea93@lalex.ecitele.com> <3641B492.7AC8@gec.nospam.com>

In article <3641B492.7AC8@gec.nospam.com>, Edward Hill writes: >Alex Lemelev wrote: >> int i , j = 3; >> i = ++j * ++j; > > But well ++ has higher precedence than * > so I'd imagine j is incremented to 4 and then incremented > to 5 and then multiplied by itself to give 25. > So what's the answer?

Attempting to use precedence rules to analyze malformed expressions like these is a popular pastime, but it turns out not to help. It's true that the "outputs" of the two ++'s are to be multiplied together, but what are those outputs?

Consider a related expression:

i = f1() * f2();

Function calls have higher precedence than multiplication, so the two functions will be called before the multiplication can happen. But which function is called first, f1 or f2? No one can say, and different compilers do it differently.

(I suppose you might try to invoke the left-to-right associativity of multiplication to claim that f1 would be called first, but associativity doesn't help here, either. Associativity says that in f1() * f2() * f3(), the results of f1 and f2 are multiplied together before being multiplied by the result of f3, but we still don't know which order the functions were called in. f3 might be called first, and its result saved for last.)

The situation with ++j * ++j is actually even worse than with f1() * f2(). In the function call case, it's probably true that either f1 is called first and then f2, or f2 is called first and then f1. Applying the same logic to ++j * ++j, we might imagine that either the left-hand ++j gets evaluated first and then the right-hand one, yielding 4 * 5 = 20, or else the right-hand one gets evaluated first and then the left-hand one, yielding 5 * 4 = 20. But it turns out that this analysis doesn't work, either.

The problem is that ++j does two things. It delivers the value j+1 to the surrounding expression, and it stores the value j+1 back into j, thus incrementing it. But we don't know (because the C Standard doesn't tell us) precisely when the updated value of j gets written back to j.

In some expressions, it doesn't matter. If we wrote

i = ++j * k;

the compiler could emit code which essentially either interpreted the expression as

j = j + 1;
i = j * k;
or
i = (j+1) * k;
j = j + 1;

If we wrote

i = ++j * ++k;

there would be at least six possible interpretations:

j = j + 1;                    k = k + 1;
k = k + 1;                    j = j + 1;
i = j * k;                    i = j * k;

i = (j+1) * (k+1); i = (j+1) * (k+1); j = j + 1; k = k + 1; k = k + 1; j = j + 1;

j = j + 1; k = k + 1; i = j * (k+1); i = (j+1) * k; k = k + 1; j = j + 1;

Now, all six of those interpretations yield the same answer (16, if j and k both start out as 3). But if you replace k in each of them by j, resulting in six possible interpretations of the expression ++j * ++j, you can get at least three different answers (16, 20, and 25, by my reckoning).

But it gets worse. The official wording in the ANSI/ISO C Standard says that if you attempt to modify the same object at one spot within an expression and refer to that same object at another spot (as in the expression ++j * j), or if you attempt to modify the same object twice within an expression (as in the expression ++j * ++j), the results are undefined [footnote 1]. What this means is that the compiler isn't even required to choose among the two (or six, or however many you can come up with) "plausible" interpretations of the expression; it can do any random thing it wants to, and it won't be in violation of the Standard. (In practice, it's not so much that compilers do "any random thing they want to" in these situations, but what does happen is that they do any random thing that falls out of their algorithms for handling well-formed expressions, algorithms which are not designed -- because they do not have to be -- to do anything reasonable with undefined expressions.)

Now, you might say (and I'd agree with you) that the expression i = ++j * ++j would be so unlikely to come up in a real program that it hardly matters what it does. But if you think you can analyze that expression and figure out what it does, then there's a flaw either in your analysis or in your understanding of C. And I would urge you to repair that flaw -- to teach yourself that you cannot analyze the behavior of expressions like these -- because that way you won't falsely imagine that you can predict the behavior of other, more insidious undefined expressions which do occasionally crop up in real programs, expressions which will cause real problems if they are retained, expressions which it will do nobody any positive good to be able to analyze or justify, expressions which should ideally be recognized as the undefined expressions they are and banished from the program as soon as possible.

As an example of how a "more insidious undefined expression" can in fact crop up in a real program, consider the following decidedly non-hypothetical scenario. (The reason I know it's not hypothetical is that I know the programmer it happened to.) The program is the interpreter for a stack machine, and it contains code like

switch(op)
{
push(pop() + pop());
break;
case SUBTRACT:
tmp = pop();
push(pop() - tmp);
break;
case MULTIPLY:
push(pop() * pop());
break;
case SUBTRACT:
tmp = pop();
if(tmp == 0) {error("divide by 0"); break; }
push(pop() / tmp);
break;
...

In the original implementation, push() and pop() are function calls. The original programmer, knowing that the order of function calls within an expression is unpredictable (see our discussion of f1 and f2 above) has taken care to use a temporary variable to ensure that the operands are popped in the right order for subtraction and division, where it matters.

But the interpreter is too slow, and a later programmer reasons that part of the problem is function call overhead. (Most of the time, it's a good idea not to worry about function call overhead too much, but in some situations, such as the inner loop of an interpreter which might be interpreting huge amounts of code, it can indeed be significant.)

I don't remember if the push and pop functions were

void push(val)
{
stack[stackp++] = val;
}

pop() { return stack[--stackp]; }

or

void push(val)
{
*stackp++ = val;
}

pop() { return *--stackp; }

(That is, although the stack and the stack pointer were both global, I don't remember whether the stack pointer was an index or a pointer into the stack.) But, in either case, it's easy to see how we might replace the push and pop functions with macros, thus removing the function call overhead in the critical inner loop, without rewriting the entire interpreter. (In fact, this interpreter had hundreds of operators, some much more complicated than simple arithmetic, so there were hundreds of calls to push() and pop() spread across many source files.)

The macros would, of course, either be

#define push(val) (stack[stackp++] = (val))
#define pop() stack[--stackp]

or

#define push(val) (*stackp++ = (val))
#define pop() *--stackp

and this seems like a very simple way to dramatically increase the efficiency of the interpreter. (It did, too, by 20 or 30 percent.) The problem was that the interpreter also began delivering wildly erroneous answers.

The problem turned out to be in those innocuous-looking lines

push(pop() + pop());
and
push(pop() * pop());

for addition and multiplication. When push() and pop() are macros, these lines expand to either

(stack[stackp++] = (stack[--stackp] + stack[--stackp]));
(stack[stackp++] = (stack[--stackp] * stack[--stackp]));
or

(*stackp++ = (*--stackp + *--stackp));
(*stackp++ = (*--stackp * *--stackp));

And these expressions bear an eerie similarity to the one that began this thread. (They're complicated by an added level of indirection, and they each attempt to modify stackp three times within one expression.) And yes, under a popular, real-world compiler, namely gcc, these expressions did produce some crazy result which was not at all the expected one but which, by a strict and proper interpretation of the C Standard, was not incorrect. (That is, it was not incorrect for the compiler and the emitted code to have produced the undesired result.) The compiler had not done anything wrong; the error was on the part of the programmer who attempted to replace the function calls with macros, macros which proved to be dangerous because of their embedded side effects.

And finally, in case anyone is doubting the truth of this story, I can tell you that the maintenance programmer who introduced the undefined behavior was (as others of you have probably already guessed) none other than the maintainer of the comp.lang.c FAQ list, Steve Summit, who presumably ought to have known better.

Steve Summit
scs@eskimo.com

Footnote 1: The real rule on undefined expressions is that you can't modify an object twice, or modify and then inspect it, between sequence points. There are a few operators -- including function calls -- which do introduce sequence points, so it's possible to come up with expressions which contain multiple side effects but which are not undefined.