DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 11 of 11

Thread: Order of Evaluation - C++ Ref Manual ambiguity

  1. #1
    Join Date
    Jun 2007
    Posts
    4

    Order of Evaluation - C++ Ref Manual ambiguity

    Hello,

    For a long time (years) I could not resolve the meaning of precedence of operators and the rules about order of evaluation. It seems there is some ambiguity in the wordings in the C++ Reference Manual in this :-
    The order of evaluation of subexpressions is determined by the precedence and grouping of operators.
    What I know :-
    1) order of evaluation of operands of individual operators undefined except some as && || ?: comma.

    My question is whether it is not best to just reword it to something
    without any reference to order of evaluation. It was explained to me precedence is only about grouping, rules about binding operands to operators and never determine order of evaluation of expressions.

    In fact all over the internet I was made to believe precedence determines order of evaluation in examples similar to these :-
    1) a * b + c is ordered (a * b), + c
    2) to force an order, use parentheses
    a * (b + c) is ordered (b + c), a * ?
    One site even placed the parentheses at the top of the precedence
    table.

    Undefined behavior -
    a = 1;
    x = (b = 1) * (a = 10) + a;//20
    blindly assuming precedence as ordering there is no undefined semantic as (a = 10) is done before ? + a

    x = ((b = 1) * (a = 10)) + a
    has the form x = op1 + op2 and order of operands evaluation is undefined and so compilers can go right to left and take the value of op2(a) first and x = 11.

    Second question:-
    Is there any situation where order of evaluation is determined by
    precedence of operators.

    Rasjid

  2. #2
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    Here is a C++ order of precedence table:

    http://www.cppreference.com/operator_precedence.html

    You can see how low the precedence for assignment is (just before the comma/ "sequential evaluation operator").

    I don't agree with your statement that compilers execute code "right to left". Compilers read code the same way you read code (at least where you read from left to right) and perform arithmetic operations: this is the order of execution of operations of equal precedence [you can always create your own language which executes right to left]. Perhaps you are thinking about evaluating the RHS of an assignment before you execute the assignment? [Being the result of the almost bottom priority of the assignment operator.]

    The () "grouping operator" has the second highest priority - only after the scoping operator. Therefore, it will (for all intents and purposes) always create a micro-environment which will impose an order of execution/evaluation of the parts of your statement. Everything inside your parens will be executed before the statement outside of the parens will be considered. I therefore do not share your concern about assignment of values - because your use of the grouping operator has imposed an order of execution. I would not trust a compiler which would return 11 for your example statement: it is not following the order of precedence and could not be trusted to evaluate consistently and correctly.

    My response to your last question is that order of precedence always determines the order of evaluation. The program will not read the memory pointed to by/named "x" until it uses the value in the execution of the statement. If the execution of the statement has changed the content of the memory location pointed to by/named "x" before "x" is called by the code, then the value at x will be different than it was before the statement began to execute. [Think about how your "high level" language statement is being compiled into instructions at a lower level language, and eventually the execution instructions at the CPU level. Your multi-operational statement is being translated into a series of single operation steps. The order of precedence tells you the order in which the parts of your multi-operational statement will be executed by the CPU. The instruction for "retrieve the content of memory location NNNNNNNN" won't execute until the stuff that comes before it has been executed; the CPU will know if it has recently computed the value which would otherwise be stored at "x" and would retrieve that value from a register or local cache - that is part of the code optimization which the compiler will generate.]
    Last edited by nspils; 06-19-2007 at 08:34 AM.

  3. #3
    Join Date
    Dec 2003
    Posts
    3,366
    yes () is effectively the highest (scope is not really part of an expression, it simply clarifies which items you are using) so when in doubt just wrap it in the correct set of parentheses.

    Yes indeed there are situations where the operators determine the evaluation.
    x = a+b/c+d is very different from (a+b)/c+d is different from (a+b)/(c+d) (just as they are in a math book!).

    The thing is, you should not have multiple equal signs in a statement like that. Some things are ok, such as
    int a = 0, b=5;
    or
    a = b = (c+d);
    but
    x = (a = b*d) + (c = m/x); ....
    this is nonsense. First off, assignments can be tricky and will evaluate to a boolean if used carelessly in this fashion. Do not try to make statements of this type, break it down into straightforward assignments that both the compiler and the human reader can make sense of and do not leave yourself in a situation that you are unsure as to how the expression will be evaluated. If you do not KNOW how it will be evaluated, use parentheses and force it to be as you want it and simplify it so that it is easy to follow the logic.

  4. #4
    Join Date
    Nov 2003
    Posts
    4,118
    I suspect that this expression has undefined behavior:
    x = ((b = 1) * (a = 10)) + a;

    Precedence isn't the question here. Rather, it about sequence points. In this expression you have two sequence points in one expression which is considered undefined behavior.
    The same problem occurs here:
    a = ++a;
    So you have to pay attention not just to operators' precedence but also to the "abstract machine" rules and sequence points.
    Danny Kalev

  5. #5
    Join Date
    Jun 2007
    Posts
    4
    Hello,
    Thanks to all replies and I continue here.

    Code:
    if (exprA && ((v = (a * b)) > 0)){
    //ok
    }
    Most programmers should know that this is safe and it saves an assignment if exprA fails.

    I am from a chess programming forum and learned C on my own. In chess programming we need the fastest codes and will resort to any style as long as it is semantically correct. I had codes of this format:-
    Code:
    if (exprA && (v = u - ((u & -(u = 1)) << 1) )){
    //undefined behaviour
    ...
    }
    A poster pointed out to me that the above has undefined semantics and rejected reasons that (u = 1) will be evaluated first :-
    1) the parentheses forces it.
    2) unary (-) has the highest precedence.
    I think he knows C very well but it was not a forum to continue the discussion. He seemed(?) to have categorically mentioned that precedence has nothing to do with order of evaluation. I now do think that the codes above indeed has undefined behavior.

    Although the codes do as I wanted, undefined behavior is just not acceptable as it is bad to rely on a particular behavior of a compiler.

    Quote Originally Posted by Danny
    I suspect that this expression has undefined behavior:
    x = ((b = 1) * (a = 10)) + a;

    Precedence isn't the question here. Rather, it about sequence points. In this expression you have two sequence points in one expression which is considered undefined behavior.
    The same problem occurs here:
    a = ++a;
    So you have to pay attention not just to operators' precedence but also to the "abstract machine" rules and sequence points.
    I think x = ((b = 1) * (a = 10)) + a has no sequence point in it's evaluation.

    Sequence point is what I consider advanced but had just read a little from what I recently found from an article by an expert.
    1) Other than functions, operators have no sequence points except
    && || ?: comma.
    2) "full expression" has a sequence point after the evaluation.
    3) where no sequence point is involved, the order of evaluation of operands is undefined.

    a[i] = i++ has undefined behavior as there is no sequence point in the evaluation and thus order of evaluation of operand is undefined. Thus a[i] or i++ may be evaluated in different order giving different results. I believe (v = u - ((u & -(u = 1)) << 1)) also has undefined behavior. (u - 1) is not a full expression and therefore has no sequence point yet. The only sequence point is at the end of all evaluation of the line. Thus the operands
    u, ((u & -(u = 1)) << 1) of operator (-) has no defined order.
    Thus the left operand u may be the first evaluated(value of u taken and stored somewhere ... ) and it may be garbaged. Another way to analyse is simply that the order of op1 - op2 is undefined.

    Kernighan and Ritchie mentioned that in C, as in most languages, the order of evaluation of operands of operators is left undefined intentionally. The reason being some machine architecture may benefit from certain order of evaluation and thus should not be restraint.

    So how should I finally relate precedence of operators and parenthesis with order of evaluation.

    It is said that codes that rely on order of behavior is bad.
    Most often we only care that the evaluation is completed and not on their order as long as it is fastest.

    I think those who draft the C standard know their job but I still have a question :-
    If we reword the relevant part of the C manual as something like "... precedence and associativity of operators determines the grouping of operands to operators..." completely leaving out any references to order of evaluation, does it change C significantly

    Best Regards,
    Rasjid

  6. #6
    Join Date
    Nov 2003
    Posts
    4,118
    if (exprA && (v = u - ((u & -(u = 1)) << 1) ))
    has undefined behavior for the same reason I stated previously: there are two many modifications of u within a single sequence point. BTW, there's always a sequence point at the end of the evaluation of an expression. However, C and C++ require that each modification will be reflected as a single step, so that no more than a single access to an object shall take place between two sequence points.
    As for the performance excuse for using such obfuscated code, I really doubt that it improves performance. Without actually disassembling the optimized executable and comparing the differences (and timing them!), I wouldn't rush to use such dangerous, hard to bug and hard to maintain code constructs.
    Danny Kalev

  7. #7
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    This has been an enlightening discussion. Thanks, guys.

  8. #8
    Join Date
    Jun 2007
    Posts
    4
    I am no expert in sequence point. I think the C++ spec says if an object is modified more than once between 2 sequence points(generally within an expression), the result of the expression is undefined.
    if (exprA && (v = u - ((u & -(u = 1)) << 1) ))
    The above has a sequence point after exprA and the next sequence point is at the end of the expression. u is modified only once and is ok. The reason should be as pointed out to me at the other forum, that op1 - op2 has no defined order that op2 must be evaluated before op1(evaluating (u)).

    Code:
    __inline int xbBishopAttack(board_t * board, int x, u64 b, u64 blocks){
    	i64 u;
    	assert(x != toSq64(b));
    	return board->brd[x].bMap & b && 
    		!( (u & u - 1) - ((u & -(u = board->brd[x].bb | b)) << 1) 
    			& board->brd[x].bMap & blocks);
    }
    The above was the actual code involved, saving (u = board->brd[x].bb | b) if && fails in the first operand.
    It is true that actual testing is best to check efficiency gains.

    Best Regards,
    Rasjid

  9. #9
    Join Date
    Nov 2003
    Posts
    4,118
    I missed one crucial term here: it's undefined behavior if there are two or more side effects between two sequence points. a side effect in this context is the modification of an object or accessing a volatile object.
    Last edited by Danny; 06-20-2007 at 06:47 AM.
    Danny Kalev

  10. #10
    Join Date
    Jun 2007
    Posts
    4
    Hello,

    I was told the answer - that an object may be modified in between 2 sequence point at most once and if it is modified, the prior value may only be used to determine what new value is to be stored. In effect restricting to codes like:-
    a = b * (c = c + 1)); //ok
    but not :-
    a = c + (c = 1); //undefined
    i = i++; is undefined, i is modified twice.
    a = b * (c = c++)); //also undefined

    Best Regards,
    Rasjid.

  11. #11
    Join Date
    Dec 2003
    Posts
    3,366
    correct, however your working example is still ugly and should not appear in code without a very good reason ... it is hard to read and the rules for when you can and cannot do this type of thing are complex enough that it has a high potential of creating a bug (again, if careless you can accidentally evaluate the assignment as a boolean) or undesirable results (some compilers will accept the incorrect examples but provide odd results that will vary from compiler to compiler). So while its good to know these rules and there are rare occasions for exploiting them, in general its not the best coding style.

Similar Threads

  1. Select statment order by Criteria
    By Gabby in forum VB Classic
    Replies: 5
    Last Post: 08-19-2002, 08:32 AM
  2. Order by Rnd Help Needed For Embedded VB???
    By James in forum VB Classic
    Replies: 5
    Last Post: 04-26-2002, 01:42 PM
  3. Some tricky SQL
    By Dave in forum VB Classic
    Replies: 9
    Last Post: 09-02-2001, 12:43 PM
  4. Re: Sort problem in MS SQL Server 7.0
    By D. Patrick Hoerter in forum Database
    Replies: 1
    Last Post: 06-26-2000, 04:57 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center