walker...to the next step

I'll write the answers to the SICP exercises here, not everyone of them, though. I'm not planning to publish a book so I only write the ones I'm interested in, plus many stuff I found helpful or funny.

So here's the first one, the 1.5.

(define (p) (p))

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

(test 0 (p))

Most people seem to agree with the conclusion about the applicative-order one, so do I. The interpreter will keep evaluating the procedure p, in an endless manner. This is a typical situation where a recursion is without a proper ending condition.

Next comes the normal-order part. Well, most people do get the right answer, but they're being vague about the detailed substitute/eval process and they ignore the fact that if is a special form, rather than a combination.

In fact, after first round, (test 0 (p)) would be expanded to:

(if (= 0 0) 0 (p)).

Here comes the thing: according to the evaluation rule of normal-order, the interpreter “would first substitute operand expressions for parameters until it obtained an expression involving only primitive operators”. So at first I thought that since (p) in (if (= 0 0) 0 (p)) is NOT "an expression involving only primitive operators", it should be further expanded, thus lead to an endless recursion. But on second thought I checked the R5RS manual and here it is:

http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_idx_98

Bingo! if is a special form so the normal-order evaluation rule does not apply to it. (p) is never evaluated if the conditional expression is true.