CS 251: Interpreter, Primitives

In the last assignment, you implemented lambda, which let you create functions within Scheme. Scheme also has primitive functions, which are "built-in" functions that are not written in Scheme themselves. You'll implement primitive functions for this assignment.

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). We'll simplify this a little bit by specifiying that your answer should always be a real. That said, an optional extension that you can add if you like would be to make it so that 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.

Sample tests

$ cat test1
(define length
  (lambda (L)
    (if (null? L)
        0
        (+ 1 (length (cdr L))))))

(length (quote ()))
(length (quote (4 5 6)))
$ cat test1 | ./interpreter
0
3

$ cat test2
(define append
  (lambda (L1 L2)
    (if (null? L1)
        L2
        (cons (car L1) (append (cdr L1) L2)))))

(append (quote (4 5)) (quote (6 7)))

(define reverse-list
  (lambda (L)
    (if (null? L)
        L
        (append (reverse-list (cdr L)) (cons (car L) (quote ()))))))

(reverse-list (quote ()))
(reverse-list (quote (1 2 3 4)))
(reverse-list (quote (("computer" "science") "is" "awesome")))
$ cat test2 | ./interpreter
'(4 5 6 7)
'()
'(4 3 2 1)
'("awesome" "is" ("computer" "science"))

Primitive functions

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. Once again, modify your value.h to allow for 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
   return makeFloatValue(exp(floatval(car(args)))); 
}

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);
    ...
}

Using my binaries

If you wish to continue using my binaries, you are free to do so. No new functionality has been added to them; it's the same code through the parser that I've supplied previously. However, because we're changing the value.h file, I need to supply you with recompiled versions of that code. This zip file is the same that I have supplied in the past, but I have made the updates to the value.h file indicated above and recompiled the files. Use if you wish; see earlier assignments for instructions on how to do so.

Memory errors

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.

What to submit

Submit via git as usual, and tag your submission as primitives. If you need to resubmit, create another tag with a dot extension, such as primitives.1, primitives.2, and so on. Make sure that you both push your tags and your code itself, as in:

      git commit -am "We are done!"
      git push
      git tag primitives
      git push --tags

Add at least four more tests to your test files that test the functionality of the primitives you have added. Indicate in a readme.txt file which tests are designed to be testing this assignment in particular. Each pair of files should be named interpreter-test.input.XX and interpreter-test.output.XX, where XX is a test number. It should be the case that if I run the following command then I get no output:

./interpreter < interpreter-test.input.XX | diff interpreter-test.output.XX -

When we test your code for grading purposes, we will use our own set of test files which we will run using exactly the same command as described above. Test carefully.

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 as well during grading.

Remember, you can test your code in valgrind this way:

./valgrind.sh  < interpreter-test.input.XX

Have fun interpreting!

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