Assignment 8 File: asst8.txt Author: CS 51 (Bob Walton) Version: 1 This is the second of three assignments in which you program an interpreter called lisp51 for a subset of the COMMONLISP language. In this assignment you will implement the evaluator and a few COMMONLISP functions. You do NOT need to copy any new files into your asst7-9 directory to do this assignment. The following are defined for this assignment: make Makes the lisp51 program. make test-primitives.out Basic tests. make test-defs.out More advanced tests done later. make asst8 Makes asst8 outputs, i.e. all tests. make print8 Prints asst8 files. make submit8 Submits for assignment 8. make sprint8 Prints asst8 for submission. The lisp51 interpreter is describe in class handouts that are separate from the assignments. Files important to this assignment include the .cc files: eval.cc p_car.cc, p_cdr.cc, p_cons.cc the .lsp file: to-be-lisp51.lsp and the documentation file: meta-lisp.lsp This handout includes a printout of the file: answers8.txt containing written questions and answers. Also included with this handout are the files: p_apply.cc, p_func.cc which give you more examples of primitive functions to look at and also let you better see how lambda closures work in the C++ implementation. Lastly, printouts of the files: test-primitives.in test-defs.in which are inputs to the tests of `make asst8' are included in this handout. In this assignment you are given a prototype for an evaluator, meta-lisp.lsp, written in COMMONLISP, and you are asked to write the evaluator in C++. A prototype is a program similar to the final program but only intended to test basic concepts used in implementing the final program. In this case the prototype tests an implementation method for argument passing, function definition, and closures. You have also been given three unimplemented primitive functions to write: prim_cons, prim_car, and prim_cdr. When lisp51 starts, it reads in the file lisp51.lsp that contains definitions of COMMONLISP functions written using the primitives of LISP51. You should not use this file until your evaluator and primitives are working fairly well, but after you have gotten to that point, you should execute the UNIX command: mv to-be-lisp51.lsp lisp51.lsp and try it out. When it is working, you will find the code for two functions is missing: APPEND and LET (and as a consequence several functions that use LET do not work, e.g. DO). You are to supply the missing code. Also, there is a brief written assignment, in answers8.txt, that is intended to improve your understanding of the C++ implementation of the LISP memory model. The specific things you MUST do for assignment 8 are: (1) Do the written exercise in answers8.txt. This is not related to the rest of the assignment, and can be done any time. (2) Read meta-lisp.lsp. Test it if you feel that will help you understand it (its in ~lib51/handouts). (3) Using meta-lisp.lsp as a guide: (a) Complete the rewrite rules for eval_sexpr in eval.cc. That is, replace all the ???'s by useful expressions. See the rewrite rules for bind_args later in eval.cc for more examples of how to write rewrite rules in this context. (b) Write pseudo-code for apply in eval.cc. Your pseudo-code will be graded on whether it matches you actual code, and expresses the algorithm of that actual code in a manner that is both logically complete and much more readable than the actual code. (b) Write the rewrite rules for eval_args in eval.cc. This is the design part of this assignment. (4) Write the code for eval_sexpr and its helper functions, apply, bind_args, eval_args, and binding_pointer. Code should be written where TBW, `To Be Written', appears. It is best to do this a little bit at a time and test frequently. Atoms that are not symbols evaluate to themselves: e.g. fixnums. To evaluate a symbol, call binding_pointer to find out where the symbol value is stored. Dereference that. Check for NULL (unbound) using unboundp, and call error if unbound. The version of binding_pointer you have been given returns the symbol_value component location of the symbol, and ignores the environment. This suffices for initial testing. Then get + working. To do so, if given (+ ...), get the function binding (symbol_function) of +, call eval_args to evaluate the arguments, call apply to apply the function binding to the evaluated arguments, and return the result. Write a simple version of apply to handle only primitive functions. Write eval_args. Bind_args is not needed yet. Then get COND working. It is a special function. The function binding of COND needs to be found, and function_apply used to apply this to the unevaluated arguments. Apply and eval_args are not called. Next you should write and test the functions in p_cons.cc, p_car.cc, and p_cdr.cc; as you will need these to test the following. You may find it helpful to implement the trace feature in eval_sexpr at this point. Use bool trace = ! unboundp (symbol_value (TRACE)) && ! null (symbol_value (TRACE)); The trace feature in meta-lisp.lsp MUST be implemented in eval.cc. It is a very simple trace and requires some thought to understand its output, but the output is complete. Now (set-symbol-function 'foo '(lambda (x y) (cons x y))) will work. But (foo 1 2) will not. You need to write bind_args, to call it from apply when that is given a (lambda ...) function, and to call apply from eval_sexpr in this case. Try writing an initial bind_args that does NOT handle a &REST parameter. You also need to extend binding_pointer to look in the environment. Now you need to handle all the things not yet done, such as macros in eval_sexpr and apply lambda_closures as made by #'(lambda ...) &REST parameter in bind_arg ((lambda (x y) (cons x y)) 1 2) The meta-lisp.lsp prototype should be used to resolve questions of what to do in different cases and whether anything has been accidentally omitted. Note that ill formed s-expressions, argument lists, function bindings, etc. should be recognized and call error. (5) Test the your C++ code very carefully by running: make test-primitives.out and examining test-primitives.out. You may find it helpful to to ci -l *tives.out and then after re-running a test rcsdiffs *tives.out so you only have to look at the differences between the current run and the last run ci'ed. Another ploy is to do more *tive.out and then / where is the name of the last function whose test worked. Once this test is passed, execute the UNIX command: mv to-be-lisp51.lsp lisp51.lsp and your lisp51 interpreter will read in this file when it starts up. Be sure there are no error messages printed while starting lisp51. Then do make test-defs.out and examine the results. There will be some errors because APPEND, LET, and functions and tests depending on LET, in particular DO and some closure tests, will not work. (6) Now write the code for APPEND and LET in lisp51.lsp, and test it with make test-defs.out The answers8.txt part of this assignment is worth 5 points, the design part 10 points, and the code part 60 points (this assignment is worth 75 points instead of the usual 60 points). There is NO separate theory part of this assignment: you need only hand in the output of make sprint. The following are the SLOC counts for a well written solution. In C++ a SLOC is defined as a non-comment line containing a semi-colon and in LISP a SLOC is a non-comment line containing a ). eval_sexpr 26 apply 27 bind_args 18 eval_args 6 binding_pointer 7 prim_car 6 prim_cdr 6 prim_cons 2 append 3 let 3 Half these SLOC counts will be the number of points that will be deducted if you do NOT do a function (they do NOT sum to 60). Good Luck!