#lang racket

; Evaluator for simple arithmetic expression trees.  In this
; version we use global state containing a hash to keep track 
; of current variable values.

; the global state is a list consisting of one element: an immutable hash

(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 (lookup-value state-in expr))
       )
      (#t 
        ; handle list here, use fold to thread previous results
        ; fold-state is a list of state followed by 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
                   (cond
                       ( (equal? e 'PLUS)
                       ; if at a plus, the first 2 items on the previous 
                       ; results list are the values to be added. 
                         (list (first e-result)
                               (+ (first (second fold-state)) 
                                  (second (second fold-state)))
                               )
                         )
                       
                       ( (equal? e 'ASSIGN)
                         ; if at an assignment, the first element is 
                         ; assigned to be the value of the 
                         ; variable in the second list element.
                         (list (list (dict-set (first (first e-result))
                                       (second (second fold-state)) 
                                       (first (second fold-state))) )
                               (first (second fold-state)) )
                         )
                       
                       (#t 
                         ; If not a plus or assignment, we have an 
                         ; expression evaluation result to save.
                         (list (first e-result)
                               (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 (list (make-immutable-hash '()) ) expr))
    ))

; look up value of identifier exp in the hash contained in the state, 
; if not present return the identifier
(define lookup-value
  (lambda (state-in exp)
    (hash-ref (first state-in) exp exp)
    )
  )


(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))
(evaluate-expression '( (2 A ASSIGN) (A A PLUS) PLUS ) )
(evaluate-expression 
    '( ( 100 ( (((40 2 PLUS) A ASSIGN) A PLUS) B ASSIGN) PLUS ) (B A PLUS) PLUS) )

; and this surprising one
(evaluate-expression '( (2 1 ASSIGN) 1 PLUS ) )

;(define h (make-immutable-hash '()))
;(define h1 (dict-set h 'a 21))
;(define h2 (dict-set h1 'b 42))
;(hash-ref h1 'a 99)
;(hash-ref h1 'b 99)
;(hash-ref h2 'b 99)