Interpreter, Define / Lambda

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 lambda as a prefix.

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

In addition to eval as described above, 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 a user-defined function (i.e. a closure). You should take the following steps in order to execute the function:

• Construct a new frame whose parent frame is the environment stored in the closure.
• Add bindings to the new frame mapping each formal parameter (found in the closure) to the corresponding actual parameter (found in args).
• 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;

      ....
    }    
    ....
}

If a function is evaluated but not applied, you should just output <#procedure>. Here is an example:

$ cat test-in-02.scm
(lambda (x) x)
$ ./interpreter < test-in-02.scm
#<procedure>

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.

• Implement the third version of define shown in Dybvig, which is the one that lets you use define alone as shorthand for both define and lambda:

(define (myfunction x y z)
   (+ x y z))

The above works, but is really shorthand for

(define myfunction
    (lambda (x y z)
       (+ x y z)))

• Implement a variation of lambda that takes a single parameter, not in parentheses, that gets bound to a list of parameters. This is described in this section of Dybvig, in the second bullet describing how formals works. Here’s an example:

$ cat test-in-02.scm
(define tryit
  (lambda x
    x))

(tryit 1 2 3)
$ ./interpreter < test-in-02.scm
(1 2 3)

Your repository will follow the same structure that it has for the previous assignments. There should be no changes at all in the files that I provide; you’ll then need to add in the files from your previous version, and/or switch over to using my binaries. But note that the binaries I provide only go through part 4 of the project; I am not providing a working if/let interpreter. (The project gets too intermingled at this point for me to be able to supply complete partial work.)

Building and testing your code will work precisely the same as on the previous assignment.

Make sure that you have added files if necessary, 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.