In this final part, you will complete your Scheme interpreter based on the starter code and your solutions to Part One and Part Two. Make all edits to SchemeEvaluator.java.

Evaluation is always done in the contex of some environment. The file Primitives.java provides values for the global environment, such as +, display, cons, and =. New environments are created when a lambda is applied (including the implicit applications, such as when using the let special form).

Evaluation Rules

Your evaluator must support the following forms and rules:

1. A symbol expression (that is, an expression that is just a symbol) is evaluated by looking up that name in the environment in which the expression is being evaluated. For example, the expression x would evaluate to whatever environment.lookupVariable("x") returns.

2. A self-evaluating expression-- like a boolean, character, string, or number-- already represents a value and can just be directly returned.

3. A list expression that doesn't start with the name of a special form is a "combination" (recall 4.1.1 of SICP). This is the application of a function: First, evaluate the operator (the expression that will be the function applied) and evaluate the operands (the arguments passed to the function by that call). Next, for a non-primitive procedure, create a new environment that extends the environment in which the lambda was originally created-- matching the names of the parameters with the right corresponding arguments. Then, in that new environment, evaluate the body of the lambda.

4. A list expression that starts with quote is the quote special form, which evaluates to the (uninterpreted) datum after it.

5. The set! special form evaluates the value to be assigned and updates the environment so that the assigned variable gets that new value.

   The following example shows you how to express that process in code:

   static Value evaluateAssignment(LinkedList<Value> body, Environment env) {
     matchSymbol(body, "set!");
     SymbolDatum variable = next(body, LexemeDatum.SymbolDatum.class);
     Value value = evaluate(next(body, Datum.class), env);
     noExtras(body, "set!");
     env.setVariable(variable.toString(), value);
     return RuntimeValue.newUnspecified();
   }

   Where next and matchSymbol are helper methods (not provided) that remove and check values from the body queue, and where noExtras checks that the body queue is then empty.

6. The define special form defines a variable in the environment (using env.defineVariable(.., ..), in constrast to the env.setVariable(.., ..) used by set!.)

   The syntactic sugar forms of define must be supported, where the following short-hands are translated into the equivalent lambdas:

   (define (f) ...) => (define f (lambda () ... ))
   (define (f . all) ... ) => (define f (lambda all ...))
   (define (f x) ... ) => (define f (lambda (x) ...))
   (define (f x y . rest) ... ) => (define f (lambda (x y . rest) ...))

7. The let special form is sugar for creating new names bound to some given expressions:

   (let ([n e] [m f]) body) => ((lambda (n m) body) e f)

   Where n and m are names (identifiers), and e and f are arbitrary expressions (including even other let expressions!). You do not need to implement the named-let form for this project.

8. The if special form conditionally executes its consequent expression or its (optional) alternative expression. For example:

   static Value evaluateIf(LinkedList<Value> body, Environment env) {
     matchSymbol(body, "if");
     Value condition = evaluate(next(body, Datum.class), env);
     Datum consequent = next(body, Datum.class);
     Datum alternative = (!body.isEmpty()) ? next(body, Datum.class) : null;
     noExtras(body, "if");
     Datum target = (condition.isTrue()) ? consequent : alternative;
     if (target == null) {
       return RuntimeValue.newUnspecified();
     }
     return evaluate(target, env);
   }

9. Your evaluator must support the cond special form.

10. Your evaluator must support the begin special form.

11. Last, but not least, your evaluator must support the lambda special form, including the various ways to express variable-arity procedures. The starter code includes a commented example Lambda class that extends RuntimeValue.Procedure. Extracting the names of the formal parameters, and determining if a lambda accepts a variable number of arguments, and keeping a reference to the current environment are all duties your lambda must handle.