Expression evaluation Order of evaluation For the abstract syntax tree + / \ / \ + 5 / \ / \ + + / \ / \ x 3 2 4 the equivalent expression is (x + 3) + (2 + 4) + 5 Correct way to evaluate this expression from the abstract syntax tree is to evaluate the tree bottom-up, left-to-right. But this constrains optimization that uses mathematical properties of operators such as commutativity and associativity. e.g., it may be preferable to evaluate of e1 + (e2 + e3) instead of (e1 + e2) + e3 (x+0) + (y + 3) + (z + 4) => x + y + z + 0 + 3 + 4 => x + y + z + 7 The compiler can evaluate 0+3+4 at compile time, so that at runtime, we have two fewer addition operations. Many languages leave order of evaluation unspecified. - even the order of evaluation of procedure parameters are not specified. It is a bad programming practice to use expressions where different orders of evaluation can lead to different results: e.g., /* Assume x = 5 */ (x++) + x gives value 11 when left-to-right evaluation is used, but gives value 10 when right-to-left evaluation is used. Note that it takes some amount of effort to understand that the value could be different, when different orders of evaluation are used. Order of evaluation matters when the evaluation of subexpressions has the side-effect of changing the values of certain variables (eg evaluation of x++ changes value of x). Using expressions with such side-effects is thus a bad idea in programming. NOTE: Side-effects make programs hard to understand, so they should be avoided as much as possible, i.e., expressions should not be used change values of variables. Left-to-right evaluation with short-circuit semantics is appropriate for boolean expressions. e1 && e2 => e2 is evaluated only if e1 evaluates to true e1 || e2 => e2 is evaluated only if e1 evaluates to false This is useful in expressions like if ((i < n) && a[i] != 0) With short-circuit code a[i] is never accessed if i >= n Another example: if ((p != NULL) && p->value > 0) But the disadvantage is that, in an expression like if ((a == b) || (c = d)) where the second expression has a statement (assignment), the value of c may or may not be the value of d depending on if a == b is true or not. Bottom-up No order specified among unrelated subexpressions. Short-circuit evaluation of boolean expressions. Delayed evaluation Delay evaluation of an expressions until its value is absolutely needed. This is generalization of short-circuit evaluation int f(int x,int y){ if(x==0) return 0; else return x*y; } Consider the call: f(0, 2*z) With strict evaluation, 2*z will be computed regardless of whether f uses its second parameter calue or not. With delayed evaluation, this is deferred until f actually uses its parameter values. In the case of the above function, you can see that the value of secon parameter is unused by f when the first paramter is 0, so in this case, 2*z will be never evaluated. In the case of functional languages, delayed evaluation works well, since the value of the expression does not change whether it is evaluated before the call or afterwards. In an imperative language with assignments, this is no longer the case. It is possible for some variables in the expression to be modified by the time delayed evaluation evaluates this expression, leading to results that are difficult to understand.