Interpreter 1: Linked List

This is a "pair" assignment, which means that if you are working on a team with someone else, you and your partner should engage in the pair programming model. You should be physically together, sharing a computer and both looking at the same screen. Each partner has an active role to play during pair programming - please review the instructions on Moodle about pair programming, and make sure you understand what you should be doing when you are the navigator and when you are the driver.

You should make sure that over the course of an assignment that you spend roughly the same amount of time each "driving." My recommendation is to take turns approximately every 15 minutes or so. Set a timer to help you remember. I will also ask you to fill out a survey about your partnership at the end of the term.

For the interpreter project, you are permitted to do a limited amount of debugging separate from your partner. If you do this, you should be sure that you're each contributing similar amounts: it's not fair, either in terms of time or in terms of learning, if one person does all the debugging. Before debuggging on your own, make sure that your partner is onboard with that. Also, make sure to share what you found with your partner afterwards.

If pair programming in real-time just doesn't work for you and your partner, then you will need to amicably split up and work individually. If you choose this option, you must communicate that to me [Anna] and send me an email with a zip file containing the code checkpoint of any work you did together (if applicable).

If things are not going well with working with your partner or you find yourselves tempted to split up the work, please talk to me. While doing a limited amount of debugging separately is fine, you should be doing the initial design and coding together - if you or your partner cannot explain how part of your interpreter works, then you have not followed the pair programming policies for this class.

You'll download the folder with the starter code from the link below. Like for previous homeworks, unzip the folder and move it to where you'd like: most likely the folder for the Docker container. Then get started in VS Code.

If when running tests you run into a permissions error, you can fix this by running the following code in the terminal:

chmod a+x test-e test-m

This tells the computer that all users should be permitted to execute (run) the files test-e and test-m.

Click here to download the starter files

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 for the rest of the term: it's worth commenting well, making sure you've organized it in a way that's readable, and so on. Future you will thank current you if you use good style and structure!

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, which can contain items of a whole variety of types. You might think: "Ah! I'll have a SchemeItem class, with subclasses for IntItem, StringItem, etc." And 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 of typing issue is to use union types. (See our online C reference that I assigned or other online tutorials.) These types allow you to have a single datatype that sometimes includes an int, sometimes a char *, etc.) Every such item should also include a tag telling you what kind of data you're storing.

typedef enum {INT_TYPE, DOUBLE_TYPE, STR_TYPE,...} itemType;

typedef struct SchemeItem {
    itemType type;
    union {
        int i;
        double d;
        char *s;
        ...
    };
} SchemeItem;

The names INT_TYPE, DOUBLE_TYPE, etc., represent types of SchemeItems. (You can read a bit about the enum here in the C Boot Camp.) The Item 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:

SchemeItem myInt;
myInt.type = INT_TYPE;
myInt.i = 5;

If you have a SchemeItem and want to determine its type, you might choose to use a switch statement:

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

You will thus want to create a linked list implementation where the nodes contain SchemeItems. There are many different ways that one can construct a linked list.

The most common approach you have likely seen is one that consists of nodes, where each node is a struct containing two items: a pointer to an item, and a pointer to another node. This is what we did in class. Don't do it this way 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 will use:

typedef struct SchemeItem {
    itemType type; // type will also have a CONS_TYPE as an option
    union {
        int i;
        double d;
        /* .... */
        struct {
            struct SchemeItem *car;
            struct SchemeItem *cdr;
        };       
    };
};

The "head" pointer for your linked list, whatever you choose to call it, should be of type SchemeItem*. It should be EMPTY_TYPE if the list is empty, or point to a SchemeItem. That SchemeItem should be one that holds a cons cell. The car of that cell should point to the first item in your linked list; the cdr should point to another SchemeItem. And so on. At the end of the linked list, the cdr of that SchemeItem should point to a EMPTY_TYPE SchemeItem.

And finally: if you insert tokens at the beginning of the list, which is the simplest way, your tokens will be represented in backwards order from what you typically want. One could handle this efficiently by writing code to add at the tail of the linked list instead of the head. Instead, we'll make things simpler 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, though you might think about tracking places to make it more efficient if you want to improve it at the end.)

You can feel free to reference any linked list code that I have shared or you have written previously, but you should not copy and paste code or directly copy it. You will likely find that while what we have done in class is relevant, it does not precisely fit this framework.

When you download the starter code, you should be able to see the following starting files:

• schemeitem.h: this defines the SchemeItem structure, described above
• linkedlist.h: this defines all of the functions that you will need to write
• main.c: this is a tester function that makes some nodes, puts them into a linked list, displays them, and cleans up memory afterwards
• justfile: contains instructions for the command just, which will compile and test your code
• test-e and test-m: usual test scripts
• test_utilities.py: helper utilities used by test-e and test-m

The missing file here is linkedlist.c, which you'll need to create yourself in order to implement everything in linkedlist.h. To compile your code, issue the command just build at the command prompt. This will follow the instructions in the justfile for building your project in order to produce an executable called linkedlist. Click on the justfile in VSCode to see what those instructions look like. At first, it won't build at all because your linkedlist.c file isn't there. Create the file and for now, create every function that you need with no code inside it so that you can get everything to build. Once you have done that, you can begin implementing your functions, and testing appropriately.

In linkedlist.h, it discusses using assert to test whether particular things are legitimate operations. assert allows you to check whether a specific condition is true, and if it is not, to halt execution of the program. For example, I might have the following line of code in car:

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(SchemeItem *): 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")

The string will then be printed too. To use assertions, make sure to include <assert.h>.

The tester code creates an executable that you can run by typing ./linkedlist, which takes parameters depending on whether or not it should run the exemplary tests. The easiest way to run the tests is to use ./test-m and ./test-e, as usual, which will automatically compile all of your code and run the ./linkedlist executable for you.

Your code should have no 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.

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., they may be separated by spaces, new lines, commas, and/or something else), but the values must be printed to the screen in the correct order.