Contents    Page-10    Prev    Next    Page+10    Index   

Postorder

The Lisp function eval evaluates a symbolic expression. We can write a version of eval using postorder traversal of an expression tree with numeric leaf values. Postorder follows the usual rule for evaluating function calls, i.e., arguments are evaluated before the function is called.


(defun myeval (x)
  (if (numberp x)
      x
      (funcall (op x)            ; execute the op
               (myeval (lhs x))
               (myeval (rhs x)) ) ) )


>(myeval '(* (+ 3 4) 5))
  1> (MYEVAL (* (+ 3 4) 5))
    2> (MYEVAL (+ 3 4))
      3> (MYEVAL 3)
      <3 (MYEVAL 3)
      3> (MYEVAL 4)
      <3 (MYEVAL 4)
    <2 (MYEVAL 7)
    2> (MYEVAL 5)
    <2 (MYEVAL 5)
  <1 (MYEVAL 35)
35