Doubt on using polymorphism in coding an expression parse tree/evaluator

Question

I am working on an interpreter for a toy language, just to learn about building an interpreter. I have already implemented a simple parser for the grammar that generates a parse tree. Now, the usual way of evaluating the parse tree would be to use polymorphism on the nodes of the parse tree, with code that looks something like below (in Python):

class Node:
    def __init__(self,left,right):
     self.left=left
     self.right=right

    def evaluate(self):
     print "throw an exception"

class AddNode(Node):
    def evaluate(self):
     return evaluate(self.left)+evaluate(self.right)

class SubNode(Node):
    def evaluate(self):
     return evaluate(self.left)-evaluate(self.right)

The method evaluate is overridden in every descendant of Node and defend to behave as needed. The value of an expression can be found by simply calling evaluate() on the root.

Another way is to not have any evaluate function in the nodes, but to generate a parse tree that simply assigns a type to the node. The evaluation code is done in a separate function that recursively examines each node and decides how to evaluate it. This would result in a function with a large "if else" construct, switch, or jump table.

In almost every place I look, and what I have been taught back in college, seems to indicate that the first method is always better. What I don't really understand completely is why the first method should be superior to the second. Why is polymorphism necessarily better in this case? The function with the large "if else" table is not there, but basically the same code is still there but moved to a different place and scattered over a lot of different classes.

This came to my attention because I figured I might need to change the meaning of certain operators later on, perhaps even allow operators to be redefined at runtime. I am also treating function calls the same as operators, so having something like a jump table that can be added to at runtime would be nice.

There is probably some significant advantage with the first method that I'm not seeing right now. Can someone please point that out?

Answer 1

That's an interesting question. It seems to me that polymorphism is still a good way to go, even when you have operator overloading.

What you are defining with your polymorphic classes are the primitive operations that are supported in the language. Operator overloading doesn't add any more primitive capability to the language. An overloaded operator is actually equivalent to a function call and should be implemented in a similar way.

Keeping the semantics of an operator localized in the operator's class will keep your design cleaner, in my opinion. That's because to implement a new primitive operation, you just need to define the class and then create an instance during parsing. The alternative would require changing the parser and the evaluator. I just have a feeling that the evaluator could become a big nest of if statements to handle various special cases for operators, and these special cases could be hidden well in the operator classes.

I'm having a hard time really believing what I'm saying here because I've used both techiques in the past and they've both worked well. ;-)