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.

- Combination of list-ref and index-of in racket
- How to undefine a variable in Scheme?
- Running Scheme from the command line
- Function that splits word
- How does the yin-yang puzzle work?
- Dr Racket Recursing Without Returning Inital Parent Node Within Function
- Chez Scheme FFI Procedure Doesn't Work After Change to Apple Silicon
- How do we convert this Scheme (Lisp) function into C#
- What is #~ in scheme?
- Racket : Run scheme file in terminal and show result
- Recursive numeric equality in Scheme
- Under any Scheme standard, is (let (x y z) x) valid code?
- Iterate through the letters of the alphabet in Racket
- What do Lisp macros have over functions that optionally evaluate their arguments?
- Delayed "let" in SICP
- Chicken Scheme pass on parameters to gcc
- Say we have an abstract data type for cities. A city has a name, a latitude coordinate, and a longitude coordinate
- Why doesn't this Scheme s-expression work when the sub expressions work?
- How do I read a web page in Racket?
- Why normal-order and applicative-order evaluation are not giving the same value?
- Implement a procedure remove that takes in a list and returns a new list with all instances of item removed from lst
- Lisp / Scheme : Evaluating nested empty list/cons : (())
- Converting a function with two recursive calls in scheme to make it tail-recursive
- GIMP: test.scm gets "unbound variable" error when run
- Upside down text
- how to redefine the function "range" in Racket/Scheme?
- Clearing the screen by printing a character?
- accumulative recursive function to produce a list of subtotals from last to first
- SICP example: Counting change, cannot understand
- What's the meaning of "explicit-control" in "explicit-control evaluator"?