Interpreter 7: Define and Lambda

Scheme actually has a number of different variations on define; you only need to implement the first one. 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" or "global" frame that contains bindings of variables created using define. You can put bindings for primitive functions in this top-level frame too; that will be part 8 of the interpreter project.

You should not print anything after a define statement. You should go about this by having define return a special Item 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, but if you want to take my apporach, schemeitem.h now has a VOID_TYPE.

Scheme is able to detect when define is used in the wrong place, but don't worry about this if you don't want to. You can just modify the current frame. We will not test for correct or incorrect behavior if define is used anywhere other than the top level. That said, you can add as optional extensions error checking as appropriate.

You will need to implement closures. Specifically, for purposes of this project a closure is just another type of SchemeItem, containing everything needed to execute a user-defined function: (1) the formal parameter names (either a list or a single item if a variable number of parameters is permitted); (2) a pointer to the function body; (3) a pointer to the environment frame in which the function was created. We can use a CLOSURE_TYPE within schemeitem.h; here's a snippet of the new starter code:

typedef enum {INT_TYPE, ..., VOID_TYPE, CLOSURE_TYPE, ...} itemType;

struct SchemeItem {
    itemType type;
    union {
        int i;

        ...

        struct Closure {
            struct SchemeItem *paramNames;
            struct SchemeItem *functionCode;
            struct Frame *frame;
        };
    }
}

There are two forms of lambda in Scheme, and you should support both:

• (lambda (a1 a2 ... an) body1 body2 ... bodym) : the function has a list of formal parameters, and exactly that number of actual parameters should be passed in when we do function application (below).
• (lambda args body1 body2 ... bodym) : the function has a single variable name for the formal parameters, and any number of actual parameters can be passed in. Then, when evaluating the function, the parameters we pass in will be contained in a list called args. (See more below on applying functions.)

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. You can supplement with more detailed error information if you wish.

Once you've finished these components, your interpreter should be able to evaluate user-defined functions, even recursive ones. Here's one non-recursive example for you to try:

$ cat test-in-01.scm
(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 < test-in-01.scm
#t
#f

Go back and look at the sections at the end of Scheme Intro 2 labeled "How to test your work". Everything there about how to run M tests and E tests applies identically here. Note that the tests will fail if your code has compiler warnings and/or valgrind errors, in addition to if its behavior is observably incorrect.

You'll submit your work on Gradescope. You should already have a file CollaborationsAndSources.txt in your working directory (if not, copy it over from the previous assignment). Go to the header for this portion of the assignment and fill in the document. Indicate in what ways (if any) you collaborated with other people on this assignment (did you talk with anyone other than Anna or our prefect? Did you share strategies with anyone? Get or give advice on debugging? These are fine things to do, and you should note them in the CollaborationsAndSources.txt file). If you used any resources outside of your notes from class, that is also something to note in CollaborationsAndSources.txt. If you didn't talk with anyone or use any outside sources, please note that explicitly. Look back at the Scheme Intro 1 instructions if you want more details on the CollaborationsAndSources.txt file.

After updating CollaborationsAndSources.txt and finishing the assignment, run ./zipitup

This will zip up your C files, header files, and collaborations and sources. We will be re-copying in our version of the tests and of the included header files.

Then, upload the created zip to Gradescope.

On Gradescope, make sure to add your partner if you worked with a partner. This page has detailed instructions for how to do that.

On Gradescope, you should see autograder output for the same tests as you ran locally. There is a small but nonzero chance that you have coded something unexpected that cause the tests pass on the computer you’re working on, but not on Gradescope. We will be grading this assignment based on the results of the tests on Gradescope, so you should make sure to pay attention to how the tests run there as well when you submit.

For grading, you'll earn at least an M if the following conditions are all met:

• All M tests pass
• A visual inspection of your code shows that you have not hyper-tailored your code to pass the tests. Hyper-tailoring your code would be doing things like checking for the exact input from the test, meaning you haven't written your code in a way that would work for similar inputs (see Homework policies for more on this).
• You have a CollaborationsAndSources.txt with the information described above.
• The work is submitted by the late deadline.

You'll earn an E if:

• All conditions above for an M are met.
• All the E tests pass.
• Your code is not significantly more complex than needed to accomplish the task.
• You have a comment before each function describing what the function does (its input/output behavior, not a play-by-play of "first checks… then makes a recursive call …").
• The work is submitted by the regular deadline or it is submitted by the late deadline and you elect to use a late token by submmitting a regrading request.

You may earn a grade of M or SP (Some Progress) and be offered to resubmit for an improved grade if:

• All tests pass (all E tests if you can resubmit for an E, and all M tests if you can resubmit for an M)
• Your code has significant stylistic or efficiency issues that we have not explicitly covered in class or on the feedback for a previous assignment.

If your code does not meet the criteria for an M or an E, then you'll earn a grade of NA (Not Assessable) or SP (Some Progress) for the assignment. Not Assessable means that your submission does not have an attempt at one or more functions in the assignment. Some Progress means that your submission has some code (in the correct language) for all functions in the assignment, but that the code does not pass all of the M tests, is hyper-tailored to the tests, and/or is missing a CollaborationsAndSources.txt file.

Good luck, ask questions, and have fun!