simple "if"-less algebraic computation using CLOS
(defmethod evaluate ((node op-node))
  (apply (value node) 
         (list (evaluate (left-node node))
               (evaluate (right-node node)))))


can be written:

(defmethod evaluate ((node op-node))
  (funcall (value node) 
           (evaluate (left-node node))
           (evaluate (right-node node))))


For this example, instead of different subclasses for every binary operation, you could just use a binop class and instantiate it with the respective functions, since they share the same evaluate method, but that depends on what else you want do do with the nodes. (Maybe, for example, you want to have different print-object methods for each of them.)

(Also, using toplevel setfs on unestablished symbols is considered bad style, but I suppose this was just for testing and demonstration purposes. In real code, defparameter or defvar should be used.)