Interpreter 8: Primitives

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

In this assignment, you'll implement the following functions: +, null?, car, cdr, cons, and equal?.

Primitives are functions not implemented in Scheme; you'll implement them as C functions that get called by your interpreter directly. More details follow in the section below on primitive functions. A few comments on these specific primitives:

• + should be able to handle any number of integer or real arguments (if 0 arguments, return 0). If any of the arguments are reals (double), return a real; else return an integer.
• null?, car, and cdr should take one argument each, and you should have error checking to make sure that's the case. Similarly, you need to check to make sure that the argument is appropriately typed.
• cons should take two arguments, and you should have error checking to make sure that's the case. 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.)
• append should take two arguments, and you should have error checking to make sure that's the case; we will not support append with varying numbers of arguments even though Guile does this. The first argument must be a list (do error checking to make sure that's the case; note that an empty list does count as a list for these purposes), and the second can be any type. Like with cons, this will mean needing to be able to display non-list pairs. (E.g., (append (quote (1 2 3)) 4) evaluates to (1 2 3 . 4) in Guile.) Recall that append works by making a copy of its first argument but not its second (copying versus not copying won't matter much at the moment, but it will matter when we add in set! in the final part of the interpreter).

There's one bit of trickiness that will come up: you're going to want to have both functions-as-closures and functions-as-primitives. Here's how to do this. In schemeitem.h, we've added a PRIMITIVE_TYPE. This will be for an Item that represents a pointer to a function. Here's how the additional portion appears:

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

struct SchemeItem {
    itemType type;
    union {
        int i;

        ...

        // A primitive style function; just a pointer to it, with the right
        // signature (pf = my chosen variable for a primitive function)
        struct SchemeItem *(*pf)(struct SchemeItem *);
    }
}

To show how I'm using primitive functions, here are some relevant functions and snippets of code from scattered spots in my implementation for an exponential function that you're not writing unless you want to do some optional additional work:

 /*
  * Given two int or double items in args,
  * returns an item representing argument 1
  * raised to the power of argument 2.
  * Raises an error with incorrect args length
  * or types.
  */
SchemeItem *primitiveExp(SchemeItem *args) {
   //Code omitted
}

/*
 * Adds a binding between the given name
 * and the input function. Used to add
 * bindings for primitive funtions to the top-level
 * bindings list.
 */
void bind(char *name, SchemeItem *(*function)(SchemeItem *), Frame *frame) {
    //Code omitted
}

void interpret(SchemeItem *tree) {

    ...

    // Make top-level bindings list:

    // First, initialize frame (code omitted)

    // Then, bind primitive functions
    bind("exp", primitiveExp, 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 in the same way where you look for them to appear directly after parentheses will lead to problems if these functions are passed as inputs to other functions or returned as outputs.

Work in this section is 100% optional, and not worth any points. Nonetheless, if you're looking for an extra challenge, these are fun additional exercises to try.

• Implement the following additional special forms: list, map, and equal?. equal? only needs to work for numbers, strings, and symbols; it does not need to perform any sort of deep equality test on a nested structure.
• Implement the following primitives: -, *, and /.

The files follow the same structure that they have for the previous assignments. The only change in the files I'm providing is the change to add a primitive function in item.h, as described above. You'll then need to add in the files from your previous version, and/or switch over to using our binaries. But note that the binaries I provide only go through part 4 of the project; I am not providing a working if/let interpreter. (The project gets too intermingled at this point for me to be able to supply complete partial work.)

Building and testing your code will work precisely the same as on the previous assignment. Note that the tokenizer assignment gives you instructions for how to run a single file (which can either be one you create or one of our tests). If your code is not passing the tests, I strongly encourage you to try running on one test (of your creation or of ours) and figure out what's going wrong there before moving on. You can run valgrind as well as use gdb; if you get stuck, reach out for help!