Menu

SICP Distilled

Ch1 - Building Abstractions With Functions

Ch2 - Building Abstractions With Data

Ch3 - Modularity, Objects, and State

Ch4 - Metalinguistic Abstraction

The Substitution Model for Function Application

To apply a compound procedure to arguments, evaluate the body of the function with each formal parameter replaced by the corresponding argument.

Let's say we have:

(defn square [x]
  (* x x))

Then to evaluate

(square 5)

(* 5 5)

A more complicated example:

Given:

(defn f [a]
  (sum-of-squares (+ a 1) (* a 2)))

(defn sum-of-squares [x y]
  (+ (* x x) (* y y)))

To evaluate:

(f 5)

We first look up the body of f

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

and replace the formal parameter a with the argument 5, getting

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

Now we need to evaluate sum-of-squares in the same way, replacing x with the value of (+ 5 1) and replacing y with the value of (* 5 2), giving the following sequence of substitutions:

(+ (square 6) (square 10))

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

(+ 36 100)

136

Though this model gets us very far, it only works for 'pure' functions. The SICP text always uses the term 'procedure' for clarity to avoid confusing them with mathematical functions. I have referred to things created with fn as functions here as the usage is pretty common, I will refer to pure functions if they have this property. See also Referential Transparancy

We have seen that we can add names to the global environment with def, another way of describing the evaluation of (square 5) is to evaluate the body

(* x x)

in an environment where x is bound to 5. This is more like what happens inside a real interpreter (and what gets to create and/or update different environments is an important part of understanding a programming language).

Applicative order versus normal order

According to the description of evaluation so far, the interpreter first evaluates the operator and operands and then applies the resulting function to the resulting arguments.

An alternative evaluation model would not evaluate the operands until their values were needed. Instead it would first substitute operand 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) would proceed according to the sequence of substitutions:

(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

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.

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.

Lisps usually use applicative-order evaluation, partly because of the additional efficiency obtained from avoiding multiple evaluations of expressions such as those illustrated with (+ 5 1) and (* 5 2) above and, more significantly, because normal-order evaluation becomes much more complicated to deal with when we leave the realm of functions that can be modelled by substitution.