schemelispevaluationsicp# Why normal-order and applicative-order evaluation are not giving the same value?

I am reading this book Structure and Interpretation of Computer Programs, 2nd edition and on page 21 under the subsection "Applicative order versus normal order" it is written that -

It can be shown that, for procedure applications that can be modeled using substitution (including all the procedures in the ﬁrst two chapters of this book) and that yield legitimate values, normal-order and applicative-order evaluation produce the same value. (See Exercise 1.5 for an instance of an “illegitimate” value where normal-order and applicative-order evaluation do not give the same result.)

Now in the above mentioned exercise, the code is as follows:

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

If I use substitution model,

- Retrieve the body of
`test`

procedure:

`(if (= x 0) 0 y)`

- Replace the formal parameter
`x`

by the argument 0 and`y`

by the argument`(p)`

:

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

`(if #t 0 (p))`

`0`

I think `0`

is a legitimate value in scheme.

Now according to the text, both normal order and applicative order evaluation should give the same result.

Normal order evaluation:

- Expansion (ﬁrst substitute operand expressions for parameters):

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

`(if #t 0 (p))`

- Reduction:

`0`

Applicative order evaluation:

`test`

will evaluate to the procedure defined.

`0`

will evaluate to the number O.

`(p)`

will evaluate to `(p)`

, which will evaluate to `(p)`

On the evaluation of the argument `(p)`

, the interpreter will continue to evaluate it forever (in an infinite recursion). So, we will not get the value of the expression.

You can see that normal order gives a value whereas applicative order does not. So, if substitution model gives a legitimate value, then why they are not the same?

Edit:

My bad. I did not evaluate the operator and the operands first in the substitution model before applying the value of operator to the operands. That is what missing in the above detail.

The substitution model will not give a legitimate value (or any value at all) as evaluation of the argument `(p)`

will never terminate. Hence, normal order will give a value of the expression whereas applicative order will not.

Solution

Given the definition

```
(define (p) (p))
```

Does the substitution model give a legitimate value for `(p)`

? Does it give any value at all?

No: it doesn't: the computation fails to terminate. So applicative and normal order are not equivalent in this case. In particular normal order will give a value to the expression `(test 0 (p))`

and applicative order will not.

In fact given the above definition of `p`

then `(p)`

simply does not have a value as it never terminates: this doesn't depend on using the substitution model, it just depends on the fact that the definition of `p`

is circular: there's no base case to the definition.

*But* given

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

Then, under normal order evaluation, `(test 0 (p))`

will never attempt to evaluate `(p)`

at all and thus will terminate. Applicative order evaluation, on the other hand, *will* attempt to evaluate all of the arguments to `test`

, and will therefore attempt to evaluate `(p)`

, and fail to terminate.

- How do I get the functions put and get in SICP, Scheme, Exercise 2.78 and on
- Trouble understanding / visualising SICP streams Hamming numbers program
- Unbound variable error in cube root function
- Scheme - Replacing elements in a list with its index
- What is the relation of parent env and the child env in MIT-Scheme?
- conda, condi, conde, condu
- Pipe-Function in scheme
- DrRacket: atom? and symbol? undefined - What's wrong?
- curry in scheme
- What are some good ways of implementing tail call elimination?
- How do I perform basic file I/O operations Scheme?
- One way to construct graph adjacency list based on adjacency pairs similar to `fold` in MIT Scheme
- Graph programming in Scheme
- "The object square is not applicable" but `square` is one internal procedure in MIT-Scheme
- How is nested variable argument interpreted in Scheme?
- Advantages of "typed Racket" over Racket
- Typed Racket - dynamic function calls (string to procedure) revisited
- How to make `set!` change the variable in `let` (Scheme)?
- How to use symbolic expressions produced by a function to define another function?
- Create an infinite stream from a list
- Why does Scheme use the procedural representation of pairs?
- Implementing a "Pythonic" map in Scheme: bad idea?
- Store external data in guile modules?
- Scheme: Returning two largest numbers from a set of three numbers
- `1.0+1e-100=1.` in MIT-scheme
- Scheme merge two lists into one
- How to recursively reverse a list using only basic operations?
- What's the proper scheme file extension?
- How to obtain my function definition in MIT Scheme?
- How does the yin-yang puzzle work?