CS 3323 Topics in Programming Languages
Lisp Interpreter Project

This final part of the assignment expands the program developed in the first three parts to accept function definitions (DEFUN . . . ) and assignment statements (SETQ . . . ).

1. SETQ: It is used to assign a value to an alphabetic atom. It should not be used inside the definition of a user's function (i.e. if it occurs there, your interpreter should report an error).

   Examples of use: (here ">" means "user types".)

        > (SETQ  ABC  (QUOTE  (A  B  C ) ) )
        (A  B  C)
        > (SETQ  TWO  2)
        TWO
        > (SETQ  THREE  3)
        THREE
        > (PLUS  TWO  THREE)
        5
        > (CONS  TWO  ABC)
        (2  A  B  C)
   

   Note that SETQ evaluates its second argument but not its first argument.

2. Implementation of SETQ: Give your interpreter a global S-expression called VARLIST that has the form:

        ( (name1  value1) (name2  value2) . . . (namen  valuen) ),
   

   where each namei is an alphabetic atom and each valuei is any S-expression. This data structure is called an Association-list or A-list. It is to be interpreted that each name has a corresponding value. At the end of the examples above VARLIST would have the value

        ( (THREE 3) (TWO 2) (ABC (A  B  C) ) )
   

   Thus evaluating (SETQ N VAL) is accomplished by
   1. Evaluating VAL, say it has value V, and
   2. CONS (N V) onto VARLIST. It will be useful to have a function PUTASSOC of three arguments (N, V, ALIST) that accomplishes step b, as well as a function LISTPUTASSOC that takes a list of names and an equal length list of values, that associates corresponding names with values, and puts them on an A-list.

   At this point, it will be legal to evaluate alphabetic atoms: their values may appear on VARLIST. To evaluate these atoms, write a function GETASSOC that takes a name N and a list of pairs ALIST and returns the first pair (X Y) that occurs on ALIST such that X = N, or NIL if there is no pair on ALIST whose first element is N. The function header should be:

        Sp getassoc (Sp N, Sp ALIST);
        /* returns first occurrence of (N VALUE) or NIL */
   

   (Note: it will not do to return just VALUE, instead of the pair. Why?)

3. DEFUN. DEFUN is used to assign a "value" to a "function variable". For example

        (DEFUN MYADD (X Y)
           (COND
              ((EQUAL X 0) Y)
              (T (PLUS 1 (MYADD (MINUS X 1) Y)))
        ))
        (SETQ FIVE (MYADD TWO THREE))
   

   if used with the earlier SETQ's, should produce the same result as

        (SETQ FIVE 5).
   

4. Implementation of DEFUN. Your program should have a global variable named FUNCLIST that is an A-list with function names and definitions. When (DEFUN <funcname> <funcbody>) is encountered you will PUTASSOC (<funcname>, <funcinfo>, FUNCLIST), where <funcinfo> is the list (<varlist> <funcbody>). None of the arguments to DEFUN are evaluated.
5. Changes to EVAL. You will have to make some changes to your EVAL function to take care of the new user-defined atoms. In particular, evaluations will take place in environments, which are represented as A-lists. Thus the value of A in environment

   ( (D  4) (C  (A  B  C))  (A  D) )
   

   is D; in that environment C has value (A B C) and Q is undefined. In every environment, numeric atoms, T, and NIL have themselves as values, and F has value NIL. EVAL will only handleDEFUN's and SETQ's, while the rest of the work will be done by a new function ENVEVA (=EVAL in an ENVironment).

   EVAL(S) now works as follows:

   if S is a list with CAR = "DEFUN" or "SETQ" then
   handle it using PUTASSOC as suggested above
   else return ENVEVAL(S, VARLIST)

   ENVEVAL(S, ALIST) works as follows:

   if S is NIL then return NIL>
   else if S is a number then return S
   else if S is an alphabetic atom then use GETASSOC(S, ALIST)
   else if CAR (S) is a user-defined function then
      begin
   	ENVEVAL the arguments (use ENVEVALARGS);
   	suppose (<funcname> (<varlist> <funcbody>) ) is the result of 	
   	GETASSOC(CAR  (S), FUNCLIST);
   	return ENVEVAL(<funcbody>, NEWALIST), where NEWALIST is the
   		result of LISTPUTASSOC (<varlist>, CDR (S), ALIST)
      end
   else if CAR (S) is a builtin function then
   	ENVEVAL the arguments and APPLY the function to the evaluated 	
   	      arguments
   else ERROR /* undefined function name -- note that SETQ and DEFUN 	
   		are not allowed here */
   

   Note: It's actually not necessary to have the separate EVAL and ENVEVAL, but one can get along with just one. We'll discuss this in class.

6. More Lisp within Lisp. Add various standard Lisp functions (usually builtin) as your own user-defined functions. Examples could include ADD1, SUB1, EQUAL, AND, OR, NOT, APPEND, various C(A's or D's)R, etc., etc. At the beginning of your main program you may want to add things like (NIL () ) and (F () ) to the VARLIST. Note that SETQ and DEFUN never replace values. Any old values remain on the respective A-list, but the most recently added ones are what will be found.
7. LOAD. For a convenient Lisp system you can optionally add a LOAD function, so that (LOAD ) will read and EVAL various Lisp S-expressions from until end-of-file. Then switch back to terminal input.
8. Reals. As mentioned in the Overview, you could fix up the interpreter to handle floating point numbers. (Be sure to use 64-bit reals.)
9. Garbage collection. Again as mentioned in the Overview, garbage collection would be a very important addition. This is a major task, almost comparable in difficulty to the rest of the project. We will discuss this in class.
10. Iterative looping. All forms of Lisp provide some form of iteration as an alternative to recursion (though recursion would always suffice). Again this will be discussed in class.