3.6.2 Substitution model of evaluation

For a procedure to be useful, we need to apply it. In Section 3.4.2, we saw the syntax and evaluation rule for an ApplicationExpression when the procedure to be applied is a primitive procedure. The syntax for applying a constructed procedure is identical to the syntax for applying a primitive procedure:

Expression ::$\Rightarrow$ ApplicationExpression
ApplicationExpression ::$\Rightarrow$ (Expression MoreExpressions)
MoreExpressions ::$\Rightarrow$ $\epsilon$ | MoreExpressions

To understand how constructed procedures are evaluated, we need a new evaluation rule. In this case, the first Expression evaluates to a procedure that was created using a ProcedureExpression, so the ApplicationExpression becomes:

ApplicationExpression ::$\Rightarrow$ (( (lambda (Parameters) Expression) MoreExpressions)

(The underlined part is the replacement for the ProcedureExpression.)

To evaluate the application, first evaluate the MoreExpressions in the application expression. These expressions are known as the operands of the application. The resulting values are the inputs to the procedure. There must be exactly one expression in the MoreExpressions corresponding to each name in the parameters list. Next, associate the names in the Parameters list with the corresponding operand values. Finally, evaluate the expression that is the body of the procedure. Whenever any parameter name is used inside the body expression, the name evaluates to the value of the corresponding input that is associated with that name.

Example 3.1: Square

Consider evaluating the following expression:

 ((lambda (x) (* x x)) 2)

It is an ApplicationExpression where the first subexpression is the ProcedureExpression, (lambda (x) (* x x)). To evaluate the application, we evaluate all the subexpressions and apply the value of the first subexpression to the values of the remaining subexpressions. The first subexpression evaluates to a procedure that takes one parameter named x and has the expression body (* x x). There is one operand expression, the primitive 2, that evaluates to 2.

To evaluate the application we bind the first parameter, x, to the value of the first operand, 2, and evaluate the procedure body, (* x x). After substituting the parameter values, we have (* 2 2). This is an application of the primitive multiplication procedure. Evaluating the application results in the value 4.

The procedure in our example, (lambda (x) (* x x)), is a procedure that takes a number as input and as output produces the square of that number. We can use the definition mechanism (from Section 3.5) to give this procedure a name so we can reuse it:

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

This defines the name square as the procedure. After this, we can apply square to any number:

Scheme output
> (square 2)  
> (square 1/4)
> (square (square 2))  
Example 3.2: Make adder

The expression

((lambda (a) (lambda (b) (+ a b))) 3)

evaluates to a procedure that adds 3 to its input. Applying that procedure to 4,

(((lambda (a) (lambda (b) (+ a b))) 3) 4)

evaluates to 7. By using define, we can give these procedures sensible names:

(define make-adder (lambda (a) (lambda (b) (+ a b))))

Then, (define add-three (make-adder 3)) defines add-three as a procedure that takes one parameter and outputs the value of that parameter plus 3.

Abbreviated Procedure Definitions. Since we commonly define new procedures, Scheme provides a condensed notation for defining a procedure1 :

Definition ::$\Rightarrow$ (define (Name Parameters) Expression)

This incorporates the lambda invisibly into the definition, but means exactly the same thing. For example,

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

can be written equivalently as:

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

Exercise 3.5. Define a procedure, cube, that takes one number as input and produces as output the cube of that number.

Exercise 3.6. Define a procedure, compute-cost, that takes as input two numbers, the first represents that price of an item, and the second represents the sales tax rate. The output should be the total cost, which is computed as the price of the item plus the sales tax on the item, which is its price times the sales tax rate. For example, (compute-cost 13 0.05) should evaluate to 13.65.

  1. The condensed notation also includes a begin expression, which is a special form. We will not need the begin expression until we start dealing with procedures that have side effects. We describe the `begin special form in Chapter 9