4

I think my book (Programming Languages: Principles and Paradigms) is wrong. a is a vector, assume a C-like language:

b = 0;
a[f(3)] = a[f(3)] + 1;

int f(int n) {
    if(b == 0) {
        b = 1;

        return 1;
    }
    else return 2;
}

It has the effect of assigning the value of a[1] + 1 to a[2] whenever the evaluation of the left-hand component of the assignment precedes the evaluation of the right-hand one.

For me, it has the opposite effect, that is assigning the value of a[2] + 1 to a[1].

Because the left-hand component is evaluated first, so f returns 1 (because b is 0), thus a[1]. Then the right-hand component is evaluated, f returns 2 (because now b is 1), thus a[2] + 1.

Am I right and the book is wrong? Unfortunatly there is no errata...

Kilian Foth
  • 107,706
  • 45
  • 295
  • 310
user34295
  • 143
  • 3
  • 20
    The title indicates a wrong premise, this depends *entirely* on the language. (Specifically on a detail that might be considered small enough to differ among two "X-like languages", which makes it kind of hard to give a clear-cut answer.) –  Feb 14 '13 at 16:28
  • 5
    This is a beautiful example of how functions having side-effects can be a really Bad Thing. If the compiler could assume that f(x) == f(x) for all x and all f, the results would be very different, and very intuitive. – John R. Strohm Feb 14 '13 at 16:34
  • 2
    @delnan: Actually, it depends on the implementation. Some languages don't define whether the left-hand side of an assignment is evaluated before or after the right-hand side, but rather warn that the order is undefined, and the programmer is expected to be smart enough to write his code in a way that it doesn't matter. – John R. Strohm Feb 14 '13 at 16:37
  • 1
    @JohnR.Strohm "It's implementation-defined" is another answer that may or may not be correct, depending on the language ;-) Though I must say I can't think of a single language that make it implementation dependent - it's usually either well-defined or undefined (in the same sense as in the C and C++ standards; i.e. relying on it makes your program invalid and implementations are not required to be consistent or even sensible about what they do with it). –  Feb 14 '13 at 16:44
  • ... And with the rise of multiple cores, there's the possibility that a future optimizer might decide it can execute both calls to `f()` simultaneously, resulting in both calls returning `1`. I'm not sure if any language currently allows for that behavior, though... – Clockwork-Muse Feb 14 '13 at 19:16
  • 2
    @delnan: In C and C++, the order of evaluation is *unspecified*, meaning the calls will occur in some order but the results will be consistent with one order or the other. The behavior of `a[i++] = a[i++] + 1`, on the other hand, is *undefined*; it can evaluate the `i++`s in either order, or it can make demons fly out of your nose. – Keith Thompson Feb 14 '13 at 22:22
  • I think the close votes are a bit premature. The question may be less than ideal, however the currently leading answer by @Keith is of exceptionally high value to the community. – mattnz Feb 15 '13 at 04:34

5 Answers5

20

You wrote "assume a C-like language". Just how C-like should it be?

First, it does appear that the author's logic is backwards:

It has the effect of assigning the value of a[1] + 1 to a[2] whenever the evaluation of the left-hand component of the assignment precedes the evaluation of the right-hand one.

In fact, it has that effect if the evaluation of the LHS follows the evaluation of the RHS.

Some "C-like" languages (in the sense that their syntax looks similar to C's) define the order of evaluation of expressions. (I think Java does this.) In such a language, the semantics of the code would depend on exactly how the language defines the order of evaluation. If the order is left-to-right, then the function call on the LHS (left-hand side) of the assignment will be evaluated first.

In C itself (and in C++), the order of evaluation is unspecified. The two function calls could be evaluated in either order, depending on the whim of the compiler (optimization can change this; so, in principle, can the phase of the moon). I don't believe the behavior of this particular code is actually undefined, which would mean that the language says nothing about how it behaves, but similar code such as:

a[i++] = a[i++] + 1;

does have undefined behavior, because i is modified twice with no intervening sequence point. In C, the above could evaluate the LHS i++ before the right one, or vice versa -- but those aren't the only possibilities. A C compiler is free to assume that your program doesn't modify i twice between sequence points. This particular example seems easy for the compiler to detect, but in more complex cases it can be difficult or impossible to do so.

But the real answer to the question is: Don't write code like that.

You really don't need to have two function calls in a single statement, where the results depend on the order in which they're evaluated. Separate the calls into distinct statements, for example:

int x = f(3);
int y = f(3);
a[x] = a[y] + 1;

And in real life, you want better names than x, y, f, and a -- and f() probably shouldn't return different results on successive calls, or it should be very clear why it needs to do so.

Write your code so that questions like this don't arise in the first place.

Keith Thompson
  • 6,402
  • 2
  • 29
  • 35
  • 1
    And another +1 for "Write your code so that questions like this don't arise in the first place." – mattnz Feb 15 '13 at 04:30
  • 1
    By the way, I don't write code like this. It's a school book... – user34295 Feb 15 '13 at 18:36
  • 1
    @Gremo: Often examples in books, intended to illustrate a point rather than be used in production, do things that shouldn't be done in real-world code. – Keith Thompson Feb 15 '13 at 19:05
  • Prefix and postfix assignment operators, except in trivial cases are confusing and sometimes dangerous. Just imagine the possibilities for `a[i--] = a[i++] + 1`; it's almost as bad as the problems with multithreaded programming and shared variables. – Michael Shopsin Feb 15 '13 at 20:23
7

The order of evaluation is usually undefined, and therefore can go either way depending on the compiler, although some pedantic languages might define it. That's why most of the time when you see an example like that, it's to warn you not to do it.

If the compiler goes strictly by the order the index is needed, the book is right, because you have to read the value, then perform the addition, then do the assignment. However, you don't have to compute the array indexes in the same order they are used, and some optimizations might take advantage of that fact.

Allow me to demonstrate with some intermediate representation pseudocode. The first pass of a compiler will usually produce something like this:

temp1 = f(3)
temp2 = a[temp1]
temp3 = temp2 + 2
temp4 = f(3)
a[temp4] = temp3

Line 1 must come before line 2. Line 2 must come before line 3. Line 3 must come before line 5. Line 4 must come before line 5. Aside from that, the order of execution is not usually defined by the language, so compilers will do whatever is more efficient or easier to implement. It is perfectly allowed to end up like this:

temp4 = f(3)
temp1 = f(3)
temp2 = a[temp1]
temp3 = temp2 + 2
a[temp4] = temp3

A compiler might do it that way if the last three lines can be combined into a single assembly instruction. Since the destination is often specified first in an assembly instruction, it might make sense to calculate the destination index first, but you don't have to do it in that order.

Another compiler might not have so many registers to work with, or have a smaller instruction set, so they might calculate the source index first in order to be able to reuse the temp1 register.

Languages usually purposely leave it undefined to allow compiler implementations to do whatever is most efficient.

Karl Bielefeldt
  • 146,727
  • 38
  • 279
  • 479
  • 1
    Correct me if I'm wrong, but before computing the value (right-hand side), the compiler should compute the l-value (left-side). In addition, the book specifies that "whenever the evaluation of the left-hand component precedes the evaluation of the right-hand one". – user34295 Feb 14 '13 at 16:21
  • 3
    @Gremo: The order of evaluation depends on the language and the compiler. In C, either order is permitted. But even assuming the LHS is evaluated first, the author's logic is backwards. – Keith Thompson Feb 14 '13 at 16:45
  • @Gremo, I added some pseudocode to illustrate the point better. – Karl Bielefeldt Feb 14 '13 at 16:47
2

I think your interpretation is correct. If the book's author has an e-mail address, you might want to contact him.

I have not read the book, but I guess the next paragraph will state that it is dangerous to rely on such side-effects, since they make code hard to read and lead to difficult bugs. Quod erat demonstrandum, I would say. :-)

Heinzi
  • 9,646
  • 3
  • 46
  • 59
1

Your line of code is equivalent to

a[x] = a [y] + 1;

The book may have it backwards, saying something happens when the left (x) is evalulated first, but actually that happens when the right (y) is evaluated first, but that is almost certainly not the point.

The point is that you don't know whether x or y will be evaluated first. You may feel that "before computing the value (right-hand side), the compiler should compute the l-value (left-side)" but you didn't write every compiler on the planet. Some compiler writers might want to go left to right, some right to left, some according to the order you will need them - you need y first, to get a value to add 1 to, and only then do you need x to figure out where to put the value - and they are all correct because this particular decision is left up to the compiler writer and you must not rely on it, ever.

Kate Gregory
  • 17,465
  • 2
  • 50
  • 84
0

You are correct. The first call to f() will evaluate to 1, subsequent ones evaluate to 2. If the left-hand operand of the assignment is indeed fully evaluated first (which is kind of debatable), then the assignment evaluates to:

a[1] = a[2] + 1;

This, however, also assumes that the value of b is never modified before this line is called, and also that f() is never called before this line.

Also note that the n parameter to f() is never used, so I assume it's quite likely that there is some typo of sorts there.

It would be interesting to know what point the author is trying to make here.

tdammers
  • 52,406
  • 14
  • 106
  • 154
  • Thank you for confirming this. The point is about left/right hand side evaluation and side effects. Indeed, quite confusing. – user34295 Feb 14 '13 at 16:18
  • No, there's no typo. The point of the example is obviously to illustrate just how big a mess can be made with side-effects. (And I still recall the late Prof. Edsger W. Dijkstra saying, in a talk at UT Austin ca. 1998, that the real objective hadn't changed in 50 years: "Don't make a mess of it!") – John R. Strohm Feb 14 '13 at 16:40