#lang racket

; Define some useful predicates on expressions we will use for both parts
(define (is-exp-leaf? E) 
    (not (list? E)) )

(define (is-exp-nested? E) 
    (and (list? E) (null? (rest E)) ) )

(define (is-exp-binary? E)
    (and (list? E) (= 3 (length E))))

(define (is-cummutative? op) 
    (or (equal? '+ op) (equal? '* op)) )

; Part 1
; evaluate op on larg, rarg.  If larg and rarg are not numbers
; the return the infix expression (larg op rarg), otherwise return the
; value of ((eval op) larg rarg)
;
; op - quoted binary operation (like '+ '/), not a procedure (like + /)
; larg, rarg - left and right arguments, numbers or expressions
;
; Note: if you want to have your own version of an operation, like say
; / which on 1/0 yields 'NaN (Not a Number), then you can add a dispatch
; cond to the else below.  You could also explicitly enumerate the possible
; operations and then generate an error when they are missing.

(define (op-eval op larg rarg)
  (cond 
   
    [ (or (not (number? larg)) (not (number? rarg))) 
      (list larg op rarg) ]
    
    [ else ((eval op) larg rarg) ]
    ))

; if s is in symbol table symtab, return the value of s, otherwise return
; the default-value.  
; The symbol table is a list of (name value) pairs
; that associates the symbol name with value.  

; If there are multiple 
; occurrences of name, then the value associated with the first one is used.

(define (lookup-sym s default-value sym-tab)
  (let (
        [ r (findf (lambda (p) (equal? s (first p))) sym-tab) ]
        )
    (if (not r) default-value (second r))
    ))


; evaluate expression E in the context of the symbol table sym-tab
(define (exp-eval E sym-tab)

  (cond
    ; the leaves are numbers or symbols.  If a symbol, get it value from sym-tab,
    ; otherwise just return the symbol.
    [ (is-exp-leaf? E) (if (number? E) E (lookup-sym E E sym-tab)) ]
    
    ; single element lists are the value of their first element, so drill down
    [ (is-exp-nested? E) (exp-eval (first E) sym-tab) ] 
    
    ; binary operations are applied to the evaluations of their arguments
    [ (is-exp-binary? E) (op-eval (second E)
                    (exp-eval (first E) sym-tab)
                    (exp-eval (third E) sym-tab)) ]
    
    [ else (error (format "Bad expression ~a" E)) ]
    ))

; tests
(define sym-1 '( (x 3) (y 4) (z 42)))
(define t 42) ; add t to the environment

(define (run-tests) 
  (map displayln
       (list 
        (exp-eval 1 sym-1)
        (exp-eval '1 sym-1)
        (exp-eval '(1) sym-1)
        (exp-eval '(1 + 2) sym-1)
        (exp-eval '(3 * 4) sym-1)
        (exp-eval '( (1 + 2) * (3 + 4) ) sym-1)
        
        (exp-eval 'x sym-1)
        (exp-eval '(1 + x) sym-1)
        
        
        (exp-eval '(t + (1 + x)) sym-1)
        (exp-eval '( (1 + x ) / (1 + x) ) '() )
        (exp-eval '( (1 * ( 2 * (3 + x) ) ) ) '() )
        ))
  #t ; returns true if all the tests ran.
  )


; Part 2



(define (equal-commute? E1 E2)
  (cond
    [ (and (is-exp-leaf? E1) (is-exp-leaf? E2)) (equal? E1 E2) ]
    
    [ (and (is-exp-nested? E1) (is-exp-nested? E2) ) 
        (equal-commute? (first E1) (first E2) ) ]

    [ (and (is-exp-binary? E1) (is-exp-binary? E2) 
           (equal? (second E1) (second E2) ) )
        (let (
            ; left and right hand args of E1 and E2
            [ op (second E1) ] ; op is same for both expressions
            [ lh-E1 (first E1) ]
            [ rh-E1 (third E1) ]
            [ lh-E2 (first E2) ]
            [ rh-E2 (third E2) ]
            )
            (if (is-cummutative? op)
                ; commutative so try both orders
                (or 
                    (and (equal-commute? lh-E1 lh-E2) (equal-commute? rh-E1 rh-E2))
                    (and (equal-commute? lh-E1 rh-E2) (equal-commute? rh-E1 lh-E2)) )
                ; not commutative so must match
                (and (equal-commute? lh-E1 lh-E2) (equal-commute? rh-E1 rh-E2))
            )
        ) ]
    [ else #f ]
    ))

(equal-commute? '5 '4)
(equal-commute? '5 '5)
(equal-commute? 'x '5)
(equal-commute? 'x 'x)
(equal-commute? '(5) '5)
(equal-commute? '(5) '(5))
(equal-commute? '(1 + x) '(x + 1))
(equal-commute? '(1 + x) '(1 + x))
(equal-commute? '(1 * x) '(x * 1))
(equal-commute? '(1 * x) '(1 * x))
(equal-commute? '(1 + x) '(x * 1))
(equal-commute? '(1 + x) '(1 * x))

(equal-commute? '(1 - x) '(x - 1))
(equal-commute? '(1 - x) '(1 - x))
(equal-commute? '(1 / x) '(x / 1))
(equal-commute? '(1 / x) '(1 / x))

(equal-commute? '((1 + x) * (y + 2)) '((y + 2) * (x + 1)))