Interpreter 1: Linked List
Table of Contents
1. Pair programming structure
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.
2. Get started
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
.
3. 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 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!
4. Items and lists
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 an Item 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
Items. (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 NULL_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 NULL_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.
5. Some specifics
When you download the starter code, you should be able to see the following starting files:
schemeitem.h
: this defines theSchemeItem
structure, described abovelinkedlist.h
: this defines all of the functions that you will need to writemain.c
: this is a tester function that makes some nodes, puts them into a linked list, displays them, and cleans up memory afterwardsjustfile
: contains instructions for the commandjust
, which will compile and test your codetest-e
andtest-m
: usual test scriptstest_utilities.py
: helper utilities used bytest-e
andtest-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(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")
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.
6. How to test and submit your work
6.1. Testing your work
Go back and look at the sections at the end of Scheme Intro 2 labeled "How to test your work". Everything there about how to run M tests and E tests applies identically here. Note that the tests will fail if your code has compiler warnings and/or valgrind errors, in addition to if its behavior is observably incorrect.
6.2. Submitting your work
You'll submit your work on Gradescope. You should already have a file
CollaborationsAndSources.txt
in your working directory (if not, copy it over from the previous assignment). Go to the header
for this portion of the assignment and fill in the document. Indicate
in what ways (if any) you collaborated with other people on this
assignment (did you talk with anyone other than Anna or our prefect? Did you share strategies with anyone?
Get or give advice on debugging? These are
fine things to do, and you should note them in the CollaborationsAndSources.txt
file). If you used any resources outside of our course
materials, that is also something to note in CollaborationsAndSources.txt
. If
you didn't talk with anyone or use any outside sources, please note
that explicitly. Look back at the
Scheme Intro 1 instructions if you want more details on the
CollaborationsAndSources.txt
file.
After updating CollaborationsAndSources.txt
and finishing the
assignment, run ./zipitup
This will zip up your C files, header files, and collaborations and sources. We will be re-copying in our version of the tests and of the included header files.
Then, upload the created zip to Gradescope.
On Gradescope, make sure to add your partner if you worked with a partner. This page has detailed instructions for how to do that.
On Gradescope, you should see autograder output for the same tests as you ran locally. There is a small but nonzero chance that you have coded something unexpected that cause the tests pass on the computer you’re working on, but not on Gradescope. We will be grading this assignment based on the results of the tests on Gradescope, so you should make sure to pay attention to how the tests run there as well when you submit.
For grading, you'll earn at least an M if the following conditions are all met:
- All M tests pass
- A visual inspection of your code shows that you have not hyper-tailored your code to pass the tests. Hyper-tailoring your code 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 similar inputs (see Homework policies for more on this).
- You have a
CollaborationsAndSources.txt
with the information described above. - The work is submitted by the late deadline.
You'll earn an E if:
- All conditions above for an M are met.
- All the E tests pass.
- Your code is not significantly more complex than needed to accomplish the task.
- You have a comment before each function describing what the function does (its input/output behavior, not a play-by-play of "first checks… then makes a recursive call …").
- The work is submitted by the regular deadline or it is submitted by the late deadline and you elect to use a late token by submmitting a regrading request.
You may earn a grade of M or SP (Some Progress) and be offered to resubmit for an improved grade if:
- All tests pass (all E tests if you can resubmit for an E, and all M tests if you can resubmit for an M)
- Your code has significant stylistic or efficiency issues that we have not explicitly covered in class or on the feedback for a previous assignment.
If your code does not meet the criteria for an M or an E, then you'll earn a
grade of NA (Not Assessable) or SP (Some Progress) for the assignment. Not Assessable means that your submission does not
have an attempt at one or more functions in the assignment. Some Progress means
that your submission has some code (in the correct language) for all functions in the
assignment, but that the code does not pass all of the M tests, is
hyper-tailored to the tests, and/or is missing a CollaborationsAndSources.txt
file.
Good luck, ask questions, and have fun!
Assignment modified from one originally created by David Liben-Nowell and subsequently updated by Dave Musicant and Laura Effinger-Dean. Thanks for sharing!