CS 3323 Topics in Programming Languages
Lisp Interpreter Project

LISP Interpreter 3--Initial Evaluator
Due March 5, 1999

The purpose of this assignment is to write a program to interpret S-expressions which do not involve user-defined functions (DEFUN) or values for alphabetic atoms (SETQ). It is assumed that you have a working S-expressions reader/writer that will convert an S-expression into internal (linked list) form, and will convert it back in order to write it out. You will need all of the functions you wrote for the previous assignments along with a few more.

Some of the objectives of the assignment are to emphasize modular programming, to practice using list structures and pointers in developing an interpreter for the Lisp primitives, and to introduce you to a functional programming style within a block-structured language. For this assignment it will help if you write code that resembles Lisp itself. Thus you should only write functions that return pointers to S-expressions. There should be no assignment statements or iterative statements, and heavy use should be made of recursion. The final result will be similar in many ways to a Lisp interpreter written in Lisp.

The main loop of your program should now be:

  1. Read an S-expression S (as before).
  2. (New step!) Evaluate it.
  3. Output the result of step 2.
Repeat steps 1 to 3 until an occurrence of the atom EXIT.

For step 2, remember the way Lisp works:

  1. if S (the S-expression just read) is a number then return S.
  2. if S is an alphabetic atom then return "nil" (since alphabetic atoms don't have values, at least not yet) and issue an error message.
  3. else (* S is a list *)
    1. Treat (CAR S) as a built-in function name.
    2. Evaluate (recursively) each element of (CDR S) and make a list of these.
    3. Apply the function determined in step a. to the list of values gotten in step b.
To implement step 3a: You might want a table of legal function names. You should implement the following functions: CAR, CDR, CONS, ATOM, PLUS, MINUS, TIMES, QUOTIENT, QUOTE, EQ, and GREATERP. In the next assignment you will have to implement COND, SETQ, and DEFUN, so you might want to put them in your table of "reserved words" at this point, even though you don't need to implement them. You may include others of your choice if you desire, e.g., CAAR, NULL, etc. For simplicity you may assume that the arithmetic functions each have exactly two arguments. (Lisp usually allows any number of arguments for these functions.)

To implement step 3b: Think recursively! If your function that evaluates is called EVAL, it should have a (two or three line) subfunction EVALARGS that EVAL's a list of S-expressions, returning a list of their values.

To implement step 3c: Write a function APPLY that takes as arguments the function from step 3a and the list from step 3b, and carries out the intent of the function on the list. (APPLY does the actual work.)

You need not worry about the abbreviated syntax for QUOTE, e.g. '(A B C) is not legal input; however, (QUOTE (A B C)) is legal and has value (A B C). Remember that QUOTE does not evaluate its argument, so EVAL will handle it separately.

EVAL will also handle EXIT and COND separately (as well as DEFUN and SETQ in the next assignment). To evaluate a COND expression note that the value of

      (COND (t1  e1) (t2  e2) . . .  (tn  en))
is:

if ((t1 e1) (t2 e2) . . . (tn en)) = () i.e. n = 0 then return NIL
else if the value of t1 <> NIL then return the value of e1
else return the value of (COND (t2 e2) . . . (tn en)).

Note: Once we get a non-null value for one of the t's, no subsequent ti or ei is evaluated. You may handle COND in this assignment or the next.

One convenient way to handle errors now is to redefine ERR as a function that always returns NIL. Thus when an error is detected, you can return something like ERR(14).

As far a modularity goes you should bear in mind that you will want to expand your program to deal with SETQ and DEFUN later. Therefore make your program modular and easy to change. It is partly for this reason that there are parts 3 and 4 of the Lisp interpreter project: simply handing in the final interpreter, even if it works, will not completely satisfy the course requirements.

What to turn in: A listing, overview documentation, and results of a sample run. You should demonstrate the full capabilities of your interpreter, including deeply nested arithmetic expressions, such as 

	(PLUS (TIMES 3 (PLUS 5 1)) (QUOTIENT (TIMES 12 3) (PLUS 7 5))),
yielding 21, and complex expressions that operate on lists, such as 
	(CONS (CAR (QUOTE (A B C))) (CDR (QUOTE (A B C)))),
yielding (A B C). In case you completed COND, you could also demonstrate this function, using enough examples to really exercise it. (For debugging, remember, try really simple inputs first, then more complex ones.)
Revision date: 1/6/99