PROJECT 1: A LISP INTERPRETER Submitting your Project: Submit your solution online by 11:59pm on Wednesday, February 18. Do this by creating a directory named 'proj1' that contains a file named lisp.c. From within that directory, type "submit proj1". A tiny Lisp-subset interpreter written in C is available in the file ~cs61c/lib/lisp.c. Your job is to extend the interpreter. Part of the object of this exercise is for you to be sure to learn any C details needed for the project that you haven't learned already, so ask questions if necessary. 1. Add a symbol table so that EVAL can look up the values of symbols. (Since there are no user-defined procedures in this Lisp, all symbols will be global.) Use an appropriate searchable data structure from 61B; it needn't be the fastest possible. 2. Add the DEFINE special form to add an entry to the symbol table, e.g., (define x (+ 2 3)) would add an entry with the name X and the value 5. It should return the name of the defined symbol (X in this example). 3. Add a vector (array) data type. For this data type, the STRUCT THING should include a pointer to a dynamically-allocated block of storage just large enough for the array, and a number indicating the length of the array. The elements of the array should be pointers to THINGs. The reader should recognize the notation #(4 5 FOO BAZ) to represent a vector, and should allocate (for this example) an array of length four. The printer should know how to print vectors, too. The elements of a vector can be of any type, of course, including lists and vectors. Also implement the following primitives: (make-vector length) returns a vector of LENGTH empty lists (vector-ref vector index) returns the INDEXth element (counting from 0) (vector-set! vector index value) changes the element's value (and returns NIL) 4. OPTIONAL --- FOR FUN, NOT FOR CREDIT! DON'T DO THIS UNTIL THE REST OF THE PROJECT IS COMPLETED. Add user-defined procedures. To do this, create a new USERPROC type that includes the procedure's text and its defining environment. Add a LAMBDA special form to create user procedures. The text of the procedure is just the LAMBDA expression (or its cdr, if you prefer, leaving out the word LAMBDA itself). An environment is a list of frames, where each frame is a symbol table like the one you created earlier. Modify the symbol lookup routine to handle a list of symbol tables. Then you have to write APPLY so that for user-defined procedures it extends the procedure's defining environment with a new frame in which the procedure's formal parameters are bound to the calling expression's actual argument values, and you have to write EVAL-SEQUENCE that evaluates the procedure's body. (Actually, since we have no primitives with side effects --- no mutation, for example --- you could get away with only allowing one expression in the body.) Basically you are redoing the metacircular evaluator from chapter 4 of SICP, but writing in C instead of in Scheme. This really isn't hard if you remember 61A!