In this problem we study two models for procedure application.

Substitution Model for Procedure Application

(Applicative-order Evaluation)

To apply a procedure to its arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument value. To illustrate this process, suppose the following definitions:

(define (square x)
  (* x x))

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))

Consider the evaluation of:

(f 5)

We begin by retrieving the body of f:

(sum-of-squares (+ a 1) (* a 2))

Then we replace the formal parameter a by the argument value 5 yielding:

(sum-of-squares (+ 5 1) (* 5 2))

Evaluating this form involves three subproblems. We must evaluate the three elements of this list to get the function sum-of-squares and its arguments, 6 and 10. These values are substituted for the formal parameters x and y in the body of sum-of-squares, reducing the expression to:

(+ (square 6) (square 10))

Using the definition of square we get:

(+ (* 6 6) (* 10 10))

Which reduces to:

(+ 36 100)

Yielding:

136

The process described in the above example is called the substitution model for procedure evaluation. The substitution model is a model that allows one to think about procedure application. Typical Scheme systems do not evaluate procedure applications by operating on the actual text of the procedure body to substitute the values for formal parameters. In practice, the "substitution" is accomplished by using a local environment for the formal parameters. This is not the only way to perform evaluation.

Normal-order Evaluation

An alternative evaluation model would first expand each procedure definition in terms of simpler and simpler procedures until it obtained an expression involving only primitive operators and would then perform evaluation. If we used this method on the previous example:

(f 5)

we get:

(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1) ) (square (* 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))

then we evaluate:

(+ (* 6 6) (* 10 10))
(+ 36 100)

yielding:

136

This gives the same answer as our previous evaluation model, but the process is different. In particular, the evaluations of (+ 5 1) and (* 5 2) are each performed twice here.

Ben Bitdiddle has invented a test to determine whether the Scheme system he has is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:

(define (p) (p))

(define (test x y)
  (if (= x 0)
    0
    y))

Then he evaluates the form

(test 0 (p))

What behavior will Ben observe with a Scheme system which uses applicative-order evaluation? What behavior will he observe with a Scheme system that uses normal-order evaluation? Explain your answers. What type of evaluation is used by scm?

Lab 3 Scheme Code