CSE 341 -- Assignment 2 -- Scheme Project

Due in lecture October 19, 1998. Turnin Information

You may work on this assignment alone or in groups of two. Group projects will be graded the same as individual projects -- in other words, we aren't expecting extra work from a group. Please feel free to send mail to cse341@cs saying you are looking for a partner for this project.

This assignment involves a traditional Lisp/Scheme activity: writing meta-circular interpreters. Starting with the meta-circular interpreter presented in Chapter 4 of Structure and Interpretation of Computer Programs, augument the interpret in the following ways:

  1. Add primitives for arithmetic (+, -, *, and /). Demonstrate that your augmented interpreter works correctly for these new primitives. Note: it's OK to implement a version of + that takes an indefinite number of arguments, or exactly two arguments. Actually, though, you would have to go out of your way to restrict it to exactly two arguments. (Why?)

  2. Add a trace facility to the interpreter. If you have defined a function factorial (in the interpreter) and then evaluate (my-trace factorial) your interpreter should print out trace information each time factorial is called and each time it exits. On function entry, print out the name of the function and the arguments; on exit print out the name again and the return value. (my-untrace factorial) should turn off tracing.

  3. Also add a second, more verbose, trace facility that prints out the environment in a nice way after entering a function, in addition to the information from my-trace. The printout should include the names and values of each variable in each frame. Indicate the different frames as well. This verbose trace facility should be invoked using (enviro-trace factorial). Demonstrate both my-trace and enviro-trace working on the recursive functions factorial, append, and map.

  4. Exercise 4.4 (page 374)

  5. Exercise 4.6 (page 375)

  6. Exercise 4.7 (page 375)

Hints

Carefully read Chapter 4 Section 1. The code for the meta-circular interpreter is on orcas on ~borning/scheme/ch4-mceval.scm (downloaded from the Structure and Interpretation of Computer Programs web page).

One thing I didn't like about this code is that it redefines the built-in functions eval and apply, and as a result of redefining apply the code can not be loaded twice. I made a slightly different version of the code that renames the new functions to my-eval and my-apply. Use whichever one you want. My version is on ~borning/scheme/my-eval.scm

The meta-circular interpreter in the book uses side effects. You can also use side effects in your code, but use them sparingly and only then they improve the clarity.

Extra Credit

For a modest amount of extra credit, do exercise 4.24 and/or exercises 4.32, 4.33, and 4.34. These extra credit exercises are a fair amount of work relative to the extra credit -- so do them only if you are particularly interested in the subject (which is in fact pretty cool), but not just because you want every possible extra point. I'd start with 4.24. The other exercises (4.32, 4.33, and 4.34) concern lazy evaluation -- we will study this topic as a class in some detail when we get to the language Miranda. Doing these exercises in Scheme will give you a useful other view on the subject. (One thing I didn't like about the book's treatment of lazy evaluation was the extensive mixing of lazy evaluation with side effects, e.g. exercise 4.27. This is ugly. Experiment with lazy evaluation for purely functional programs -- much cleaner.)

Read Section 4.2 of the book for the lazy evaluation extra credit exercises. Code for the analyzing evaluator is on ~borning/scheme/ch4-analyzingmceval.scm, and ~borning/scheme/ch4-leval.scm for the lazy evaluator.