Extended Exercise: Evaluating Scheme, Part 2

The goal of this section is to extend the evaluator of section  so that it can cope with function applications and function definitions. In other words, the new evaluator simulates what happens in DrScheme when we enter an expression in the Interactions window after clicking Execute. To make things simple, we assume that all functions in the Definitions window consume one argument.

Exercise 17.7.1

Extend the data definition of exercise  so that we can represent the application of a user-defined function to an expression such as (f (+ 1 1)) or (* 3 (g 2)). The application should be represented as a structure with two fields. The first field contains the name of the function, the second one the representation of the argument expression. Solution

A full-fledged evaluator can also deal with function definitions.

Exercise 17.7.2

Provide a structure definition and a data definition for definitions. Recall that a function definition has three essential attributes:

1. the function's name,
2. the parameter name, and
3. the function's body.

Translate the following definitions into Scheme values:

1. (define (f x) (+ 3 x))
2. (define (g x) (* 3 x))
3. (define (h u) (f (* 2 u)))
4. (define (i v) (+ (* v v) (* v v)))
5. (define (k w) (* (h w) (i w)))

Exercise 17.7.3

Develop evaluate-with-one-def. The function consumes (the representation of) a Scheme expression and (the representation of) a single function definition, P.

The remaining expressions from exercise  are evaluated as before. For (the representation of) a variable, the function signals an error. For an application of the function P, evaluate-with-one-def

1. evaluates the argument;
2. substitutes the value of the argument for the function parameter in the function's body; and
3. evaluates the new expression via recursion. Here is a sketch:

   (evaluate-with-one-def (subst ... ... ...) 
                          a-fun-def) 
   

Exercise 17.7.4

Develop the function evaluate-with-defs. The function consumes (the representation of) a Scheme expression and a list of (representations of) function definitions, defs. The function produces the number that DrScheme would produce if we were to evaluate the actual Scheme expression in the Interactions window and if the Definitions window contained the actual definitions.

The remaining expressions from exercise  are evaluated as before. For an application of the function P, evaluate-with-defs

1. evaluates the argument;
2. looks up the definition of P in defs;
3. substitutes the value of the argument for the function parameter in the function's body; and
4. evaluates the new expression via recursion.