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

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

Goals

This assignment is designed to help you with the following:

• continuing to evaluate Scheme expressions
• using function pointers to add your own built-in functions

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

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

Just want to get started? Jump ahead to suggestions for your code, then come back here when you’re ready to read the specifics about each primitive function.

You can almost execute some of your early Scheme programs! For this penultimate part of the project, you will add the ability for your interpreter to execute the following built-in functions: +, null?, car, cdr, cons, and (for AD requirements) append.

For all functions, you should have error checking to make sure the number of arguments is as expected.

Primitive: +

The + function should be able to handle any number of integer or real arguments (if there are no arguments, it should return 0). If any of the arguments are reals, return a real; otherwise, return an integer.

Primitives: null?, car, and cdr

These functions should take one argument each. You need to check to make sure that the argument is appropriately typed.

Primitive: cons

The cons function should take two arguments. You’ll also need to modify the code you have that handles output, because cons allows you to create non-list pairs. You’ll need to add functionality to use a dot to separate such pairs. This portion of the Dybvig Scheme book does a decent job at describing how such output should work. (Note that the display function in our linkedlist binaries won’t work on pairs such as this one. If you’re using our binaries and using the linkedlist display function, you’ll need to write your own instead.)

Primitive: append (AD only)

The append function should take two arguments; we will not support append with varying numbers of arguments even though Guile allows this. The first argument must be a list (add error checking for this–an empty list does count as a list for this purpose!), and the second can be any type. Like with cons, this will mean needing to be able to display non-list pairs. For example:

(append (quote (1 2 3)) 4)   ; evaluates to: (1 2 3 . 4)

Note that append works by making a copy of its first argument but not its second (copying versus not won’t matter much now, but it will when we add in set! in the final part of this project). This should be a shallow copy, meaning that we create new cons cells to represent the outermost list layer, but nested lists will still point to shared memory.

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 additional functions: list and map.

• Implement the following primitives: -, *, and /.

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 PRIMITIVE_TYPE and pf in scheme_item_t

Copy over your .c files from P6.

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

Implementing primitive functions

Primitives are functions not implemented in Scheme; you’ll implement them as C functions that get called by your interpreter directly. There is one bit of trickiness that will come up: you’re going to want to have both functions-as-closures and functions-as-primitives. As we discussed in class, you can use a new PRIMITIVE_TYPE we’ve added to schemeitem.h. This will be for a scheme_item_t that represents a pointer to a function. Here’s how the additional portion appears:

typedef enum { INT_TYPE, ..., PRIMITIVE_TYPE, ... } item_type_t;

typedef struct scheme_item_t {
    item_type_t type;
    union {
        int i;
        ...
        // A primitive style function; just a pointer to it, with the right
        // signature (pf = primitive function)
        struct scheme_item_t *(*pf)(struct scheme_item_t *);
    };
} scheme_item_t;

Here are some snippets of code you can make use of, using our sqrt example from class (see Lesson 24 classwork):

/*
 * Uses the C sqrt function to compute the square root
 * of the int/real value in args.
 * Raises an error if more than one arg or invalid type.
 */
scheme_item_t *primitiveSqrt(scheme_item_t *args) {
    ...
}

/*
 * Add a binding between the given name and the input
 * function; used to add bindings for primitive functions
 * in the top-level (i.e., global) bindings list.
 */
void bind(char *name,
          scheme_item_t *(*function)(scheme_item_t *),
          frame_t *frame) {
    ...
}

void interpret(scheme_item_t *tree) {
    ...

    // Make top-level bindings list
    ...

    // Then, bind primitive functions
    bind("sqrt", primitiveSqrt, frame);

    ...
}

Note that it really is important that you bind the functions and not just that you look for a primitive function name occurring as the first thing after parentheses. Primitive functions aren’t special forms like if or lambda, and treating them the same way where you look for them to appear directly afer parens will lead to problems if these functions are passed as inputs to other functions or returned as inputs.

For example, your interpreter should support the following:

(define f car)
(f '(1 2 3))   ; evaluates to: 1

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.