;; A simple LISP interpreter written by Dr Klefstad for ICS 141 at UC Irvine.
;; Of course, I deleted lots of it to let you learn more about evaluation.
;; Note the new top-level function, my-top, is defined at the bottom of this file.

;; To run this, load this file into the lisp interpreter, then call
;; (my-top)
;; then type in expressions to be evaluated.

;; The homework assignment gives a list of good test cases
;; listed in order that you should probably implement thim in to ensure you
;; enough working to go on to the next test case.

;; We will use association lists, alists, for the stack of variables and
;; their values.  An alist is a list of this form:
;; ((var1 . val1) (var2 . val2) ... (varN . valN))
;; where each vari is a symbol representing a variable (or parameter) name
;; and each vali is the value of the variable.  assoc returns the association
;; of a given symbol, e.g,
;; (assoc 'myvar '((a . 10)(b a b c)(myvar d e f)))
;; returns (myvar d e f) and you take the cdr of that to get myvar's value
;; (d e f)

;; Assoc returns the association (binding) of a variable in the association
;; list. An association list may contain multiple definitions of a variable
;; with the same name, for example with parameters to a recursive function.
;; Assoc always finds the first association of a variable, and this is how we
;; implement dynamic scoping. 

;; As evaluation proceeds deeper into recursion, new variables are added onto
;; the front of the current association list.  New defintions of a variable 
;; will hide previously made definitions effectively hiding them from access.
;; The previously made definitions will come back into scope when
;; recursive evaluation unwinds.

;; We us a special global variable, called global-alist, for saving top-level
;; definitions made using defun or setq. Note the global-alist is passed in
;; to my-eval only in the call made by my-top defined below.

(defvar global-alist nil)

;; DONE
(defun my-assoc (v alist)
  (cond
    ((null alist) nil)
    ((eq v (car (car alist))) (car alist))
    (T (my-assoc v (cdr alist)))
  )
)

;; DONE
(defun my-eval (e alist)
    (cond ((atom e) (my-eval-atom e alist))
          (t (my-apply (car e) (cdr e) alist))
    )
)

;; DONE
(defun my-eval-atom (e alist)
  (cond
    ((my-assoc e alist) (cdr (my-assoc e alist)))
    (T e)
  )
)

;; DONE
(defun my-apply (fn args alist)
    (cond ((atom fn) (my-apply-atom fn args alist))
          ( t (my-apply-lambda fn args alist)))
)

;; DONE
(defun my-eval-list (l alist)
  (cond
    ((null (cdr l)) (my-eval (car l) alist))
    (t 
      (my-eval (car l) alist)
      (my-eval-list (cdr l) alist)
    )
  )
)

;; You need to write this one.

(defun my-apply-lambda (fn args alist)
;; bind the formals to the evaluated actuals then evaluate the body in that
;; new scoping context (i.e., that becomes the new alist for recursive
;; evaluation of the function body.  Return the value of the last 
;; expression in the body (using eval-list)).
  (my-eval-list (cdr fn) (my-bind-formals (car fn) args alist))
)

;; DONE

(defun my-bind-formals (formals actuals alist)
  (cond 
    ((null (cdr formals)) 
      (cons (cons (car formals) (my-eval (car actuals) alist)) alist)
    )
    (T 
      (cons 
        (cons (car formals) (my-eval (car actuals) alist))
        (my-bind-formals (cdr formals) (cdr actuals) alist) 
      )
    )
  )
)

;; You need to write this one.  Handle the primitives as special cases, then
;; handle user defined functions (defined via defun) in the default case.
;; Handle car, cdr, cons, eq, quote, cond, defun, setq, eval, print, atom, null,
;; listp, apply, equal, +, -, mod, floor and user defined functions (defined via defun).
;; This should allow you to interpret your functions from HW4.

(defun my-apply-atom (fn args alist)
    (cond ((eq fn 'eq)
            (eq (my-eval (car args) alist) (my-eval (cadr args) alist))
          )
          ((eq fn 'car)
            (car (my-eval (car args) alist))
          )
          ((eq fn 'cdr)
            (cdr (my-eval (car args) alist))
          )
          ((eq fn 'cons)
            (cons (my-eval (car args) alist) (my-eval (cadr args) alist))
          )
          ((eq fn 'quote)
            (car args)
          )
          ((eq fn 'setq) 
            (my-eval-setq (car args) (my-eval (cadr args) alist))
          )
          ((eq fn 'cond) 
            (my-eval-cond args alist)
          )
          ((eq fn 'defun) 
            (my-eval-defun args alist)
          )
          ((eq fn 'eval) 
            (my-eval (my-eval (car args) alist) alist)
          )
          ((eq fn 'null) 
            (null (my-eval (car args) alist))
          )
          (T 
            (my-apply (cdr (my-assoc fn global-alist)) args alist)
          )
    )
)

;; DONE
(defun my-eval-setq (var val)
  (setq global-alist (cons (cons var val) global-alist))
)

;; You need to write this one.  You should know how cond works at this point.
;; Remember, cond clauses have one or more expressions in each clause.

(defun my-eval-cond (clauses alist)
  (cond
    ((null clauses) nil) ;; if there are no more clauses
    ((null (my-eval (car (car clauses)) alist)) ;; if the first clause is nil!
      (my-eval-cond (cdr clauses) alist)
    )
    (T 
      (my-eval-list (cdr (car clauses)) alist)
    )
  )
)

;; DONE
(defun my-eval-defun (body alist)
  (setq global-alist (cons body global-alist))
)

;; to push a new value, (setq global-alist (cons (cons 'newvar 'newval) global-alist))
(defun my-top ()
    (prog ()
        top
            (print (my-eval (read) global-alist))
            (terpri) 
            (go top) 
    )
)

(my-top)