Interpreter 7: Primitives

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). This should be a shallow copy, meaning that we create new cons cells to represent the outermost list layer, but nested lists will still point to shared memory.

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 a SchemeItem 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 choose to implement it as part of the final project submission.

 /*
  * 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.

For the final project submission, you will get to choose what additional functionality you want your interpreter to have, and you'll implement (several small, a few medium, or 1-2 large) enhancements. It's not required to get started on these extensions now, but if you'd like to, here are some ideas:

• 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. Each of these counts as a small extension.
• Implement the following primitives: -, *, and /. Each of these count as a small extension.

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 schemeitem.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!