Part 5 - Evaluating if/let/quote

Due: Monday, May 18, 2026, at 10pm

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

Goals

This assignment is designed to help you with the following:

  • beginning to evaluate Scheme expressions, starting with litrals and symbols, as well as if, let, and quote special forms

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

Now that you (should) have a working parser, you are welcome to change up partners for the rest of the term. If you’re changing partners from P4, you are expected to still complete your original P4 code without looking at what your new partner has done.

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
  • a visual inspection of your code shows that you have not hyper-tailored it to pass the tests
  • your code uses some helper functions to simplify your eval function
  • readme.txt contains your collaboration statement, sources, and reflection

Note that hyper-tailoring in this case 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 other similar inputs.

Advanced requirements:

  • satisfy the Core requirements
  • all AD tests pass
  • your code is not significantly more complex than needed to accomplish the task
  • 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 eval function

Assignment overview

Just want to get started? Jump ahead to suggestions for your code, then come back here when you’re ready to dive more deeply into the nitty-gritty details of evaluating Scheme.

It’s finally time to start evaluating Scheme! In this part of the interpreter project, you’ll handle simple atoms (expressions that aren’t lists) as well as a few special forms. Specifically, you must support the correct evaluation of the following types of Scheme expressions:

  1. Boolean, integer, real, and string literals; they evaluate to themselves

  2. (if condition trueExpr falseExpr)

  3. (let list-of-bindings body); you will need to implement the creation of new frames

  4. Symbols; now that you’ve implemented let and frames, you should be able to evaluate a bound symbol

  5. (quote expr); you’ll also need to be able to support the abbreviated form 'expr (your parser should already be converting 'expr into (quote expr))

When you’re done with this part of the project, you should be able to evaluate very simple programs like this:

(let ((x #t)) (if x 25 1))

The above program should evaluate to 25.

Environment model of evaluation

Recall the environment model of evaluation that we’ve been talking about in class: we want to evaluate an expression x in an environment e (i.e., a chain of frames):

  1. If x is a literal, its value is that literal.

  2. If x is a symbol, look up its value in e.

  3. If x is of the form (if condition trueExpr falseExpr), evaluate falseExpr if condition evaluates to #f, and instead evaluate trueExpr otherwise. (In other words, you should treat any resulting value of condition that is not #f as true.)

  4. If x is of the form ((let ((var1 expr1) (var2 expr2) ... (vark exprk)) body)), do the following: a. Create a new frame f whose parent frame is e. b. Evaluate each expri in frame e; add a binding in f from vari to the result of evaluating expri. c. Evaluate body using frame f and return the result.

…

n. Otherwise, x must be of the form (e1 e2 ... ek), so evaluate each ei and invoke the procedure that is the value of e1 given the values of each of the other sub-expressions. (You don’t have to do this yet.)

You’ll do all of this inside a function named eval:

scheme_item_t *eval(scheme_item_t *tree, frame_t *frame);

Frames and bindings

What is a frame? As we’ve discussed in class, a frame is a pointer to its parent frame as well as a collection of bindings. A binding is a mapping from a variable name (i.e., a symbol) to a value.

Bindings are created whenever we introduce new variable names. For example, in the following program, the bindings for x and y are stored in a single frame:

(let ((x 5) (y "hello"))
  (if #t x y))

You will have to construct a new frame whenever eval encounters a let special form. This frame should be passed in when calling eval on the body of the let expression; this frame will be used to resolve (find the value of) each variable encountered while evaluating the body.

You will need to implement data structures for frames and bindings. The easiest approach is probably to use linked lists. The linked list of frames essentially forms a stack: you push on a new frame just before evaluating the body of the let expression, and pop the frame off before returning (although the “pop” really happens automatically when you return from eval). Within each frame, you should store a list of bindings (i.e., variable-value pairs) using another linked list. When you need to resolve a variable, check the current frame first, then its parent if you haven’t found it, then the parent’s parent, and so on until you reach a frame with no parent (i.e., the global frame).

Evaluation errors

There will be many cases in which evaluation is not possible. For example:

  • When an if expression has fewer than 3 arguments. (Technically Scheme has two syntaxes for if, but we’re only going to support the one with 3 arguments).

  • When an if expression has more than 3 arguments.

  • When the list-of-bindings for let does not contain a nested list.

  • When you encounter a variable that is not bound in the current frame or any of its ancestors.

  • …

In any of these cases, you should print "Evaluation error" at the start of your error message so that the tests will pass. You might enhance these messages by adding more text, like "Evaluation error: if has fewer than 3 arguments". While these more detailed error messages are not required, writing better error messages may help you now or later in the project with debugging, as if things go wrong when they shouldn’t, you’ll have a better sense for what happened.

After printing the error message, your program should immediately quit, making sure to use texit to clean up memory on your way out.

Multiple S-expressions

As discussed in the parser assignment, a Scheme program is a list of S-expressions. Your interpreter should follow a read-evaluate-print loop: after evaluating a given S-expression, it should print out the result of that evaluation. You can do this by completing the function interpret, which is a wrapper that calls eval for each top-level S-expression in the program.

Some other parts of the Scheme program may also have multiple S-expressions, such as the body of a let. If the body of a let has multiple expressions, you should evaluate each one of them, and return the rest of the last one as the value of the entire let expression.

Advice for quote

You should not implement quote by trying to somehow wrap the quoted expression in some sort of enclosure indicating that it is quoted.

You may feel tempted to do otherwise! You may even be convinced that storing quote or a single quote somehow explicitly after evaluation will help you in some way. You may even find that by doing so, you can succeed at this task. Don’t do it; it’s a trap! It may help you get this part of the project to work, but you’ll find yourself in hot water later, and it will be much more frustrating to go back through your old code and fix it then.

This reflects a common and interesting point of confusion: quote does not tell the interpreter to do something to its arguments. Rather, it tells the interpreter to not do something.

If you are feeling a strong urge to annotate something indicating that an expression is quoted, don’t do it. If you are experiencing such compulsions because your tree is not printing properly, the experience of past students in this course has sometimes been that the problem is the code for printing the parse tree, not structuring it in the first place.

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:

  • display function:: You can implement the Scheme function display to print out the value of a given expression. (See this section of Dybvig for more info.)

The simplest cases to get you started are these:

(display x)               ;; displays value of a particular variable
(display "Hello, world!") ;; displays a particular string without the quotes

You can handle non-printable characters (newlines, tabs, etc.) inside the strings in any reasonable way, as long as the code doesn’t crash.

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 a struct for a frame

  • interpreter.h: the header file for the functions you’ll need to write for this assignment

Copy over your .c files from your Parser assignment. You’ll also create a new file interpreter.c for this assignment.

Like in P3 and P4, you can also use provided binaries instead of your own previous code. However, you won’t have provided binaries available for parts beyond the parser, because the code for evaluation is too intertwined for us to be able to stub out parts for you.

Evaluating Scheme

At the core of your interpreter, you will need to implement a function eval to evaluate Scheme code. Given an expression tree and a frame in which to evaluate that expression, eval returns the value of the expression.

Here is a rough sketch of what your eval function might look like at first (but don’t forget to go back and refactor to add more helper functions!):

scheme_item_t *eval(scheme_item_t *tree, frame_t *frame)
{
    // TODO: declare a variable to store the resulting value
    ...

    // Act out what we've been discussing in class
    switch (tree->type)
    {
        // Option #1: literal
        case INT_TYPE:
            ...
            break;

        case ...:
            ...
            break;

        // Option #2: symbol
        case SYMBOL_TYPE:
            ...
            break;

        // Options #3-#n: some expression stored as a list
        case CONS_TYPE: // Q: how could the following be its own function?
            scheme_item_t *first = car(tree);
            scheme_item_t *args = cdr(tree);

            // Do some error checking
            ...

            // Special form: if
            if (strcmp(first->s, "if") == 0)
            {
                result = evalIf(args, frame); // helper functions for the win!
            }

            // Handle other special forms...
            ...

            // Error: unrecognized form
            else
            {
                evaluationError();
            }

            break;

        ...
    }

    ...
}

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

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.