On sequence points and evaluation order
Nikolaos Papaspyrou
I have a couple of questions regarding side effects, order of
evaluation and the meaning of a "sequence point" in the standard.
I would appreciate if somebody could take some time to answer...
Question 1: Consider the following two programs.
int i = 0; int i = 0;
int main () { int f () { return (i = 1); }
return (i = 1) + i;
} int main () {
return f() + i;
}
As far as common sense is concerned, the two programs are equivalent.
I believe the behavior of the program on the left is undefined
according to the standard, since between two consecutive sequence
points (before and after the return statement) a write and a read
operation occur for object "i", and the read operation does not intend
to calculate the value that the write operation will store.
The program on the right does exactly the same thing, only there seems
to be an extra sequence point just before function "f" is called. Now
the read and write operations do not occur between two successive
sequence points. Therefore (please correct me in this, for I believe
this statement is wrong), the behavior of this program is not
undefined (so what is it?).
Question 2: Consider the following similar program.
int f () { printf("message 1\n"); return 1; }
int g () { printf("message 2\n"); return 2; }
int main () {
return f() + g();
}
Evaluation order is not specified and therefore we cannot determine
which message will be printed first. However, behavior is not
undefined but depends on the implementation.
Assuming that both programs in the previous question have undefined
behavior (as I believe it is), why do we consider a call to "printf"
to be so drastically different from a write operation to a variable?
How will we implement "printf" after all? Won't it have to change a
few global or static objects, since we usually have buffers for
"stdout"? And if I implement such a buffer myself, in my own "printf"
in my own program, will two calls like this have undefined behavior
because I'm assigning twice to the same variable?
Conclusion: If all this is true, it seems like the whole idea of
unspecified order of evaluation is not well defined. I assume this is
not the case, so there must be a number of mistakes in my arguments.
Could you please help me in locating them?
Thanks,
Nikos Papaspyrou.
---------------------------------------------------------------------
Nikolaos S. Papaspyrou (nic...@softlab.ntua.gr)
National Technical University of Athens
Department of Electrical & Computer Engineering
Division of Computer Science
Polytechnioupoli, 15773 Zografou, Athens, Greece
Tel: +30-1-7722486, +30-1-7018391 (home), FAX: +30-1-7784578
Jerry Coffin
>I have a couple of questions regarding side effects, order of
>evaluation and the meaning of a "sequence point" in the standard.
>I would appreciate if somebody could take some time to answer...
>Question 1: Consider the following two programs.
> int i = 0; int i = 0;
> int main () { int f () { return (i = 1); }
> return (i = 1) + i;
> } int main () {
> return f() + i;
> }
>As far as common sense is concerned, the two programs are equivalent.
>I believe the behavior of the program on the left is undefined
>according to the standard, since between two consecutive sequence
>points (before and after the return statement) a write and a read
>operation occur for object "i", and the read operation does not intend
>to calculate the value that the write operation will store.
>The program on the right does exactly the same thing, only there seems
>to be an extra sequence point just before function "f" is called. Now
>the read and write operations do not occur between two successive
>sequence points. Therefore (please correct me in this, for I believe
>this statement is wrong), the behavior of this program is not
>undefined (so what is it?).
Both are undefined - the order of evaluation of `f() + i' is undefined.
The compiler is free to treat it as if you had written either:
int temp = i;
i = temp + f();
or:
f();
i = i + i;
(Or in theory, since this is undefined behavior, it can do anything else
it wants to as well, but generally it'll evaluate the arguments and
produce a result, but you can't predict what it'll be. )
>Question 2: Consider the following similar program.
> int f () { printf("message 1\n"); return 1; }
> int g () { printf("message 2\n"); return 2; }
> int main () {
> return f() + g();
> }
>Evaluation order is not specified and therefore we cannot determine
>which message will be printed first. However, behavior is not
>undefined but depends on the implementation.
>Assuming that both programs in the previous question have undefined
>behavior (as I believe it is), why do we consider a call to "printf"
>to be so drastically different from a write operation to a variable?
Because it's a function call, and a sequence point between having
evaluated the arguments to a function, and actually invoking the
function.
>How will we implement "printf" after all? Won't it have to change a
>few global or static objects, since we usually have buffers for
>"stdout"? And if I implement such a buffer myself, in my own "printf"
>in my own program, will two calls like this have undefined behavior
>because I'm assigning twice to the same variable?
No - there's always a sequence point betwen evaluating the arguments to
a function, and invoking the function. Therefore, printf is not the
issue here. The presence or lack of a sequence point is the issue. If
you have a function call, it forces a sequence point. If you used
various other things, they force sequence points as well. e.g. if you'd
written:
f(), i = i + i;
you'd have a perfectly valid, well defined statement. However, if you
do the more obvious:
i = f(), i+i;
I believe the result is still technically undefined. The assignment
operator doesn't force a sequence point, so in theory the compiler could
treat evaluate the i on the left side before or after the entire right
side. However, from a practical viewpoint, it's pretty hard to assign
the correct value to i until after you figure out what it is, which is
done after the sequence point introduced by the comma operator. OTOH,
even a little bit of optimization allows the compiler to "know" the
value of `i' before executing the statement, so it could treat this as:
i = 0;
f();
and still be legal. ( I think...)
>Conclusion: If all this is true, it seems like the whole idea of
>unspecified order of evaluation is not well defined. I assume this is
>not the case, so there must be a number of mistakes in my arguments.
>Could you please help me in locating them?
Well, it's a simple situation. Storing to a variable more than once
between sequence points is undefined. Some things, including function
call, force sequence points. Other things don't. If you have something
that gives undefined results due to storing multiple values to a single
object between sequence points, then certainly introducing a sequence
point (whether by a function call, comma operator, or separating things
into multiple statements) can certainly render the results defined.
(Note: "can" not necessarily "will")
Later,
Jerry.
/* I can barely express my own opinions; I certainly can't
* express anybody else's.
*
* The universe is a figment of its own imagination.
*/
Christopher R. Volpe
>nic...@cs.cornell.edu (Nikolaos Papaspyrou) wrote:
>>Question 1: Consider the following two programs.
>
>> int i = 0; int i = 0;
>
>> int main () { int f () { return (i = 1); }
>> return (i = 1) + i;
>> } int main () {
>> return f() + i;
>> }
>
>>As far as common sense is concerned, the two programs are equivalent.
>>I believe the behavior of the program on the left is undefined
>>according to the standard, since between two consecutive sequence
>>points (before and after the return statement) a write and a read
>>operation occur for object "i", and the read operation does not intend
>>to calculate the value that the write operation will store.
>
>>The program on the right does exactly the same thing, only there seems
>>to be an extra sequence point just before function "f" is called. Now
>>the read and write operations do not occur between two successive
>>sequence points. Therefore (please correct me in this, for I believe
>>this statement is wrong), the behavior of this program is not
>>undefined (so what is it?).
>
>Both are undefined
No. The one on the left is undefined. It can crash. The one on the right
returns a value to the OS that must be either 1 or 2.
>- the order of evaluation of `f() + i' is undefined.
The standard does not associate the word "undefined" with order of evaluation.
>The compiler is free to treat it as if you had written either:
>int temp = i;
>i = temp + f();
>
>or:
>
>f();
>i = i + i;
I think you're confused here. I don't see either of those programs doing
anything remotely like assigning the result of (i+i) back into i.
>
>(Or in theory, since this is undefined behavior, it can do anything else
>it wants to as well, but generally it'll evaluate the arguments and
>produce a result, but you can't predict what it'll be. )
Except that it's not undefined behavior in the program on the right.
>
>>Question 2: Consider the following similar program.
>
>> int f () { printf("message 1\n"); return 1; }
>> int g () { printf("message 2\n"); return 2; }
>
>> int main () {
>> return f() + g();
>> }
>
>>Evaluation order is not specified and therefore we cannot determine
>>which message will be printed first. However, behavior is not
>>undefined but depends on the implementation.
>
>>Assuming that both programs in the previous question have undefined
>>behavior (as I believe it is), why do we consider a call to "printf"
>>to be so drastically different from a write operation to a variable?
>
>Because it's a function call, and a sequence point between having
>evaluated the arguments to a function, and actually invoking the
>function.
And if you noticed in the right-hand program in the first question, there was
also a function call and sequence point.
>>How will we implement "printf" after all? Won't it have to change a
>>few global or static objects, since we usually have buffers for
>>"stdout"? And if I implement such a buffer myself, in my own "printf"
>>in my own program, will two calls like this have undefined behavior
>>because I'm assigning twice to the same variable?
>
>No - there's always a sequence point betwen evaluating the arguments to
>a function, and invoking the function. Therefore, printf is not the
>issue here. The presence or lack of a sequence point is the issue. If
>you have a function call, it forces a sequence point. If you used
>various other things, they force sequence points as well. e.g. if you'd
>written:
>
> f(), i = i + i;
>
>you'd have a perfectly valid, well defined statement. However, if you
>do the more obvious:
>
> i = f(), i+i;
>
>I believe the result is still technically undefined. The assignment
Huh? You first have "i = f()", which is fine, then you have a comma operator,
which forces a sequence point, then you have "i+i", which is evaluated and the
results discarded. Why is this undefined?
>operator doesn't force a sequence point, so in theory the compiler could
>treat evaluate the i on the left side before or after the entire right
>side. However, from a practical viewpoint, it's pretty hard to assign
>the correct value to i until after you figure out what it is, which is
>done after the sequence point introduced by the comma operator. OTOH,
Perhaps you meant "i = (f(), i+i)". This is still not undefined. The
expression on the right is used to compute the new value of i in the top level
assignment. And the subexpression on the right has a sequence pint between the
evaluatin of "i=1" in f(), and the evaluation of "i+i". I see nothing
technically wrong with this according to the rules of the STandard.
--
Chris Volpe Phone: (518) 387-7766 (Dial Comm 8*833
GE Corporate R&D Fax: (518) 387-6560
PO Box 8, Schenectady, NY 12301 Email: vol...@crd.ge.com
Eivind Eklund
nic...@cs.cornell.edu (Nikolaos Papaspyrou) writes:
>
>
>I have a couple of questions regarding side effects, order of
>evaluation and the meaning of a "sequence point" in the standard.
>I would appreciate if somebody could take some time to answer...
>
>
>
> int i = 0; int i = 0;
>
> int main () { int f () { return (i = 1); }
> return (i = 1) + i;
> } int main () {
> return f() + i;
> }
>
>As far as common sense is concerned, the two programs are equivalent.
>I believe the behavior of the program on the left is undefined
>according to the standard, since between two consecutive sequence
>points (before and after the return statement) a write and a read
>operation occur for object "i", and the read operation does not intend
>to calculate the value that the write operation will store.
>
>The program on the right does exactly the same thing, only there seems
>to be an extra sequence point just before function "f" is called. Now
>the read and write operations do not occur between two successive
>sequence points. Therefore (please correct me in this, for I believe
>this statement is wrong), the behavior of this program is not
>undefined (so what is it?).
The sequence point is not the same as order of evaluation determination.
The sequence point for the function call is regarding the expressions
inside the function parameter list; they will be evaluated before the
function is called. This do, however, not determine whether the rest of
the expression the function call appear in have been evaluated. (The
sequence point also mean that the values of all variables have to be in
memory at this point; ie, the function can read any variable it have
some way of getting access to, and get a value that correspond to what
the rest of the program believe it is.)
The value of i in the expression return f() + i; can be evaluated before
or after the function call, so it is invoking undefined behaviour (order
of evaluation.)
--
Eivind Eklund
eivind...@funcom.com
FUNCOM don't speak for me, and I return the courtesy.
Barry Margolin
Nikolaos Papaspyrou <nic...@cs.cornell.edu> wrote:
>Assuming that both programs in the previous question have undefined
>behavior (as I believe it is), why do we consider a call to "printf"
>to be so drastically different from a write operation to a variable?
>few global or static objects, since we usually have buffers for
>"stdout"? And if I implement such a buffer myself, in my own "printf"
>in my own program, will two calls like this have undefined behavior
>because I'm assigning twice to the same variable?
The basic idea is that a programming language definition must define a
certain number of constraints on implementations, so that programmers can
know what to expect. But language designers try not to over-constrain the
specification, to allow implementors enough freedom to add optimizations
and try clever code generation strategies.
The choices of where to introduce sequence points appears to have been made
mostly by looking at existing implementations when the standard was being
defined. If most implementations ordered certain sequences the same way,
the standard authors cast that in stone by defining a sequence point; for
instance, evaluating all the arguments to a function before calling the
function. But if implementations differed, and there was no compelling
reason to require a particular order, they didn't; for instance, the order
of evaluation of function arguments or subexpressions of an expression.
--
Barry Margolin
BBN PlaNET Corporation, Cambridge, MA
bar...@bbnplanet.com
Phone (617) 873-3126 - Fax (617) 873-6351
Jerry Coffin
>In article <49nbij$e...@rdsunx.crd.ge.com>, vo...@bart.crd.ge.com (Christopher
>R. Volpe) writes:
><snip>
>|> Perhaps you meant "i = (f(), i+i)". This is still not undefined. The
>|> expression on the right is used to compute the new value of i in the top
>level
>|> assignment. And the subexpression on the right has a sequence pint between
>the
>|> evaluatin of "i=1" in f(), and the evaluation of "i+i". I see nothing
>|> technically wrong with this according to the rules of the STandard.
>Is `i + (f(),i+i)' well defined? Or to focus in, is `i + (f(),1)' well
>defined? i.e. is the sequence point before and after the evaluation of i=1 by
>calling f _between_ the evaluation of the i in i + and the modification? I
>thought this issue was not resolved last time it was discussed here.
>Is this any different from i = (f(),1)?
No, and I'm quite certain that all of these are undefined -- Chris seems
to be assuming that since the value of the right side is needed for the
assignment, that it must be evaluated first, which is to say that the
assignment operator would form a sequence point between evaluation of
the right side and the left side. However, the standard makes no such
guarantee that I can find. In this case, a little flow control will
allow the compiler the pre-compute the value of the right side, assign
that to i, then evaluate the call to `f ' in the right side for its side
effect, and not violate any rules I can find.
Tanmoy Bhattacharya
R. Volpe) writes:
<snip>
|> expression on the right is used to compute the new value of i in the top
level
|> assignment. And the subexpression on the right has a sequence pint between
the
|> evaluatin of "i=1" in f(), and the evaluation of "i+i". I see nothing
|> technically wrong with this according to the rules of the STandard.
Is `i + (f(),i+i)' well defined? Or to focus in, is `i + (f(),1)' well
defined? i.e. is the sequence point before and after the evaluation of i=1 by
calling f _between_ the evaluation of the i in i + and the modification? I
thought this issue was not resolved last time it was discussed here.
Is this any different from i = (f(),1)?
Cheers
Tanmoy
--
tan...@qcd.lanl.gov(128.165.23.46) DECNET: BETA::"tan...@lanl.gov"(1.218=1242)
Tanmoy Bhattacharya O:T-8(MS B285)LANL,NM87545 H:#9,3000,Trinity Drive,NM87544
Others see <gopher://yaleinfo.yale.edu:7700/00/Internet-People/internet-mail>,
<http://alpha.acast.nova.edu/cgi-bin/inmgq.pl>or<ftp://csd4.csd.uwm.edu/pub/
internetwork-mail-guide>. -- <http://nqcd.lanl.gov/people/tanmoy/tanmoy.html>
fax: 1 (505) 665 3003 voice: 1 (505) 665 4733 [ Home: 1 (505) 662 5596 ]
Paul Eggert
says `f()+f()' has undefined behavior when f has side effects
(e.g. if f is defined by `int f() { static int i; return i++; }').
Other people think the standard defines behavior for `f()+f()'.
Still other people think that that this example has undefined behavior,
but other, similar examples have defined behavior.
I don't know if the ISO C committee has issued an official ruling on this.
It is clearly an unnecessarily messy area in the C Standard.
As a practical matter, if the implementation does function inlining,
I wouldn't rely on the behavior being well-defined here.
Christopher R. Volpe
>tan...@qcd.lanl.gov (Tanmoy Bhattacharya) wrote:
>
>>In article <49nbij$e...@rdsunx.crd.ge.com>, vo...@bart.crd.ge.com (Christopher
>>R. Volpe) writes:
>><snip>
>>|> expression on the right is used to compute the new value of i in the top
>>level
>>|> assignment. And the subexpression on the right has a sequence pint between
>>the
>>|> evaluatin of "i=1" in f(), and the evaluation of "i+i". I see nothing
>>|> technically wrong with this according to the rules of the STandard.
>
It must yield one of two values, in an unspecified way, depending on which of
the two operands of the top-level "+" is evaluated first. (I've lost some
context here, but I assume f() modifies i.) I wouldn't call this
"well-defined", but it does not invoke undefined behavior either.
>>Or to focus in, is `i + (f(),1)' well
>>defined?
Same answer. It depends on order of evaluation, so it yields an unspecified
result, but it does not violate any shall-rules in any semantics sections.
>>i.e. is the sequence point before and after the evaluation of i=1 by
>>calling f _between_ the evaluation of the i in i + and the modification? I
Huh? I think the definition of "sequence point" requires the modification to
occur between those two sequence points. I'm not sure what you're asking here.
It seems pretty clear to me that the evaluation of "i" in "i + ..." occurrs
outside the sequence points that delimit the modification of i. Whether it
comes before or after is unspecified, but it does not occur within.
>>thought this issue was not resolved last time it was discussed here.
>
>>Is this any different from i = (f(),1)?
>
>No,
I'm going to assume that "i" starts off with the value 0, and f() increments i.
If I am not recalling the context correctly, let me know. Anyway, that above
expression looks completely well defined to me. At least, the modification in
f() is completely isolated by sequence points, so the worst it can be is
"unspecified".
>and I'm quite certain that all of these are undefined
I can see the possibility of an argument for the unspecified case, but where
is the argument for the undefined case?
-- Chris seems
>to be assuming that since the value of the right side is needed for the
>assignment, that it must be evaluated first, which is to say that the
>assignment operator would form a sequence point between evaluation of
>the right side and the left side.
No. I am well aware that the assignment operator forces no such sequence
point. Otherwise "i = i++" would be well defined, and I do not claim that.
Requiring the right hand side to be evaluated *before* the assignment is made
does not imply that a sequence point separate the two. In this case, we don't
need a sequence point from the assignment, because we have one bounding the
function call.
What is the purpose of the sentence, "Furthermore, the prior value shall be
accessed only to determine the value to be stored"? Why not simply state, "the
object shall not be modified and have the prior value accessed between the
same pair of sequence points"? The reason is to distinguish expressions like
"i = i+1" from expressions like "++i + i", the assumption here being that in
the former case, the *evaluation* of the RHS must occur strictly before the
modificiation to i on the LHS. Note that this does not imply that *side
effects* of the RHS must take place before the modification of i on the LHS,
because that would require a sequence point. Rather, only the evaluation of
the RHS must occur before the modification. This is just a formal way of
stating the intuitively obvious: that you must know what you're going to
write before you write it.
But now we have another complication thrown in. The evaluation of the "1" on
the right side of the comma operator in the expression in question must occur
before the top-level i modification, based on the above principle. But we also
have, as a result of the semantics of the comma operator, that the evaluation
of f() must occur STRICTLY PRIOR to the evaluation of the "1", and hence the
top level modification of "i". And either the sequence point inherent in the
function call, or the sequence point associated with the comma operator, is
enough to guarantee that the modification of i within f() must be complete
before the top level modification of i.
So no, I do not assume a sequence point inherent in the "=" operator. But the
principle of "knowing what to write before you write it" implied by the
"Furthermore,..." clause in 3.3, combined with the semantics of the comma
operator and the sequence points associated with function calls make this
expression well defined.
> However, the standard makes no such
>guarantee that I can find. In this case, a little flow control will
>allow the compiler the pre-compute the value of the right side, assign
>that to i, then evaluate the call to `f ' in the right side for its side
>effect, and not violate any rules I can find.
It appears to violate the semantics of the comma operator to me. To
"precompute the value of the right side", one must evaluate the right operand
of the comma operator, because that's where the value of the right side comes
from. And if you evaluate the call to f() after that, you've just broken the
semantics of the comma operator.
Nick Maclaren
Paul Eggert <egg...@twinsun.com> wrote:
>This point has been debated before. Some people think the standard
>says `f()+f()' has undefined behavior when f has side effects
>(e.g. if f is defined by `int f() { static int i; return i++; }').
>Other people think the standard defines behavior for `f()+f()'.
>Still other people think that that this example has undefined behavior,
>but other, similar examples have defined behavior.
The example that really baffles me is '(++i,j)+(j,++i)', because the
standard assumes an ordering of operations without defining what that
ordering is. If anyone thinks that this example is easy, write out
the parse tree and consider its consequences!
>I don't know if the ISO C committee has issued an official ruling on this.
>It is clearly an unnecessarily messy area in the C Standard.
This is a little unfair, in that X3J11 had a horrible task trying to
specify anything workable. Admittedly, they might have done better
than they did, but whatever is specified is bound to be either messy
or a severe restriction on existing practice.
>As a practical matter, if the implementation does function inlining,
>I wouldn't rely on the behavior being well-defined here.
Absolutely! Nor would I rely on it if the compiler supports any
automatic parallelisation.
Nick Maclaren,
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: nm...@cam.ac.uk
Tel.: +44 1223 334761 Fax: +44 1223 334679
Kevin Quitt
> i = f(), i+i;
>
>I believe the result is still technically undefined. The assignment
>operator doesn't force a sequence point, so in theory the compiler could
>treat evaluate the i on the left side before or after the entire right
>side.
The assignment is not a sequence point, but the comma is, so the assignment
must be made before i+1 is evaluated.
--
#include <standard.disclaimer> http://emoryi.jpl.nasa.gov/
_
Kevin D Quitt USA 91351-4454 96.37% of all statistics are made up
Mark Brader
> says `f()+f()' has undefined behavior when f has side effects
> (e.g. if f is defined by `int f() { static int i; return i++; }').
> Other people think the standard defines behavior for `f()+f()'.
On the contrary, the problem is that some people (i.e. the first group
above) insist on reading the completly un-messy sentence (in 6.6/3.6,
semantics):
# Except as indicated, statements are executed in sequence.
as if there was something in the standard$ that indicated that statements
could be interleaved.
> I don't know if the ISO C committee has issued an official ruling on this.
We can expect one soon, as part of the package of Record of Response 2
and Technical Corrigendum 2. Balloting on that should have been finished
a while ago now, but I haven't heard the results of it.
> As a practical matter, if the implementation does function inlining,
> I wouldn't rely on the behavior being well-defined here.
As a practical matter, any implementer that *I* caught not producing
the behavior I expect here could expect a bug report from me.
$ - Okay, the "as if" rule allows it, but only if you can't tell it's
happening, so that doesn't affect the "debate".
--
Mark Brader, m...@sq.com | "Ah, determinism (likewise, forgetfulness) reigns."
SoftQuad Inc., Toronto | --Steve Summit
My text in this article is in the public domain.
Mark Brader
> The example that really baffles me is '(++i,j)+(j,++i)', because the
> standard assumes an ordering of operations without defining what that
Right; the ordering is unspecified -- except that the left-hand ++i must
be evaluated before the left-hand j with a sequence point intervening,
and the right-hand j must be evaluated before the right-hand ++i with
a sequence point intervening. Therefore the sequence
1. right-hand j
2. left-hand ++i
3. right-hand ++i
4. left-hand j
is possible. (The ++ can be broken up into subsidiary operations, but it
isn't necessary for this analysis.) The comma operators force sequence
points between steps 1 and 3, and between 2 and 4, but neither of these
sequence points has to be between 2 and 3. Therefore i may be modified
twice without a sequence point intervening - whether this happens or not
is unspecified, since it depends on the evaluation order. Therefore it
is unspecified whether or not the expression causes undefined behavior.
Therefore the expression does cause undefined behavior.$
See? It's not so hard.
$ - This follows from the rule about implicitly undefined behavior that is
bundled in with the definition if "undefined behavior" in 3.16/1.6.
--
Mark Brader, m...@sq.com "Logic is logic. That's all I say."
SoftQuad Inc., Toronto -- Oliver Wendell Holmes
Mark Brader
> > > Is `i + (f(),i+i)' well defined?
Chris Volpe (vo...@ausable.crd.ge.com) writes:
> It must yield one of two values, in an unspecified way, depending on which
> of the two operands of the top-level "+" is evaluated first. (I've lost
> some context here, but I assume f() modifies i.) I wouldn't call this
> "well-defined", but it does not invoke undefined behavior either.
I agree with everything here and, I believe, in the rest of Chris's long
article, *except* the implication that one of the two operands of the
top-level + must be evaluated first. I don't think Chris really meant to
make that implication. The evaluation sequence
f()
left-hand i
right-hand i
right-hand +
top-level +
is one of the possibilities, and the left-hand operand of the top-level +
is evaluated within the time that the right-hand operand is being done.
--
Mark Brader \ Peter Neumann on updating software to work after 1999:
m...@sq.com \ This problem gives new meaning to "going out on a date"
SoftQuad Inc., Toronto \ (which many systems will do on 1/1/00).
Nick Maclaren
|> Nick Maclaren (nm...@cus.cam.ac.uk) writes:
|> > The example that really baffles me is '(++i,j)+(j,++i)', because the
|> > standard assumes an ordering of operations without defining what that
|> > ordering is. ...
|>
|> Right; the ordering is unspecified -- except that the left-hand ++i must
|> be evaluated before the left-hand j with a sequence point intervening,
|> and the right-hand j must be evaluated before the right-hand ++i with
|> a sequence point intervening. Therefore the sequence
|>
|> 1. right-hand j
|> 2. left-hand ++i
|> 3. right-hand ++i
|> 4. left-hand j
|>
|> is possible. (The ++ can be broken up into subsidiary operations, but it
|> isn't necessary for this analysis.) The comma operators force sequence
|> points between steps 1 and 3, and between 2 and 4, but neither of these
|> sequence points has to be between 2 and 3. Therefore i may be modified
|> twice without a sequence point intervening - whether this happens or not
|> is unspecified, since it depends on the evaluation order. Therefore it
|> is unspecified whether or not the expression causes undefined behavior.
|> Therefore the expression does cause undefined behavior.$
|>
|> See? It's not so hard.
Please, Oh Great Guru, now explain what is meant by the sentence in the
standard which says "At sequence points, volatile objects are stable in
the sense that previous evaluations are complete and subsequent
evaluations have not yet occurred.", if we assume that 'i' and 'j' are
volatile.
E.g., does the concept of a 'previous sequence point' imply a partial
or complete ordering? And is such an ordering decidable from the C code
alone, or is it implementation-specific? And is it decidable during
translation, or can it be data-dependent?
Actually, I am pretty sure that I know how you interpret the standard,
but I am also sure that (a) it doesn't confirm your interpretation
unambiguously and (b) many or most implementors will assume variant
readings.
Lawrence Kirby
nm...@cus.cam.ac.uk "Nick Maclaren" writes:
>In article <49qtc0$7...@light.twinsun.com>,
>Paul Eggert <egg...@twinsun.com> wrote:
>>This point has been debated before. Some people think the standard
>>says `f()+f()' has undefined behavior when f has side effects
>>(e.g. if f is defined by `int f() { static int i; return i++; }').
>>Other people think the standard defines behavior for `f()+f()'.
>>Still other people think that that this example has undefined behavior,
>>but other, similar examples have defined behavior.
>
>The example that really baffles me is '(++i,j)+(j,++i)', because the
-a- b c -d-
>standard assumes an ordering of operations without defining what that
>ordering is. If anyone thinks that this example is easy, write out
>the parse tree and consider its consequences!
This expression defines a partial ordering. Using the subexpression labels I
have shown expression, there is a sequence point between expressions a and
b and also between c and d. There is no sequence point between a and b
and c and d since + does not define any sequence point. In particular the
following order of evaluation is permitted with . indicating a sequence point:
c . d a . b
Therefore i is modified twice between sequence points and the expression
has undefined behaviour. Looking at a simple parse tree:
.
. +
. / \
. / . \
. / . \
. / . \
. / . \
. , . ,
. / \ . / \
. / \ . / . \
a b . c . d
The dots indicate the 'scope' of a side effect in expression a. You'll see
that the sequence point in the comma only protects expression b from it.
Then you just have to work out how to deal with something like:
(j,++i,j) + (j,++i,j)
The rule seems to be "if you can find any permissible ordering (subject
to the partial orderings defined by sequence points) which would result in
undefined behaviour according to the standard then the expression has
undefined behaviour". It may be possible to derive that in the
general case from the parse tree (at least where the objects that side
effects act on can be identified at compile time) but the rules are probably
not trivial.
I would say in your expression the following orderings are possible:
a . b c . d
c . d a . b
a c . b d
a c . d b
c a . b d
c a . d b
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------
Christopher R. Volpe
[snip]
|> I agree with everything here and, I believe, in the rest of Chris's long
|> article, *except* the implication that one of the two operands of the
|> top-level + must be evaluated first. I don't think Chris really meant to
|> make that implication. The evaluation sequence
|>
|> f()
|> left-hand i
|> right-hand i
|> right-hand +
|> top-level +
|>
|> is one of the possibilities, and the left-hand operand of the top-level +
|> is evaluated within the time that the right-hand operand is being done.
Agreed. What I meant was that it is unspecified whether the left hand i is
evaluated before or after f() is called.
|>
|>My question, which Chris was responding to, was whether the the i that
|>is the left operand of the top-level +, henceforth called the
|>top-level i, can be evaluated interleaved with the evaluation of f()
|>(Remember, f() contains a i=1). If it can, then there is a possible
|>sequence of evaluation where i is both modified (in f) and accessed
|>(top-level i) without intervening sequence points.
If that is the case, I'm switching back to Pascal. (0.1 :-)) I want to look at
a function definition and be able to say, "Ok, here's a semicolon, and there's
the next semicolon, and the only thing that's going to happen between these
two is what's *written* between these two" (as far as the abstract machine is
concerned, since obviously I don't give a hoot about what gets interleaved
where for optimization purposes, as long as the semantics are intact.)
|>
|>I do not have an opinion: how could I? As an ordinary user of the
|>language, all I can pray for is that the committee does not decide that
|>even this interleaving is prohibited by the panacea of `statements are
|>executed in sequence' :-(
I agree that "statements are executed in sequence" has nothing to do with
this.
|>
|>The issue of `f()+f()' is different: there one is talking of two
|>statements from two functions. Here we are talking about part of an
|>expression in the caller interleaving with evaluation of a statement
|>in f. In fact in `f()+f();', though the two operands of the + can be
|>interleaved, wasn't the informed opinion last time that _none_ of the
|>statements of one f can be evaluated before _any_ of the statements of
|>the other f, whatever effect that may have on optimization, though
|>which f is called first is indeterminate (Am I misremembering?). All
I hope that was the consensus.
|>this to satisfy the _unsatisfiable_ edict of `statements are evaluated
|>in sequence': after all `f()+f();' is a statement --- is it done
|>before or after the statements comprising f?
It's not unsatisfiable, because the edict includes the phrase "except where
otherwise specified", and function calls are one of those exceptions.
Nick Maclaren
|> In article <TANMOY.95...@qcd.lanl.gov>, tan...@qcd.lanl.gov (Tanmoy Bhattacharya) writes:
|> |>
|> |>My question, which Chris was responding to, was whether the the i that
|> |>is the left operand of the top-level +, henceforth called the
|> |>top-level i, can be evaluated interleaved with the evaluation of f()
|> |>(Remember, f() contains a i=1). If it can, then there is a possible
|> |>sequence of evaluation where i is both modified (in f) and accessed
|> |>(top-level i) without intervening sequence points.
|>
|> If that is the case, I'm switching back to Pascal. (0.1 :-)) I want to look at
|> a function definition and be able to say, "Ok, here's a semicolon, and there's
|> the next semicolon, and the only thing that's going to happen between these
|> two is what's *written* between these two" (as far as the abstract machine is
|> concerned, since obviously I don't give a hoot about what gets interleaved
|> where for optimization purposes, as long as the semantics are intact.)
I recommend switching back to Pascal, if that is powerful enough for
your purposes :-(
Not merely does the standard allow strange things to happen between
semicolons, but I can witness that a very high proportion of compilers
actually produce such code. On the other hand, many of the really
ghastly examples that I have seen are associated with signal-handling,
which is something you can't do at all in standard Pascal (or Fortran,
for that matter).
In extreme cases (like the Cray YMP), not merely do I have to make an
unreasonable proportion of my local variables static AND volatile, but
I have to compile the most sensitive parts of my code without any
optimisation at all. That particular example does not involve signal
handling and shows that, even if the standard mandates a particular
instruction ordering, it is unsafe to rely on it.
Tanmoy Bhattacharya
R. Volpe) writes:
<snip>
|> |>this to satisfy the _unsatisfiable_ edict of `statements are evaluated
|> |>in sequence': after all `f()+f();' is a statement --- is it done
|> |>before or after the statements comprising f?
|>
|> It's not unsatisfiable, because the edict includes the phrase "except where
|> otherwise specified", and function calls are one of those exceptions.
And 6.3 `the order of evaluation of subexpressions and ... are both
unspecified' (i.e. the clause which allowed interleaved expressions in the
first place) does not count as `except where otherwise specified'? If the
sequence point on both sides of i++ still leaves i + (a,i++,b) undefined; why
should i + f() where f() is a; i++; b; be any different?
Or rather, not why should it be different: it can be different by fiat. But,
I do not see even the genesis of the claim that the standard currently
specifies it clearly.
Christopher R. Volpe
|>I recommend switching back to Pascal, if that is powerful enough for
|>your purposes :-(
It ain't, and I'm not yet convinced I need to.
|>
|>Not merely does the standard allow strange things to happen between
|>semicolons,
I'm not talking about signals, in case that's what you had in mind.
|> but I can witness that a very high proportion of compilers
|>actually produce such code. On the other hand, many of the really
|>ghastly examples that I have seen are associated with signal-handling,
|>which is something you can't do at all in standard Pascal (or Fortran,
|>for that matter).
Can you give me an example of the kind of code that compilers generate that
indicates that something funny is going on between sequence points?
|>
|>In extreme cases (like the Cray YMP), not merely do I have to make an
|>unreasonable proportion of my local variables static AND volatile, but
|>I have to compile the most sensitive parts of my code without any
|>optimisation at all. That particular example does not involve signal
|>handling and shows that, even if the standard mandates a particular
|>instruction ordering, it is unsafe to rely on it.
If a particular buggy compiler refuses to accept identifiers with the prefix
"_xyxy", does that make it unsave to use such identifiers in general?
Christopher R. Volpe
|>In article <4a6r9u$h...@rdsunx.crd.ge.com>, vo...@bart.crd.ge.com (Christopher
|>R. Volpe) writes:
|><snip>
|>|> |>this to satisfy the _unsatisfiable_ edict of `statements are evaluated
|>|> |>in sequence': after all `f()+f();' is a statement --- is it done
|>|> |>before or after the statements comprising f?
|>|>
|>|> It's not unsatisfiable, because the edict includes the phrase "except where
|>|> otherwise specified", and function calls are one of those exceptions.
|>
|>And 6.3 `the order of evaluation of subexpressions and ... are both
|>unspecified' (i.e. the clause which allowed interleaved expressions in the
|>first place) does not count as `except where otherwise specified'?
In my opinion, no. What does the order of evaluation of subexpressions have to
do with statement sequencing? (Except in the case of function calls, which I
already mentioned.)
|> If the
|>sequence point on both sides of i++ still leaves i + (a,i++,b) undefined; why
|>should i + f() where f() is a; i++; b; be any different?
Because the commas in "(a,i++,b)" do not delimit statements.
|>
|>Or rather, not why should it be different: it can be different by fiat. But,
|>I do not see even the genesis of the claim that the standard currently
|>specifies it clearly.
I admit that it's not so cut and dry. There is definitely room for argument
here. But in my opinion, Once control is transferred to the function, leaving
the function to go compute something else in the calling expression
constitutes a break in the statement sequence.
Paul Eggert
> What does the order of evaluation of subexpressions have to
> do with statement sequencing?
The two issues are closely related when
the implementation must execute statements to evaluate the subexpressions.
> There is definitely room for argument here.
Agreed. But that's why we have standards: to settle such arguments.
Unfortunately, the C Standard falls short in questions involving order
of evaluation. Other language standards (e.g. Ada, Algol, Fortran, PL/I)
answer these questions satisfactorily, but the C standard has a
unusual method of formalizing order-of-evaluation issues,
and in practice this method hasn't worked very well.
Nick Maclaren
Christopher R. Volpe <vo...@ausable.crd.ge.com> wrote:
>In article <4a6sjr$t...@lyra.csx.cam.ac.uk>, nm...@cus.cam.ac.uk (Nick Maclaren) writes:
>|> but I can witness that a very high proportion of compilers
>|>actually produce such code. On the other hand, many of the really
>|>ghastly examples that I have seen are associated with signal-handling,
>|>which is something you can't do at all in standard Pascal (or Fortran,
>|>for that matter).
>|>
>Can you give me an example of the kind of code that compilers generate that
>indicates that something funny is going on between sequence points?
Not easily. What they do is to move assignments across sequence points,
in cases where only signal handlers or debuggers can detect the move,
and assume that nobody will notice! Sometimes they make incorrect
moves, and sometimes don't update locations before function calls. It
all depends.
>|>In extreme cases (like the Cray YMP), not merely do I have to make an
>|>unreasonable proportion of my local variables static AND volatile, but
>|>I have to compile the most sensitive parts of my code without any
>|>optimisation at all. That particular example does not involve signal
>|>handling and shows that, even if the standard mandates a particular
>|>instruction ordering, it is unsafe to rely on it.
>
>If a particular buggy compiler refuses to accept identifiers with the prefix
>"_xyxy", does that make it unsave to use such identifiers in general?
Yes and no. It does, if at least one compiler handles them incorrectly
and you have reason to believe that others will do the same. I gave
the Cray YMP as an example - it is NOT the only compiler that has
produced demonstrably wrong code from a correct program of mine.
Mark Brader
Call it Expression A.
> > > because the standard assumes an ordering of operations without
> > > defining what that ordering is. ...
> > Right; the ordering is unspecified -- except that the left-hand ++i must
> > be evaluated before the left-hand j with a sequence point intervening,
> > and the right-hand j must be evaluated before the right-hand ++i with
> > a sequence point intervening. Therefore the sequence
> > 1. right-hand j
> > 2. left-hand ++i
> > 3. right-hand ++i
> > 4. left-hand j
> > is possible. ... Therefore the expression [causes] undefined behavior.
>
> Please, Oh Great Guru, now explain what is meant by the sentence in the
> standard which says "At sequence points, volatile objects are stable in
> the sense that previous evaluations are complete and subsequent
> evaluations have not yet occurred.",
The Great Guru says that this sentence is self-explanatory. And so do I. :-)
> if we assume that 'i' and 'j' are volatile.
If you're talking specifically about Expression A, the sentence does not
apply to it, because the expression causes undefined behavior.
> E.g., does the concept of a 'previous sequence point' imply a partial
> or complete ordering?
Time is linearly ordered, therefore a complete ordering of sequence
points exists. (It may be possible for two sequence points to occur
simultaneously in code such as Expression A, but no program could detect
this, so it doesn't matter.)
> And is such an ordering decidable from the C code alone,
Not in the presence of code such as Expression A. The relative ordering
of the sequence points from the comma operators depends on aspects of the
evaluation order which are explicitly unspecified.
> or is it implementation-specific? And is it decidable during
> translation, or can it be data-dependent?
When it is unspecified, it could be completely random. To drop into the
practical for a moment, it could depend on which of several CPUs on a
machine happened to be available. Of course, often the order of sequence
points is fully specified by the standard; this is the case with code like
a++;b++;c++;d++; or (i>.9)?--i:--j||--k;;; it just isn't *always* true.
--
Mark Brader "[This computation] assumed that everything
m...@sq.com would work, a happy state of affairs found
SoftQuad Inc., Toronto only in fiction." -- Tom Clancy
Mark Brader
> Which allows for interleaving! [Given the expression (++i,j)+(j,++i)]
> (++i,j) may be executed on one CPU, and (j,++i) on another. And yet, if
> (++i,j) had been f(i) and (j,++i) had been g(j), the compiler was not
> free to calculate f(i) on one CPU while it calculated g(j) on the other.
Exactly.
--
Mark Brader | "Just because the standard provides a cliff in
m...@sq.com | front of you, you are not necessarily required
SoftQuad Inc., Toronto | to jump off it." -- Norman Diamond
Tanmoy Bhattacharya
|> > > > The example that really baffles me is '(++i,j)+(j,++i)',
|> > E.g., does the concept of a 'previous sequence point' imply a partial
|> > or complete ordering?
|> > And is such an ordering decidable from the C code alone,
|> > or is it implementation-specific? And is it decidable during
|> > translation, or can it be data-dependent?
|>
|> When it is unspecified, it could be completely random. To drop into the
|> practical for a moment, it could depend on which of several CPUs on a
|> machine happened to be available. Of course, often the order of sequence
|> points is fully specified by the standard; this is the case with code like
|> a++;b++;c++;d++; or (i>.9)?--i:--j||--k;;; it just isn't *always* true.
Which allows for interleaving! (++i,j) may be executed on one CPU, and
(j,++i) on another. And yet, if (++i,j) had been f(i) and (j,++i) had been
g(j), the compiler was not free to calculate f(i) on one CPU while it
calculated g(j) on the other.
`Except as otherwise specified' statements are executed in sequence. And,
yet, the `unspecified ordering' of operands is not `otherwise' specified.
Is the otherwise specified specifically meant to exclude the otherwise
unspecified? :-)
Nick Maclaren
|> > > > The example that really baffles me is '(++i,j)+(j,++i)',
|>
|>
|> > Please, Oh Great Guru, now explain what is meant by the sentence in the
|> > standard which says "At sequence points, volatile objects are stable in
|> > the sense that previous evaluations are complete and subsequent
|> > evaluations have not yet occurred.",
|>
|> The Great Guru says that this sentence is self-explanatory. And so do I. :-)
I think that we have forgotten the title of this newsgroup. We are not
talking primarily about what you can assume in portable programs, nor
about actual implementations, but about what the standard says. I have
failed to find any definition of 'previous' or 'subsequent' in the
standard - can you give me a reference?
In particular, WHERE does it say that those terms refer to the chronology
of execution and not the textual order of the input program?
|> > And is such an ordering decidable from the C code alone,
|>
|> Not in the presence of code such as Expression A. The relative ordering
|> of the sequence points from the comma operators depends on aspects of the
|> evaluation order which are explicitly unspecified.
|>
|> > or is it implementation-specific? And is it decidable during
|> > translation, or can it be data-dependent?
|>
|> When it is unspecified, it could be completely random. To drop into the
|> practical for a moment, it could depend on which of several CPUs on a
|> machine happened to be available. Of course, often the order of sequence
|> points is fully specified by the standard; this is the case with code like
|> a++;b++;c++;d++; or (i>.9)?--i:--j||--k;;; it just isn't *always* true.
This is all true, but more-or-less irrelevant. You keep explaining some
practical constraints, but never refer back to the standard to justify
your claim that this is what it means. I quite agree that your position
is sensible, self-consistent and so on. But where is the evidence that
it is what the standard means?
Look, it is precisely BECAUSE I know about that problem that I posted
the example that I did. I was dealing with language standards problems
on non-deterministic computers 20 years ago. You have chosen the
interpretation that gives most latitude to the compiler's implementor,
but there are other possible ones. When a compiler vendor asks me
whether your interpretation is permitted by the standard, I currently
have to say "I think so, but cannot be certain."
Thad Smith
nm...@cus.cam.ac.uk (Nick Maclaren) wrote:
>In article <1995Dec9.0...@sq.com>, m...@sq.com (Mark Brader) writes:
>|> > > > The example that really baffles me is '(++i,j)+(j,++i)',
>|>
>|> > standard which says "At sequence points, volatile objects are stable in
>|> > the sense that previous evaluations are complete and subsequent
>|> > evaluations have not yet occurred.",
>I have
>failed to find any definition of 'previous' or 'subsequent' in the
>standard - can you give me a reference?
>
>In particular, WHERE does it say that those terms refer to the chronology
>of execution and not the textual order of the input program?
Without definition, these words have the normal English
meaning. Since the sentence references sequence points and completion
of evaluations, which are only dynamic events, the meaning is clearly
chronology of execution, not textual order.
Let's say we have (A,B) + (C,D), where each of the letters is an
expression involving volatile objects. We know that there are
different possible orderings of execution and that the expression
contains two sequence points. Because the C execution model is
sequential, we know that there IS an (unspecified) ordering and that
at each sequence point, whenever it occurs, all volatile objects are
stable. Thus if there are multiple volatile side effects of C, they
may occur on either side of the AB sequence point, but may not
straddle it.
Thad
Mark Brader
> talking primarily about what you can assume in portable programs, nor
> about actual implementations, but about what the standard says.
Right. The claimed existence of implementations that allow statements in
different functions to be improperly executed out of sequence is irrelevant.
> I have failed to find any definition of 'previous' or 'subsequent' in the
> standard ... In particular, WHERE does it say that those terms refer to
> the chronology of execution and not the textual order of the input program?
Oh! That's from 5.1.2.3/2.1.2.3. Sequence points are defined as
"certain specified POINTS IN THE EXECUTION SEQUENCE". My emphasis.
> I quite agree that your position is sensible, self-consistent and so on.
> But where is the evidence that it is what the standard means?
I thought this was well known, but maybe it didn't come up in this thread.
Section 6.3/3.3 states explicitly that "Except as indicated by the syntax
or otherwise specified later ... the order of evaluation of subexpressions
and the order in which side effects take place are both unspecified."
Section 6.6/3.6 states explicitly that "Except as indicated, statements are
executed in sequence", thus implying the special status of function call
subexpressions.
That's all it takes.
--
Mark Brader | Well, unfortunately, that is impossible, or very difficult, or
m...@sq.com | highly inadvisable, or would require legislation--one of those.
SoftQuad Inc., Toronto -- Sir Humphrey ("Yes Minister", Lynn & Jay)
David Adrien Tanguay
>Section 6.6/3.6 states explicitly that "Except as indicated, statements are
>executed in sequence", thus implying the special status of function call
>subexpressions.
That's a leap of faith, not an implication. However, ANSI 3.6.6.4 "The return
statement" says "A return statement terminates execution of the current
function and RETURNS CONTROL to its caller" (emphasis mine). This implies that
control previous left the caller. When? Add 6.6/3.6, wave you hands
vigourously, and I think they say a function can't be executed in parallel
with its calling statement.
Aside from maybe 3.6.6.4, is there anywhere in the standard that says the
execution model is single-threaded?
--
David Tanguay d...@Thinkage.on.ca http://www.thinkage.on.ca/~dat/
Thinkage, Ltd. Kitchener, Ontario, Canada [43.24N 80.29W]