CS 381, Spring 2002
Programming Assignment 3
Due: Monday, April 29
Lisp Interpreter in Lisp

In this assignment we will investigate how the Lisp evaluation function eval could itself be written in Lisp. In order to not get confused with the built-in function named eval, we will call your function myEval. We will not do all the features of eval, in particular we will not include user defined functions. But we will do enough that you will see how an interpreter can be written in its own language.

Our development of myEval will proceed in four major steps. As I describe the steps, I will give you some expressions that your interpreter should be able to handle after each step. The best way to solve this assignment is to create a file, named progThree, that will contain your solution as far as you have developed it. You can then load and reload the assignment as you work on it.

Handling Primitive Values

You are going to be creating a function named myEval, which is (nearly) equivalent to the Lisp function named eval. This function will take one argument, and return the result of evaluating the argument. Ultimately, for example, if you enter:

>	(myEval `(+ 2 (* 3 4)))
14

you should get back the result 14, which which is two more than the product of 3 and 4.

At the highest level the function divides into two cases; lists, and everything else.

Step 1. Your first version of myEval has as its body an if expression that tests if the argument is a list. You can use listp to do the test. For the moment, if it is a list return nil, otherwise return the argument. After writing this your function should correctly handle the following:

>	(myEval `3)
3
>	(myEval `t)
t
>	(myEval `nil)
nil
>	(myEval 'A)
A

step 2. Next we will handle the evaluation of lists. The body of the list case will be a cond expression. We will be adding clauses to this as we go along. The first function we will handle is the special build-in function quote. Recall that this is the function that delays the evaluation of its argument. So the quote function simply returns its first argument.

To add quote to what you have done, you need to check that the first element of the list argument is the literal symbol quote, and if so then return the 2nd element of the list. Be careful. Think about where in the list the quote symbol is, and where in the list the first argument is. (By the way, there is a useful shorthand for combined car's and cdrs, the function caar is the car of the car, the function cadr is the car of the cdr, and so on).

After you have this you should be able to handle the following:

>	(myEval `(quote 3))
3
>	(myEval `(quote (a b c)))
(A B C)

Evaluating Arguments to Functions

The function quote, and cond (which we will consider later) are what are known as special forms, since unlike almost every other function, they do not evaluate their arguments prior to their beginning execution. (As we have been learning in the class mail list, the functions and and or are also special forms in the real Lisp system, and we will return later to show how these are handled). Every other lisp function will first evaluate its arguments. So we can make life a little bit easier by doing this action in one place. We evaluate a the arguments, then pass the list of arguments on to a second function, along with the function name. The traditional name for this second function is apply, and hence we will call our function myApply.

We will create myApply in the next section, but so that you have a way of testing your program, let us make a dummy version of myApply that just returns its argument:


(defun myApply (fun lst) lst)

In order to evaluate a list of arguments, we can use the function myMap you created in assignment 2. Make sure you understand how, if you have a list of unevaluated arguments, you can myMap the myEval function in order to create a list of evaluated arguments. Using this technique, extend the cond statement in your function myEval so that for the last case it strips off a function name, then passes the function name and the list of evaluated arguments to apply.


(if 
	(listp expr)
		(cond
			...
			(t (myApply (car expr) (myMap #`myEval (cdr expr))))
		)
		expr) ; the else part of the if

Using the dummy version of myApply you should be able to generate the following results:


>(myEval `(+ 2 3))
(2 3)
>(myEval `(car (quote (a b c))))
((A B C))

The last item is, of course, not correct, but it shows that the arguments have been evaluated. This is a problem we will now fix.

Writing apply

The apply function takes two arguments. The first is the name of a function, and the second is the list of arguments to the function. The implementation of this function is a simple big cond conditional that tests for each built-in function, and if the test is true, performs the function on the argument list. For example, if the function is car it returns the car of the argument list. If the function is + it returns the sum of the argument values.

Write this cond function and include the following built-in operations:

car Be careful here. The argument is a list of arguments. Where is the first argument? How do you get to it? Where is the car of the first argument?
cdr Again, be careful.
atom (true if argument is a list with only one element, and that element is an atom). Yes, you use a call on atom to implement atom.
null (true if argument is a list with only one element, and that element is the null list).
numberp (see description of atom)
print This function prints its argument, returning the result generated by print. (This is not really a function in the pure sense of the word, since it has a side effect. But it is easy to do, and we will make use of it in a later section.)
cons return the cons of the two argument values
eq (true if argument is a list with two values, and those values are eq to each other).
+ this is the addition; Like the real Lisp system, it can take any number of arguments, including zero. Use the recursive function sum you wrote for programming assignment 0 to compute the sum of the arguments. (If you want to you can add * and other arithmetic operations, but the grading script will use only addition).
< true if argument is a list with two values, and the first value is less than the second. (Again, if you want to you can add other relational operators, but the grading script will use only less than.)

At the very end of your conditional, if nothing else matches return the value nil. (The real lisp interpreter trips into the debugger at this point).

The real lisp system has many more built-in operations, of course. But these are sufficient for demonstration purposes. You can add more if are so inclined, but these are the only ones we will use in the grading script.

With your version of apply, you should be able to execute the following:


>	(myEval `(+ 2 3))
5
>	(myEval `(+ 2 3 4))
9
>	(myEval `(car (quote (a b c))))
A
>	(myEval `(numberp (quote (a b c))))
nil
	(myEval `(+ 2 (print 3)))
3
5

Writing and, or and cond

Having written apply and eval, we can now go back and add in some more special forms, namely the boolean operators and and or, and the conditional statement cond.

First we handle and and or. Remember that these use short circuit evaluation. This means that they take two arguments (the real Lisp functions take any number of arguments, but we will handle only two) and only evaluate the second one if the result cannot be determined by the first argument.

Both functions work the same way. Evaluate the first argument. If the results can be determined by the first argument, then return it. Otherwise evaluate the second argument, and return the results.

A subtle question is; in a functional language how can you tell if an argument has or has not been evaluated. (This is philosophically related to the age old question -- if a tree falls in a forest and nobody is there to hear it, does it make any sound?). Well, we can use the one non-functional feature that you have implemented, namely the function print, to see this. If you surround an argument with print and you don't see it on the output, then you know it was not evaluated.

Under what conditions can you determine the result of an and looking at only the first argument? What about or? What do you need to do if the results are not determined? Armed with this information, write the statements that evaluate these two special forms. Here are some test cases:

> (myEval `(and t t))
T
> (myEval `(and (< 2 4) (print (< 3 4))))
T
T
> (myEval `(and (< 4 2) (print (< 3 4))))
NIL
> (myEval `(or (< 2 4) (print (< 3 4))))
T

The test cases will only use and and or as binary functions, that is, as functions that take exactly two arguments. In the real Lisp system these functions can take any number of arguments, including zero. If you want to impress the TA and the professor, you can write your functions to handle this case. (We will see it when we look at your code). If you do this, however, make sure you handle the binary case correctly.

Put the code to handle and and or into your version of myEval, handling it right before you invoke the general case where you call myApply.

The cond statement, you will recall, has an indefinite number of arguments. Each argument is assumed to be a pair, the first element a predicate and the second an expression. It examines each element in turn. If the predicate is true it returns the evaluation of the second argument. If the predicate is false, it looks at the rest of the list. If no element has a predicate that is true, then the function itself returns the empty list.

This is easily implemented in a recursive fashion, which we will call evalCond. The function evalCond will take a cond expression where the cond take has been stripped off, leaving only a list of predicate and expression pairs. This is a recursive function.

What is the base case? The empty list. What do you want to do in the base case? Return the empty list.

Now what about the induction case. Assuming you have a list that is not empty, what do you want to do? You want to call myEval on the predicate (which is found where? be careful here.). If myEval returns true then you want to call myEval on the expression part (again, which is found where? Be careful).

What if the evaluation of the predicate return false? What do you want to do then?

Adding cond to your function myEval right before the myApply case (that is, after you have handled numbers and quote, t and nil, but before you reach the case where you call myApply). Now you should be able to handle the following:


>(myEval `(cond ((< 2 3) 7) (t 8)))
7
(myEval `(cond ((< (car (quote (2 4))) 3) (+ 3 4)) (t 8)))
7
(myEval `(cond ((< 4 3) 7) ((< 8 5) 4)))
nil

That`s it. This is the version of the assignment you are to hand in.

What to hand in

Hand in a file, named progThree, that contains the definitions for the functions myEval, myApply, and evalCond, and any other function definitions you require, such as myMap, and the definition of the recursive function sum used in the evaluation of the addition instruction. Your file, of course, should also have some identifying comments (but not your student ID number!).

What we left out

What have we left out? Really not much. There are quite a few more built-in operations, and we have left out the functions that bind a name to a value, such as defun and set. The latter require one more data structure (to keep the name/value associations) and writing this data structure cannot be done in a functional fashion, so and we have omitted them. Still, it is pretty amazing how small a lisp interpreter in lisp really is.