Extended Exercise: Evaluating Scheme, Part 2

The goal of this section is to extend the interpreter of section  so that it can cope with function applications and function definitions. In other words, the new interpreter 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 function to an expression. 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 interpret-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 interpreted as before. For (the representation of) a variable, the function signals an error. For an application of the function P, interpret-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 of the idea:

   (interpret-with-one-def (substitute val-of-arg fun-para fun-body)
                           a-fun-def) 
   

Exercise 17.7.4

Develop the function interpret-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 interpreted as before. For an application of the function P, interpret-with-defs

1. evaluates the argument;
2. looks up the definition of the function 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.