What's the explanation for Exercise 1.6 in SICP?
new-if
is a function. When a function is called, what's the first thing that Scheme does with the argument list? It evaluates all the arguments.
new-if
is a procedure, and Scheme uses applicative-order evaluation (1.1.5), so even before new-if
is actually performed, it has to evaluate all the arguments first, which are guess
and (sqrt-iter (improve guess x) x)
. You can see that the latter argument is a recursion, which calls a new new-if
procedure, this is how the infinite loop occurs.
The ordinary if
need not evaluate its arguments first, just go along the way, this is the difference between if
and new-if
. :)
First of all you have to understand the difference between applicative order evaluation and normal order. Lisp uses applicative order, but conditional expressions are evaluated not like normal functions (sicp chapter 1.1.6):
(if <predicate> <consequent> <alternative>)
To evaluate an if expression, the interpreter starts by evaluating the
<predicate>
part of the expression. If the<predicate>
evaluates to a true value, the interpreter then evaluates the<consequent>
and returns its value. Otherwise it evaluates the<alternative>
and returns its value.
There are three ways a form may be evaluated in Scheme:
-
Applicative Order
- evaluate the arguments and then apply
- given
f(x)=x+x
:3*f(1)*f(1)
⇒3*2*2
-
Normal Order
- fully expand and then reduce
- given
f(x)=x+x
:3*f(1)*f(1)
⇒3*(1+1)*(1+1)
(also used in "lazy evaluation")
-
Special Forms For example:
- Booleans
and
andor
. For example:(and <e1> ... <en>)
evaluates Left → Right. If any evaluates to false, the value of the and expression is false, and the rest of the<e>
's are not evaluated. - Conditionals like
if
andcond
-
(if <predicate> <consequent> <alternative>)
: If the<predicate>
evaluates to a true value, the interpreter then evaluates the<consequent>
and returns its value. Otherwise it evaluates the<alternative>
and returns its value -
(cond (<p1> <e1>) ... (<pn> <en>))
: The predicate<p1>
is evaluated first. If its value is false, then<pn>
is evaluated. If<pn>
's value is also false, then<pn+1>
is evaluated. When true predicate, the interpreter returns the value of the corresponding consequent expression<e>
.
-
- Booleans
In the case of Exercise 1.6:
-
new-if
is a normal procedure. In Scheme (and many other languages), arguments are fully evaluated before the procedure is called. This is known as applicative order. ∴sqrt-iter
is called every timenew-if
is called, resulting in an infinite loop. - For the reader's edification, normal
if
s are a special form. The recursive statement wouldn't be evaluated unless the<alternative>
is called.