Exercise SICP 1.5

Question

Exercise 1.5. Ben Bitdiddle invented the test to determine which interpreter he is facing, using the applicative order of evaluation or normal order evaluation. It defines the following two Procedures:

(define (p) (p))

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

Then it evaluates the expression

(test 0 (p))

What kind of behavior will Ben observe with the help of an interpreter that uses the evaluation of the applicative order? What behavior will he observe using an interpreter that uses a normal order estimate?

I understand the answer to the exercise; my question is how (p) is interpreted compared to 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?

Also, suppose we change the definition to (define (p) p). Given the definition (test 0 (p)) and (test 0 p), both values ​​are 0. Why is this happening? Why is the translator not hanging? I am using Dr. Racket with SICP.

Answer 1

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

In your interpreter, evaluate p .

 p <Return> ==> P : #function 

Now evaluate (p) . Make sure you know how to kill your translator! (Perhaps there is a Stop button in Dr. Racket.)

 (p) 

Please note that nothing happens. Or at least nothing is visible. The interpreter rotates, eliminating tail calls (so, using about 0 memory), causing p .

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

As for your second question: you define p as a function that returns itself. Again, try evaluating p and (p) with (define (p) p) and see what you get. My assumption (I use a computer on which I can’t install anything and which does not have a circuit) is that they will evaluate the same thing. (I can even argue that (eq? p (p)) will evaluate to #t .)