Interpreter 5: if/let

This is a "pair" assignment, which means that if you are working on a team with someone else, you and your partner should engage in 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 spend roughly the same amount of time each "driving." My recommendation is to take turns approximately every 15 minutes or so. Set a timer to help you remember. I will also ask you to fill out a survey about your partnership at the end of the term.

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.

You'll 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. Copy over CollaborationsAndSources.txt and your .c files from previous stages of the project (unless you'd like to use the binaries that I provide, see towards the end of the assignment). 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.

Note 10/28 9AM: If you are planning to use my binaries, rather than your own parser code, proceed with caution. I just discovered a bug in my parser code and am working on a fix. (It won't affect the M or E tests for this assignment, but may affect additional test cases that you write.)

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.

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 or the quote symbol; that's coming later.

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

Work in this section is 100% optional, and not worth any points. 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 if you wish; they will be unnecessary for the core part of the project going forward, though they may play into later optional extensions:

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

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