#lang racket

; First cut at evaluator for simple arithmetic expression trees.  In this
; version we do not need any global state.  But in the next version with 
; variables we will.

(define evaluate-expression-r
  (lambda (state-in expr)
    (cond  
      ( (not (list? expr)) 
        ; handle simple atomic term here, use new symbol number and update
        ; the next symbol number
        (list state-in expr)
       )
      (#t 
        ; handle list here, use fold to thread previous results
        ; fold-state is a list of threaded state (unused) and a list 
        ; containing the value of the expressions that are the subtrees 
        ; of the current expression.   There should be two values on the 
        ; latter list when the recursion encounters an operation
      
        (foldl 
        (lambda (e fold-state) 
           (let ( [ e-result (evaluate-expression-r (first fold-state) e) ] )
             ; now pass on state and augmented result
             (list (first e-result) ; state-out
                   (if (equal? e 'PLUS)
                       ; if at a plus, the first 2 items on the previous 
                       ; results list are the values to be added.  
                       (+ (first (second fold-state)) 
                          (second (second fold-state)))
                       
                       ; If not a plus, we have an expression evaluation 
                       ; result to save.
                       (append (second fold-state) (list (second e-result)))
                       )
              )
           )
           )
         
         (list state-in '()) ; initial state and result
         expr
        )
       )
      )
    )
    )

(define evaluate-expression
  (lambda (expr)
    (second (evaluate-expression-r '() expr))
    ))



(evaluate-expression 1)
(evaluate-expression '( (42 10 PLUS) (1 3 PLUS) PLUS))
(evaluate-expression 
    '( ((42 10 PLUS) (1 3 PLUS) PLUS) ((2 4 PLUS) (8 16 PLUS) PLUS) PLUS))