Due: Wednesday, June 3, 2026, at 5pm

Starter code: p8_setletrec.zip or p8_setletrec.tar
Upload solutions via Gradescope

Goals

This assignment is designed to help you with the following:

• continuing to evaluate Scheme expressions
• getting enough to try and really bootstrap Scheme

Collaboration policy

For this assignment, you may work alone or with a partner, but you must type up all of the code yourself. (It is therefore unexpected for two code submissions to be completely identical.)

If you worked with a partner for P5/P6/P7, you must work with the same partner or work alone for P8.

You may also discuss the assignment at a high level with other students.

You should list any student with whom you discussed the assignment, and the manner of discussion (high level, partner, etc.) in your readme.txt file.

If you work alone, you should say so instead.

Assessment

Core requirements:

• all CR tests pass
• your code uses some helper functions to simplify your code
• readme.txt contains your collaboration statement, sources, and reflection

Advanced requirements:

• satisfy the Core requirements
• all AD tests pass
• each function has a comment before it describing its high-level behavior
• your code uses good C coding style, including using helper functions to reduce the size/complexity of your code

Assignment overview

We’re on the home stretch – for this final part of your interpreter, you will add the following functionality:

• set! special form
• < built-in function
• equal? built-in function

In addition, as part of the AD requirements you will add:

• letrec special form

Special form: set!

You can 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 frame (unlike how we’ve restricted the testing of your define implementation). We’ll have set! return a VOID_TYPE, similar to define.

Primitives: < and equal?

The < function should return a boolean indicating whether one number is smaller than another.

For equal?, you only have to handle numbers, strings, and symbols; it does not need to perform any sort of deep equality test on a nested structure. Also, for symbols you should feel free to just check whether the symbols are the same (e.g., (define a 1) (equal? a a) would return true, whereas (define a 1) (define b 1) (equal? a b) would return false).

Special form: letrec (AD only)

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

Optional extensions

The work in this section is 100% optional and does not contribute to your grade in any way. Still, if you’re looking for an extra challenge or ideas on what to practice to study the material, there will be occasional “optional extensions” sections of assignments that contain one or more additional exercises to try.

Here are some optional extensions that naturally arise at this part of your interpreter project:

• Implement the following functions: >, = (just like equal? but works only with numbers), <=, >=, not, list, map.

• Implement the following special forms: let*, and, or, cond.

One final extension I’ll list here is that you could add 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:

$ ./interpreterRepl
> (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 (use man isatty in the terminal–although not in docker–to learn more). You should only print the prompts if stdin is 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.

If you really want to dive into this approach, optionally figure out how to use the readline library to provide things like history and editing for your REPL.

Getting started

As before, you should download the starter files as a zip file or tarfile, unzip that file, and copy the folder to where you’ll work (probably your ProgrammingLanguages folder). Refer to the Assignment 1 instructions if you’re unsure what to do.

In the starter code, you should find the same files as in the tokenizer assignment, with the following notable changes:

• schemeitem.h: updated to include UNSPECIFIED_TYPE in item_type_t

Copy over your .c files from P7.

Like in P7, you can also use provided binaries instead of your own previous code for parts P1–P4. However, I am not providing a working if/let/quote/define/lambda/etc. interpreter; the code for evaluation is too intertwined for us to be able to stub out parts for you.

Notes on testing your code

The tests for this portion use both your old functionality and this new functionality together, which may 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, not just print statements and reading code. (Personally, I recommend using gdb in the terminal.)

Implementing letrec

Still not quite sure how to interpret letrec? Here is a rough guide to evaluating (letrec ((x1 e1) ... (xn en)) body1 ... bodyn) with current frame f, although it doesn’t include all needed error checking:

1. Create a new frame frame with parent f.
2. Create each of the bindings, and set their values to UNSPECIFIED_TYPE (see schemeitem.h for this addition).
3. Evaluate each of the e1, …, en using frame.
4. After all of these evaluations are complete, replace bindings for each xi to the evaluated result of ei (from step 2) in frame.
5. Evaluate body1, …, bodyn sequentially using frame, returning the result of evaluating bodyn.

Testing your work

To run your code, first create a file with some of your own Scheme code in it. Look back at the instructions from the tokenizer assignment for using your own Scheme program.

As with previous assignments, there are CR and AD tests for core and advanced functionality. Look at the instructions from A2 if you want a refresher on how to run these tests.

For the interpreter project, the tests will fail if your code has compiler warnings and/or valgrind errors, so make sure to run the tests in the Docker environment.

Submitting your work

For this assignment, you will submit just one code file. You are strongly encouraged to run ./zipitup to use that script to gather your files for Gradescope.

C code

The file interpreter.c should contain your functions. Make sure to add a comment above each of your functions (including any helper functions you choose to write) to describe its behavior at a high level (e.g., what it takes as input and what it returns as output).

You may choose to add additional files to store your evaluation functionality. If you do, make sure to update your justfile as well.

Readme

For each assignment for this course you will also need to submit a file readme.txt in which you should write:

1. Your collaborations with anyone on the assignment
2. Your use of any outside sources on the assignment
3. Your reflection

You should be specific about your collaborations and sources – they shouldn’t just be empty or lists of names of people. If you worked alone and/or did not use any outside sources, you should say so.

For your reflection, spend a couple of sentences answering the following:

• Were there any particular issues or challenges you dealt with in completing this assignment?
• How long did you spend on this assignment?

Submitting to Gradescope

As always, use ./zipitup to gather your files. Submit the resulting .zip file to Gradescope.

Note that it is possible (although unlikely) that the tests will pass on your computer but fail on Gradescope. If this happens, it’s probably because you coded something in an unusual way. Double-check that you’re submitted to the correct assignment and then check if any error messages can help you troubleshoot. If you’re still having issues, check with Tanya.