To evaluate an application combination, the interpreter follows a similar process as for operator combinations, which we described in section 1.1.3. That is, the interpreter evaluates the elements of the combination and applies the function (which is the value of the function expression) to the arguments (which are the values of the argument expressions of the application combination).
In more detail, the interpreter proceeds as follows when evaluating application combinations:
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 combination with two arguments and a function expression sum_of_squares. Evaluating this combination involves three subproblems. We must evaluate the function expression 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 return expression of sum_of_squares, reducing the expression to
square(6) + square(10)
(6 * 6) + square(10)
36 + square(10)
36 + (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 above, 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 operands until their values were needed. Instead it would first substitute argument expressions for parameters until it obtained an expression involving only operators, and would then perform the evaluation. If we used this method, the evaluation of
f(5)
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.)