Due: Friday, May 22, 2026, at 10pm

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

Goals

This assignment is designed to help you with the following:

• continuing to evaluate Scheme expressions
• working with define and lambda special forms
• implementing closures and using them in procedure application

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, you must work with the same partner or work alone for P6.

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 eval/apply functions
• readme.txt contains your collaboration statement, sources, and reflection

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/apply functions

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 working with frames and closures to support procedure definitions and applications.

You’re making progress! For this part of the project, you will add the ability for your interpreter to evaluate the following types of Scheme expressions:

1. (define var expr)

2. (lambda params body)

3. (e1 e2 ... en); both evaluating the expression and applying the procedure that is the result of evaluating e1

Once you have finished these three, your interpreter will be able to run your own Scheme procedures (even recursive ones!). Here’s a non-recursive example you could store in a file named test_p6.scm:

$ cat test_p6.scm
(define not
  (lambda (bool)
    (if bool #f #t)))

(define testit
  (lambda (cond conseq alt)
    (let ((nconseq (not conseq)) (nalt (not alt)))
      (if cond nconseq nalt))))

(testit #t #f #t)
(testit #f #f #t)

$ ./interpreter < test_p6.scm
#t
#f

Special form: define

Scheme actually has a number of different variations on define; you only need to implement the first one. Unlike let, define does not create a new frame in the environment; rather, it modifies the current frame. You will therefore need to have a “top” or “global” frame that contains bindings of variables created using define. (You can put bindings for primitive functions in this top-level frame too; that will be a later part of this project.)

Recall from P5:

Your interpreter should follow a read-evaluate-print loop: after evaluating a given S-expression, it should print out the result of that evaluation.

However, you should not print anything after a define expression. You could go about this by having define return a scheme_item_t with a new type VOID_TYPE (this has been added to schemeitem.h); then you should only print the result of an expression if it is not VOID_TYPE. There are of course other ways of doing this, but this is my suggestion.

Scheme is able to detect when define is used in the wrong place, but don’t worry about this if you don’t want to. You can just modify the current frame. We will not test for correct or incorrect behavior if define is used anywhere other than the top level. That said, you can add as optional extensions error checking as appropriate.

Special form: lambda

You will need to implement closures. For the purpose of this project, a closure is just another type of scheme_item_t, containing everything need to execute a user-defined function:

1. the formal parameter names (either a list or single item if a variable number of parameters is permitted)
2. a pointer to the function body
3. a pointer to the environment frame in which the procedure was created

We can use a new CLOSURE_TYPE within scheme_item_t: here’s a snippet of the new code in schemeitem.h:

typedef enum {INT_TYPE, ..., VOID_TYPE, CLOSURE_TYPE, ... } item_type_t;

typedef struct scheme_item_t {
    item_type_t type;
    union {
        int i;
        ...
        struct {
            struct scheme_item_t *paramNames;
            struct scheme_item_t *functionCode;
            frame_t *frame;
        }; // For CLOSURE_TYPE
        void *ptr;
    };
} scheme_item_t;

There are two types of lambda in Scheme, and you should support both:

• (lambda (a1 a2 ... ak) body1 body2 ... bodym): the function has a list of formal parameters, and exactly that number of actual parameters must be passed in when we do procedure application

• (lambda args body1 body2 ... bodym): the function has a single varaible name for the formal parameters, and any number of actual parameters can be passed in; when evaluating the procedure, the parameters we pass in will be contained in a list called args

Procedure application

If the expression to be evaluated is of the form (e1 e2 ... en), then you should recursively evaluate e1 through en and apply the value of e1 to the remaining values. To actually apply the resulting procedure from e1, you should create a function called apply:

scheme_item_t *apply(scheme_item_t *function, scheme_item_t *args);

You should call this function after you’ve evaluated each subexpression in (e1 e2 ... en). Here, function is a user-defined function (i.e., a closure). Invoking apply should apply the given function to the (already evaluated) arguments by creating a new frame with the appropriate parent, binding the formal parameter(s) to the actual parameter(s), and then evaluating all expressions in the body of the function sequentially, returning the result of evaluating the final body expression.

Note: You may need to handle binding the parameters slightly differently for the two versions of lambda described above.

When displaying a result, if an S-expression evaluates to a function, you should just output <#procedure>. Let’s say you have a file test_print_proc.scm that just contains a lambda:

$ cat test_print_proc.scm
(lambda (x) x)

$ ./interpreter < test_print_proc.scm
<#procedure>

As usual, your program should never crash or segfault on bad input; just print "Evaluation error" and exit gracefully. You can supplement with more detailed error information if you wish.

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 closures in scheme_item_t

Copy over your .c files from P5.

Like in P5, 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 interpreter; the code for evaluation is too intertwined for us to be able to stub out parts for you.

Evaluating Scheme with procedure application

The changes in this part of the project require us to support function application. Here is an updated 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...
            ...

            // Otherwise, assume it's procedure application
            else
            {
                // TODO: Evaluate a user-defined function
                // TODO: (fill in for P6)
            }

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

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.