This assignment is the final phase of your interpreter. Under college policy, no extensions are allowed past the end of the last final exam.
This last stage consists of a list of additions to make to your interpreter. This assignment is perhaps longer than many of the others, for two reasons; all portions within it are independent, and it gives you more flexibility at this busy point in the term to work on your project. That said, don't underestimate the amount of work here; this assignment has more individual pieces to do than any of the other interpreter project parts.
Required additions to your interpreter are as follows:
Here are some more detailed specifications. As in some previous assignments, I have included links for more detail to "The Scheme Programming Language" by R. Kent Dybvig. Though we're technically working with the Racket dialect of Scheme, all of the features below that you are implementing are the same between both languages (at least, they are for our purposes), and I find Dybvig's writing to be clearer than the Racket language reference.
let*: Read the specification in Dybvig. You might implement this by using a new frame for each binding, or by adding to a single frame as you evaluate more definitions.
letrec: Read the specification in Dybvig. One particular statement Dybvig makes is "The order of evaluation of the expressions is unspecified, so a program must not evaluate a reference to any of the variables bound by the letrec expression before all of the values have been computed. (Occurrence of a variable within a lambda expression does not count as a reference, unless the resulting procedure is applied before all of the values have been computed.) If this restriction is violated, an exception with condition type &assertion is raised." For purposes of this assignment, you do not have to perform this particular bit of error checking. By avoiding this, I was able to make my implementation of letrec nearly identical to my implementation for let, where the key difference was which frame I used to evaluate expressions. Of course, you can add in this error checking if you wish as an optimal extension.
set!: Read the specification in Dybvig. This should be similar to define, except that it does not create a new variable; rather, it modifies an existing one.
begin should evaluate each of its arguments and return the result of the last argument. Read the specification in Dybvig. (DrRacket additionally adds an alternative wacky other implementation of begin that behaves differently at the top-level. You don't need to implement this version.)
You may assume that all of the conditions for cond have type boolean; we will not test otherwise. Your code for cond should allow either #t or else as a default case. (If you've done things right, #t should work automatically; you'll need to code else as a special case.)
For both cond and begin, if there's nothing to return (i.e. zero arguments to begin or no true cases for cond), return VOID_TYPE.
Strangely, cond technically allows additional arguments or none at all following the condition, like
(cond (#t 3 5 7))
(cond (#t))
We will not test any cases like this, and you do not need to implement them.
More primitive functions. Feel free to add others to get your old Scheme code working. The following functions are required:
Arithmetic: *, -, /, modulo, <, > and =.
Here are some optional additions that I encourage, in addition to other optional ideas I have suggested throughout the project. If you have implemented anything optional, explain what you have done in a readme.txt file.
A simple interface. The classic core of an interpreter is the read-eval-print loop, a.k.a. REPL. You can add this functionality to your code so that you can more easily use your interpreter interactively. For example:
$ ./interpreter > (define factorial . (lambda (n) . (if (= n 0) . 1 . (* n (factorial (- n 1)))))) > (factorial 5) 120 >
One issue you will run into with this is you get unnecessary printouts of prompts when you are using a file for input instead of typing the code in manually. You can figure out whether the interpreter is being called interactively using the isatty and fileno functions (man isatty). You should only print the prompts if stdin is not interactive.
Note that you can end an interactive session by typing Ctrl-D (sending an "end-of-file" character), so there is no need for a "quit" command.
Your code should have no memory leaks or memory errors when run on any input (correct or incorrect) using valgrind. We will be checking this during grading.
Submit via git as usual, and tag your submission as complete. If you need to resubmit, create another tag with a dot extension, such as complete.1, complete.2, and so on. Make sure that you both push your tags and your code itself, as in:
git tag complete
git commit -am "We are done!"
git push
git push --tags
Add at least four more tests to your test files that test the functionality of the primitives you have added. Indicate in a readme.txt file which tests are designed to be testing this assignment in particular.
Each pair of files should be named interpreter-test.input.XX and interpreter-test.output.XX, where XX is a test number. It should be the case that if I run the following command then I get no output:./interpreter < interpreter-test.input.XX | diff interpreter-test.output.XX -
When we test your code for grading purposes, we will use our own set of test files which we will run using exactly the same command as described above. Test carefully.
Your code should have no memory leaks or memory errors when run on any input (correct or incorrect) using valgrind. We will be checking this as well during grading.
Remember, you can test your code in valgrind this way:
./valgrind.sh < interpreter-test.input.XX
Have fun interpreting!
This assignment was originally created by David Liben-Nowell and has since been updated by Dave Musicant and Laura Effinger-Dean.