CS 251: Programming Languages

Spring 2018

proj6: Apply

Due: Monday, 05/21 at 22:00

1. Goals

To support applying functions created with lambda expressions; to support the define special form.

2. Introduction

You have an evaluator with the ability to handle if, let, and quote special forms. We now extend its capabilities to handle define and lambda special forms. In particular, we will be able to apply functions created with lambda. In the next checkpoint, we will be able to apply built-in functions.

3. Tasks

Extend your collection with at least 4 pairs of test files to test the functionality specified in this checkpoint. (More is better!) As before, each pair of files should be named test.eval.input.XX and test.eval.output.XX, where XX is a test number.
Add VOID_TYPE and CLOSURE_TYPE to value.h.
Your eval function must additionally handle the following Scheme features: define, define-bound variables, lambda, and combinations.
Implement an apply function in interpreter.c that handles applying lambda expressions.
Modify your Makefile to compile your new interpreter code, if necessary. When I'm in your directory and I execute the command make interpreter, I should get an executable file called interpreter in that directory.

4. Specification

Support the correct evaluation of various types of Scheme expressions.

(define var expr).
Bind var to the value of expr in the top-level frame. (You may assume that all define expressions occur at the top level and affect the top-level environment.)
The return value of a define expression is unspecified in the R5RS standard. I strongly suggest returning a VOID_TYPE value. Moreover, modify your interpreter so it does not print VOID_TYPE values.
Make sure define-bound variables resolve correctly.
(lambda (x1 x2 ... xk) body).
The value of this expression is a procedure object called a closure, which is a Value of CLOSURE_TYPE, consisting of all the data needed to apply this procedure later. Specifically, in the Value union, add a struct Closure consisting of (pointers to)
- a list of formal parameter names;
- the function body; and
- the frame in which the lambda expression was evaluated.
Combinations: (e1 ... en), where e1 is not a special form.
First, recursively evaluate e1 through en (in some unspecified order). Then, apply the value of e1 to the remaining values by calling an apply function with the following prototype:
```
Value *apply(Value *function, Value *args);
```
In the next checkpoint, you will extend apply to handle primitive functions such as + and cons. For now, apply should handle the case of function being a CLOSURE_TYPE, as follows:
- construct a new frame whose parent frame is the frame 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) in the new frame; and
- return this result (to eval).

When you are done, you should be able to handle a test like this one:

(define not
  (lambda (bool)
    (if bool #f #t)))
    
(define tofu
  (lambda (cond conseq alt)
    (let ((nconseq (not conseq))
          (nalt (not alt)))
      (if cond nconseq nalt))))
    
(tofu 23 #f #t)

5. Possible extensions

Support multiple expressions in the body of lambda as in let.
Support the syntactic sugar for binding variables to procedures that Dybvig and I eschew.
Support internal definitions at the beginning (only) of the body of a lambda, let, let*, or letrec expression.

6. Submission

Your code should have no memory leaks or memory errors when run on any input (correct or incorrect) using Valgrind. We will be checking this during grading, so you should test your code via Valgrind yourself.

Follow the submission instructions from the previous checkpoint; tag your commit with proj6 and push the tag to GitHub.

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

Start early, have fun, and discuss questions on Moodle.