Due: Monday, April 27, 2026, at 10pm

Starter code: p1_linkedlist.zip
Upload solutions via Gradescope

Goals

This assignment is designed to help you with the following:

• starting your interpreter project!
• representing a Scheme list in C
• more practice, as always, with pointers, memory, and C

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

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
• the CR tests’ list is displayed in the correct order
• a visual inspection of your code shows that you have not hyper-tailored it to pass the tests
• 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
• the AD tests’ list is displayed in the correct order
• 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

Assignment overview

For this first part of the interpreter project, you’ll create a linked list that you’ll then use throughout the rest of the project. This code will stay with you the rest of the term, so it’s worth commenting well, making sure you’ve organized it in a way that’s readable, etc. Future-you will thank current-you if you use good style and structure!

Representing a list element

One of the first questions to arise will be: “What is this a linked list of? Integers? Strings? More lists?” The catch is that you’ll be storing lists created in Scheme, in which lists can contain items of a variety of types. You might think: “Ah! I’ll have an Item class, with subclasses for IntItem, StringItem, etc.” That would be wonderful, if you were implementing this list using an OOP (object-oriented programming) language. Oops. ;)

In C, one way to handle this type issue is to use union types. These types allow you to have a single datatype that sometimes includes an int, sometimes a char *, etc. Every such item should also have a tag telling you what kind of data you’re storing.

Here’s what this will look like for us:

typedef enum {
    INT_TYPE, REAL_TYPE, STR_TYPE, /* ... */
} item_type_t;

typedef struct scheme_item_t {
    item_type_t type;
    union {
        int i;
        double r;
        char *s;
        /* ... see below for more details ... */
    };
} scheme_item_t;

The names INT_TYPE, REAL_TYPE, etc. represent the types of items we’ll store. (You can read a bit about enums here in the C Boot Camp.)

The scheme_item_t struct includes a field type containing one of these tags, as well as a union of various possible fields. For example, you could create an item containing the integer 5 as follows:

scheme_item_t my_int;
my_int.type = INT_TYPE;
my_int.i = 5;

If you have a scheme_item_t and want to take different actions based on what type it is, you may want to use a switch statement:

switch (item.type)
{
    case INT_TYPE:
        // do something with item.i
        break;

    case REAL_TYPE:
        // do something with item.r (a double representing a real number)
        break;

    /* ... */
}

Representing a list

The scheme_item_t struct defined above enables us to represent elements of various different types. Now we need to implement a linked list in which each node contains a scheme_item_t. We have multiple choices.

The most common approach, which we saw for linked lists in class, is to have each node in the list be a struct with a value and a next pointer. Don’t use this approach for the assignment. There’s a better way for our purposes that will save you much pain later.

Because you will eventually be using your linked list to represent Scheme expressions (more formally, S-expressions), you will have a much easier time if your linked list actually resembles a Scheme linked list. Specifically, each node should be a “cons cell” with two pointers within, and it should not be strictly typed.

Here is an abbreviation of the technique that you should use:

typedef struct scheme_item_t {
    item_type_t type; // also has CONS_TYPE as an option
    union {
        int i;
        double r;
        /* ... */
        struct {
            struct scheme_item_t *car;
            struct scheme_item_t *cdr;
        };
    };
} scheme_item_t;

The “head” pointer for your linked list, whatever you choose to call it, should be of type scheme_item_t *. It should be NULL_TYPE if the list is empty or point to a scheme_item_t. That scheme_item_t should be one that holds a cons cell (type == CONS_TYPE). The car of that cell should point to the first item in your linked list; the cdr should point to another “cons cell”, and so on. At the end of the linked list, the cdr of that scheme_item_t should point to a NULL_TYPE scheme_item_t.

Additional details

If you insert elements at the beginning of the list, which is the simplest way, they will be stored in backwards order from what you typically want. We could handle this efficiently by writing code to add at the tail of the linked list instead of the head. However, we’ll get some additional practice with C pointers and linked lists by writing an additional function to reverse a linked list.

(Is this less efficient than it could be? Yep, it is. This project is large enough; we won’t focus very much on efficiency, but you may want to think about keeping track of these inefficiencies if you want to improve it later.)

For this assignment, you can feel free to reference any linked list code I have shared or you have written previously, but I still expect you to type things up and to also keep in mind that what you’ve done previously will not fit precisely in this framework.

Getting started

As before, you should download the starter files, 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 following files:

• schemeitem.h: defines the scheme_item_t structure described above

• linkedlist.h: provides signatures for all of the functions you will need to write

• main.c: provides tests for your code by making some nodes, putting them into a linked list, displaying them, and cleaning up memory afterwards

• justfile: contains instructions for the command just, which we will use to compile and test your code

• test-cr and test-ad: usual test scripts

• test_utilities.py: contains helper utilities used by test-cr and test-ad

The missing file here is linkedlist.c, which you’ll need to create yourself in order to implement everything in linkedlist.h. Here are some steps I recommend to get you started:

1. Try compiling the starter code, before adding linkedlist.c, to see the error message. You can compile the code with just by typing:

just build

2. Now add a blank linkedlist.c file to the same folder as the rest of the assignment files, and try compiling again. You should get a bunch of linker errors about undefined functions.

3. Finally, go through and add a blank function to linkedlist.c for each function declared in linkedlist.h (make sure to include linkedlist.h so you can get the scheme_item_t definition alongside all of the function prototypes). Functions with a return type of void can have an empty body; otherwise, return something meaning empty (e.g., 0, false, or NULL). Note that to return a NULL pointer you’ll need to include stdlib.h.

4. Try building now. If it’s successful, you’ll get a short message showing the command it ran (note that $ is my prompt):

$ just build
clang -gdwarf-4 -fPIC linkedlist.c main.c -o linkedlist

5. The last part of the command above says that the executable (the “output” from clang, hence -o) is named linkedlist. Try running this using ./linkedlist. When I do, I get an assertion failure on line 132 of main.c:

$ ./linkedlist
linkedlist: main.c:132: int main(int, char **): Assertion `length(head) == correctLength' failed.
[2]    903042 IOT instruction (core dumped)  ./linkedlist

6. If you look at the code, you’ll see this is checking the length after adding one element to the list. Go ahead and implement just enough functions to make it past this line. For this, I recommend makeNull, cons, and length. You can also change reverse to just return the list (you need to fix this later).

7. You should use assert to validate whether operations are legitimate. Using assert allows you to check whether a specific condition is true, and if not, to halt execution of the program. For example, I might have the following line of code in my length function:

assert(list != NULL);

This will halt execution of the program if list is in fact equal to NULL. It will print out an error like:

linkedlist: linkedlist.c:164: int length(Item *): Assertion `list != NULL' failed.

That’s useful for debugging, both for you and for anyone else who might use your linked list in their code (like future-you). You can also add a string afterwards if you want to give more info, e.g.,:

assert(list != NULL && "Error (length): input list is NULL");

If the assertion fails, then the string is also printed. Add assertions to each of your already-implemented functions and be sure to include <assert.h>. Re-compile and re-run your code to make sure it still works as it did before.

8. Implement the rest of the functions. Once you have completed the core requirements (check main.c to figure out which functionality you need for Advanced requirements), then ./test-cr should pass. You can also run the same tests as ./test-ad by typing ./linkedlist AD at the terminal.

Keep in mind that your code should not have any memory errors when running on any input (correct or incorrect) using valgrind. The testing scripts will automatically run valgrind on your code, and show you if there are memory errors. Look at line 68 of test_utilities.py to see the command that the scripts run. I recommend you read up on valgrind errors if you run into issues!

9. Make sure the list is printed correctly. In addition to checking if your code passes the tests, we will check if your display prints the values in the list in the correct order. There are no particular formatting requirements (e.g., elements may be separated by spaces, new lines, commands, and/or something else), but the values must be printed to the screen in the correct order.

Good luck, and try to have fun with this! If you get stuck, take some time to draw the testing code’s linked list on a whiteboard/paper with all of its cons cells, and try to use gdb to walk through the code and debug what’s happening. If in doubt, post on the Moodle Q&A forum with any error messages you can’t make sense of!

Testing your work

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 linkedlist.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). It’s okay to just copy the comments from linkedlist.h, or you can write your own (shorter) descriptions.

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.