Interpreter Project
Extension 2: Tracing procedures: trace, untrace

Extension 2 may be completed at any stage of the final project.
Final project due Monday, May 8 at noon
Reminder: Notes about extensions

The extensions are intended to serve three purposes; they will:

  1. Give you a much more detailed understanding of the material.
  2. Make your interpreter more complete.
  3. Provide you with a chance to earn some extra credit.
You should not be attempting any of the extensions unless you are completely finished with all previous parts. You will lose far more points for failing to complete required sections of the interpreter than you could possibly gain by completing all of the extensions.

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.

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.

Implementing trace and untrace

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 minor detail, your implementation should continue to work.

Play around with trace in DrScheme to make sure you understand how it works.

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. The "minor detail" that you may need to go back and fix (unless you anticipate well) is when a traced procedure calls itself recursively. You can test that out once you write lambda in Part 5.
  3. You do not need to try and handle expressions such as (trace a b c); if you can handle (trace a), (trace b), and (trace c), that will be adequate.
  4. 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.