Interpreter, if/let

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 iflet as a prefix. Note that you’ll again need to create a team; this happened because we had a few partner tweaks in the class, and GitHub requires that we reset the teams to do that. Please name the team with both of your GitHub usernames. For example, if users FSchiller and StevieP are working together, please name the team FSchiller-StevieP. The order doesn’t matter. If you’re working in a partnership, you’ll need one of the two of you to do this; choose amongst yourselves.

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

1. Boolean, integer, real, and string literals. (They evaluate to themselves.)

2. (if test trueExpr falseExpr)

   You may assume that test evaluates to a boolean.

3. (let list-of-bindings body)

   You will need to implement the creation of new frames. Much more on this in a bit.

4. Variables. Now that you’ve implemented let and frames, you should be able to evaluate a bound symbol.

When you’re done with this part of the project, you should be able to evaluate very simple programs like this:

(let ((x #t)) (if x 3 5))

This should evaluate to 3. Your programs won’t yet be able to handle functions; that’s coming later.

At the core of your interpreter, you will need to implement a function to evaluate Scheme code:

Value *eval(Value *tree, Frame *frame) { ... }

Given an expression tree and a frame in which to evaluate that expression, eval returns the value of the expression. I’ll explain the “frame” in a moment. Here’s a skeleton of my eval function, to give you an idea of where to start:

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(tree);
        Value *args = cdr(tree);

        // Sanity and error checking on first...

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

        // .. other special forms here...

        else {
           // not a recognized special form
           evalationError();
        }
        break;
     }

      ....
    }    
    ....
}

We will be discussing this, but here is a brief overview of how to evaluate Scheme code.

The eval function mentioned above takes a pointer to a “frame”; what is a frame? A frame is a collection of bindings. OK, what’s a binding? A binding is a mapping from a variable name (i.e. a symbol) to a value. Frames are created whenever we introduce new variable names. For example, in the program

(let ((x 5) (y "hello")) (if #t x y))

the bindings for x and y are stored in a single frame. You will have to construct a frame whenever eval encounters a let. This frame should be passed in when calling eval on the body of the let expression. The frame is used to resolve (find the value of) each variable encountered during evaluation. When eval tries to evaluate x, it looks in the current frame to find a value for x.

There’s one other crucial detail here: frames can be chained together to create a larger environment consisting of multiple frames. For example, in the program

(let ((x "hello")) (let ((y "goodbye")) (if #t x y)))

each of the two let expressions creates a separate frame. When eval evaluates x, it first checks the innermost let’s frame; since that frame only contains a binding for y, it then checks the outer let’s frame, where it finds a binding for x with value "hello".

To summarize, evaluating a let expression of the form:

(let ((var1 expr1) (var2 expr2) ... (varn exprn)) body)

consists of the following steps:

1. Let e be a pointer to the current frame. Create a new frame f whose parent frame is e.
2. For i = 1 through n:
   • Let vali be the result of evaluating expri in frame e.
   • Add a binding from vari to vali to f.
3. Evaluate body using frame f and return the result.

You will need to implement data structures for frames and bindings. The easiest approach is to use linked lists. The linked list of frames essentially forms a stack: you push on a new frame just before evaluating the body of the let expression, and pop the frame off before returning (although the “pop” really happens automatically when you return from eval). Within each frame you should store a list of variable/value pairs (i.e. bindings), using another linked list. When you need to resolve a variable, check the current frame first, then its parent if that variable is not in the current frame, then its parent, and so on until you reach a frame with no parent.

There are going to be many cases in which evaluation is not possible. For example:

• When an if expression has fewer than 3 arguments
• When the condition of an if expression evaluates to something other than a boolean
• When the list-of-bindings for let does not contain a nested list
• When you encounter a variable that is not bound in the current frame or any of its ancestors
• etc…

In each of these cases you may immediately quit, printing “evaluation error”. Make sure to clean up memory on your way out; use texit for this.

In any of these cases, you should print “Evaluation error” at the start of your error message so that the tests will pass. You might enhance these messages by adding more text to it, like “Evaluation error: if has fewer than 3 arguments” or the like.

As discussed in the parser assignment, a Scheme program is a list of S-expressions. You should call eval on each S-expression. This is what the function interpret, that you need to write, should do: it is a thin wrapper that calls eval for each top-level S-expression in the program. You should print out any necessary results before moving on to the next S-expression.

This is also true for let itself. If the body of let has multiple expressions, you should evaluate each one of them, and return the result of the last one. See the last test below for an example of this.

Work in this section is 100% optional, and doesn’t contribute towards your grade. Nonetheless, if you’re looking for an extra challenge, these are fun additional exercises to try.

Here are some additional details in the Scheme language that you can integrate these if you wish; they will be unnecessary for the core part of the project going forward, though they may play into later capstone tasks:

• Implement the Scheme function display (described further down in this section of Dybvig). Don’t work hard at getting lots of edge cases right; we’ll only test the following two types of uses:

    (display x)  ;; displays value of a particular variable
    (display "hello world") ;; displays a particular string without the quotes
  

  You can handle non-printable characters (newlines, etc) inside the strings in any reasonable way, so long as the code doesn’t crash.

• Implement the Scheme functions when and unless (described further down in this section of Dybvig).

Your repository will follow the same structure that it has for the previous assignments. The key changes are in value.h, which now includes a struct for a frame, and interpreter.h, which is the header file for the new functionality. You’ll need to add interpreter.c, which implements the functions specified in interpreter.h.

Again as usual, you may use my binaries if you wish instead of using your own previous code, and the directions on how to do so are the same. I continue to encourage you enthusiastically to use your own code!

If you’re working on a team, you and your partner each wrote your own parser for the previous assignment. If you are going to continue building on your own code, you’ll need to choose one of the two parsers to use going forward. Have a rock-paper-scissors tournament with your teammate to decide which, or choose the one that passed more tests. If you have time and want to work with your partner on merging the two together to make an even better parser, feel free.

Building and testing your code will work precisely the same as on the previous assignment (make test and make capstone).

Add all of your files to your Git repository and push to GitHub. (It’s up to you if you want to submit your interpreter executable or not.) Your submitted files should be exactly what you checked out, but also with a file named interpreter.c (and possibly your other old .c files as well if you are using your own.) Your Makefile may have changed if you modified it to work with my binaries.

Make sure that you have added your new .c correctly, then push to GitHub. (You can leave out your compiled executables as well as the .o object files if you wish.)

Make sure to label your submission as usual via an appropriate commit message, and make sure your tests have run on GitHub.

Have fun interpreting!

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