NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/lang/c/16220

Text File | 1992-11-09 | 7.9 KB | 206 lines

Newsgroups: comp.lang.c
Path: sparky!uunet!snorkelwacker.mit.edu!bloom-picayune.mit.edu!news
From: [e-mail] (Steve Summit)
Subject: retrospective on evaluation order
Message-ID: <[e-mail]>
Sender: [e-mail] (News system)
Nntp-Posting-Host: adam.mit.edu
Organization: none, at the moment
References: <josef.720691377@uranium> <[e-mail]> <[e-mail]>
Date: Mon, 9 Nov 1992 17:31:26 GMT
Lines: 193

In article <josef.720691377@uranium>, Josef Moellers <[e-mail]> writes:
> Furthermore, as "boolean" operations are nothing special in C, I wonder
> whether in
>     a() || b()
> b _should_ be called if a() returns TRUE.

I'd like to thank Josef for asking this question, which in the
surrounding context has crystallized the question and
helped me for the first time to understand it perfectly clearly.

I do understand evaluation order well enough to write C programs
correctly.  But there has always been something missing in my
understanding of other people's misunderstandings.  Josef's
question is actually on the FAQ list (question 4.3 in the latest
versions), but it was put there at (as I recall) Karl Heuer's
request -- I didn't really see (until now) what it added.  (I
think I'll revise section 4 again, to make things even clearer.)

Years ago, a colleague scoffed at some third person's
misunderstanding of evaluation order with the comment, "Don't
they understand the difference between precedence and evaluation
order?"  I agreed and nodded knowingly, but that comment has
always bothered me as well, because the concept of precedence is
not wholly divorced from or orthogonal to evaluation order.

"Precedence" tells you, in the absence of explicit or overriding
parentheses, how an expression is grouped; it determines the
shape of the "parse tree" corresponding to a given expression.
This grouping (i.e. the shape of the parse tree) *does* impose
some partial ordering on the evaluations which will take place:
obviously, you must evaluate the operands of an operator before
applying the operator (actually, even here there are exceptions
with respect to the "short-circuiting" operators, which is what
Josef is asking about).

Therefore, given the expression

    a + b * c

, precedence tells us that the multiplication must happen before
the addition, as we learned back in Algebra.  In the expression

    d + e + f

, precedence tells us nothing, although associativity tells us
that d should be added to e and the sum added to f, i.e. that it
should be evaluated as

    (d + e) + f

 .

So far I seem to be making the wrong point: in these simple
examples, precedence and associativity have almost completely
determined the "evaluation order," that is, the order in which
the multiplications and additions should take place.  This is
because, in these simple examples, the partial ordering implied
by precedence and associativity has apparently been sufficient to
order the entire expression.  As soon as we begin to consider
side effects, however, we will see that partial ordering does not
tell the whole story.

Let us look at

    g() + h() * j()

 .  As before, the multiplication must happen before the
addition, but what does that tell us about the order in which the
three functions are called?  Not much.  h() and j() must be
called before the multiplication can take place, and all three
before the addition can take place, but that still leaves many
orders in which the calls could be interleaved.  In particular,
nothing says that we need call h() and j(), then perform the
multiplication, then call g(), then do the addition; g() could
easily be called first.  (To answer another question, we do know
that all three functions must in principle be called; there is no
short-circuiting implied by things like multiplication by 0.)

Once we begin considering side effects, we find that complete
evaluation order is unspecified even for simpler expressions,
such as

    k() + l()

and

    volatile int m, n;
    int p = m + n;

We don't know whether k() or l() will be called first, and we
don't know whether the variables m or n will be *fetched* first
(and, since they are volatile, presumably this may make a
difference to us).

We can now turn to a couple of final points, the first of
historical interest only.  K&R ("Classic") C gave a compiler
license to rearrange associative operators.  That is, given

    d + e + f

, the compiler might emit code to add e to f first, or even d to f.
This license has been revoked under ANSI C; compilers must appear
to honor the prescribed associativity as it applies to evaluation
order (although the "as if" rule still allows rearrangements if
they are guaranteed not to make a difference).  The difference
(between being able to rearrange at will and being able to
rearrange only if it can't make a difference) is subtle, but can
be important in numerical work and when things like overflow are
possible.

Secondly, what about those "short-circuiting" operators?  Given

    k() + l()

, we don't know what order the functions will be called in.
However, given

    q() || r()

, we *are* guaranteed that q() will be called first, and
furthermore that r() will not be called at all if q() returns
nonzero (i.e. "true").  Given

    s() && t()

, we are similarly guaranteed that s() will be called first, and
that t() will not be called if s() returns zero ("false").  Given

    u() ? w() : x()

, we are guaranteed that u() will be called first, and that only
one of w() and x() will be called.  Finally, given

    y(), z()

, we are guaranteed that y() will be called first, then z().

To summarize: precedence and associativity impose a partial
ordering on some of the operations which take place during the
evaluation of a full expression, but they are in general
insufficient to completely determine the order, particularly when
side effects are considered.  The four operators ||, &&, ?:, and
, (comma) do impose constraints on the order in which their
respective operands are evaluated, although order of evaluation
within those operands, and order of operation within the larger
expression containing the ||, &&, ?:, or , operator, may still
have unspecified aspects.

                    Steve Summit
                    [e-mail]

P.S.  In this article, I have deliberately been casual rather
than rigorous in my explanations.  (In particular, I have freely
used the term "precedence" which Chris correctly points out can
be superfluous as well as misleading.)  I have glossed over a few
fine points; more formal explanations can be found in any number
of nearby articles under the Subject: order of evaluation.  This
article doesn't really say anything that other correct answers
have not; the entire issue is summed up by a single sentence in
section 3.3 of the ANSI C Standard [X3.159-1989, p. 39]:

    Except as indicated by the syntax or otherwise specified
    later (for the function-call operator (), &&, ||, ?:, and
    comma operators), the order of evaluation of
    subexpressions and the order in which side effects take
    place are both unspecified.

In the interest of some rigor, I should make one other point:  In
the expression

    e1 + e2

, we said that e1 and e2 must be evaluated before the addition
can take place.  This is still, in two respects, a partial
ordering: not only do we not know whether e1 or e2 is evaluated
first; we cannot even assume that one of them is evaluated first.
There is no "sequence point" implied by an addition operator, so
we had best assume that the evaluations of e1 and e2 happen at
the same time; this is why we must rule out expressions such as

    i++ + i++

, the behavior of which is undefined, and is *not* guaranteed to
be the same as

    tmp1 = i++, tmp2 = i++, tmp1 + tmp2

 .  In other words, the commutativity of addition does *not* mean
that it doesn't make a difference which increment happens first.
See the FAQ list, question 4.2, or recall one of Chris' colorful
descriptions of a compiler's throwing several values up into the
air and not catching them reliably until the dust settles at the
next sequence point.