Programming Languages Homework 5 Due 10/29

Write a LISP interpreter. There is a heavily commented start on-line in eval.l in my src/hw5 directory. (The functions I wrote completely have no point values associated with them.)
- (5 points) Write my-assoc that takes a variable and an alist (association list) and returns the association of the variable in that alist.
```
(my-assoc 'b '((a . 1)(b . 2)(c . 3)(b . z)))
--> (b . 2)
(my-assoc 'z '((a . 1)(b . 2)(c . 3)(b . z)))
--> nil
```
- Write my-eval which takes an expression and an alist. It returns the evaluation of that expression within that variable binding context. Here is a start. You'll need to write my-eval-atom and my-apply.
- 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 should bind the formals to the evaluated actuals, then evaluate the lambda body in that scoping environment. Note it should return the value of the function body. Note the function may be a lambda or a symbol. If it is a symbol, it is a function name and the function lambda will be on the alist.
- (10 points) Write my-eval-atom that will handle evaluation of all types of atoms.
- Write my-apply that handles applying a function to a list of actual parameters. The function may be either an atomic function name or a lambda, which is a literal function body.
- (10 points) Write my-apply-atom that will cons, car, cdr, eq, quote, cond, eval, defun, and setq as special cases. As a default, it should find the function on the alist and then recursivly my-apply it to the arguments in the context of the alist.
- (20 points) Write my-apply-lambda that will handle evaluation of user-defined function bodies.
- (10 points) 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. This function is called by my-apply-lambda.
- (10 points) Write my-eval-defun that puts a function definition on the global alist used by my-top. Note you must add them onto the global-alist by using setq.
- (20 points) Write my-eval-cond that evaluates conditionals properly.
- (10 points) Write my-eval-list that takes a list and an alist and evaluates each expression in the list in the context of the alist and returns the value of the last expression in the list. You must use this function for evaluating function bodies and true cond clauses as they allow a list of expressions (not just one).
- (5 points) Write my-eval-setq that takes a var and a val and changes the value of var to be the evaluated val. This is called by my-apply-atom when the function is setq. Note it must change the value association on the global alist.
- Write my-top loops over a read eval print loop calling my-eval with the global alist instead of eval. This is the function you will call at the top level to test your eval.
- Here are some sample expressions you may use to test your interpreter. You can use the real Lisp interpreter to see what the correct answer is for each if you are not sure.
```
(my-top) ; to get your my-eval evaluating top-level expressions
t
nil
"Hello"
10
'(a b c)
(car '(a b c))
(cdr '(a b c))
(cons 'd '(a b c))
(eq 'a 'a)
(eq '(a b) '(a b)) ; should be nil
(eq t t)
(eq nil nil)
(eq t nil)
(atom 'a)
(atom '(a b c))
(listp 'a)
(listp '(a b c))
(setq x '(a b c))
x
(cond (t t))
(cond (nil nil))
(cond (nil nil)
    (t t))
(cond ((eq 'a 'a) 'b)
    (t 'c))
(cond ((eq 'a 'b) 'b)
    (t 'c))
(defun member (a l)
  (cond ((eq l nil) nil)
      ((eq a (car l)) t)
      (t (member a (cdr l)))))
(member 'a '(a b c))
(member 'a '(b a c))
(member 'd '(b a c))
(defun fact (n)
  (cond ((eq n 0) 1)
      (t (* n (fact (- n 1))))))
(fact 3)
```
Submit: a listing of your lisp interpreter and sample runs showing it correctly handles all the sample expressions listed above. Also submit an electronic version of your program so we may run it if necessary.
Note if you are using Unix for the first time, check out my introduction to Unix at Unix Introduction

(0 points) Consider the following C++ declarations and assume int is 4 bytes, double is 8 bytes, and char is one byte:

struct Bar
{
  char c,d,e,g;
  double f;
  int i;
};
union Foo
{
  char c;
  double f;
  Bar b;
};
Foo a[10];
Bar b;
Foo f;
Give the size (in bytes and in decimal) of each of the following variables:


b

f

a


Give the address (in decimal) of each of the following assuming the address of a is 1000:


a[5].b.g

a[4].b.i 

a[6].f