SICP Exercise 1.5

Question

Exercise 1.5. Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:

(define (p) (p))

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

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation?

I understand the answer to the exercise; my question lies in how (p) is interpreted versus p. For example, (test 0 (p)) causes the interpreter to hang (which is expected), but (test 0 p) with the above definition immediately evaluates to 0. Why?

Moreover, suppose we changed the definition to (define (p) p). With the given definition, (test 0 (p)) and (test 0 p) both evaluate to 0. Why does this occur? Why doesn't the interpreter hang? I am using Dr. Racket with the SICP package.

Answer 1

p is a function. (p) is a call to a function.

In your interpreter evaluate p.

p <Return>
==>  P : #function

Now evaluate (p). Make sure you know how to kill your interpreter! (Probably there is a “Stop” button in Dr. Racket.)

(p)

Note that nothing happens. Or, at least, nothing visible. The interpreter is spinning away, eliminating tail calls (so, using near 0 memory), calling p.

As p and (p) evaluate to different things, you should expect different behaviour.

As to your second question : You are defining p to be a function that returns itself. Again, try evaluating p and (p) with your (define (p) p) and see what you get. My guess (I am using a computer on which I cannot install anything and which has no scheme) is that they will evaluate to the same thing. (I might even bet that (eq? p (p)) will evaluate to #t.)