Interpreter 5: if/let/quote

This is a "pair" assignment, which means that you and your partner should use the pair programming model. You should be physically together, sharing a computer and both looking at the same screen.

Each partner has an active role to play during pair programming - please review the instructions on Moodle about pair programming, and make sure you understand what you should be doing when you are the navigator and when you are the driver. You should make sure that over the course of an assignment that you each spend roughly the same amount of time "driving." My recommendation is to set a timer and switch drivers every 10-15 minute.

For the interpreter project, you are permitted to do a limited amount of debugging separate from your partner. If you do this, you should be sure that you're each contributing similar amounts: it's not fair, either in terms of time or in terms of learning, if one person does all the debugging. Before debuggging on your own, make sure that your partner is onboard with that. Also, make sure to share what you found with your partner afterwards.

If pair programming in real-time just doesn't work for you and your partner, then you will need to amicably split up and work individually. If you choose this option, you must communicate that to me [Anna] and send me an email with a zip file containing the code checkpoint of any work you did together (if applicable).

If things are not going well with working with your partner or you find yourselves tempted to split up the work, please talk to me. While doing a limited amount of debugging separately is fine, you should be doing the initial design and coding together - if you or your partner cannot explain how part of your interpreter works, then you have not followed the pair programming policies for this class.

Download the folder with the starter code from the link below. Like for previous homeworks, unzip the folder and move it to where you'd like: most likely the folder for the Docker container. Then get started in VS Code.

If when running tests you run into a permissions error, you can fix this by running the following code in the terminal:

chmod a+x test-e test-m

This tells the computer that all users should be permitted to execute (run) the files test-e and test-m.

Click here to download the starter files.

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)

   Usually, test will evaluate to a Boolean, but that is not strictly required in Scheme. So, your code should evaluate falseExpr if test evaluates to #f, and should evaluate trueExpr otherwise. In other words, we will treat anything that is not #f as true.

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.
5. (quote expr). You'll also need to be able to support the abbreviated form 'expr. That said, the parser should already be converting the second form into the first.

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.

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

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

Given an expression tree and a frame (aka environment) in which to evaluate that expression, eval returns the value of the expression. I'll explain more about the "frame" in a moment. Here's a skeleton of my eval function, to give you an idea of where to start:

SchemeItem *eval(SchemeItem *tree, Frame *frame) {
   switch (tree->type)  {
     case INT_TYPE: {
        ...
        break;
     }
     case ......: {
        ...
        break;
     }  
     case SYMBOL_TYPE: {
        ... //Code to implement what should happen if we have a symbol
        break;
     }  
     case CONS_TYPE: {
        SchemeItem *first = car(tree);
        SchemeItem *args = cdr(tree);

        // Some error checking here (omitted from sample code) before moving to cases

        if (!strcmp(first->s,"if")) {
            result = evalIf(args, frame); //Helper functions can make your code easier to navigate!
        }

        // .. other special forms here...

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

      ....
    }    
    ....
}

We started discussing this topic on Friday, and will get much farther into the details this week. But in the meantime, here's 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. Bindings 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 (yes, there are two syntaxes available for if in full Scheme, but we're only going to support the one we've been using in which if always has three arguments)
• When an if expression has more than 3 arguments.
• 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 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. While these more detailed error messages are not required, writing better error messages may help you now or later in the project with debugging, as if things go wrong when they shouldn't, you'll have a better sense for what happened.

You should then immediately quit, and make sure to clean up memory on your way out; use texit for this.

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 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. (The interpreter follows a read-evaluate-print loop: after you evaluate a top level S-expression, the result of that evaluation is printed.)

Some other parts of the code may also have multiple S-expressions, such as the body of let. 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.

Do not implement quote by trying to somehow wrap up the quoted expression in some sort of enclosure indicating that it is quoted.

Some of you will feel tempted to do otherwise! Some of you may find that you are convinced that storing quote or a single quote somehow explicitly after evaluation will help you in some way. Some of you might even find that by doing so, you can succeed at this task. Don't do it. It's a trap. It might help you get this part of the assignment to work, but you'll get into hot water later - and it will be much more frustrating to go back through your old code and fix it later. This reflects a common and interesting point of confusion: quote does not tell the interpreter to do something to its arguments; rather, it tells the interpreter to not do something.

If you are feeling a strong urge to annotate something indicating that something is quoted, don't do it. If you are experiencing such compulsions because your tree is not printing properly, past experience has sometimes been that the problem is the code for printing the parse tree, not structuring it in the first place.

For the final project submission, you will get to choose what additional functionality you want your interpreter to have, and you'll implement (several small, a few medium, or 1-2 large) enhancements. It's not required to get started on these extensions now, but if you'd like to, here are some ideas:

• Implement the Scheme function display (described further down in this section of Dybvig). The simplest cases, which are those I'd focus on, are the following:

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

  Display is a small extension.

• Implement the Scheme functions when and unless (described further down in this section of Dybvig). Each of these is a small extension.

If you do any of these extensions, remember to write your own tests to make sure that they work!

Your repository will follow the same structure that it has for the previous assignments. The key changes are in schemeitem.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! To do so, copy in the .c files from your last assignment. Note that I will not able to provide binaries for parts beyond the parser - the code for evaluation gets too intertwined to be able to do so effectively.

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 (just build, test-m, and test-e). Gradescope will copy in fresh copies of the tester files and the supporting architecture when running the tests.