# SICP - Solution: Exercise 1.20

##### October 14, 2018

## Exercise 1.20 #

The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative

`gcd`

procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed in 1.1.5. (The normal-order-evaluation rule for if is described in Exercise 1.5.) Using the substitution method (for normal order), illustrate the process generated in evaluating`(gcd 206 40)`

and indicate the remainder operations that are actually performed. How many remainder operations are actually performed in the normal-order evaluation of`(gcd 206 40)`

? In the applicative-order evaluation?

## Solution #

```
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
```

### Normal-order evaluation #

With an interpreter that uses **normal-order evaluation**, the interpreter will “fully expand and then reduce”.

```
(gcd 206 40)
(if (= 40 0)
206
(gcd 40 (remainder 206 40)))
(gcd 40 (remainder 206 40))
(if (= (remainder 206 40) 0)
40
(gcd (remainder 206 40)
(remainder 40 (remainder 206 40))))
; 1*remainder
(if (= 6 0)
40
(gcd (remainder 206 40)
(remainder 40 (remainder 206 40))))
(gcd (remainder 206 40)
(remainder 40 (remainder 206 40)))
(if (= (remainder 40 (remainder 206 40)) 0)
(remainder 206 40)
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
; 1*remainder
(if (= (remainder 40 6) 0)
(remainder 206 40)
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
; 1*remainder
(if (= 4 0)
(remainder 206 40)
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
(if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0)
(remainder 40 (remainder 206 40))
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
(remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
; 4*remainder
(if (= 2 0)
(remainder 40 (remainder 206 40))
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
(remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
(remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
(if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0)
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
(gcd (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) (remainder a (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))))
; 7*remainder
(if (= 0 0)
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
(gcd (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) (remainder a (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
; 4*remainder
2
```

Using **normal-order evaluation**, `remainder`

is called 18 times.

### Applicative-order evaluation #

An interpreter that uses **applicative-order evaluation** will “evaluate the arguments and then apply”.

```
(gcd 206 40)
(if (= 40 0)
206
(gcd 40 (remainder 206 40))) ; 1*remainder
(gcd 40 6)
(if (= 6 0)
40
(gcd 6 (remainder 40 6))) ; 1*remainder
(gcd 6 4)
(if (= 4 0)
6
(gcd 4 (remainder 6 4))) ; 1*remainder
(gcd 4 2)
(if (= 2 0)
4
(gcd 2 (remainder 4 2))) ; 1*remainder
(gcd 2 0)
(if (= 0 0)
2
(gcd 0 (remainder 2 0)))
2
```

Using **applicative-order evaluation**, `remainder`

is called 4 times.