CS 251: Programming Languages

Fall 2017

proj7: Primitives

Due: Friday, 11/10 at 22:00

1. Goals

To support applying Scheme primitive functions implemented in C; to implement a few primitive functions.

2. Introduction

In the previous checkpoint, you implemented the evaluation of lambda expressions, allowing you to create functions within Scheme. Scheme also has primitive functions, which are "built-in" functions that are not written in Scheme themselves. In this checkpoint, implement the framework for supporting primitive functions. Also, implement a few primitive functions to make sure the framework is working; many more primitive functions are to be implemented later.

3. Tasks

Extend your collection with at least 4 pairs of test files to test the functionality specified in this checkpoint. (More is better!) As before, each pair of files should be named test.eval.input.XX and test.eval.output.XX, where XX is a test number.

Add PRIMITIVE_TYPE to value.h to support primitive functions. The value of a primitive function Value is a pointer to a function in C. For example, the C function implementing the Scheme primitive + might look like this:

Value *primitiveAdd(Value *args) {
   // error checking on args, a list of inputs
   // compute the result as a single value
   return [the single value];
}

In general, a primitive function implementation takes a Value * (a list of arguments) as input and returns a Value * (a single value) as output. The C syntax to express this is fairly nasty:

struct Value {
   valueType type;
   union {
      int i;
      ...

      /* A pointer to a C implementation of a Scheme primitive function.
       * Note: `pf' is the variable name I chose for the function pointer.
       */
      struct Value *(*pf)(struct Value *);
   }
}

Update apply to handle primitive functions. For example:

Value *apply(Value *function, Value *args) {
   ...
   if (function->type == PRIMITIVE_TYPE) {
      return (function->pf)(args);
   } else {
      ...
   }
}

Implement a few primitive functions themselves: +, null?, car, cdr, and cons. See notes below.

Bind these primitives in the top-level environment. For example:

void bind(char *name, Value *(*function)(Value *), Frame *frame) {
   Value *value = makeNull();
   value->type = PRIMITIVE_TYPE;
   value->pf = function;
   frame->bindings = ...
   ...
}

void interpret(Value *tree) {
   ...
   Frame *top = makeFrame(NULL);
   bind("+", primitiveAdd, top);
   bind("null?", primitiveIsNull, top);
   ...
}

Modify your Makefile to compile your new interpreter code, if necessary. When I'm in your directory and I execute the command make interpreter, I should get an executable file called interpreter in that directory.

4. Specification

Support the correct application of various Scheme primitive functions.

+ must handle any number of numerical (integer or float) arguments. (If zero arguments, return 0.) The correct return type is an integer if all arguments are integers, and a float if any argument is a float. However, for simplicity, you may choose to always return a float.
null?, car, and cdr each takes one argument. Do error checking to make sure that is the case. Similarly, check to make sure that the argument is appropriately typed.
cons takes two arguments. Again, do error checking. You'll also need to modify the code you have that handles output, because cons allows you to create non-list (dotted) pairs.
```
(cons 1 (cons 2 3))
(cons (cons 1 2) 3)
(cons 1 (cons 2 (cons 3 (quote ()))))
```
should evaluate to
```
(1 2 . 3)
((1 . 2) . 3)
(1 2 3)
```
In particular, I strongly prefer that you do not output the list (1 2 3) as the equivalent (1 . (2 . (3 . ()))) after making these modifications.

When you are done, you should be able to handle a test like this one:

(define length
  (lambda (lst)
    (if (null? lst)
        0
        (+ 1 (length (cdr lst))))))

(length (quote ()))
(length (quote (4 5 6)))

(define append
  (lambda (lst1 lst2)
    (if (null? lst1)
        lst2
        (cons (car lst1) (append (cdr lst1) lst2)))))

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

(define reverse
  (lambda (lst)
    (if (null? lst)
        lst
        (append (reverse (cdr lst)) (cons (car lst) (quote ()))))))

(reverse (quote ()))
(reverse (quote (1 2 3 4)))
(reverse (quote (("computer" "science") "is" "awesome")))

5. Possible extensions

Correct + return type (see above).
Support infinite precision for integers and integer addition. An int in C has a fixed size in memory and therefore its value is bounded in magnitude. Scheme's integer, in constrast, is not bounded by specification, and can grow arbitrarily large in theory. (In practice, it is obviously limited by the physical machine's memory.) Create a BigInt struct that can prepresent arbitrarily large integers (until malloc fails to return more memory). Add BigInt as a type of Value, and switch to BigInt in + when necessary (or when tokenizing very large numbers).
Support dotted-pair notation for input, such as (cdr (quote (1 2 . 3))). You will likely need to modify your tokenizer.

6. Submission

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, so you should test your code via Valgrind yourself.

Follow the submission instructions from the previous checkpoint; tag your commit with proj7 and push the tag to GitHub.

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

Start early, have fun, and discuss questions on Moodle.