CS 251: Interpreter, Define / Lambda

For this phase of the project, you must support the correct evaluation of the following types of Racket expressions:

1. (define var expr)

   Racket actually has a number of different variations on define; you only need to implement the first one. (The previous link is to documentation on the Scheme standard, which I think is more readable than the reference for define for Racket in particular. They both say the same thing where it matters.) Unlike let, define does not create a new environment frame; rather, it modifies the current environment frame. You will therefore need to have a "top" frame which contains bindings of variables created using define. You can put bindings for primitive functions in this top-level frame too; you'll read more about that later.

   You should not print anything after a define statement. You should go about this by having define return a special Value with type VOID_TYPE, and only print the result of an expression if it is not VOID_TYPE. There's probably other ways of doing this too. Add a VOID_TYPE to value.h.

   Racket is able to detect when define is used in the wrong place - don't worry about this if you don't want to. You can just modify the current frame. Similarly, if a variable name is already defined in the current frame, you don't have to detect that if you don't wish to -- you can just add a new binding for it or overwrite the old binding. We will not test for correct or incorrect behavior if define is used anywhere but at the top-level. That said, you can add as optional extensions error checking as appropriate.

2. (lambda params body)

   You will need to implement closures. Specifically, for purposes of this project a closure is just another type of value, containing everything needed to execute a user-defined function: (1) a list of formal parameter names; (2) a pointer to the function body; (3) a pointer to the environment frame in which the function was created. Add a CLOSURE_TYPE to your value.h. Within your Value union, add a Closure. Here's a snippet of my Value definition:

   typedef enum {INT_TYPE, ..., VOID_TYPE, CLOSURE_TYPE, ...} valueType;
   
   struct Value {
       valueType type;
       union {
           int i;
   
           ...
   
           struct Closure {
               struct Value *paramNames;
               struct Value *functionCode;
               struct Frame *frame;
           } cl;
       }
   }
   

3. Function application: (e1 ... en)

   You should recursively evaluate e1 through en and then apply the value of e1 to the remaining values. The section below on function application has more details.

As usual, your program should never crash or segfault on bad input; just print "evaluation error" and exit gracefully.

Once you've finished these components, your interpreter should be able to evaluate recursive user-defined functions. For example, the following should work:

$ cat test1
(define not
  (lambda (bool)
    (if bool #f #t)))
    
(define testit
  (lambda (cond conseq alt)
    (let ((nconseq (not conseq)) (nalt (not alt)))
      (if cond nconseq nalt))))
    
(testit #t #f #t)
(testit #f #f #t)
$ ./interpreter < test1
#t
#f

Function application

In addition to eval from part 1, you will need to implement function application. To do this, create a function called apply:

Value apply(Value *function, Value *args);

You should call this function once you've evaluated the function and the arguments. Here, function is either a user-defined function (i.e. a closure). You should take the following steps in order to execute the function:

1. Construct a new frame whose parent frame is the environment stored in the closure.
2. Add bindings to the new frame mapping each formal parameter (found in the closure) to the corresponding actual parameter (found in args).
3. Evaluate the function body (found in the closure) with the new frame as its environment, and return the result of the call to eval.

Here's my new eval skeleton, modified to support function application:

Value *eval(Value *tree, Frame *frame) {
   switch (tree->type)  {
     case INT_TYPE:
        ...
        break;
     case ......:
        ...
        break;
     case SYMBOL_TYPE:
        return lookUpSymbol(tree, frame);
        break;
     case CONS_TYPE:  
        Value *first = car(expr);
        Value *args = cdr(expr);

       // Sanity and error checking on first...

        if (!strcmp(first->s,"if")) {
            result = evalIf(args, frame);
        }

        // .. other special forms here...

        else {

            // If not a special form, evaluate the first, evaluate the args, then
            // apply the first to the args.
            Value *evaledOperator = eval(first, frame);
            Value *evaledArgs = evalEach(args, frame);
            return apply(evaledOperator,evaledArgs);
        }
        break;

      ....
    }    
    ....
}

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 lambda. If you need to resubmit, create another tag with a dot extension, such as lambda.1, lambda.2, and so on. Make sure that you both push your tags and your code itself, as in:

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

Add at least four more tests to your test files that test the functionality of define and lambda. Indicate in a readme.txt file which tests are designed to be testing this assignment in particular.

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