teaching machines

Precedence vs. Evaluation Order

July 1, 2016 by . Filed under programming languages, public, ratorvaders.

I’ve been working on a little computer science learning game called Rator Vaders. Complex expressions drop from the sky, and the player has to fire at the highest precedent operator and evaluate it. This process continues until only a literal value is left, which can be sent to the Big Bit Bucket in the Sky with one more shot. The game is meant to give my students an opportunity to playfully engage with data, types, and operators. Now, how would you pick off the expression a + b - c / d? Answer this question before reading on. When I wrote the code to determine the highest-precedent operation in an expression tree, I gave that title to the leftmost-leafmost operation. A two-operand operation gives highest precedence to an operation in its left operand. If the left operand has no operation, then the right operand is given a chance. If it too contains no operation, then the operation itself has the highest precedence: 
class BinaryOperation
  ... 
  def highest_precedent
    winner = left.highest_precedent
    if winner.nil?
      winner = right.highest_precedent
      if winner.nil?
        winner = self
      end
    end
    return winner
  end
end
This criteria for precedence seemed a bit too simple when I wrote it—but I shrugged off the doubt. Then a + b - c / d attacked Earth, and I stepped up to defend it. The middle schooler within me shot at the / first, as it has highest precedence. But the leftmost-leafmost operation is +, and that’s what Rator Vaders wanted me to shoot. I realized that my leftmost-leafmost criteria was naive. It is not the same as the precedence rules that we learned in school. However, the evaluation order is not important here. Whichever of + or / happens first, the outcome is the same, as the two subtrees do not depend on each other: I wondered, then, what happens in a real programming language? Will a compiler force the division to happen first? I tried to answer that question without resorting to assembly code or Stack Overflow (because that would be cheating). C++’s operator overloading allowed me to hook into the operations: 
#include <iostream>

class Int {
  public:
    Int(int i) :
      i(i) {
    }

    Int operator+(const Int &that) {
      std::cout << "+" << std::endl;
      return Int(i + that.i);
    }

    Int operator-(const Int &that) {
      std::cout << "-" << std::endl;
      return Int(i - that.i);
    }

    Int operator/(const Int &that) {
      std::cout << "/" << std::endl;
      return Int(i / that.i);
    }

  private:
    int i;
};

int main() {
  Int a(1);
  Int b(2);
  Int c(3);
  Int d(4);

  Int answer = a + b - c / d;

  return 0;
}
The output vindicated my leftmost-leafmost criteria: 
+
/
-
At the back of my mind, I was thinking about the expression a + b - c / d as an implementer of a programming language would think of it: as a tree structure that can be evaluated with a post-order traversal. Such a traversal will always evaluate the leftmost-leafmost operation first. Once you have a tree structure of an expression, you don’t really care about precedence anymore. Precedence was used to construct the tree in the first place, but it’s not important when it comes time to evaluate the tree. The C# specification even states that the evaluation order is left to right. Apparently the C++ specification leaves execution order open to the compiler writer. So, this has been a big day of for me. I learned that execution order and precedence are different notions. Now I must gracefully inflict that knowledge on my Rator Vaders players, who are closer to grade school than implementing a programming language.