WRITE IN PURE LISP( DO NOT USE IF-ELSE, IN-BUILT FUNCTIONS) DO NOT MODIFY FUNCTIONS THAT ARE ALREADY GIVEN IN THE STARTER CODE UNTIL SPECIFIED IN THE INSTRUCTIONS

Instructions:

1. Write MY-EVAL which takes an expression and an alist and returns the evaluation of that expression within that variable binding context. (See the start linked above.) You will need to write the helper functions MY-EVAL-ATOM and MY-APPLY listed below. Note all the test cases listed below are for MY-EVAL. There are no individual test cases for any other functions. 2. Write MY-EVAL-ATOM that handles the evaluation of all types of atoms.

3. Write MY-APPLY that takes a function, a list of unevaluated actual parameters, and an alist, and applies that function to the evaluated arguments. It returns the value of the function body. The function may be a lambda or a symbol. If the function is a symbol, it is a function name, and the function lambda will be in alist. MY-APPLY should bind the formals to the evaluated actuals, then evaluate the lambda body in that scoping environment.

4. Write MY-APPLY-ATOM that will handle each of the built-in primitives CONS, CAR, CDR, EQ, QUOTE, NULL, ATOM, LISTP, COND, EVAL, PRINT, DEFUN, SETQ, etc - and all the functions of PureLisp in Homework 4. As a default, call a user-defined function. To do so, find the lambda function associated with the function name on the alist and then recursively MY-APPLY the lambda to the arguments in the context of the alist.

5. Write MY-APPLY-LAMBDA that handles evaluation of user-defined function bodies. It will use MY-BIND-FORMALS and MY-EVAL-LIST.

6. Write MY-BIND-FORMALS that takes a list of formal parameters and a list of actual parameters and returns a new alist with each formal bound to its corresponding evaluated actual, pushed onto the front of the supplied alist. MY-BIND-FORMALS is called by MY-APPLY-LAMBDA.

7. Write MY-EVAL-LIST that takes a list and an alist, evaluates each expression in the list in the context of the alist, and returns the value of the last expression in the list. MY-EVAL-LIST evaluates function bodies and true COND clauses, which allow a list of expressions (not just one).

8. Write MY-EVAL-COND that evaluates conditionals properly. Remember, a cond has a list of arguments. They are cond-clauses. Each cond-clause is a list of expressions. The first one is treated like a conditional in if-then-else statements. If the first one evaluates to non-nil, then evaluate the rest and return the value of the last one (using MY-EVAL-LIST).

9. Write MY-EVAL-DEFUN that adds a function definition to the global alist used by MY-TOP (#12 below) and returns the name of the function being defined. The function definitions must be added to the global alist using SETQ. Return the name of the newly defined function.

10. Write MY-EVAL-SETQ that takes a var and a val and changes the value of var to be the evaluated val. MY-EVAL-SETQ is called by MY-APPLY-ATOM when the function is SETQ. MY-EVAL-SETQ must change the value association on the global alist using SETQ. SETQ returns the evaluated second argument, which must also be returned from MY-EVAL-SETQ.

11.Use MY-TOP that loops over a read-eval-print loop calling MY-EVAL with the global alist instead of EVAL. MY-TOP should be called at the top level to test your implementation of MY-EVAL.

Starter CODE:

;; 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. ;; You need to write this one. (defun my-assoc (v alist) nil ) ;; This one is done (defun my-eval (e alist) (cond ((atom e) (my-eval-atom e alist)) (t (my-apply (car e) (cdr e) alist)) ) ) ;; You need to write this one. (defun my-eval-atom (e alist) ;; how do you evaluate an atom??? ;; Remember there are special cases: T, NIL, MY-SYMBOL, 10, "Hello" ) ;; This one is done, but you must write the functions it calls (defun my-apply (fn args alist) (cond ((atom fn) (my-apply-atom fn args alist)) ( t (my-apply-lambda fn args alist))) ) ;; You need to write this one. ;; Utility function for eval-cond and apply-lambda. Evaluates each expression ;; in l and returns the value of the last expression (defun my-eval-list (l alist) nil ) ;; 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)). ) ;; You need to write this one. (defun my-bind-formals (formals actuals alist) ;; This takes a list of formals and unevaluated actuals. It should evaluate ;; each actual and bind it to its corresponding formal placing them all on ;; the front of the alist. It should return the alist with the new bindings ;; on the front. This will be used to evaluate calls to functions defined ;; via defun. ;; e.g., (my-bind-formals '(a) '((add 1 b)) '((b . 10))) ;; will return ((a . 11) (b . 10)) ;; Note there will be one actual parameter for each formal parameter. ) ;; 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))) ;; I wrote the first one, eq, for you, you write the rest ((eq fn 'car) ) ((eq fn 'cdr) ) ((eq fn 'cons) ) ((eq fn 'quote) ) ((eq fn 'setq) (my-eval-setq ;; you'll have to figure out the arguments to pass nil nil)) ((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)) (T (my-apply nil ;; get the lambda from the alist args alist)) ) ) ;; setq and defun will push a new association on the global-alist. ;; whenever we apply a function, we will bind the formals to the evaluated ;; actuals pushing these new bindings onto the local alist and then ;; evaluate the body of the function in that new scoping context. ;; You need to write this one. (defun my-eval-setq (var val) nil ;; just push a new association of the var and its evaluated val onto the ;; 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) nil ) ;; You need to write this one. ;; Hint: just push the function body onto the global alist. It is already an ;; association, e.g., (equal (L1 L2) (cond (...))) and (assoc 'equal in ;; the global alist will return this. You can then take the cdr and you ;; have a list containing the formal parameters and the expressions in ;; the function body. defun returns the name of the function. (defun my-eval-defun (body alist) nil ) ;; This one is done, it just initializes the global alist where global ;; settings, like those defined via setq and defun, go. (defvar global-alist nil) ;; to push a new value, (setq global-alist (cons (cons 'newvar 'newval) global-alist)) ;; This one is done, it will become the new top-level for LISP. After you ;; load this file, call (my-top) and then you can type in expressions and ;; define and call functions to test your my-eval. Note it uses the prog which ;; allows defining local variables, labels and goto looping similar to features ;; found in imperative languages. (defun my-top () (prog () top ;; read an s-expression, evaluate it using my-eval passing in the global-alist, ;; then print the result, functions and global variables will be on global-alist (print (my-eval (read) global-alist)) (terpri) ;; prints a newline (go top) ;; loops forever ) )