Interpreter 9: Final Part

Table of Contents

This assignment is the final phase of your interpreter! It involves implementing several additional special forms and primitive functions, such that most of the code we wrote at the beginning of the term could now be run in your interpreter.

Note that this assignment is due at 10pm on the last day of class. You cannot use late tokens on this assignment. If you need an exception to this policy due to extreme circumstances, reach out to your class dean and me (Anna).

This assignment is to be done individually.

You can talk to other people in the class, me, and any of the course staff (graders, lab assistants, prefects) for ideas and to gain assistance. You can get direct help debugging your code from me and any of the course staff, and you're welcome to show us your code during debugging or other conversations. The code that you write should be your own, and you shouldn’t directly show or share your code with other students (although you may discuss general debugging strategies with others). Similarly, you should not look at other's code. See the course syllabus for more details or just ask me if I can clarify.

Both you and your interpreter partner can access your code from the previous part by downloading it from Gradescope. You should not work with your interpreter partner on this assignment.

1. Get started

You'll download the folder with the starter code from the link below. Like for previous homeworks, unzip the folder and move it to where you'd like: most likely the folder for the Docker container. Then get started in VS Code.

If when running tests you run into a permissions error, you can fix this by running the following code in the terminal: 

chmod a+x test-e test-m

This tells the computer that all users should be permitted to execute (run) the files test-e and test-m.

Click here to download the starter files

2. Functionality

Required additions to your interpreter are as follows:

2.1. Some missing special forms

Implement the following special forms: letrec and set!.

  • letrec: Recall that letrec allows you to define (mutually) recursive procedures. Take a look at the specification in Dybvig. The key difference from let is that the bound variables can be accessed from other variables bound in the same let, but unlike let*, the values can't be accessed until all expressions have been evaluated. For instance, consider:
(letrec ((x 3) (y x)) 
  x)

This violates the description in Dybvig that "The order of evaluation of the expressions expr … 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." The specification says that if this restriction is violated, an exception (i.e., evaluation error) should be raised. However, Guile doesn't handle it correctly! It prints 3. Your interpreter should handle this correctly by raising an evaluation error.

Similarly, consider: 

(define y 5)
(letrec ((x y) (y x))
    x)

Again, the value of a variable is accessed before all variables are bound, so your interpreter should raise an evaluation error. This differs from Guile, which appears to print nothing in response to this.

Still not quite sure how to interpret letrec? Here's a rough guide to evaluating (letrec ((x1 e1) ... (xn en)) body1 ... bodyn), although it doesn't inclue all needed error checking:

  1. Create a new frame env’ with parent env.
  2. Create each of the bindings, and set the to UNSPECIFIED_TYPE (this is in schemeitem.h)
  3. Evaluate each of e1, …, en in environment env’.
  4. After all of these evaluations are complete, replace bindings for each xi to the evaluated result of ei (from step 2) in environment env’.
  5. Evaluate body1, …, bodyn sequentially in env’, returning the result of evaluating bodyn.
  • set!: Read the specification in Dybvig. This should be similar to define, except that it always modifies an existing variable, and may be used in contexts outside of the global environment (unlike how we've restricted the testing of your define implementation). We'll have set! return a VOID_TYPE, similar to define.

2.2. One more primitive functions

Implement < (the less-than function)

2.3. Notes on testing your code

The tests for this portion use both your old functionality and this new functionality together, which may mean lead to finding some bugs in your old code. Part of completing this assignment may involve some debugging that is not directly related to the new functionality. One note from past experience is that until now, we have had limited ability to test if you are doing the right thing when you have a let or lambda with multiple bodies. In both cases, each body should be evaluated (starting from the first), and the result of evaluating the final body should be returned.

I strongly encourage you to implement one new piece of functionality at a time, testing with small test cases as you go, and to use a debugger for debugging. This can be visually in VSCode or using gdb on the command line.

#+BEGINCOMMENT

3. Exemplary functionality

There is some functionality that your interpreter will likely need if you want your interpreter to successfully run with the Scheme assignments that you built earlier this term. I'm putting all of this functionality in the "exemplary" category. If you are swamped for time and are looking for just "meets expectations," you can skip this section.

  • Implement cond.
    • 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.)

    • 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.

    • If there's nothing to return (i.e. no true cases for cond), return VOID_TYPE.
  • Additional primitive functions:, *, /, and modulo.
    • * should be able to take any number of numeric arguments >= 2, but for the other functions you may assume two numeric arguments (i.e., print evaluation error if not).
    • / should return a real (i.e., double) if the numbers do not divide evenly. (Guile returns a fraction; don't do this.) For example, (/ 5 2) should return 2.5. We will only test division with two arguments.
    • modulo may further assume that its arguments are integers. We will not test non-integer cases for modulo.

#+ENDCOMMENT

4. Starter files and your code

The files follow the same structure that they have for the previous assignments. You'll then need to add in the files from your previous version, and/or switch over to using our binaries. But note that the binaries I provide only go through part 4 of the project; I am not providing a working if/let interpreter. (The project gets too intermingled at this point for me to be able to supply complete partial work.)

Building and testing your code will work precisely the same as on the previous assignment.

5. How to test and submit your work

For this final assignment, please note that if you haven't already, you must fill out the partner evaluation form (linked on Moodle) in order to earn an E or an M. The deadline for this for is the last day of classes, and it is required even if you worked individually.

5.1. Testing your work

Go back and look at the sections at the end of Scheme Intro 2 labeled "How to test your work". Everything there about how to run M tests and E tests applies identically here. Note that the tests will fail if your code has compiler warnings and/or valgrind errors, in addition to if its behavior is observably incorrect.

5.2. Submitting your work

You'll submit your work on Gradescope. You should already have a file CollaborationsAndSources.txt in your working directory (if not, copy it over from the previous assignment). Go to the header for this portion of the assignment and fill in the document. Indicate in what ways (if any) you collaborated with other people on this assignment (did you talk with anyone other than Anna or our prefect? Did you share strategies with anyone? Get or give advice on debugging? These are fine things to do, and you should note them in the CollaborationsAndSources.txt file). If you used any resources outside of your notes from class, that is also something to note in CollaborationsAndSources.txt. If you didn't talk with anyone or use any outside sources, please note that explicitly.

After updating CollaborationsAndSources.txt and finishing the assignment, run ./zipitup

This will zip up your C files, header files, and collaborations and sources. We will be re-copying in our version of the tests and of the included header files.

Then, upload the created zip to Gradescope.

On Gradescope, you should see autograder output for the same tests as you ran locally. There is a small but nonzero chance that you have coded something unexpected that cause the tests pass on the computer you’re working on, but not on Gradescope. We will be grading this assignment based on the results of the tests on Gradescope, so you should make sure to pay attention to how the tests run there as well when you submit.

For grading, you'll earn at least an M if the following conditions are all met:

  • All M tests pass
  • A visual inspection of your code shows that you have not hyper-tailored your code to pass the tests. Hyper-tailoring your code would be doing things like checking for the exact input from the test, meaning you haven't written your code in a way that would work for similar inputs see Homework policies for more on this).
  • You have a CollaborationsAndSources.txt with the information described above.
  • The work is submitted by the deadline.

You'll earn an E if:

  • All conditions above for an M are met.
  • All the E tests pass.
  • Your code is not significantly more complex than needed to accomplish the task.
  • You have a comment before each function describing what the function does (its input/output behavior, not a play-by-play of "first checks… then makes a recursive call …").

If your code does not meet the criteria for an M or an E, then you'll earn a grade of NA (Not Assessable) or SP (Some Progress) for the assignment. Not Assessable means that your submission does not have an attempt at one or more functions in the assignment. Some Progress means that your submission has some code (in the correct language) for all functions in the assignment, but that the code does not pass all of the M tests, is hyper-tailored to the tests, and/or is missing a CollaborationsAndSources.txt file.

Good luck, ask questions, and have fun! When you've completed this assignment, you'll be able to run pretty complicated Scheme code, including code from earlier assignments.

This assignment was originally created by David Liben-Nowell and has since been updated by Dave Musicant, Jed Yang, and Laura Effinger-Dean. Thanks for sharing!