8/16/12

Curious look into code evaluation

If you have been programming for a while, you already should know about operator precedence. If you for some reason don't, now is a good time to read about it on from Wikipedia or the documentation of your language of choice.

Before proceeding, remember that this may contain some erroneous information, and if you notice any, please inform me so that article can be fixed.

Let's take a rather simple set of expressions:

int i = 5; 
i = ++i + ++i;

This seems rather simple, doesn't it? So did I think, but the results (which we'll see a bit late) left me thinking wtf was actually going on. If we look at the Wikipedia-article, we can see that unary operators such as prefix and suffix increment and decrement come before the addition and substraction, at least in C-family of languages. Now, what do you think the answer will be? Write your guess down somewhere, we'll take a small plunge in to the world of compilers soon.

So, you got your answer? Good. If you did a quick test with a short code of piece, shame on you. Now, let me guess what you got.

If you used Python or Ruby, you got 10.
If you used JS, Java or C#, you got 13.
If you used C, C++ or Perl, you got 14.

Wait, what? How does this even happen?




Let's start with compilers. In order for compiler to produce machine-readable code, it takes your statement and usually produces object code in the middle of compiling before finally making the code machine-readable. So,

int i = 5;

is a simple statement, and doesn't really need anything to be done to it - we reserve a temporary name in the object code for i and mark that it should contain integer value of 5. Now comes the tricky part, how do we evaluate

i = ++i + ++i;

because even though it seems simple, there are many ways to evaluating values of statements. Okay, if we go with the Wikipedia-article, it begins to look simple: we simply insert 6 (5 + 1 as per increment) into the variable i. Then... do we increment the i (now 6) again before making the addition, or do we do addition (6 + 6) before increment? And now that we have started walking this path down, shouldn't we maybe increment i twice before doing any kind of addition operation? Or maybe the increments should be done after the addition? Uh oh, what a mess!

As said above, there are many ways how expressions can be evaluated, which is called evaluation strategy. Evaluation strategy, in short, describes the order of operations and function calls by a set of usually deterministic rules.

Let's start with Java. How come Java gives a result of 13, which can only be obtained if we first increment i to 6 and then before adding i to it we increment i again? According to Oracle's specification "The Java programming language guarantees that the operands of operators appear to be evaluated in a specific , namely, from left to right." (section 15.7). Adding to that, in section 15.7.1 we have this: "The left-hand operand of a binary operator appears to be fully evaluated before any part of the right-hand operand is evaluated."

What does this mean then? Left-hand operand in their given example code

class Test1 {
   public static void main(String[] args) { int i = 2;
      int j = (i=3) * i;
      System.out.println(j);
   }
}

would be the assignment (i=3) which must be fully evaluated before moving onwards towards right, which in this case would be the * i operand. It should be noted that left-handedness and right-handedness isn't limited to having just two operations happening: for example, if we had the following

i = 1 + 2 - 3 * 4;

where would we start? If we read the Java specification, it says the left hand operand will be evaluated before right hand operand. This might seem misleading at first, making you think that we first evaluate 1 + 2, after that we would deduct 3 from that addition and finally multiply with 4. However, the left-hand operand being evaluated means just that: in the expression 1 + 2 it just means that first we evaluate the left hand side (1) before evaluating the right part (2). As such, it has nothing to do with in which order the operators are executed. Looking at C++ operator precedence chart which for the most part applies also to Java, we see that there's unary addition which comes before multiplication. However, unary addition is not what we use in normal maths, since unary operators have only one operand, and in this case it would mean that the unary operator only denotes the 'sign' of the value, meaning that it's either positive or negative. So, as we should have learned while studying basic algebra (or even earlier), * comes before + or -. So, logically that gives us the result of -9, since the statement could be read as

i = (1 + 2 - (3 * 4));

Now that we understand this, we can take a new look at the original, problematic statement. So, ++ operand should happen before the addition operand, right? Well, not quite. First we evaluate the left side operand obviously, as in ++i which returns as 6. What happens after that? This value is obviously stored, ++i is applied again returning 7 and after that the addition operator is applied, after which the result of 6 + 7 is stored into the variable called i. Suddenly this seems logical, doesn't it?

Now then, why do Ruby and Python return 10 then? It seems that even though the prefix ++-operator is legal syntax, it doesn't actually get applied! As it turns out, Python doesn't actually have an increment operator, and ++i is treated as if it had two unary operators instead of increment! This is also the reason why ++i  is legal syntax, but i++ is not.As is the case with Python, Ruby doesn't have an increment operator either. With this in mind, we could modify the code to look like this

i = 5
i = (i + 1) + (i + 1)


This gives us the result of 12, as is logical since we only add (i + 1) with itself, and we're not actually incrementing i. The same is the case in Ruby, and the creator of Ruby (sadly a StackOverflow link since apparently the original source has been lost in time and 404) has few reasons as to why there is no increment and decrement operators in Ruby:
  • C's increment/decrement operators are in fact hidden assignment. They affect variables, not objects. You cannot accomplish assignment via method. Ruby uses +=/-= operator instead.
  • Self cannot be a target of assignment. In addition, altering the value of integer 1 might cause severe confusion throughout the program.
These do seem rather valid reasons, and as we have just seen with the varying results for the same equation, ++ can really obfuscate the code and what it does unless you pay attention to language specification and operator precedence as well as associativity and evaluation strategy.

So, let's go back to Perl, C++ and C. They give us a result of 14, so obviously both increments are applied before the addition operator. But what is the difference between Java/C# and C/C++ in this regard? Since Java and C# have rather clearly defined order of evaluation, the result is 13. As this article explains, "Notice that we deviate from the usual evaluation rules for expressions. In particular, we don't substitute the current values of each variable into the expression. We must, instead, substitute only after the preincrement has been done." which means that the values returned into the expression are 6 and 7 respectively, which are then added and give us the result of 13.

So, how does this work in C/C++ then? Unfortunately, C++ standard doesn't actually define the order of subexpressions, which usually should be no problem, but in this case it is. So, in this case the compiler is free to rearrange the order of the evaluation parts of the expression (assuming that the meaning stays unchanged). See this StackOverflow answer for an in-depth answer. So, in this case the compiler (gcc is what I tested it with) decided that both ++i-expressions are evaluated first and only after them being evaluated does the compiler evaluate the +-operation (with both sides now having twice incremented i  as operands). Perl works the same way, it doesn't define when the variable is incremented or decremented, you only know that it'll be done sometime after the value is returned or before the value is returned.

So, what did we learn from all of this?
  1. Know your languages' operators and how they work and in what order
  2. For the love of all that is holy, be smart and don't use increment and decrement operators where their side-effects (self-assignment) can have surprising results - it doesn't hurt to write one line more for a more clear code. Remember the rule of thumb when writing code - imagine that the person who has to maintain your code is a homicidial maniac who will come and kill you if you've written obfuscated code
As a reward for making it all the way through, have a picture of a cat.


No comments:

Post a Comment