Final project due
Monday, May 8 at noon

Interpreter Project
Part 6: Meta-Circularity

Be sure that the code you have written so far can pass the tests provided for you in the i-tests file from Part 5. You should add your own tests cases to make sure that your interpreter is working properly.

If you are still working on Part 5, please let me know if you need help.

As in previous steps, use update37 to download Part 6, and use the accompanying merge program to merge to your code from Part 5 with new code provided in Part 6. Note that there aren't any tests provided in Part 6, you should write your own.

This is the final section of the interpreter. You will begin (and possibly complete) the process of making your interpreter meta-circular.

There will also be Extension 3, which you can implement for extra credit; however, you will need to have completed Extension 1 completed in order to complete Extension 3.

Be sure to read the final section which describes the files you should turn in when you have completed all sections of the project.

Your interpreter is sophisticated enough to be able to execute Scheme programs of substantial complexity. Aside from a few examples (most notably, the stream examples), your interpreter can evaluate all the code you have written in this course so far. In fact, with just a few more modifications, it's possible to run the interpreter itself in the interpreter. Interpreters that can do this are called "meta-circular" interpreters. Of course, the resulting "meta-interpreter" can do the same thing, yielding a "meta-meta interpreter", which of course can do the same thing, yielding...

Adding all the necessary primitives

The first step to take in order to make your interpreter become meta-circular is to ensure that every primitive and special form that you have used in writing this project has been implemented in your interpreter. Below is a list of the most common primitives and special forms you may have used (excluding map and apply). However, depending on your particular implementation, you may have used others which you must also implement.

not, void, void?, string?, pretty-print
cadr, cdar, caddr, cadar, et cetera
list-ref, pair?, read

Next, there are a number of primitives you have likely never even heard of before, but which are now part of your program because I have included them in the code I gave you in Part 6 as part of implementing load (which is described in another section). The primitives you will need to add are:

eof-object?
open-input-file 
close-input-port

Implementing map

Scheme's primtive map requires that the first argument be a Scheme procedure (which Scheme displays as something like #<procedure:3:5>). However, when our interpreter sees a procedure, it turns it into a closure, not a Scheme procedure. For this reason, unlike with other primitives, we cannot directly use Scheme's map primitive. Instead, we must implement map ourselves.

We will only implement the basic version of map which takes two arguments, a procedure and a single list, and provides as output a new list where each element is the result of applying the procedure to each item in the list. For example:

INTERPRETER> (map (lambda (n) (+ n 1)) '(1 2 3 4 5))
(2 3 4 5 6)

Note: While you might not care about the difference, doing what we just did for map -- and what we're about to do below for apply -- means that in our interpreter, map and apply are special forms, whereas in Scheme, they are primitives.

Completing the implementation of apply is required for meta-circularity since it was used in defining apply-primitive-procedure. The implementation of apply is trivial.

We can't use Scheme's primitive apply for the same reason that we couldn't use Scheme's version of map: namely, that Scheme's version expects Scheme procedures, not our closures.

The syntax for apply is: (apply proc list-of-args) where proc is a procedure and args is a list of arguments to pass to the procedure. The result of the above statement is to call the function proc with the arguments stored in the list-of-args. For example, (apply cons '(a (b))) will give you (a b). You may wish to try a few examples in Scheme first, just to make sure you understand how apply is working.

You'll certainly notice the similarities between the Scheme procedure apply and the procedure i-apply you wrote: both take a procedure and a list of arguments to apply the procedure to. This should indicate to you that to get apply working in your interpreter, you are going to want to make a single call to i-apply. Your only job, therefore, is to figure out what parameters you should be passing. Then add a line to i-eval to test for apply.

The implementation for eval-and and eval-or are nearly identical. Write one first, then copy-and-paste and make the necessary small modifications.

Note that both functions can handle an arbitrary number of predicates, anything that isn't #f is considered true, and that both functions always return the result of the last tested item.

(define x 5)
(define y 20)

(or (= x 3) (< y 10) (+ x y) (< y x)) ; => 25  -- no, that's not a typo
(and (= x 5) (< y 30) (+ x y) (< x y)) ; => #t
(and) ; => #t
(or) ; => #f

Actually implementing meta-circularity

Believe it or not, you don't need to write any more code to get meta-circularity to work. However, the code you already wrote might not work as well you thought it did -- and you may need to go back and alter a few things. To make things worse, debugging a meta-circular interpreter is quite difficult. That said, many students have accomplished this in years past, so there's no reason you can't do it too!

One way to test whether or not your interpreter is meta-circular, is to copy and paste all of your code, excluding any lines that begin (require (lib ...)) and (trace ...), from interpreter.ss onto the INTERPRETER> prompt. (Be sure you press Enter after you paste your code or Dr. Scheme won't even begin evaluating what you've pasted!) Unfortunately, doing this is EXTREMELY slow -- probably due to a bug in Dr. Scheme -- because Dr. Scheme insists on highlighting each line a darker shade of green as it is being read, and for some strange reason, this takes a while.

The other way to test it, and the way that I will test it after you have handed it in, is to simply load your file into your interpreter. The eval-load function will read any file, evaluating each statement one-by-one, and return void. To help you in debugging problems, the eval-load function prints out the result of evaluating each statement in the file you are loading. (Note: If you'd rather mimic Scheme's behavior a little more closely, you can change the line (i-print (i-eval user-input env)) to (i-eval user-input env) in the eval-load function and omit the printing of each statement as it is evaluated.) I've written all of the code for loading files, you just need to add the following line to your i-eval function:

      ((load? exp) (eval-load exp env))

To help you try it out, I have included a small file in the i-6 directory. First run your interpeter, then at the INTERPRETER> prompt, type (load "test.ss"). The test program will define two functions which compute factorial: a recursive process solution, factorial-r, and an interative process solution, factorial-i. When each function is loaded, it's name will be displayed. Once it is loaded, try out each function:

(factorial-r 5)
(factorial-i 5)

Assuming that things worked, it's time to try loading your interpreter into itself. At the INTERPRETER> prompt, type (load "interpreter.ss"). You will see each function name printed out as it is loaded into your interpreter. It may not work the first time. Getting your interpreter to read in all of its own code can be challenging.

When you get the INTERPRETER> prompt after loading the interpreter.ss file, your interpreter has actually loaded all of its own code into itself... which means you can now type (repl) and run your interpreter inside of itself...

If, after typing (repl) you get the INTERPRETER> prompt, that prompt is actually from your interpreter running inside of itself!

Now it's time to see if your interpreter running inside of itself works. Many times, you can get to the INTERPERTER> prompt but some simple things (like primitives) don't work. So, try running some simple tests of your interpreter running inside itself. When you are confident it is working, try some more difficult tests.

When you think it's working, now it's time to try loading your interpreter into your interpreter which is already running in your interpreter. Type (load "interpreter.ss") and press enter. This will now load your interpreter code into your meta-circular interpreter. When it is complete (it may take 5-10 minutes), and you are presented with the interpreter prompt, it means you can just run (repl) again, and now you are running your interpreter in your interpreter in your interpreter, in Dr. Scheme. Test it out on something really simple, like (+ 3 4). It may take two or three minutes to give you an answer.

Finally, if you are daring, and you have a lot of time to kill, you can load your interpreter into itself again. Expect to wait a very long time. I'd recommend going to lunch, taking a walk, and going to dinner, maybe even going to sleep, and waking up the next morning to see if it finished. I started mine running and came back 4 hours later and it was still going... it can be very very slow. However, if you get a new prompt, type (repl) to run the meta-meta-meta-meta-interpreter and expect to wait a very long time for anything to happen. Theoretically you could keep doing this forever, but I doubt you'd want to try -- or wait.

You will not receive full credit for the interpreter unless:

1. You use handin37 by noon on Monday, May 8 to turn in the final version of your code. No late projects will be accepted.
2. Your interpreter.ss has all debugging statements removed and you have no functions that are traced. It may be helpful to comment your code if you believe I may have a difficult time understanding functions you have written. Add comments only where you feel they are necessary.
3. Your code is organized so that similar portions go together. (Unless you moved things around, it should already be organized in this way.)
4. Your program executes! You will be penalized substantially if the file you turn in produces errors simply trying to execute the code. In other words, if I press the Run button, your program should not produce any errors.
5. Your i-tests.ss file includes the tests for all of the portions of the interpreter (both my tests and your tests).
6. You write a README file (2-3 pages long) that gives an overview of how your interpreter works and explains any special features that you have added to your language. This file should be a text file that you create in emacs or drscheme, not a Microsoft Word (or other word processing) document. In your overview, you should describe the steps your interpreter must go through when handling the following expressions:

   INTERPRETER> (define f (lambda (n) (if (= n 1) 1 (* n (f (- n 1))))))
   f
   INTERPRETER> (f 4)
   24
   

   You may want to trace i-eval to be sure you understand all of the steps that are being done. However, you should not include the trace in your overview. Simply explain what happens.
7. You make sure that if sections of the interpreter don't work, you comment this adequately and keep your interpreter from crashing. In addition, you should describe them in the README report. If there are required features that you didn't implement, you need to state that in the report as well.