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.
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 values of a whole variety of types. You might think: "Ah! I'll have a Value class, with subclasses for IntValue, StringValue, etc." And that would be totally awesome, 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 Kochan or online tutorials.) These types allow you to have a single datatype that sometimes includes an int, sometimes a char *, etc.) Every such value should also include a tag telling you what kind of data you're storing.
typedef enum {INT_TYPE,DOUBLE_TYPE,STR_TYPE,...} valueType;
struct Value {
valueType type;
union {
int i;
double d;
char *s;
...
};
};
typedef struct Value Value;
The names INT_TYPE, DOUBLE_TYPE, etc., represent types of Values. The Value struct includes a field (type) containing one of these tags, as well as a union of various possible fields. For example, you could create a value containing the integer 5 as follows:
Value myInt; myInt.type = INT_TYPE; myInt.i = 5;
If you have a Value and want to determine its type, the easiest approach is to use a switch statement:
switch (val.type) {
case INT_TYPE:
// do something with val.i
break;
case DOUBLE_TYPE:
// do something with val.d
break;
...
}
You will thus want to make some sort of linked list implementation where the nodes contain Values. 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 a value, and a pointer to another node.
Don't do it this way for the assignment. There's a better way that will save you much pain later.
Because you will eventually be using your linked list to represent Scheme 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:
struct Value {
valueType type; // type will also have a CONS_TYPE as an option
union {
int i;
double d;
/* .... */
struct ConsCell {
struct Value *car;
struct Value *cdr;
} c;
};
};
typedef struct Value Value;
The "head" pointer for your linked list, whatever you choose to call it, should be of type Value*. It should be NULL if the list is empty, or point to a Value. That Value 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 Value. And so on. At the end of the linked list, the cdr of that Value should point to a NULL_TYPE Value.
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? Yeah. 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 leverage any linked list code that we may or may not have written in class, though bear in mind that it might not fit this framework.
After you check out your blank repository ((it has your teamname, followed by "linkedlist"), download this zip file and add the contents to your git project. The files you get include:
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 "make" at the command prompt. This will follow the instructions in the Makefile for building your project in order to produce an executable called linkedlist. 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.
When we test your code for grading purposes, we will use value.h and linkedlist.h exactly as provided here, so don't change them. We will also use main.c exactly as provided here. Furthermore, we will use a fancier main.c, of our own devising, that follows the specifications in linkedlist.h, to see if you've carefully tested your linked list. The main.c that I have provided very intentionally does not test all possible cases. You should test further.
Your code should have no memory leaks or memory errors when run on any input (correct or incorrect) using valgrind. We will be checking this during grading.
To run your code, issue this command at a prompt:
./linkedlistTo run your code through valgrind, I have provided a shell script to set all the appropriate options. You can do it this way:
./valgrind.sh ./linkedlist
Push all of your code into your git repository. Your submitted files should be exactly what you checked out, but also with a file named linkedlist.c. If you wish, you can also submit an updated main.c for us to look at with additional testing code that you write; but remember, your code needs to run with the original main.c that we provide. You might perhaps create a different main.c for your own testing purposes, and for your own testing, you can modify the Makefile accordingly. When we grade, we will simply copy out your linkedlist.c file into our own project, and test it.
Good luck, and have fun!