seek for some explanation on SICP exercise 1.5

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)"?

lisp scheme sicp

Edit Report

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 b

answered 2013-04-16T14:27:00.067

seek for some explanation on SICP exercise 1.5

1 Answer

Your Answer