Menu

- Chapter 1 Distilled
- Introduction
- 1.1 - The Elements Of Programming
- Expressions
- Naming and the Environment
- Evaluating Combinations
- Defining New Functions
- The Substitution Model
- Exercises
- Predicates
- Conditional Expressions
- Example: Newton’s Method
- Functions as Black-Box Abstractions
- 1.2 - Procedures and the Processes They Generate
- Linear Recursion and Iteration
- Tree Recursion
- Orders of Growth
- Exponentiation
- Example: Testing For Primality
- 1.3 Higher Order Functions
- Project - Blackjack

- Chapter 2 Distilled
- Introduction
- Data Abstraction
- Everything From Nothing
- Abstractions In Clojure
- Clojure's Data Structures
- Data Abstraction, Revisited
- Escher
- Project - Escher
- Symbolic Data
- Representing Sets
- Huffman Encoding Trees
- Zippers

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)
```

Take the body of the function

`(* x x)`

Replace formal parameter,

`x`

, with the value of the argument,`5`

```
(* 5 5)
```

- evaluate it to get 25

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).

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.