seek for some explanation on SICP exercise 1.5

Question

The question can be found here.

In the book, I found one description of normal order evaluation was:

"An alternative evaluation model would not evaluate the operands until their values were needed. Instead it would first substitute operand expressions for parameters until it obtained an expression involving only primitive operators, and would then perform the evaluation."

I also found another description in short: "fully expand and then reduce".

In the exercise, I thought the definition of p was something like (lambda () (p)), which would never expand to a primitive operator, thus never terminate.

However, on the other hand, after googling some answers to this question, it seems normal order evaluation should terminate because it only evaluates things as needed, and actually (p) won't be evaluated.

So I think there must be some difference between "expand" and "evaluate" and what the interpreter does here is to evaluate things.

What exactly is the difference, or are there some points that I have missed?

Another question: Should I say "(p) is evaluated to (p)" or "(p) is expanded to (p)"?

Answer 1

You're right that an applicative-order evaluator would not terminate if asked to evaluate (p). However, the question at hand mentions that if has a particular evaluation semantics which is shared by the applicative and normal-order evaluators. Specifically, "Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression."

The code from the exercise is

(define (p) (p))

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

and the test under consideration is

(test 0 (p))

Normal-order evaluation is the "fully expand and then reduce" option. Under normal-order evaluation, (test 0 (p)) is fully expanded as

(test 0 (p)) ==
(if (= 0 0)
  0
  (p))

Since if has the semantics described above, and the test condition in the expansion is (= 0 0), which is true, the normal-order evaluator determines to evaluate the consequent, which is 0, so the value of the expression is 0.

Using the applicative-order evaluation however, the first step in evaluating (test 0 (p)) is to evaluate the expressions test, 0, and (p), and then call ^{("apply", hence "applicative")} the value of test with the values produced by evaluating 0 and (p). Since the evaluation of (p) will not complete, neither will the evaluation of (test 0 (p)).

Answer 2

Under the normal evaluation rules, (p) would be evaluated by calling the function p with no arguments. For example (in Common Lisp):

> (defun p ()
    5)
  => P
> (p)
  => 5

Your question started by mentioning something known as 'lazy evaluation'. Common Lisp does not do this by default; it evaluates all arguments to a function from left to right. Scheme does not specify the order in which they are evaluated, just that they will be.

However, before things can be evaluated, they need to be expanded (which can mean a number of things in lisp), which gives lisp the ability to control the order of evaluation. For example, p could be a macro. In this case, the normal evaluation rules don't necessarily apply. Again, in Common Lisp:

> (defmacro p ()
    (print "I'm being expanded!") ; print on expansion
    (terpri) ; new line.
    `(progn (print "I'm being evaluated!") ; print on evaluation
            (terpri)
            5))
  => P

This is entered the Read Evaluate Print Loop. The expression is read, then expanded, evaluated, then printed.

> (p)
  I'm being expanded!
  I'm being evaluated!
  => 5

To stop the expansion being evaluated, let's stick it in a lambda. You will notice that it still prints the expansion message.

> (defvar foo (lambda () (p)))
  I'm being expanded!
  => COMPILED FUNCTION #<LAMBDA>

Now we call it, and the form is evaluated.

> (funcall foo) ; call the function 
  I'm being evaluated!
  => 5

You can expand a macro invocation on its own.

> (macroexpand-1 '(lambda () (p)))
  I'm being expanded!
  => (lambda () (progn (print "I'm being evaluated!")
                       (terpri)
                       5))

Languages such as Haskell have lazy evaluation by default. In the passage you quoted, SICP has you imagine a lazy version of lisp. For such a lisp to work, and only evaluate things that are needed, it would need to not just blindly expand and evaluate everything until it arrives at a value (see the discussion of the substitution model in SICP), but to just expand things and only evaluate things when it is specifically asked for their values. You can compare this to the example above, where we expanded the macro P in the body of a lambda expression, forcing the evaluation with FUNCALL when we wanted the value. Later in SICP, you will use a similar technique to implement lazy lists.

As I say, Haskell does this sort of thing automatically, and it's not hard to imagine a lisp that does the same (though, currently no popular ones do). I suppose I went on a bit of a tangent, given the actual question in the book, but hopefully you'll have got a bit of an idea of how to tell what is evaluated and when, and the difference it can make.