To evaluate a function application, the interpreter follows the process described in section 1.1.4. That is, the interpreter evaluates the elements of the application and applies the function (which is the value of the function expression of the application) to the arguments (which are the values of the argument expressions of the application).
We can assume that the mechanism for applying primitive functions to arguments is built into the interpreter. For compound functions, the application process is as follows:
f(5)
sum_of_squares(a + 1, a * 2)
sum_of_squares(5 + 1, 5 * 2)
Thus the problem reduces to the evaluation of an application with two arguments and a function expression sum_of_squares. Evaluating this application involves three subproblems. We must evaluate the operator to get the function to be applied, and we must evaluate the argument expressions to get the arguments. Now 5 + 1 produces 6 and 5 * 2 produces 10, so we must apply the sum_of_squares function to 6 and 10. These values are substituted for the parameters x and y in the body of sum_of_squares, reducing the expression to
square(6) + square(10)
(6 * 6) + (10 * 10)
36 + 100
136
The process we have just described is called the substitution
model for
function
application. It can be taken as a model that
determines the meaning
of
function
application, insofar as the
functions
in this chapter are concerned. However, there are two
points that should be stressed:
substitutionis accomplished by using a local environment for the parameters. We will discuss this more fully in chapters 3 and 4 when we examine the implementation of an interpreter in detail.
mutable data,we will see that the substitution model breaks down and must be replaced by a more complicated model of function application.[1]
According to the description of evaluation given in section 1.1.4, the interpreter first evaluates the function and argument expressions and then applies the resulting function to the resulting arguments. This is not the only way to perform evaluation. An alternative evaluation model would not evaluate the arguments until their values were needed. Instead it would first substitute argument expressions for parameters until it obtained an expression involving only primitive operators, and would then perform the evaluation. If we used this method, the evaluation of
f(5)
sum_of_squares(5 + 1, 5 * 2) square(5 + 1) + square(5 * 2) (5 + 1) * (5 + 1) + (5 * 2) * (5 * 2)
6 * 6 + 10 * 10 36 + 100 136
x * x
This alternative fully expand and then reduce
evaluation method is known as
normal-order evaluation, in contrast to the evaluate
the arguments and then apply
method that the interpreter actually
uses, which is called
applicative-order evaluation. It can be shown that, for
function
applications that can be modeled using substitution (including all the
functions
in the first two chapters of this book) and that yield legitimate values,
normal-order and applicative-order evaluation produce the same value.
(See exercise 1.5
for an instance of an illegitimate
value where normal-order
and applicative-order evaluation do not give the same result.)
JavaScript uses applicative-order evaluation, partly because of the additional efficiency obtained from avoiding multiple evaluations of expressions such as those illustrated with above and, more significantly, because normal-order evaluation becomes much more complicated to deal with when we leave the realm of procedures that can be modeled by substitution. On the other hand, normal-order evaluation can be an extremely valuable tool, and we will investigate some of its implications in chapters 3 and 4.[2]