## SICP Goodness - Applicative Order v.s. Normal Order

Some goodness from the book Structure and Interpretation of Computer Programs

Do you think Computer Science

equalsbuilding websites and mobile apps?Are you feeling that you are doing

repetitiveandnot so intelligentwork?Are you feeling a bit

sickaboutreading manualsandcopy-pastingcode and keeppoking arounduntil it worksall day long?Do you want to understand the

soulofComputer Science?If yes,

read SICP!!!

This is the first post of this **SICP Goodness** series, in which I discuss some of my own findings from reading the book SICP.

Today’s topic is about two ways to perform evaluation of the program: **Applicative Order** and **Normal Order**.

Let’s put here the example from the book.

First, define some functions to calculate the sum of squares of two numbers.

```
(define (square x) (* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
(define (f a)
(sum-of-squares (+ a 1) (* a 2)))
```

Now, let’s evaluate the expression `(f 5)`

using the two models.

# Applicative Order Evalutation

The process of this approach can be summarized as **evaluate the function and arguments and then apply**.

```
(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(sum-of-squares 6 10)
(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136
```

# Normal Order Evaluation

The process of this approach can be summarized as **fully expand and then reduce**.

The steps are as follows:

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

It feels like applicative order is more *eager* while normal order is more *lazy*.

There are some cases that the two yield different results.

Exercise 1.5 gives a way to test wether the language uses applicative order or normal order.

The test is as follows:

```
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
(test 0 (p))
```

Try figure out how this test can behave differently under different evaluation models.

## Answer

`p`

is a endless recursive function, it will exec forever. If the language is applicative order, then when evaluate `(test 0 (p))`

,
it will first try to evaluate `(p)`

, which will of course end up in an endless loop. However, if the language is normal order, this evaluation gets delayed.

```
(test 0 (p))
(if (= 0 0)
0
(p))
0
```

And the `(p)`

is now pushed to the `else`

part of the `if`

. When the `if`

clause gets evaluated, it just returns 0 without even look at `(p)`

.

Clever isn’t it.

Twitter

Google+

Facebook

Reddit

LinkedIn

StumbleUpon

Email