Interpreter Project

Extension B, like other extensions, serves three purposes. The extensions will...

1. ...give you a much more detailed understanding of the material.
2. ...make your interpreter more complete.
3. ...provide you a chance to earn some extra credit.

You may attempt to complete the Extensions at any point during the project. You do not need to attempt them after a specific required portion of the project. In addition, you should not run handin37 separately to hand in an extension: simply hand in the extension along with the next required section you complete.

Finally, since these extensions are considered "advanced" features, you will receive far less guidance in completing them then you will receive for the required portions of the project. This does not mean that you cannot ask questions; rather, I will provide less information to you up front, forcing you to work out details on your own.

Though it may not seem logical to implement trace and untrace before implementing lambda, you will actually be able to complete the entire implementation of these two functions without much of an idea of how lambda will eventually operate, and you can test your current implementation of trace on the primitive procedures. Of course, once you add lambda to your interpreter, you will want to go back and make sure that everything works. Chances are that, with one detail, your implementation should continue to work.

Play around with trace in DrScheme to make sure you understand how it works. There is a sample file you can try to get yourself started, located in the lectures/04-24 directory. Do not move your interpreter.scm to that directory.

You should also read the Help Desk entry for trace. In Dr.Scheme, select Help, then Help Desk. In the new window that pops up, type "trace" into the search bar at the bottom of the window and press Enter. On the results page, click on:

(trace variable ...) in "trace.ss: Tracing Top-level Procedure Calls"

A few pieces of advice:

1. Your test for whether or not you are trying to apply a traced procedure should be done in eval-application.
2. Be sure you can handle expressions such as (trace a b c) (which traces all three functions); on its own, (trace) does nothing.
3. Be sure you correctly handle what happens if an already-traced function is traced. For example (the colors are just for easy reading, you should not try to output specially colored text):
   > (define f (lambda (x) (+ x 1)))
   > (trace f)
   (f)
   > (f 5)
   |(f 5)
   |6
   6
   > (trace f)
   (f)
   > (untrace f)
   (f)
   > (f 5)
   6
   
4. The "detail" that you may need to go back and fix (unless you anticipated well or read the Help Desk page) is how to deal with nesting the output of traced procedures which call other traced procedures (or themselves recursively). You can test that out once you write lambda in Part 5.
5. Your version of trace can be more powerful than the built-in trace -- if you want it to be. Once you are able to define your own procedures using lambda, you'll be able to trace procedures that are defined locally inside other procedures; the DrScheme version of trace will not let you do that. You may find that it is actually easier to allow for this "more powerful" version than to try and mimic DrScheme's version.