So far we have seen how Racket breaks down and evaluates expressions such as:
(+ 1 2)
(+ 3 4 (* 2 5))
by following these steps:
We have been slightly handwavy with step 3. How exactly do you 'apply'
procedures? For primitive functions like
not, we can
assume that it is built into the interpreter . We are more interested in
something more complex: how do we apply compound (i.e. user defined) procedures? Since we
can define arbitarily many compound procedures, they can't all be built into the
interpreter. There needs to be a a common step-by-step way to apply compound
procedures. One way to think about this is the Substitution Model, which we
will explore in this subsection.
To apply a compound procedure with the Substitution Model, you substitute each formal parameter in the body with the corresponding argument's value and evaluate it normally. What does this actually mean? It's easier to see through an example:
sum-of-squares procedure from the very first lab, which can be
defined as follows:
(define (sum-of-squares x y) (+ (square x) (square y))) ;; This line is the 'body' of the procedure (define (square x) (* x x))
How does the Substitution Model handle
(sum-of-squares 3 4) ?
(+ (square 3) (square 4))
(+ (* 3 3) (* 4 4)).
(+ 9 16)
Step 1 and 2 are the most crucial part of the Substitution Model: finding what values are passed into the function, and substituting every occurence of a variable in the body with its corresponding value.
You might have noticed by now that the names of formal parameters are arbitary. For example all of the followings are equivalent:
(define (square x) (* x x))
(define (square apple) (* apple apple))
(define (square magikarp) (* magikarp magikarp))
The Substitution Model handles all three equivalently, though it is best to pick a name that is easy to understand (In this case, the first definition is ideal). The main point is to stay consistent within the body. The following for example, might cause an error:
(define (square x) (* apple apple))
When we use Substitution Model with
(square 4) with the definition above, you
can notice that things are not properly defined. The procedure
square accepts an argument,
x which in this case is 4. What do we do in the body? We need to find the
apple and do
(* apple apple). What is the value of
don't know! We only know what
Does Racket actually use the Substitution Model to apply compound procedures? Not quite. We use the Substitution Model to help us think about procedure application. Racket does something slightly more complicated, which we will explore in Unit 3 and 4. Later on, we will find that the Substitution Model is not sufficient to explain some functions in Racket. This model will serve as a framework which we will build on.
Our method of evaluation by evaluating operator, evaluating the operands and then applying the operator is just one possible rule of evaluation. The ordering we have been using is called "Applicative Order". An alternative method of evaluation would be to not evaluate the operand until the value is needed. This method is called "Normal Order". We can see the difference between these 2 from the following example:
(square (+ 3 2))
Note that the input to square is (
+ 3 2).
(square (+ 3 2))
(* 5 5)
In Applicative Order, you would evaluate the parameter
x, before you go the
body of square, which is
(* x x). When you evaluate
(+ 3 2), you get
this is what you pass into square. So
x is bound to
(square (+ 3 2))
(* (+ 3 2) (+ 3 2))
(* 5 5)
In Normal Order, you don't evaluate
(+ 3 2) until you absolutely need to. So in this case, the
(square x) is bound to
(+ 3 2).
Notice that, in Normal Order, since you don't evaluate the
x, which is
(+ 3 2), until it's needed, you need to evaluate it twice. On the other hand, in Applicative Order, since you evaluate the operand
x before applying the procedure, you only evaluate
(+ 3 2) once.
Consider the following piece of code:
(define (double_first a b) (+ a a)) (double_first (+ 1 1) (+ 2 2))
Some takeaways from this subsection: