; convenience aliases
(define first-of car)
(define rest-of cdr)
(define second-of cadr)
(define third-of caddr)
(define fourth-of cadddr)

; binding functions
(define add-binding
  (lambda (var val bindings)
    (if (null? bindings)
        (list (list var val))
        (let ((entry (first-of bindings))
              (rest (rest-of bindings)))
          (if (equal? var (first-of entry))
              (cons (list var val) rest)
              (cons entry (add-binding var val rest)))))))

(define lookup-binding
  (lambda (var bindings)
    (let ((result (assoc var bindings)))
      (if result result (list var 'undef)))))

; expression predicates
(define number-expr? number?)

(define bool-expr?
  (lambda (expr)
    (cond ((equal? expr 'true) #t)
          ((equal? expr 'false) #t)
          (else #f))))

(define id-expr?
  (lambda (expr)
    (if (equal? expr 'undef)
        #f
        (symbol? expr))))

(define binary-op-expr?
  (lambda (expr)
    (and (list? expr)
         (equal? (length expr) 3)
         (let ((op (second-of expr)))
           (if (member op '(+ - * / and or < > <= >= == !=)) #t #f)))))

; statement predicates
(define do-stmt?
  (lambda (expr)
    (and (list? expr)
         (>= (length expr) 1)
         (equal? (first-of expr) 'do))))

(define assign-stmt?
  (lambda (expr)
    (and (list? expr)
         (equal? (length expr) 3)
         (id-expr? (first-of expr))
         (equal? '= (second-of expr)))))

(define if-stmt?
  (lambda (expr)
    (and (list? expr)
         (equal? (length expr) 4)
         (equal? (first-of expr) 'if)
         (equal? (third-of expr) 'then))))

(define while-stmt?
  (lambda (expr)
    (and (list? expr)
         (equal? (length expr) 3)
         (equal? (first-of expr) 'while))))

;; expression eval

(define eval-expr
  (lambda (expr bindings)
    (cond ((number-expr? expr) expr)
          ((bool-expr? expr) expr)
          ((id-expr? expr) 
           (let ((binding (lookup-binding expr bindings)))
             (second-of binding)))
          ((binary-op-expr? expr) (eval-binary-op expr bindings))
          (else 'error))))

(define eval-binary-op
  (lambda (expr bindings)
    (let ((operator (second-of expr)))
      (cond ((member operator '(+ - / * < > <= >= == !=)) (eval-math-op expr bindings))
            ((member operator '(and or)) (eval-logic-op expr bindings))
            (else 'error)))))

(define eval-math-op
  (lambda (expr bindings)
    (let ((operand1 (eval-expr (first-of expr) bindings))
          (operator (second-of expr))
          (operand2 (eval-expr (third-of expr) bindings)))
      (if (and (number-expr? operand1) (number-expr? operand2))
          (cond ((equal? operator '+) (+ operand1 operand2))
                ((equal? operator '-) (- operand1 operand2))
                ((equal? operator '*) (* operand1 operand2))
                ((equal? operator '/) (/ operand1 operand2))
                ((equal? operator '<) (if (< operand1 operand2) 'true 'false))
                ((equal? operator '>) (if (> operand1 operand2) 'true 'false))
                ((equal? operator '<=) (if (<= operand1 operand2) 'true 'false))
                ((equal? operator '>=) (if (>= operand1 operand2) 'true 'false))
                ((equal? operator '==) (if (= operand1 operand2) 'true 'false))
                ((equal? operator '!=) (if (= operand1 operand2) 'false 'true))
                (else 'error))
          'error))))

(define eval-logic-op
  (lambda (expr bindings)
    (let ((operand1 (first-of expr))
          (operator (second-of expr))
          (operand2 (third-of expr)))
      (cond ((equal? operator 'and)
             (if (equal? (eval-expr operand1 bindings) 'false)
                 'false
                 (eval-expr operand2 bindings)))
            ((equal? operator 'or)
             (if (equal? (eval-expr operand1 bindings) 'true)
                 'true
                 (eval-expr operand2 bindings)))
            (else 'error)))))
            

;; statement eval

(define eval-stmt
  (lambda (expr bindings)
    (cond ((assign-stmt? expr) (eval-assign expr bindings))
          ((do-stmt? expr) (eval-do expr bindings))
          ((if-stmt? expr) (eval-if expr bindings))
          ((while-stmt? expr) (eval-while expr bindings))
          (else 'error))))


;; top level eval

(define eval-program
  (lambda (program variable)
    (lookup-binding variable (eval-do (cons 'do program) '()))))