Interpreter, Primitives

Hopefully, you've got the hang of it by now as to how these projects start. Feel free to go back again to the tokenizer assignment if you want detailed instructions on how to clone the repository to Repl.it. Here is the new GitHub Classroom link that you'll need to create the repository on GitHub. Once you have created your repository, its name will have primitives as a prefix.

Here are the particular primitive functions you need to implement: +, null?, car, cdr, and cons.

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, return a real; else return an integer.
• null?, car, and cdr should take one argument each, but 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, but 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 my linkedlist binaries won't work on pairs such as this one. If you're using my binaries and using the linkedlist display function, you'll need to write your own instead.)

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 value.h, use a PRIMITIVE_TYPE. Since this is a function to a pointer in C, here's how the additional portion appears:

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

struct Value {
    valueType 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 Value *(*pf)(struct Value *);
    }
}

To show how I'm using primitive functions, here's relevant 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:

Value *primitiveExp(Value *args) {
   // check that args has length one and car(args) is numerical
   // assume that car(args) is of type double, should check that as well
   Value *result = talloc(sizeof(Value));
   result->type = DOUBLE_TYPE;
   result->d = exp(car(args)->d);
   return result;
}

void bind(char *name, Value *(*function)(struct Value *), Frame *frame) {
    // Add primitive functions to top-level bindings list
    Value *value = talloc(sizeof(Value));
    value->type = PRIMITIVE_TYPE;
    value->pf = function;
    frame->bindings = ....
    ....
}

void interpret(Value *tree) {

    ...

    // Make top-level bindings list
    Frame *frame = talloc(sizeof(Frame));
    frame->bindings = makeNull();
    frame->parent = NULL;


    bind("+", primitiveAdd, frame);
    bind("exp", primitiveExp, frame);
    ...
}

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 primitives and/or special forms: list, append, 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.

Your repository will follow the same structure that it has for the previous assignments. There should be no changes at all in the files that I provide, apart from an updated value.h; you'll then need to add in the files from your previous version, and/or switch over to using my binaries. But note that the binaries I provide only go through part 4 of the project. (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 assignments (make test, and make capstone).

What to submit Push all of your files to GitHub. Your Makefile may have changed if you modified it to work with my binaries. If you did this, add a readme.txt file explaining what you did.

The graders and I need to know which commit is the one that we should use for grading. This is handled well in Git with tags. You did this back in the original clab. If you've forgotten how to tag in Git, look at the end of part 1 of the C lab. Name your tag primtives-done.

Have fun interpreting!

This assignment was originally created by David Liben-Nowell and has since been updated by Dave Musicant and Laura Effinger-Dean.